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
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
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
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
participants (2)
-
bhattach -
Dominique Devienne