networkx is_isomorphic taking weights into account

user_9415489 0
Viewed 320
import networkx as nx
import numpy as np

def is_isomorphic(graph1, graph2):
    G1 = nx.from_numpy_matrix(graph1)
    G2 = nx.from_numpy_matrix(graph2)
    isomorphic = nx.is_isomorphic(G1,G2)
    print("isomorphic? \t", str(isomorphic))
    return isomorphic


graph1 = np.array([[1, 0.5, 1.5],
                   [0, 1,   0],
                   [0, 0,   2]])

graph2 = np.array([[1,  0, 1.5],
                   [0,  1, 1.5],
                   [0,  0, 2]])

print(is_isomorphic(graph1,graph2))

Suppose I have two graphs: graph1 with node 1 being bonded with a node 1 and 2 and graph2 where node 2 is being bonded with two node 1s. So if we look at these graphs as molecules, these two graphs are not isomorphic. Now when I call is_isomorphic(), this results in a True value, meaning that the two graphs are isomorphic.

How do I make sure that the weights are being taken into account?

Thank you!

networkx graph python
2 Answers

In the documentation for nx.is_isomorphic, there is an option of a argument edge_match. It returns True or False based on whether you want the edges to be considered a match:

The function will be called like edge_match(G1[u1][v1], G2[u2][v2]).

Here's an example:

nx.is_isomorphic(G1, G2, edge_match=lambda x, y: x==y)
user_29667230

You can use iso.categorical_edge_match to define a comparison function, so that in checking if both networks are isomorphic, the edge weight attributes are taken into account:

G1 = nx.from_numpy_matrix(graph1)
G2 = nx.from_numpy_matrix(graph2)

Note that the weights, are basically just edge attributes:

G1.edges(data=True)
# EdgeDataView([(0, 0, {'weight': 1.0}), (0, 1, {'weight': 0.5})...
G2.edges(data=True)
# EdgeDataView([(0, 0, {'weight': 1.0}), (0, 2, {'weight': 1.5})...

So we want to define a comparison function in which these attributes are compared when iso.categorical_edge_match receives two edges from G1 and G2:

import networkx.algorithms.isomorphism as iso
em = iso.categorical_edge_match('weight', 'weight')

Now when using nx.is_isomorphic set edge_match to the comparison function em defined above with iso.categorical_edge_match, so that it is called with each edge being compared to check if their weights are equal:

nx.is_isomorphic(G1, G2, edge_match=em)
# False

Since edge_match expects a callable, and we only want to compare on an attribute, in this case we could also define our own simple comparison function so that the edge attributes are also considered:

nx.is_isomorphic(G1, G2, edge_match=lambda x,y: x['weight']==y['weight'])
# False
user_96986840
Related