Directed Acyclical Graph Traversal... help?

Question

a little out of my depth here and need to phone a friend. I've got a directed acyclical graph I need to traverse and I'm stumbling into to graph theory for the first time. I've been reading a lot about it lately but unfortunately I don't have time to figure this out academically. Can someone give me a kick with some help as to how to process this tree?

Here are the rules:

• there are n root nodes (I call them "sources")
• there are n end nodes
• source nodes carry a numeric value
• downstream nodes (I call them "worker" nodes) preform various operations on the incoming values like Add, Mult, etc.

As you can see from the graph below, nodes a, b, and c need to be processed before d, e, or f.

What's the proper order to walk this tree?

Answer 1

I would look into linearization of DAGs which should be achievable through Topological sorts.

Linearization, from what I remember, basically sorts in an order which holds to the invariant that for all nodes (Node_X) that have an outdegree to any other given node NodeA, NodeX appears before NodeA.

This would mean that, from your example, nodes a,b, and d would be processed first. Node c second. Nodes e and f, last.

http://en.wikipedia.org/wiki/Topological_sorting

Answer 2

You need to process the nodes via a Topological sort. The sort is not necessarily unique so there might be more than one available order (not that this should matter anyway).

The linked wikipedia page should have concrete algorithms to help you.