networkx.algorithms.similarity.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可赎回的 )--匹配期间,如果g1中的节点n1和g2中的节点n2相等,则返回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数字的 最大的编辑距离要考虑。

返回

  • edit_pathslist of tuples (node_edit_path, edge_edit_path) )--节点编辑路径:元组列表(u,v)边编辑路径:元组列表((u1,v1),(u2,v2)

  • cost数字的 )--最佳编辑路径成本(图形编辑距离)。

实际案例

>>> G1 = nx.cycle_graph(4)
>>> G2 = nx.wheel_graph(5)
>>> paths, cost = nx.optimal_edit_paths(G1, G2)
>>> len(paths)
40
>>> cost
5.0

引用

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