How to compare directed graphs in Networkx?

Question

I have two directed Networkx graphs with equal number of nodes and edges.

How to compare the structure of these two different graphs in Networkx? Node names don't matter. I tried to use Networkx DiGraph.order(), DiGraph.degree() etc. from Information about graph structure but all parameters of my graphs are equal.

And generally how to compare structures of more than 2 graphs and find only graphs with unique structure. Is there special function for this in Networkx?

Answer 1

To determine if two graphs are isomorphic you can use the function is_isomorphic(). Unfortunately there is no function to compare more than 2 graphs. But you can compare all possible graph combinations and build the graph iso_graph from combinations which are isomorphic. To find all isomorphic graph groups you can use the function connected_components() or find_cliques() with iso_graph:

import networkx as nx
from itertools import combinations

G1 = nx.path_graph(4)
G2 = nx.path_graph(4)
G3 = nx.path_graph(4)
G4 = nx.path_graph(5)
G5 = nx.path_graph(5)
G6 = nx.path_graph(5)

graphs = {G1: 'G1', G2: 'G2', G3: 'G3', G4: 'G4', G5: 'G5', G6: 'G6'}
iso_pairs = {(graphs[g1], graphs[g2]) for g1, g2 in combinations(graphs, 2) if nx.is_isomorphic(g1, g2)}
# {('G1', 'G3'), ('G5', 'G6'), ('G4', 'G6'), ('G1', 'G2'), ('G4', 'G5'), ('G2', 'G3')}

iso_graph = nx.from_edgelist(iso_pairs) 
for c in nx.connected_components(iso_graph):
    print(c)
# {'G1', 'G3', 'G2'}
# {'G5', 'G6', 'G4'}

%matplotlib inline # jupyter notebook
nx.draw(iso_graph, with_labels=True)