如何区分网络中的等价图

Question

我有一个关于图等价性的问题。

假设：

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

第一个is_isomorphic(graph1,graph2)应该返回True，因为顶点标签对我来说只是虚拟变量。在第一种情况下，顶点2与2个不同的顶点结合；在第二种情况下，顶点3与2个不同的顶点结合。

第二个is_isomorphic(graph3,graph4)应该返回False，因为在graph3中，顶点2与相同的2个顶点结合；在graph4中，顶点1被绑定到两个不同类型的顶点。

有什么办法可以解决这个问题吗？如果这样可以加快计算速度，就可以发出包networkx，因为我只对邻接矩阵感兴趣。注意:这个问题也必须扩展到更大的邻接矩阵。

Answer 1

以下内容适用于给定的示例(希望通常能完成您想要的事情)：

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