在networkx中从有向图（DiGraph）中删除一个节点，同时保留其子节点并重新映射它们的边。

Question

我希望能够从 networkx 的 DiGraph 中删除一个节点，同时保留所有子节点并重新映射它们的边缘到父节点的父节点（或者删除旧的边缘并创建新的边缘）。该节点将基于其节点属性（例如所属组）被删除。请注意，保留 HTML 标签。

例如，我希望以编程方式删除具有属性 Group B 的节点，并将所有直接子节点重新映射到原始父节点（在存在多个祖父母的情况下，我想将其映射到所有祖先）。

我可以考虑通过迭代 DiGraph ，查看其直接后继和前任，并在它们之间创建关系，然后删除节点，但是是否有更优雅的方法？

for node in DiG.nodes(data=True):
  if node[1].get('node_group') == "Group B":
    pre = DiG.predecessors(node[0])
    suc = DiG.successors(node[0])
    for p in pre:
      for s in suc:
        DiG.add_edge(s, p) 
    DiG.remove_node(node[0])

- Napoleon Borntoparty

Answer 1

一种做法是通过识别需要“移除”的节点，然后将它们与其前置节点或“父节点”压缩。 边缩合 是从图中移除一条边并合并两个先前连接的节点。

因此，在您提供的小例子中进行检查：

from networkx.drawing.nx_agraph import graphviz_layout

edgelist = [('Group A', 'Group B'), ('Group B', 'Group C'), 
            ('Group B', 'Group D'), ('Group B', 'Group E')]
G = nx.from_edgelist(edgelist, create_using=nx.DiGraph)

plt.figure(figsize=(6,6))
pos=graphviz_layout(G, prog='dot')
nx.draw(G, pos=pos,
        node_color='lightgreen', 
        node_size=1500,
        with_labels=True, 
        arrows=True)

现在，我们可以使用nx.contracted_nodes函数找到相关的节点，并将与之前节点之一相连的边进行缩减：

parent = next(G.predecessors('Group B'))
G = nx.contracted_edge(parent, 'Group B')

plt.figure(figsize=(6,6))
nx.draw(G, pos=pos,
        node_color='lightgreen', 
        node_size=1500,
        with_labels=True, 
        arrows=True)

- yatu

---

干杯！这看起来正是我想要的 - 你能否请澄清一下当有多个父节点时会发生什么，例如，当“B组”有父节点“ A组”和“ X组”时？另外 - 在输入元组中边的方向是否很重要？ - Napoleon Borntoparty

据我所见，一旦您将节点与其父节点之一合并，只有该父节点会保留，并且连接到子节点的先前边缘现在将连接到父节点。是的，元组顺序将确定在收缩后哪个节点仍然存在。如果您像这样合同（node1，node2）-> node1将保留。 - yatu