Traversal of cyclic directed graph

Question

I have a cyclic directed graph. Starting at the leaves, I wish to propagate data attached to each node downstream to all nodes that are reachable from that node. In particular, I need to keep pushing data around any cycles that are reached until the cycles stabilise.

I'm completely sure that this is a stock graph traversal problem. However, I'm having a fair bit of difficulty trying to find a suitable algorithm --- I think I'm missing a few crucial search keywords.

Before I attempt to write my own half-assed O(n^3) algorithm, can anyone point me at a proper solution? And what is this particular problem called?

Prink

This is probably some sort of all to all broadcast (or all to all scatter) communication problem. Might help if you search with these keywords. – Gridley

Maybe these things are clear to everyone else, but what do you mean by starting at the leaves and propagating data downstream? Wouldn't a leaf be a node with no nodes downstream from it? Also, what does it mean for a cycle to stabilise? – Hypochromia

I think what I'm calling 'leaves' would possibly be more clearly described as 'roots', although given it's a cyclic graph neather term is particularly intuitive --- I mean a node with no parents. Downstream is in the direction of the children. Because traversal of a cycle may reveal more information that may need to be propagated to already visited nodes, some nodes may need to be visited more than once, meaning deciding when to terminate can be tricky; hence stabilisation. In fact, it turns out there's a much easier way to do this --- see answer. – Prink

Answer 1

Since the graph is cyclic (i.e. can contain cycles), I would first break it down into strongly connected components. A strongly connected component of a directed graph is a subgraph where each node is reachable from every other node in the same subgraph. This would yield a set of subgraphs. Notice that a strongly connected component of more than one node is effectively a cycle.

Now, in each component, any information in one node will eventually end up in every other node of the graph (since they are all reachable). Thus for each subgraph we can simply take all the data from all the nodes in it and make every node have the same set of data. No need to keep going through the cycles. Also, at the end of this step, all nodes in the same component contains exactly the same data.

The next step would be to collapse each strongly connected component into a single node. As the nodes within the same component all have the same data, and are therefore basically the same, this operation does not really change the graph. The newly created "super node" will inherit all the edges going out or coming into the component's nodes from nodes outside the component.

Since we have collapsed all strongly connected components, there will be no cycles in the resultant graph (why? because had there been a cycle formed by the resultant nodes, they would all have been placed in the same component in the first place). The resultant graph is now a Directed Acyclic Graph. There are no cycles, and a simple depth first traversal from all nodes with indegree=0 (i.e. nodes that have no incoming edges), propagating data from each node to its adjacent nodes (i.e. its "children"), should get the job done.

Paulus

Perfect. This makes several other problems I've been working on vastly more tractable, too. Thanks! – Prink