如何使用networkx(Python)计算图形编辑距离

Question

我正在处理图形编辑距离；根据定义，它是将原始图G1变换为同构于G2的图的最小成本和；

图形编辑操作通常包括：

• 顶点插入，将单个新的标记顶点引入到图中
• 顶点删除从图中删除单个(通常是断开连接的(顶点
• 顶点替换以更改给定顶点的标签(或颜色(
• 边插入，在一对顶点之间引入一条新的彩色边
• 删除边以删除一对顶点之间的单个边
• 边替换以更改给定边的标签(或颜色(

现在我想使用networkx的实现-我没有任何边标签，G1和G2的节点集是相同的，我不想要同构于G2的图，但我想要G2本身；

这主要是因为G1:1->2->3和G2:3->2->1彼此同构，但如果节点代表一些事件，从因果关系的角度来看，它们是非常非常不同的；

因此，在这种情况下，我一直在运行如下测试：

import networkx as nx
G=nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_edges_from([(1, 2),(2,3)])

G2=nx.DiGraph()
G2.add_node(1)
G2.add_node(2)
G2.add_node(3)
G2.add_edges_from([(3, 2),(2, 1)])

nx.graph_edit_distance(G,G2)

但它返回距离为零，这是有意义的，因为图彼此同构；

所以我尝试设置node_match，但仍然没有成功

import networkx as nx
def nmatch(n1, n2):
return n1==n2 
G=nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_edges_from([(1, 2),(2,3)])

G2=nx.DiGraph()
G2.add_node(1)
G2.add_node(2)
G2.add_node(3)
G2.add_edges_from([(3, 2),(2, 1)])

nx.graph_edit_distance(G,G2, node_match=nmatch)

如果我们假设删除或添加边/顶点的成本为1，那么编辑距离应该为4，因为我们可以：

• 删除G中的两条边，添加G2中的2条边

在不考虑同胚性但真正等效的情况下，如何计算编辑距离？

Answer 1

你似乎并不是在比较你想要的。nmatch中的n1和n2总是{}。来自文件

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

您不是在比较节点对象，而是与它们相关联的字典(作为您需要的任何数据(

添加节点时，您可以将自定义数据添加到该字典中，例如：

import networkx as nx
def nmatch(n1, n2):
return n1==n2
G=nx.DiGraph()
G.add_node(1, id=1)
G.add_node(2, id=2)
G.add_node(3, id=3)
G.add_edges_from([(1, 2),(2,3)])

G2=nx.DiGraph()
G2.add_node(1, id=1)
G2.add_node(2, id=2)
G2.add_node(3, id=3)
G2.add_edges_from([(3, 2),(2,1)])

nx.graph_edit_distance(G,G2, node_match=nmatch)

返回2，因为您可以进行2次边缘替换。如果您希望结果为4(2次插入，2次删除(，您可能会增加替换成本

Answer 2

这是另一个解决方案，可以产生2个

import networkx as nx
G=nx.DiGraph()
G.add_node(1, id=1)
G.add_node(2, id=2)
G.add_node(3, id=3)
G.add_edges_from([(1, 2),(2,3)])

G2=nx.DiGraph()
G2.add_node(1, id=1)
G2.add_node(2, id=2)
G2.add_node(3, id=3)
G2.add_edges_from([(3, 2),(2,1)])
# arguments
# arguments for nodes
def node_subst_cost(node1, node2):
# check if the nodes are equal, if yes then apply no cost, else apply 1
if node1 == node2:
return 0
return 1
def node_del_cost(node):
return 1  # here you apply the cost for node deletion
def node_ins_cost(node):
return 1  # here you apply the cost for node insertion
# arguments for edges
def edge_subst_cost(edge1, edge2):
# check if the edges are equal, if yes then apply no cost, else apply 3
if edge1==edge2:
return 0
return 1
def edge_del_cost(node):
return 1  # here you apply the cost for edge deletion
def edge_ins_cost(node):
return 1  # here you apply the cost for edge insertion
paths, cost = nx.optimal_edit_paths(
G,
G2,
node_subst_cost=node_subst_cost,
node_del_cost=node_del_cost,
node_ins_cost=node_ins_cost,
edge_subst_cost=edge_subst_cost,
edge_del_cost=edge_del_cost,
edge_ins_cost=edge_ins_cost
)
print(cost)

如果您在Python2.7上运行它，请在标题中添加以下行

# This Python file uses the following encoding: utf-8
from __future__ import print_function, unicode_literals
from __future__ import absolute_import, division