optimize_graph_edit_distance#

optimize_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, upper_bound=None)[source]#

返回图 G1 和 G2 的图编辑距离 (GED) 的连续近似值。

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

参数：
G1, G2: 图

图 G1 和 G2 必须是相同类型。

node_match可调用对象

一个函数，如果 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可调用对象

一个函数，如果 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可调用对象

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

这些函数将被调用，例如

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可调用对象

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

这些函数将被调用，例如

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。

upper_bound数值

考虑的最大编辑距离。

返回：
图编辑距离的连续近似值的生成器。

另请参阅

graph_edit_distance, optimize_edit_paths

参考文献

[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)
>>> for v in nx.optimize_graph_edit_distance(G1, G2):
...     minv = v
>>> minv
7.0
在本页上