Given an acyclic directed graph, return a collection of collections of nodes "at the same level"?
<p>Firstly I am not sure what such an algorithm is called, which is the primary problem - so first part of the question is what is this algorithm called?</p>

<p>Basically I have a <code>DiGraph()</code> into which I insert the nodes <code>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]</code> and the edges <code>([1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10])</code></p>

<p>From this I'm wondering if it's possible to get a collection as follows: <code>[[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]</code></p>

<p>EDIT: Let me add some constraints if it helps.
- There are no cycles, this is guaranteed
- There is no one start point for the graph</p>

<p>What I'm trying to do is to collect the nodes at the same level such that their processing can be parallelized, but within the outer collection, the processing is serial.</p>

<p>EDIT2: So clearly I hadn't thought about this enough, so the easiest way to describe "level" is interms of <em>deepest predecessor</em>, all nodes that have the same depth of predecessors. So the first entry in the above list are all nodes that have 0 as the deepest predecessor, the second has one, third has two and so on. Within each list, the order of the <em>siblings</em> is irrelevant as they will be parallelly processed.</p>

<p>A topological sort will achieve this, as Ami states. The following is a Boost Graph Library implementation, with no context, but the pseudocode can be extracted. The <code>toporder</code> object just provides the iterator to a topological ordering. I can extract the general algorithm if desired. </p>

<pre><code>template&lt;typename F&gt;
void 
scheduler&lt;F&gt;::set_run_levels()
{

  run_levels = std::vector&lt;int&gt;(tasks.size(), 0);
  Vertexcont toporder;

  try
    {
      topological_sort(g, std::front_inserter(toporder));
    }
  catch(std::exception &amp;e)
    {
      std::cerr &lt;&lt; e.what() &lt;&lt; "\n";
      std::cerr &lt;&lt; "You most likely have a cycle...\n";
      exit(1);
    }

  vContIt i = toporder.begin();

  for(;
      i != toporder.end();
      ++i)
    {
      if (in_degree(*i,g) &gt; 0)
        {
          inIt j, j_end;
          int maxdist = 0;
          for(boost::tie(j,j_end) = in_edges(*i,g);
              j != j_end;
              ++j)
            {
              maxdist = (std::max)(run_levels[source(*j,g)], maxdist);
              run_levels[*i] = maxdist+1;
            }
        }
    }
}
</code></pre>

<p>I think I once applied this to the same problem, then realized it was unnecessary. Just set up the tasks on a hair-trigger, with all tasks signaling completion to their dependents (by a condition_variable, promise). So all I needed was to know the dependencies of each task, find the initial task, then fire. Is a full specification of <code>run_level</code> needed in your case?</p>

python algorithm graph graph-theory networkx