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

Bisque

you have to give a rigorous definition of "pattern" and "matching". – Rocambole

Can the pattern contain cycles, i.e. "A->B->A->C" ? – Tilley

If you have the pattern you can code it yourself. Please be aware that the answer to your question depends on the programming language that you are using to program the graphs. Therefore, we cannot help you if you don't provide us this information. – Enterprise

bacchus, i use python and now searching for graph lib and now choosing from: networkx, python-graph, graph-tool – Bisque

look this question: #45330007 – Goldofpleasure

Answer 1

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

Actinal

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

Premise

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.

Enterprise

"you just need to traverse the graph and compare the paths" - "just" doing a lot of the heavy lifting here. – Sungkiang