graph_edit_distance#

graph_edit_distance(G1, G2, node_match=None, edge_match=None, node_subst_cost=None, node_del_cost=None, node_ins_cost=None, edge_subst_cost=None, edge_del_cost=None, edge_ins_cost=None, roots=None, upper_bound=None, timeout=None)[source]#

返回图 G1 和 G2 之间的 GED（图编辑距离）。

图编辑距离是一种图相似度度量，类似于字符串的 Levenshtein 距离。它被定义为将图 G1 转换为与图 G2 同构的图所需的编辑路径（节点和边的编辑操作序列）的最小成本。

参数:
G1, G2: 图

两个图 G1 和 G2 必须是同类型的。

node_match可调用对象 (callable)

一个函数，如果在匹配期间应将 G1 中的节点 n1 和 G2 中的节点 n2 视为相等，则返回 True。

该函数将被调用，形式如下：

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

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

如果指定了 node_subst_cost，则忽略此参数。如果既未指定 node_match 也未指定 node_subst_cost，则不考虑节点属性。

edge_match可调用对象 (callable)

一个函数，如果在匹配期间应将 G1 中节点对 (u1, v1) 和 G2 中节点对 (u2, v2) 的边属性字典视为相等，则返回 True。

该函数将被调用，形式如下：

edge_match(G1[u1][v1], G2[u2][v2]).

也就是说，该函数将接收正在考虑的边的边属性字典。

如果指定了 edge_subst_cost，则忽略此参数。如果既未指定 edge_match 也未指定 edge_subst_cost，则不考虑边属性。

node_subst_cost, node_del_cost, node_ins_cost可调用对象 (callable)

分别返回节点替换、节点删除和节点插入成本的函数。

这些函数将被调用，形式如下：

node_subst_cost(G1.nodes[n1], G2.nodes[n2]), node_del_cost(G1.nodes[n1]), node_ins_cost(G2.nodes[n2]).

也就是说，这些函数将接收节点属性字典作为输入。这些函数应返回正数值。

如果指定了 node_subst_cost 函数，它将覆盖 node_match。如果既未指定 node_match 也未指定 node_subst_cost，则使用默认的节点替换成本 0（匹配期间不考虑节点属性）。

如果未指定 node_del_cost，则使用默认的节点删除成本 1。如果未指定 node_ins_cost，则使用默认的节点插入成本 1。

edge_subst_cost, edge_del_cost, edge_ins_cost可调用对象 (callable)

分别返回边替换、边删除和边插入成本的函数。

这些函数将被调用，形式如下：

edge_subst_cost(G1[u1][v1], G2[u2][v2]), edge_del_cost(G1[u1][v1]), edge_ins_cost(G2[u2][v2]).

也就是说，这些函数将接收边属性字典作为输入。这些函数应返回正数值。

如果指定了 edge_subst_cost 函数，它将覆盖 edge_match。如果既未指定 edge_match 也未指定 edge_subst_cost，则使用默认的边替换成本 0（匹配期间不考虑边属性）。

如果未指定 edge_del_cost，则使用默认的边删除成本 1。如果未指定 edge_ins_cost，则使用默认的边插入成本 1。

roots2元组

一个元组，其中第一个元素是 G1 中的一个节点，第二个元素是 G2 中的一个节点。在比较时强制匹配这些节点，以允许有根图之间的比较。

upper_bound数值

要考虑的最大编辑距离。如果没有小于或等于 upper_bound 的编辑距离，则返回 None。

timeout数值

最大执行秒数。达到超时后，返回当前找到的最佳 GED。

另请参阅

optimal_edit_paths, optimize_graph_edit_distance
is_isomorphic

测试图编辑距离是否为 0

参考文献

[1]

Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, Patrick Martineau. An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems. 4th International Conference on Pattern Recognition Applications and Methods 2015, Jan 2015, Lisbon, Portugal. 2015, <10.5220/0005209202710278>. <hal-01168816> https://hal.archives-ouvertes.fr/hal-01168816

示例

>>> G1 = nx.cycle_graph(6)
>>> G2 = nx.wheel_graph(7)
>>> nx.graph_edit_distance(G1, G2)
7.0

>>> G1 = nx.star_graph(5)
>>> G2 = nx.star_graph(5)
>>> nx.graph_edit_distance(G1, G2, roots=(0, 0))
0.0
>>> nx.graph_edit_distance(G1, G2, roots=(1, 0))
8.0
在本页