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)[source]#

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

图编辑路径是一系列节点和边编辑操作，将图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数值

考虑的最大编辑距离。

Returns:

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 是同构的。