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