Python NetworkX：节点收缩后的图形更新

Question

我创建了一个 networkX 有向图如下：

import networkx.algorithms.isomorphism as iso
import networkx as nx
G1 = nx.DiGraph()
G1.add_nodes_from(range(1,7))

# Creating Acyclic Directed Graph
G1.add_edges_from([(1,2),(2,3),(3,4),(1,4),(4,5),(5,6)])

绘制时，G1 如下所示：

现在我想使用 NetowrkX 的“contract_node”功能在节点 1 中收缩节点 2。我绘制图形并在收缩后打印所有节点和边。

H = nx.contracted_nodes(G1,1,2,self_loops=False)
print(H.nodes)
print(H.edges)

它只是将节点 2 折叠到节点 1 中，并删除 2 和 1 之间的所有边，就好像节点 2 从未存在过一样，从而使节点索引不连续 [1,3,4,5,6]。相反，我想在节点收缩后更新图形并拉回收缩节点上方的所有节点（在本例中为 2），以便我的节点列表和边缘列表如下所示：

Node List : [1,2,3,4,5]
Edge List : [(1,3),(1,2),(2,3),(3,4),(4,5)]

基本上通过契约节点数更新契约节点上方所有节点的节点idx（在这种情况下为1，因为我正在契约单个节点）并更新各自的链接。

是否有 NetworkX 函数可以执行此操作？如果没有，实现这一目标的最佳方法是什么？最终，我想融合有序图中的节点（排序节点和边列表），然后将其与其他有序图（排序节点和边列表）进行同构比较。 NetworkX 的同构函数提供布尔结果（图是同构的或图不是同构的）但它们不提供有关 2 个非同构图之间的分歧点的任何信息。是否有 NetworkX 对此提供支持？给定一个起始节点，为了找到分歧点，我计划使用 nx.edge_bfs() 为 2 个有序图获取所有边列表，并将它们进行比较以找到分歧点以进行进一步调查。如果节点 idx 不连续，则此方法将失败。感谢您的宝贵时间。

Answer 1

您可以使用 nx.relabel_nodes 重新标记节点和边。
示例：

>>> mapping = dict(zip(sorted(H), range(1,len(H)+1)))
>>> mapping
{1: 1, 3: 2, 4: 3, 5: 4, 6: 5}
>>> H2 = nx.relabel_nodes(H, mapping)
>>> H2.nodes
NodeView((1, 2, 3, 4, 5))
>>> H2.edges
OutEdgeView([(1, 3), (1, 2), (2, 3), (3, 4), (4, 5)])

Python NetworkX：节点收缩后的图形更新

Python NetworkX : Graph update after node contraction

networkx

python-3.x