CODEWITHSUNDEEP
pythonnetworkxdirected-graph
cookie1986
cookie1986

Reputation: 895

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

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: Graph A

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 Graph B = Sub-graph of Graph A

Graph C 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.

Upvotes: 4

Views: 956

Answers (1)

Paul Brodersen
Paul Brodersen

Reputation: 13041

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.

Upvotes: 4

Related Questions