CODEWITHSUNDEEP
javadirected-acyclic-graphs
SMUsamaShah
SMUsamaShah

Reputation: 7890

Assign priorities to DAG

I have DAG stored as an array. How can I assign priorities to the DAG in a way that parent node gets the highest priority and all leaf nodes the lowest priority?

If I have a DAG as following

    A       # A -> B,C                      # A     
   / \      # B -> D        ----->          # B C   //can be used in parallel
  C   B     # C -> E                        # D 
  \    \    # D -> E                        # E
   \   D    # E ->                             
    \ /
     E

I have both parent and children stored in the array which I am using as DAG.

Topological Sort returns a linear list e.g. A,C,B,D,E only.

Upvotes: 3

Views: 357

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

I think what you're looking for is called a topological ordering, a way of ordering the nodes in a DAG so that no node appears before each of its parents. Fortunately, topological orderings can be found very efficiently (in linear time) using various topological sorting algorithms, including one based on a simple DFS of the DAG.

Hope this helps!

Upvotes: 2

Related Questions