Removing a node from DiGraph in networkx while preserving child nodes and remapping their edges

user_9365576 0
Viewed 905

I would like to remove a node from a DiGraph in networkx in such a way that all child nodes are preserved and their edges are remapped (or old edges deleted + new created) to the parent of their parent node. The node will be removed based on the node attributes (such as what group it belongs to).

Removal of node Group B

For instance, I wish to programmatically remove nodes which have attribute Group B and remap all immediate child nodes to the original parent (in the case of multiple grandparents, I want to map to all of them).

I can think of a crude approach by iterating over the DiGraph, looking at its immediate successors and predecessors, creating relationships between them and then removing the node, but is there perhaps any more elegant way?

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])
networkx graph-theory python
1 Answers

One way you could do this is by identifying the nodes you want to "remove" and contract them with their predecessors, or "parent" nodes. An edge contraction removes an edge from the graph and merges the two nodes that where previously joined.

So checking on the small example you've proposed:

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)

enter image description here

Now we can find the nodes in question and contract the edges that link them to one of its predecessors with 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)

enter image description here

user_96986840
Related