Check whether a networkx graph is a subgraph of another one

Question

I have a networkx graph G, and I wish to check whether another networkx graph, H, can be embedded in it. Simple examples include:

• checking whether G contains a triangle (this can be done via networkx.triangles)
• checking whether G contains a path/cycle of length k
• checking whether G contains a star with k leaves (this can be done via degree sequence)

etc.

I know the problem is in general NP-complete, but I would like to see if something a little bit better than naive exists, or if you have recommendations about how to write such a method.

Answer 1

I've been doing some extensive work with graphs in python and I'd recommend not using networkx for larger problems. Since the library is pure python it is perfect for smaller graphs and portability, but for larger subgraph isomorphisms I've found that graph-tool works very well.

The function call you are looking for in graph-tool is under the topology section:

graph_tool.topology.subgraph_isomorphism