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 04:38:04

On Wed, Oct 28, 2015 at 7:29 PM, bhattach <bhattach_at_[hidden]> wrote:

> Although I've been using graphs for 30+ years, I'm new to Boost Graph
> Library. I'd like to do "classical levelization" of a DAG -- as is commonly
> used in applications like digital logic simulation, etc -- whereby
>
>    level(v) = max_level(set of predecessors of v) + 1
>

This is in
http://www.boost.org/doc/libs/master/libs/graph/doc/file_dependency_example.html

I just did that for my graph last night. I struggled a bit, because my
edges are "reversed".
So my version uses out_degree/out_edges/target and not
in_degree/in_edges/source.
Here's my version, using C++11:

    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, bidirectionalS, const MyNode*,
const MyEdge*>;
    using Vrtx = boost::graph_traits<Graph>::vertex_descriptor;
    using Edge = boost::graph_traits<Graph>::edge_descriptor;

    Graph dag;

    // Gather the vertices of our graph
    for (const MyNode& node : nodes) {
        Vrtx v = add_vertex(dag);
        dag[v] = &node;
    }

    // Gather the edges of our graph
    for (const MyNode& node : nodes) {
        Vrtx v = get dag's vertex from my node;
        for (const MyEdge& edge : node.edges()) {
            Vrtx parent_v = get dag's vertex from my edge;
            Edge e; bool inserted;
            std::tie(e, inserted) = add_edge(v, parent_v, dag);
            assert(inserted);
            dag[e] = &edge;
        }
    }

    const auto vrtx_count = num_vertices(dag);
    const auto edge_count = num_edges(dag);
    std::cout << "Graph has " << vrtx_count << " vertices "
        "and " << edge_count << " edges" << std::endl;

    try {
        std::vector<Vrtx> sorted_vertices;
        topological_sort(dag, std::back_inserter(sorted_vertices));
        //std::cout << "topological_sort:" << std::endl;
        for (Vrtx v : sorted_vertices) {
            const MyNode* p_node = dag[v];
            //std::cout << "- " << p_node->name() << " "
            //    << in_degree(v, dag) << " in, "
            //    << out_degree(v, dag) << " out" << std::endl;
        }

        std::vector<int> time(vrtx_count, 1);
        for (Vrtx u : sorted_vertices) {
            if (out_degree(u, dag) > 0) {
                int maxdist = 0;
                for (Edge e : range_of(out_edges(u, dag))) {
                    Vrtx v = target(e, dag);
                    maxdist = std::max(time[v], maxdist);
                }
                time[u] = maxdist + 1;
            }
        }

        std::cout << "topological_sort with levels:" << std::endl;
        for (Vrtx v : sorted_vertices) {
            const MyNode* p_table = dag[v];
            int node_level = time[v];
            std::cout << "- [" << node_level << "] " << p_node->name() <<
std::endl;
        }
    } catch (const boost::bad_graph& e) {
        std::cout << "Cannot sort graph: " << e.what() << std::endl;
    }