pythongraphnetworkxisomorphism

Graph isomorphism with constraints on the edges using networkx


I would like to define my own isomorphism of two graphs. I want to check if two graphs are isomorphic given that each edge has some attribute --- basically the order of placing each edge. I wonder if one can use the method:

networkx.is_isomorphic(G1,G2, edge_match=some_callable) 

somehow by defining function some_callable().

For example, the following graphs are isomorphic, because you can relabel the nodes to obtain one from another.

G1G2

Namely, relabel [2<->3].

But, the following graphs are not isomorphic.

G3G4

There is no way to obtain one from another by re-labeling the nodes.


Solution

  • Here you go. This is exactly what the edge_match option is for doing. I'll create 3 graphs the first two are isomorphic (even though the weights have different names --- I've set the comparison function to account for that). The third is not isomorphic.

    import networkx as nx
    G1 = nx.Graph()
    G1.add_weighted_edges_from([(0,1,0), (0,2,1), (0,3,2)], weight = 'aardvark')
    G2 = nx.Graph()
    G2.add_weighted_edges_from([(0,1,0), (0,2,2), (0,3,1)], weight = 'baboon')
    G3 = nx.Graph()
    G3.add_weighted_edges_from([(0,1,0), (0,2,2), (0,3,2)], weight = 'baboon')
    
    def comparison(D1, D2):    
        #for an edge u,v in first graph and x,y in second graph
        #this tests if the attribute 'aardvark' of edge u,v is the 
        #same as the attribute 'baboon' of edge x,y.
    
        return D1['aardvark'] == D2['baboon']
    
    nx.is_isomorphic(G1, G2, edge_match = comparison)
    > True
    nx.is_isomorphic(G1, G3, edge_match = comparison)
    > False