Resolved: How to test if one graph is a subgraph of another in Networkx?

Question:

I am new to building directed graphs with networkx and I’m trying to work out how to compare two graphs. More specifically, how to tell if a smaller graph is a subgraph (unsure of the exact terminology) of a larger graph
As an example, assume I have the following directed graph:

I would like to be able to check whether a series of smaller graphs are sub-graphs of this initial graph. Returning a True value if they are (graph B), and False if they are not (graph C):

Graph B = Sub-graph of Graph A

Graph C != Sub-graph of Graph A
Example Code

import networkx

A = nx.DiGraph()
A.add_edges_from([('A','B'),('B','C'),('C','A')])
nx.draw_networkx(A)


B = nx.DiGraph()
B.add_edges_from([('A','B')])
nx.draw_networkx(B)

C = nx.DiGraph()
C.add_edges_from([('A','B'),('A','C')])
nx.draw_networkx(C)

I’ve had a look through the documentation and cannot seem to find what I need. An alternative I have been considering is to represent the nodes as a sequence of strings, and then searching for each substring in the main graphs string sequence – however, I can’t imagine this is the most effecient/effective/stable way to solve the problem.

Answer:

You are looking for a subgraph isomorphisms.

nx.isomorphism.DiGraphMatcher(A, B).subgraph_is_isomorphic()
# True

nx.isomorphism.DiGraphMatcher(A, C).subgraph_is_isomorphic()
# False

Note that the operation can be slow for large graphs, as the problem is NP-complete.

If you have better answer, please add a comment about this, thank you!

Resolved: How to test if one graph is a subgraph of another in Networkx?

Resolved: Why doesn’t stringstream consume output during hex formatting?

Resolved: CMake path for python3 libraries doesn’t change (windows 10)

Resolved: GLMM with quasi-Poisson distribution

Leave A Reply