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)[源代码]#
返回图g1和g2之间GED（图形编辑距离）的连续近似值。
图形编辑距离是一种图形相似性度量，类似于字符串的Levenshtein距离。它被定义为编辑路径（节点和边缘编辑操作序列）将图g1转换为图g2同构的最小成本。
- 参数
- G1, G2: graphs
两个图G1和G2必须属于同一类型。
- node_match可调用
在匹配过程中，如果G1中的节点N1和G2中的节点N1应该被视为相等，则返回True的函数。
函数的调用方式如下
节点匹配（g1.nodes [n1] ，G2节点 [n2] ）
也就是说，函数将接收n1和n2的节点属性字典作为输入。
如果指定了节点“SUBST”成本，则忽略此项。如果既不指定节点匹配也不指定节点子节点成本，则不考虑节点属性。
- edge_match可调用
如果G1中的节点对(U1，v1)和G2中的(U2，v2)的边属性词典在匹配期间被视为相等，则返回True的函数。
函数的调用方式如下
边沿匹配（G1） [u1] [v1] ，G2 [u2] [v2] ）
也就是说，函数将接收正在考虑的边的边属性字典。
如果指定了边缘子成本，则忽略。如果既不指定边匹配也不指定边子成本，则不考虑边属性。
- node_subst_cost, node_del_cost, node_ins_cost可调用
分别返回节点替换、节点删除和节点插入开销的函数。
函数的调用方式如下
节点子节点成本（g1.nodes [n1] ，G2节点 [n2] ，节点成本（g1.nodes） [n1] ，节点成本（g2.nodes） [n2] ）
也就是说，函数将接收节点属性字典作为输入。函数应返回正数。
如果指定，函数节点“SUBST”成本将覆盖“节点匹配”。如果既不指定节点_match也不指定节点_subst_cost，则使用默认的节点替换成本0（匹配期间不考虑节点属性）。
如果未指定节点删除成本，则使用默认的节点删除成本1。如果未指定节点插入成本，则使用默认的节点插入成本1。
- edge_subst_cost, edge_del_cost, edge_ins_cost可调用
分别返回边替换、边删除和边插入成本的函数。
函数的调用方式如下
边缘成本（g1 [u1] [v1] ，G2 [u2] [v2] ）边缘成本（g1 [u1] [v1] ）边缘成本（g2） [u2] [v2] ）
也就是说，函数将接收边缘属性字典作为输入。函数应返回正数。
如果指定，函数边_subst_cost将覆盖边_match。如果既没有指定边缘匹配，也没有指定边缘子成本，则使用默认的边缘替换成本0（匹配期间不考虑边缘属性）。
如果未指定边缘删除成本，则使用默认的边缘删除成本1。如果未指定边缘插入成本，则使用默认的边缘插入成本1。
- upper_bound数字
要考虑的最大编辑距离。
- 返回
- 图形编辑距离的连续近似生成器。
工具书类
- 1
Zeina Abu Aisheh、Romain Raveaux、Jean-Yves Ramel、Patrick Martineau。一种求解模式识别问题的精确图形编辑距离算法。2015年第四届模式识别应用和方法国际会议，2015年1月，葡萄牙里斯本。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