CODEWITHSUNDEEP
pythongraphnetworkxisomorphism
Cica Gustiani
Cica Gustiani

Reputation: 76

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.

Upvotes: 2

Views: 719

Answers (2)

Cica Gustiani
Cica Gustiani

Reputation: 76

Here answer the problem specifically in the question, with the very same graphs. Note that I'm using the networkx.MultiGraph and consider some 'ordering' in placing those edges.

import networkx as nx

G1,G2,G3,G4=nx.MultiGraph(),nx.MultiGraph(),nx.MultiGraph(),nx.MultiGraph()

G1.add_weighted_edges_from([(0, 1, 0), (0, 2, 1), (0, 3, 2)], weight='ordering')
G2.add_weighted_edges_from([(0, 1, 0), (0, 3, 1), (0, 2, 2)], weight='ordering')                                                                            
G3.add_weighted_edges_from([(0, 1, 0), (0, 1, 1), (2, 3, 2)], weight='ordering')
G4.add_weighted_edges_from([(0, 1, 0), (2, 3, 1), (0, 1, 2)], weight='ordering')

def comparison(D1,D2):
    return D1[0]['ordering'] == D2[0]['ordering']

nx.is_isomorphic(G1,G2, edge_match=comparison)                                                                                          
>True

nx.is_isomorphic(G3,G4, edge_match=comparison)                                                                                          
>False

Upvotes: 0

Joel
Joel

Reputation: 23827

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

Upvotes: 3

Related Questions