时间戳

首页 > 解决方案 > 如何通过考虑节点名称来测量图形编辑距离

python-3.x - 如何通过考虑节点名称来测量图形编辑距离

问题描述

我已经使用库 networkx 在 python 中定义了两个图，现在我想考虑节点的“名称”来测量这两个图之间的距离

我创建了两个图表，看起来完全一样（树形图）

G=nx.Graph()
G.add_edges_from([("A","B"),("A","C")])

H=nx.Graph()
H.add_edges_from([("X","Y"),("X","Z")])

res=nx.graph_edit_distance(G,H)
res2=nx.optimize_edit_paths(G,H)
res3=nx.optimal_edit_paths(G,H)

我希望替换所有节点，因为节点没有相同的名称，但我得到成本（更改/距离）0 的结果。这意味着该函数没有考虑节点的名称。

在文档中建议使用函数“node_math”，但我不知道如何使用它。它似乎不是networkx功能。

标签： python-3.xnetworkx

解决方案

它给出答案的原因0是因为它认为节点是相等的。如果您看到文档，它会提到

node_match (callable) - 如果 G1 中的节点 n1 和 G2 中的 n2 在匹配期间应被视为相等，则返回 True 的函数。

该函数将被称为

node_match(G1.nodes[n1], G2.nodes[n2]).

也就是说，该函数将接收 n1 和 n2 的节点属性字典作为输入。

现在，既然你还没有声明任何属性，那么在这种情况下

G.nodes['A'] will return {}

和

H.nodes['Z'] will return {}

现在，由于两者都是空字典，因此它们将被视为相等。

这是您的代码的修改版本，我在其中为您的节点添加了标签属性。

import networkx as nx

G=nx.Graph()
G.add_nodes_from([("A", {'label':'a'}), ("B", {'label':'b'}),
                  ("C", {'label':'c'})])

G.add_edges_from([("A","B"),("A","C")])

H=nx.Graph()
H.add_nodes_from([("X", {'label':'x'}), ("Y", {'label':'y'}),
                  ("Z", {'label':'z'})])
H.add_edges_from([("X","Y"),("X","Z")])

# This is the function which checks for equality of labels
def return_eq(node1, node2):
    return node1['label']==node2['label']

print(nx.graph_edit_distance(G, H, node_match=return_eq))
# Output: 3

推荐阅读