Menu
I'm trying to find tool/algorithm for searching sections that corresponds to specified pattern in oriented graph, e.g.:
A->B->C or or A<->B->C
Please, suggest me direction of my searches.
I mean pattern matching. I need to find all group of nodes and edges, that matching specified pattern
927
In the context of searching a single graph G, graph pattern matching is to find all the occurrences of a query graph Q in a given data graph G, specified by a matching function.
Given an undirected graph, a matching is a set of edges, such that no two edges share the same vertex. In other words, matching of a graph is a subgraph where each node of the subgraph has either zero or one edge incident to it. A vertex is said to be matched if an edge is incident to it, free otherwise.
In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern.
For example, x* matches any number of x characters, [0-9]* matches any number of digits, and . * matches any number of anything. A regular expression pattern match succeeds if the pattern matches anywhere in the value being tested.
Isn't this the Subgraph isomorphism problem? If yes, the Wikipedia page contains a section on algorithms.
176
Graph pattern matching is the functionality at the core of graph rewrite tools, they offer it pre-implemented.
In e.g. GrGen you write down your example pattern as a:A --> b:B --> c:C, the tool then generates a pattern matcher for it, one that is adapted to the characteristics of the host graph (optimized by taking statistics about the graph into account).
25
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
