如何解释networkx.optimal_edit_paths的输出？

Question

我想要可视化一个图形序列，其中一个被编辑成另一个编辑步骤一次。这样做的一个子任务是在源图和目标图之间创建中间图。

networkx.optimal_edit_paths看起来是为每个中间图获取所需信息的一种很有希望的工具，但我发现输出本身有点难理解。

让我们从文件中拿出他们的例子：

import networkx as nx
G1 = nx.cycle_graph(4)
G2 = nx.wheel_graph(5)
paths, cost = nx.optimal_edit_paths(G1, G2)

现在看看paths内部，我看到了这个输出：

/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释 
* [([(0, 0), (1, 1), (2, 2), (3, 3), (None, 4)], [((0, 1), (0, 1)), ((1, 2), (1, 2)), (None, (0, 2)), ((0, 3), (0, 3)), ((2, 3), (2, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(0, 0), (1, 1), (None, 2), (3, 3), (2, 4)], [((0, 1), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((0, 3), (0, 3)), (None, (2, 3)), ((1, 2), (1, 4)), ((2, 3), (3, 4)), (None, (0, 4))]), ([(0, 0), (2, 1), (1, 2), (None, 3), (3, 4)], [(None, (0, 1)), ((0, 1), (0, 2)), ((1, 2), (1, 2)), (None, (0, 3)), (None, (2, 3)), ((0, 3), (0, 4)), ((2, 3), (1, 4)), (None, (3, 4))]), ([(0, 0), (2, 1), (3, 2), (None, 3), (1, 4)], [(None, (0, 1)), ((0, 3), (0, 2)), ((2, 3), (1, 2)), (None, (0, 3)), (None, (2, 3)), ((0, 1), (0, 4)), ((1, 2), (1, 4)), (None, (3, 4))]), ([(0, 0), (3, 1), (2, 2), (1, 3), (None, 4)], [((0, 3), (0, 1)), ((2, 3), (1, 2)), (None, (0, 2)), ((0, 1), (0, 3)), ((1, 2), (2, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(0, 0), (3, 1), (None, 2), (1, 3), (2, 4)], [((0, 3), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((0, 1), (0, 3)), (None, (2, 3)), ((1, 2), (3, 4)), ((2, 3), (1, 4)), (None, (0, 4))]), ([(0, 0), (None, 1), (1, 2), (2, 3), (3, 4)], [(None, (0, 1)), ((0, 1), (0, 2)), (None, (1, 2)), ((1, 2), (2, 3)), (None, (0, 3)), ((0, 3), (0, 4)), ((2, 3), (3, 4)), (None, (1, 4))]), ([(0, 0), (None, 1), (3, 2), (2, 3), (1, 4)], [(None, (0, 1)), ((0, 3), (0, 2)), (None, (1, 2)), ((2, 3), (2, 3)), (None, (0, 3)), ((0, 1), (0, 4)), ((1, 2), (3, 4)), (None, (1, 4))]), ([(1, 0), (0, 1), (3, 2), (2, 3), (None, 4)], [((0, 1), (0, 1)), ((0, 3), (1, 2)), (None, (0, 2)), ((1, 2), (0, 3)), ((2, 3), (2, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(1, 0), (0, 1), (None, 2), (2, 3), (3, 4)], [((0, 1), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((1, 2), (0, 3)), (None, (2, 3)), ((0, 3), (1, 4)), ((2, 3), (3, 4)), (None, (0, 4))]), ([(1, 0), (2, 1), (3, 2), (0, 3), (None, 4)], [((1, 2), (0, 1)), ((2, 3), (1, 2)), (None, (0, 2)), ((0, 1), (0, 3)), ((0, 3), (2, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(1, 0), (2, 1), (None, 2), (0, 3), (3, 4)], [((1, 2), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((0, 1), (0, 3)), (None, (2, 3)), ((0, 3), (3, 4)), ((2, 3), (1, 4)), (None, (0, 4))]), ([(1, 0), (3, 1), (0, 2), (None, 3), (2, 4)], [(None, (0, 1)), ((0, 1), (0, 2)), ((0, 3), (1, 2)), (None, (0, 3)), (None, (2, 3)), ((1, 2), (0, 4)), ((2, 3), (1, 4)), (None, (3, 4))]), ([(1, 0), (3, 1), (2, 2), (None, 3), (0, 4)], [(None, (0, 1)), ((1, 2), (0, 2)), ((2, 3), (1, 2)), (None, (0, 3)), (None, (2, 3)), ((0, 1), (0, 4)), ((0, 3), (1, 4)), (None, (3, 4))]), ([(1, 0), (None, 1), (0, 2), (3, 3), (2, 4)], [(None, (0, 1)), ((0, 1), (0, 2)), (None, (1, 2)), ((0, 3), (2, 3)), (None, (0, 3)), ((1, 2), (0, 4)), ((2, 3), (3, 4)), (None, (1, 4))]), ([(1, 0), (None, 1), (2, 2), (3, 3), (0, 4)], [(None, (0, 1)), ((1, 2), (0, 2)), (None, (1, 2)), ((2, 3), (2, 3)), (None, (0, 3)), ((0, 1), (0, 4)), ((0, 3), (3, 4)), (None, (1, 4))]), ([(2, 0), (0, 1), (1, 2), (None, 3), (3, 4)], [(None, (0, 1)), ((0, 1), (1, 2)), ((1, 2), (0, 2)), (None, (0, 3)), (None, (2, 3)), ((0, 3), (1, 4)), ((2, 3), (0, 4)), (None, (3, 4))]), ([(2, 0), (0, 1), (3, 2), (None, 3), (1, 4)], [(None, (0, 1)), ((0, 3), (1, 2)), ((2, 3), (0, 2)), (None, (0, 3)), (None, (2, 3)), ((0, 1), (1, 4)), ((1, 2), (0, 4)), (None, (3, 4))]), ([(2, 0), (1, 1), (0, 2), (3, 3), (None, 4)], [((1, 2), (0, 1)), ((0, 1), (1, 2)), (None, (0, 2)), ((0, 3), (2, 3)), ((2, 3), (0, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(2, 0), (1, 1), (None, 2), (3, 3), (0, 4)], [((1, 2), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((2, 3), (0, 3)), (None, (2, 3)), ((0, 1), (1, 4)), ((0, 3), (3, 4)), (None, (0, 4))]), ([(2, 0), (3, 1), (0, 2), (1, 3), (None, 4)], [((2, 3), (0, 1)), ((0, 3), (1, 2)), (None, (0, 2)), ((0, 1), (2, 3)), ((1, 2), (0, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(2, 0), (3, 1), (None, 2), (1, 3), (0, 4)], [((2, 3), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((1, 2), (0, 3)), (None, (2, 3)), ((0, 1), (3, 4)), ((0, 3), (1, 4)), (None, (0, 4))]), ([(2, 0), (None, 1), (1, 2), (0, 3), (3, 4)], [(None, (0, 1)), ((1, 2), (0, 2)), (None, (1, 2)), ((0, 1), (2, 3)), (None, (0, 3)), ((0, 3), (3, 4)), ((2, 3), (0, 4)), (None, (1, 4))]), ([(2, 0), (None, 1), (3, 2), (0, 3), (1, 4)], [(None, (0, 1)), ((2, 3), (0, 2)), (None, (1, 2)), ((0, 3), (2, 3)), (None, (0, 3)), ((0, 1), (3, 4)), ((1, 2), (0, 4)), (None, (1, 4))]), ([(3, 0), (0, 1), (1, 2), (2, 3), (None, 4)], [((0, 3), (0, 1)), ((0, 1), (1, 2)), (None, (0, 2)), ((1, 2), (2, 3)), ((2, 3), (0, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(3, 0), (0, 1), (None, 2), (2, 3), (1, 4)], [((0, 3), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((2, 3), (0, 3)), (None, (2, 3)), ((0, 1), (1, 4)), ((1, 2), (3, 4)), (None, (0, 4))]), ([(3, 0), (1, 1), (0, 2), (None, 3), (2, 4)], [(None, (0, 1)), ((0, 1), (1, 2)), ((0, 3), (0, 2)), (None, (0, 3)), (None, (2, 3)), ((1, 2), (1, 4)), ((2, 3), (0, 4)), (None, (3, 4))]), ([(3, 0), (1, 1), (2, 2), (None, 3), (0, 4)], [(None, (0, 1)), ((1, 2), (1, 2)), ((2, 3), (0, 2)), (None, (0, 3)), (None, (2, 3)), ((0, 1), (1, 4)), ((0, 3), (0, 4)), (None, (3, 4))]), ([(3, 0), (2, 1), (1, 2), (0, 3), (None, 4)], [((2, 3), (0, 1)), ((1, 2), (1, 2)), (None, (0, 2)), ((0, 1), (2, 3)), ((0, 3), (0, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))]), ([(3, 0), (2, 1), (None, 2), (0, 3), (1, 4)], [((2, 3), (0, 1)), (None, (0, 2)), (None, (1, 2)), ((0, 3), (0, 3)), (None, (2, 3)), ((0, 1), (3, 4)), ((1, 2), (1, 4)), (None, (0, 4))]), ([(3, 0), (None, 1), (0, 2), (1, 3), (2, 4)], [(None, (0, 1)), ((0, 3), (0, 2)), (None, (1, 2)), ((0, 1), (2, 3)), (None, (0, 3)), ((1, 2), (3, 4)), ((2, 3), (0, 4)), (None, (1, 4))]), ([(3, 0), (None, 1), (2, 2), (1, 3), (0, 4)], [(None, (0, 1)), ((2, 3), (0, 2)), (None, (1, 2)), ((1, 2), (2, 3)), (None, (0, 3)), ((0, 1), (3, 4)), ((0, 3), (0, 4)), (None, (1, 4))]), ([(None, 0), (0, 1), (1, 2), (2, 3), (3, 4)], [(None, (0, 1)), ((0, 1), (1, 2)), (None, (0, 2)), ((1, 2), (2, 3)), (None, (0, 3)), ((0, 3), (1, 4)), ((2, 3), (3, 4)), (None, (0, 4))]), ([(None, 0), (0, 1), (3, 2), (2, 3), (1, 4)], [(None, (0, 1)), ((0, 3), (1, 2)), (None, (0, 2)), ((2, 3), (2, 3)), (None, (0, 3)), ((0, 1), (1, 4)), ((1, 2), (3, 4)), (None, (0, 4))]), ([(None, 0), (1, 1), (0, 2), (3, 3), (2, 4)], [(None, (0, 1)), ((0, 1), (1, 2)), (None, (0, 2)), ((0, 3), (2, 3)), (None, (0, 3)), ((1, 2), (1, 4)), ((2, 3), (3, 4)), (None, (0, 4))]), ([(None, 0), (1, 1), (2, 2), (3, 3), (0, 4)], [(None, (0, 1)), ((1, 2), (1, 2)), (None, (0, 2)), ((2, 3), (2, 3)), (None, (0, 3)), ((0, 1), (1, 4)), ((0, 3), (3, 4)), (None, (0, 4))]), ([(None, 0), (2, 1), (1, 2), (0, 3), (3, 4)], [(None, (0, 1)), ((1, 2), (1, 2)), (None, (0, 2)), ((0, 1), (2, 3)), (None, (0, 3)), ((0, 3), (3, 4)), ((2, 3), (1, 4)), (None, (0, 4))]), ([(None, 0), (2, 1), (3, 2), (0, 3), (1, 4)], [(None, (0, 1)), ((2, 3), (1, 2)), (None, (0, 2)), ((0, 3), (2, 3)), (None, (0, 3)), ((0, 1), (3, 4)), ((1, 2), (1, 4)), (None, (0, 4))]), ([(None, 0), (3, 1), (0, 2), (1, 3), (2, 4)], [(None, (0, 1)), ((0, 3), (1, 2)), (None, (0, 2)), ((0, 1), (2, 3)), (None, (0, 3)), ((1, 2), (3, 4)), ((2, 3), (1, 4)), (None, (0, 4))]), ([(None, 0), (3, 1), (2, 2), (1, 3), (0, 4)], [(None, (0, 1)), ((2, 3), (1, 2)), (None, (0, 2)), ((1, 2), (2, 3)), (None, (0, 3)), ((0, 1), (3, 4)), ((0, 3), (1, 4)), (None, (0, 4))])]
*/

只挑出这个列表中的第一个元素：

>>> paths[0]
([(0, 0), (1, 1), (2, 2), (3, 3), (None, 4)], [((0, 1), (0, 1)), ((1, 2), (1, 2)), (None, (0, 2)), ((0, 3), (0, 3)), ((2, 3), (2, 3)), (None, (0, 4)), (None, (1, 4)), (None, (3, 4))])

然后是第一个元素的第一个元素：

>>> paths[0][0]
[(0, 0), (1, 1), (2, 2), (3, 3), (None, 4)]

然后是第一个更深层次的元素：

>>> paths[0][0][0]
(0, 0)

文件中“返回”一节的内容如下：

返回：

edit_pathslist of tuples (node_edit_path, edge_edit_path)

    node_edit_path : list of tuples (u, v) edge_edit_path : list of tuples ((u1, v1), (u2, v2))

我还注意到：

>>> [len(i) for i in paths]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

我假设这些内容给出了如何应用每个编辑的信息，但我还没有完全理解文档中简洁的解释中所发生的事情。

如何从迭代应用编辑的角度正确地解释输出？

Answer 1

paths的每个元素都是图形的一对编辑序列，第一个元素表示顶点的编辑，第二个元素表示对边的编辑。

因此，paths[0]是将G1编辑成G2的一种方法。paths[0][0]表示对此转换所需顶点集的更改序列，paths[0][1]表示所需边缘集中的更改。

在对顶点集的更改中，我看到有时会发生(None, <number>)。我怀疑它们代表了一个名为<number>的节点的创建。同样，在paths[0][1]中，我看到了像(None, (<number1>,<number2>))这样的元组，我认为它代表了在顶点<number1>和<number2>之间创建一个新的边缘。

相反，通过调用paths, cost = nx.optimal_edit_paths(g2, g1)来逆转源图和目标图的顺序显示了一个相反的模式。(<number>, None)表示删除名为<number>的节点，((<number1>,<number2>), None)表示删除边缘(<number1>,<number2>)。