how distinguish equivalent graphs in networkx

user_9415489 0
Viewed 189

I have a question regarding graph equivalency.

Suppose that:

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, edge_match=lambda x, y: x==y)
    return isomorphic


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

graph3 = np.array([[1, 0, 1],
                   [0, 1, 1],
                   [0, 0, 2]])
graph4 = np.array([[1, 1, 1],
                   [0, 1, 0],
                   [0, 0, 2]])

print(is_isomorphic(graph1,graph2))
# should return True
print(is_isomorphic(graph3,graph4))
# should return False

The first is_isomorphic(graph1,graph2) should return True since the vertex labels are nothing but dummy variables to me. In the first case, vertex 2 is bonded to 2 different vertices; in the second case, vertex 3 is bonded to 2 different vertices.

The second is_isomorphic(graph3,graph4) should return False since in graph3, vertex 2 is bonded to the same 2 vertices; and in graph4, vertex 1 is bonded to 2 different kind of vertices.

Is there a pythonic way to solve this problem? The package networkx could be emitted if that makes calculations faster since I am only interested in the adjacency matrices. Note: this problem must be scalable to bigger adjacency matrices too.

networkx graph numpy python
1 Answers

The following works for your given examples (and hopefully does generally the thing you want):

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)

    # remove selfloops (created by the calls above)
    # and add "shadow nodes" for the node types
    for node in list(G1.nodes):
        G1.remove_edge(node, node)
        G1.add_edge(node, "type" + str(graph1[node, node]))
    for node in list(G2.nodes):
        G2.remove_edge(node, node)
        G2.add_edge(node, "type" + str(graph2[node, node]))

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


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

graph3 = np.array([[1, 0, 1],
                   [0, 1, 1],
                   [0, 0, 2]])
graph4 = np.array([[1, 1, 1],
                   [0, 1, 0],
                   [0, 0, 2]])

print(is_isomorphic(graph1, graph2))
# True
print(is_isomorphic(graph3, graph4))
# False
user_113393110
Related