How to sort depended objects by dependency for maximum concurrency

I have a list of dependencies (or better a DAG without cycles):

Input (for example):

Item A depends on nothing
Item B depends on C, E
Item C depends on A
Item D depends on E
Item E depend开发者_运维百科s on A

What I'm looking for is: "What is the best* parallel order of the items?"

*best means: maximum concurrency level

Result (for example):

[A], [E, C], [D, B]

The best approach seems to be Pseudocode for getting order based on Dependency but I think I miss a basic algorithm on this.

This looks a lot like https://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique and https://en.wikipedia.org/wiki/Critical_path_method

Assuming that you want the maximum concurrency level to get the thing done as soon as possible, once you have organised things so that it takes no longer than the critical path you have something that does as well as the best possible solution - and if there is no limit on the amount of parallel tasks you can run, you can get the critical path just by scheduling every action as soon as all of its dependencies have completed.

I'm not sure you actually want the kind of answer you think you want. For example, in your scenario, you might get item D done before item C if D and E were faster than C, so the list-of-lists you got won't necessarily tell the whole story.

If you have to actually implement this kind of workflow, as opposed to just predicting the workflow in advance, it's easy to do it optimally; whenever a task completes, just scan all the remaining tasks and fire off in parallel any of them whose dependencies are satisfied. If you want to compute it in advance, then maybe you want to reconsider the structure of your result?

  GetLists(tasks[1..m], depends[1..m])
   1. topological_sort(tasks)
   2. cumulative = set()
   3. lists = queue()
   4. i = 0
   5. while |cumulative| != m do
   6.    temp = set()
   7.    while depends[i] is a subset of cumulative do
   8.       temp = temp union {tasks[i]}
   9.       i = i + 1
  10.    cumulative = cumulative union temp
  11.    lists.enqueue(temp)

Something like that might work. Note that the lynchpin is doing a "topological sort" to ensure that you get termination. Also note that, as is, this algorithm is only correct for the set of inputs with a valid solution. If there is no solution, this loops forever. Easy to fix, but you can handle that.

An example: A depends on nothing, B and C depend on A, E depends on A and C and D depends on C and B.

  Topological sort: A, B, C, D, E.
  cumulative = {}
  lists = []
  i = 0
  |cumulative| = 0 < 5 so...
     temp = {}
     depends[A] = {} is a subset of {} so
        temp = {A}
        i = 1
     depends[B] = {A} is not a subset of {}, so break
     cumulative = {A}
     lists = [{A}]
  |cumulative| = 1 < 5 so...
     temp = {}
     depends[B] = {A} is a subset of {A}, so
        temp = {B}
        i = 2
     depends[C] = {A} is a subset of {A}, so
  ...

You get the idea.