Check whether a networkx graph is a subgraph of another one
graph-theory, networkx, python
Solution
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`
Problem
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.