Geek Answers Handbook

Directional acyclic schedule ... help?

a bit out of my depth here and need to call a friend. I have a directed acyclic graph that I need to go through, and for the first time I came across graph theory. I have read a lot about this recently, but, unfortunately, I do not have time to understand this academically. Can someone give me a kick with some help on how to handle this tree?

Here are the rules:

  • there are n root nodes (I call them "sources")
  • there are n end nodes
  • Source nodes carry a numerical value
  • nodes located downstream (I call them "working" nodes) perform various operations on incoming values, such as Add, Multi, etc.

As can be seen from the graph below, the nodes a, band cmust be processed before d, eor f.

What is the correct order for this tree?

enter image description here

+5
source share
2 answers

I would look at the linearization of DAG, which must be achieved through topological varieties.

Linearization, from what I can remember, mostly sorted in the order that keeps invariant for all nodes (Node_X), which have the advantage of any other given node NodeA, NodeXappears in front 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

+5

. , ( ).

wikipedia , .

+5

More articles:


All Articles