I have the acyclic directed graph of tasks I want to perform. Each edge of the graph is a dependency, e.g. task 4 could be performed only after 1 and 2 completed.
0
`----> 1 ------------> 4 ---> 7
` ^ ^
`---> 3 | |
` `------> 2 -----/ |
` `------> 5 ----------- /
` `------> 6 ---------- /
`
`--> 8
`------> 9
`------> 10
`------> 11
I need to perform all tasks consequently but with optimizations like running tasks in parallel where it is possible.
Topological sorting allows me to build just a sequence of tasks execution:
0, 1, 3, 8, 2, 5, 6, 9, 10, 11, 4, 7
But I need something like:
0, [1, 3, 8], [2, 5, 6, 9, 10, 11], 4, 7
// [...] - means parallel processing
Could you recommend any algorithm to achieve this?