On Wed, Oct 28, 2015 at 7:29 PM, bhattach <bhattach@yahoo.com> 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.... 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; }