Re: [Boost-users] Levelization of DAG in Boost graph -- trying again

Subject: Re: [Boost-users] Levelization of DAG in Boost graph -- trying again
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2015-10-30 17:54:00

On Fri, Oct 30, 2015 at 8:46 PM, bhattach <bhattach_at_[hidden]> 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