CODEWITHSUNDEEP
pythongraphnetworkx
drastega
drastega

Reputation: 1773

How to compare directed graphs in Networkx?

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

enter image description here 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?

Upvotes: 4

Views: 7423

Answers (2)

Mykola Zotko
Mykola Zotko

Reputation: 17824

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)

iso_graph

Upvotes: 4

Simone Aonzo
Simone Aonzo

Reputation: 921

The most common function for measuring graph similarity is the "edit distance".

The graph edit distance is the number of edge/node changes needed to make two graphs isomorphic.

Networkx several (optimized) versions: https://networkx.github.io/documentation/latest/reference/algorithms/similarity.html

Upvotes: 0

Related Questions