Efficient way to replace nodes in a networkx graph with follow-through edges

Question

I am trying to replace nodes in the graph with follow-through edges. This means that each predecessor of the replaced/removed node will be connected to each successor of the replaced/removed node.

For example, considering a path graph with 5 nodes such that edges (0, 1), (1, 2), (2, 3), (3, 4), I wish to replace nodes 1 and 3 with follow-through edges ((0,2) for node 1) and ((2,4) for node 3). The final graph should have the edges (0, 2), (2, 4).

Answer 1

Networkx has no built-in functions/algorithms for it so you should do it manually. Itertools module will help you to automatize the construction of edges to create:

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)

So G.edges will return the needed edges (1->2->3 moved to 1->3 and 3,4,6,7 are pairly connected):

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

---

P.S. I doubt if the more efficient method in networkx exists. In networkx you should check each node's predecessors/successors so the O-complexity will be the same anyway.