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.