title: Algorithm for computing partial orderings of dependency graphs
body: <p>I'm trying to compute a partial "topological sort" of a dependency graph, which is actually a DAG (Directed Acyclic Graph) to be precise; so as to execute tasks without conflicting dependencies in parallel.</p>
  
  <p>I came up with this simple algorithm because what I found on Google wasn't all that helpful (I keep finding only algorithms that themselves run in parallel to compute a normal topological sort).</p>
  
  <pre><code>visit(node)
  {
      maxdist = 0;
      foreach (e : in_edge(node))
      {
          maxdist = max(maxdist, 1 + visit(source(e)))
      }
      distance[node] = maxdist;
      return distance[node];
  }
  
  make_partial_ordering(node)
  {
      set all node distances to +infinite;
      num_levels = visit(node, 0);
      return sort(nodes, by increasing distance) where distances &lt; +infinite;
  }
  </code></pre>
  
  <p>(Note that this is only pseudocode and there would certainly be a few possible small optimizations)</p>
  
  <p>As for the correctness, it seems pretty obvious: For the leafs (:= nodes which have no further dependency) the maximum distance-to-leaf is always 0 (correct because the loop gets skipped due to 0 edges).
  For any node connected to nodes n1,..,nk the maximum distance-to-leaf is 1 + max{distance[n1],..,distance[nk]}.</p>
  
  <p>I did find this article after I had written down the algorithm: <a href="http://msdn.microsoft.com/en-us/magazine/dd569760.aspx" rel="noreferrer">http://msdn.microsoft.com/en-us/magazine/dd569760.aspx</a>
  But honestly, why are they doing all that list copying and so on, it just seems so really inefficient..?</p>
  
  <p>Anyway I was wondering whether my algorithm is correct, and if so what it is called so that I can read up some stuff about it.</p>
  
  <p>Update: I implemented the algorithm in my program and it seems to be working great for everything I tested.
  Code-wise it looks like this:</p>
  
  <pre><code>  typedef boost::graph_traits&lt;my_graph&gt; my_graph_traits;
    typedef my_graph_traits::vertices_size_type vertices_size_type;
    typedef my_graph_traits::vertex_descriptor vertex;
    typedef my_graph_traits::edge_descriptor edge;
  
    vertices_size_type find_partial_ordering(vertex v,
        std::map&lt;vertices_size_type, std::set&lt;vertex&gt; &gt;&amp; distance_map)
    {
        vertices_size_type d = 0;
  
        BOOST_FOREACH(edge e, in_edges(v))
        {
            d = std::max(d, 1 + find_partial_ordering(source(e), distance_map));
        }
  
        distance_map[d].insert(v);
  
        return d;
    }
  </code></pre>