python - 从networkx中的有向图中删除一个节点，同时保留子节点并重新映射它们的边缘

Question

我想以这样一种方式从DiGraphinnetworkx中删除一个节点，即所有子节点都被保留，并且它们的边缘被重新映射（或旧边缘删除 + 新创建）到其父节点的父节点。该节点将根据节点属性（例如它所属的组）被删除。

例如，我希望以编程方式删除具有属性的节点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])

标签： pythonnetworkxgraph-theory

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)