python - networkx is_isomorphic 考虑权重

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)
    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))

假设我有两个图表: graph1节点 1 与节点 1 和 2 以及 graph2 绑定(bind)其中节点 2 与两个节点 1 绑定(bind)。因此，如果我们将这些图视为分子，这两个图不是同构的。现在当我调用 is_isomorphic() ，这将导致 True值，意味着这两个图是同构的。

我如何确保将重量考虑在内？

谢谢!

Answer 1

您可以使用 iso.categorical_edge_match 定义一个比较函数，以便在检查两个网络是否同构时，边缘 weight属性被考虑:

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

请注意，权重基本上只是边缘属性:

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})...

所以我们要定义一个比较函数，在 iso.categorical_edge_match 时比较这些属性。从 G1 接收两条边和 G2 :

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

现在使用 nx.is_isomorphic设置 edge_match到比较函数 em上面用 iso.categorical_edge_match 定义，以便在比较每条边时调用它以检查它们的权重是否相等:

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

由于 edge_match期望一个可调用的，我们只想比较一个属性，在这种情况下，我们还可以定义自己的简单比较函数，以便也考虑边缘属性:

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