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同构的图。编辑操作包括替换、删除和插入。

图编辑距离定义为编辑路径的最小成本。

Parameters:

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。

Returns:

生成器，生成元组(node_edit_path, edge_edit_path, cost): node_edit_path : 元组列表 (u, v) edge_edit_path : 元组列表 ((u1, v1), (u2, v2)) cost : 数值