How to reduce a DAG by replacing each longest non-

Question

I'd like to reduce a DAG by replacing each longest non-branching path by an edge connecting the start and the end of the path.

For example, for a graph like this, I'd like to reduce it

a->b->c->d
a->d

to the following. Of course, a real DAG can be more complex than this.

a->d
a->d

I don't find a way to do so with networkx. Does anybody know how to do so in network? Thanks.

Answer 1

As far as I know, Networkx doesn't support it out of the box. However it isn't too complicated to implement. You can simply iterate over the nodes in the graph, and follow the next steps:

1. Remove every node with exactly one incoming edge and one outgoing edge.
2. Connect with a new edge the source node of the incoming edge to the target node of the outgoing edge.

This seems to work:

def should_remove_node(graph, node):
    return graph.in_degree(node) == 1 and graph.out_degree(node) == 1

for node in list(G.nodes()):
    if should_remove_node(G, node):
        in_node = list(G.in_edges(node))[0][0]
        out_node = list(G.out_edges(node))[0][1]
        G.add_edge(in_node, out_node)
        G.remove_node(node)