Levelization of DAG in Boost graph -- trying again
Not sure why my previous attempt to post a new topic didn't succeed -- page kept showing a note that the post was not accepted by the mailing list. Trying one more time. ------------------------ 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 I used record_distances() with breadth_first_search() and suitably defined property map, but I suspect that's returning level(v) = min_level(set of predecessors of v) + 1 Is there a simple way to use breadth_first_search() to get the level numbers I want, or do I need to write my own levelization routine? Thanks in advance for comments/suggestions/pointers. Debashis Bhattacharya -- View this message in context: http://boost.2283326.n4.nabble.com/Levelization-of-DAG-in-Boost-graph-trying... Sent from the Boost - Users mailing list archive at Nabble.com.
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; }
Dominique: Thanks for the response! I believe you're saying the general answer is "you've to do this yourself" -- which is what I expected. I also believe you can have a simpler solution -- see http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/ It's based on topological sorting (available with BGL -- don't have to write your own, unlike the solution shown at the URL above) 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. Don't have time to code and debug today. Will post the answer when I do this next week. Debashis. -- View this message in context: http://boost.2283326.n4.nabble.com/Levelization-of-DAG-in-Boost-graph-trying... Sent from the Boost - Users mailing list archive at Nabble.com.
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
Dominique: My bad. I looked at your reply hurriedly, and I got a bit lost in the rest of code in what you posted, I guess. The part of your code for computing longest path looks good. I'm not quite sure why you're gathering up all the vertices and edges first -- must admit didn't spend much time trying to understand. After a long delay -- got distracted by other stuff -- here's slightly different code for the same result (the essential pieces re-typed -- I have to operate within some restrictions, and cannot copy-paste my actual code; there may be typos introduced due to re-typing) using namespace std; using namespace boost; #define NINF ((int) std::numeric_limits<int>::min()) typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; Graph* g; vector<int>* levelNums; // Assume a Graph has been created and is pointed to by g. It has one source and multiple sinks // Assume vector pointed to be levelNums has been created typedef property_map<Graph, vertex_index_t>::type IndexMap; IndexMap index = get(vertex_index, *g); typedef graph_traits<Graph>::vertex_descriptor vd; vector<vd> topoVertexOrder; // Topological Sort topological_sort(*g, back_inserter(toptVertexOrder)); typedef graph_traits<Graph>::adjacency_iterator adjIt; adjIt adj_v, adj_vend; vector<vd>::reverse_iterator it; it = topoVertexOrder.rbegin(); // Init source to level 0, rest to level NINF levelNums->at(index[*it]) = 0; ++it; for (; it != topoVertexOrder.rend(); ++it) { levelNums->at(index[*it]) = NINF; } // Walk through topologically sorted list and compute level numbers -- easily generalized to longest paths // when edges have distance associated instead of each edge counting as distance 1 for (it = topoVertexOrder.rbegin(); it != topoVertexOrder.rend(); ++it) { if (levelNums->at(index[*it]) != NINF) { tie(adj_v, adj_vend) = adjacent_vertices(*it, *g); for (; adj_v != adj_vend; adj_v++) { if (levelNums->at(index[*adj_v]) < levelNums->at(index[*it]) + 1) { levelNums->at(index[*adj_v]) = levelNums->at(index[*it]) + 1; } } } } -- View this message in context: http://boost.2283326.n4.nabble.com/Levelization-of-DAG-in-Boost-graph-trying... Sent from the Boost - Users mailing list archive at Nabble.com.
participants (2)
-
bhattach
-
Dominique Devienne