考虑权重的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))

假设我有两个图:节点1与节点1和节点2结合的graph1图，以及节点2与两个节点1s连接的graph2图。所以如果我们把这些图看作分子，这两个图不是同构的。现在，当我调用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设置为与iso.categorical_edge_match一起定义的比较函数em时，这样就可以在比较每个边时调用它，以检查它们的权重是否相等：

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

Answer 2

在文献资料 for nx.is_isomorphic中，有一个参数edge_match选项。它根据是否希望边缘被视为匹配返回True或False：

函数将被调用为edge_match(G1u1，G2u2)。

下面是一个例子：

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