Search code examples
pythongraphnetworkxisomorphic

Check graph equality using networkx isomorphic


I have two graphs as follows

import networkx as nx

G1, G2 = nx.DiGraph(), nx.DiGraph()
G1.add_edges_from([("s1", "s2"), ("s2", "s3"), ("s3", "s4")]) # G1: 1->2->3->4
G2.add_edges_from([("s1", "s2"), ("s2", "s3"), ("s3", "s7")]) # G2: 1->2->3->7

nx.is_isomorphic(G1, G2)

By definition, we know the above two graphs are isomorphic, so is_isomorphic returns True.

However, I wish to check structure equality between two graphs, meaning nodes and edges are the same (but weights allow difference). Since G1 and G2 have different last node, I am looking for the is_isomorphic function returning False.

Q: Is it possible using is_isomorphic to identify the non-equality?

P.S. I tried to use iso.categorical_node_match or iso.numerical_node_match or iso.numerical_edge_match as plug-in parameter in is_isomorphic:

  1. network: numerical_edge_match
  2. networkx: is_isomorphic

But I am still not sure how to call these iso function correctly in node_match or edge_match.


Solution

  • During comparison, node attributes are compared. By default, node attributes are a blank dictionary (and do not incorporate node label information). A quick way to fix that is to use nx.convert_node_labels_to_integers and specify the key for label attributes:

    G1_int = nx.convert_node_labels_to_integers(G1, label_attribute='label')
    G2_int = nx.convert_node_labels_to_integers(G2, label_attribute='label')
    print(G1_int.nodes[0])
    # {'label': 's1'}
    

    Now, to make sure that nx.is_isomorphic uses the relevant attribute information, we can specify custom node_match function:

    nx.is_isomorphic(G1_int, G2_int, node_match = lambda x,y: x==y)
    # False