10

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

Jamal
  • 365
  • 2
  • 3
  • 10
  • you have to give a rigorous definition of "pattern" and "matching". – akappa May 01 '11 at 12:18
  • Can the pattern contain cycles, i.e. "A->B->A->C" ? – Anders Lindahl May 01 '11 at 12:31
  • 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. – CRM May 01 '11 at 13:22
  • bacchus, i use python and now searching for graph lib and now choosing from: networkx, python-graph, graph-tool – Jamal May 01 '11 at 13:28
  • look this question: https://stackoverflow.com/questions/45329507/software-uses-some-sort-of-structural-pattern-match-crud-algorithm-on-hypergra – Dmitry Ponyatov Aug 02 '17 at 16:05

3 Answers3

4

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

MarcoS
  • 13,386
  • 7
  • 42
  • 63
3

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

Visitor
  • 31
  • 1
1

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.

Community
  • 1
  • 1
CRM
  • 4,569
  • 4
  • 27
  • 33
  • *"you just need to traverse the graph and compare the paths"* - "just" doing a lot of the heavy lifting here. – Peter Wood Jun 24 '23 at 22:30