用后续边缘替换网络图中节点的有效方法

Question

我试图用后面的边缘替换图中的节点。这意味着，替换/删除节点的每个前身将连接到替换/删除节点的每个后继产品。

例如，考虑一个带有5个节点的路径图，例如边缘(0, 1), (1, 2), (2, 3), (3, 4)，我希望用后续边缘(节点1的(0,2)(和(节点3的(2,4)(替换节点1和3。最终图应具有边缘(0, 2), (2, 4)。

Answer 1

NetworkX没有内置函数/算法，因此您应该手动进行操作。Itertools模块将帮助您自动化边缘的构造以创建：

import itertools as it
import networkx as nx

G = nx.DiGraph()
G.add_edges_from([
    (1,2),
    (2,3),
    (3,5),
    (4,5),
    (5,6),
    (5,7)
])
nodes_to_delete = [2, 5]
for node in nodes_to_delete:
    G.add_edges_from(
        it.product(
            G.predecessors(node),
            G.successors(node)
        )
    )
    G.remove_node(node)

因此，G.edges将返回所需的边缘(1->2->3移至1->3，3,4,6,7成对连接(：

OutEdgeView([(1, 3), (3, 6), (3, 7), (4, 6), (4, 7)])

---

p.s。我怀疑网络中更有效的方法是否存在。在networkx中，您应该检查每个节点的前任/后继产品，以便O-complexity无论如何都相同。