optimize_edit_paths#
- optimize_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, strictly_decreasing=True, roots=None, timeout=None)[source]#
GED (图编辑距离) 计算：高级接口。
图编辑路径是将图 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数值
要考虑的最大编辑距离。
- strictly_decreasing布尔值
如果为 True，则返回严格递减成本的连续近似值。否则，返回成本小于或等于先前最小成本的所有编辑路径。
- roots2元组
一个元组，其中第一个元素是 G1 中的节点，第二个元素是 G2 中的节点。在比较中，强制匹配这些节点以允许比较有根图。
- timeout数值
最大执行秒数。达到超时后，返回当前最佳 GED。
- 返回值:
- 元组 (node_edit_path, edge_edit_path, cost) 的生成器
node_edit_path : 元组列表 (u, v) edge_edit_path : 元组列表 ((u1, v1), (u2, v2)) cost : 数值
参考文献
[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), 2015年1月, 里斯本, 葡萄牙. 2015, <10.5220/0005209202710278>. <hal-01168816> https://hal.archives-ouvertes.fr/hal-01168816