Subgraph pattern matching
Hi Tiago,
Just started using graph-tool, thank you very much for all your effort with this project. I am currently using graph-tool to capture an AST of a C++ program. One thing I would like to have is the ability to query this graph with some kind of pattern matching language. As a starting point, I have successfully constructed a subgraph corresponding to the query, and then used the subgraph_isomorphism method to find all matches. For instance, if I want to find all occurrences of two perfect nested loops, I would create a subgraph:
q1 [type="loop"] -> q2 [type="loop"]
and invoke subgraph_isomorphism method against a graph capturing the program AST:
n1 [type="loop"] -> n2 [type="loop"]->n3 ["type="if"] ->n4 ["type="loop"]
and it would find:
n1 [type="loop"]->n2 [type="loop"]
However, I would like to be able to have the ability to match any nested loop, e.g. by supporting multiple hops, and in this case match: n2-> ... -> n4. I understand this cannot be done with subgraph_isomorphism .
Ideally, I would love to have something like a graph database query language, as explained here: https://neo4j.com/docs/developer-manual/current/cypher/clauses/match/
but I am not sure where to start. Do you have any suggestions, possibly leveraging existing work with graph-tool?