On Fri, Oct 30, 2015 at 8:46 PM, bhattach <bhattach@yahoo.com> wrote:
It's based on topological sorting (available with BGL -- don't have to write your own, unlike the solution shown at the URL above)
that's this part std::vector<Vrtx> sorted_vertices; boost::topological_sort(dag, std::back_inserter(sorted_vertices)); followed by a one-pass
traversal of the vertices in the topologically sorted order to compute level number/longest path distance using your own code.
and that's this part std::vector<int> time(vrtx_count, 1); for (Vrtx u : sorted_vertices) { if (boost::out_degree(u, dag) > 0) { int maxdist = 0; for (Edge e : range_of(boost::out_edges(u, dag))) { Vrtx v = boost::target(e, dag); maxdist = std::max(time[v], maxdist); } time[u] = maxdist + 1; } } So I'm not sure what you mean by "don't have to write your own". --DD