optimal_edit_paths#

optimal_edit_paths(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)[源代码]#

返回将 G1 转换为 G2 的所有最低成本编辑路径。

图编辑路径是将图 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。

upper_bound数值

要考虑的最大编辑距离。

返回:
edit_paths元组列表 (node_edit_path, edge_edit_path)

  • node_edit_path : 元组列表 (u, v)，表示 G1 和 G2 之间的节点转换。u 对于插入操作是 None，v 对于删除操作是 None。

  • edge_edit_path : 元组列表 ((u1, v1), (u2, v2))，表示 G1 和 G2 之间的边转换。对于插入操作是 (None, (u2,v2))，对于删除操作是 ((u1,v1), None)。

cost数值

最优编辑路径成本（图编辑距离）。当成本为零时，表示 G1 和 G2 是同构的。

另请参阅

graph_edit_distance, optimize_edit_paths

注意

要将 G1 转换为与 G2 同构的图，请应用返回的 edit_paths 中的节点和边编辑。对于同构图，成本为零，路径表示不同的同构映射（同构）。也就是说，编辑涉及重命名节点和边以匹配 G2 的结构。

参考文献

[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(4)
>>> G2 = nx.wheel_graph(5)
>>> paths, cost = nx.optimal_edit_paths(G1, G2)
>>> len(paths)
40
>>> cost
5.0
本页目录