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 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::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.
