Pattern matching in graphs

Question

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

Answer 1

Isn't this the Subgraph isomorphism problem? If yes, the Wikipedia page contains a section on algorithms.

Answer 2

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).

Answer 3

Regarding possible libraries you can find an answer here Python Graph Library.

As for the pattern matching, if you know the pattern you're searching for, you just need to traverse the graph and compare the paths or you can use a function to retrieve a path between nodes and check if the pattern exists.