Re: [Boost-users] Levelization of DAG in Boost graph -- trying again

Subject: Re: [Boost-users] Levelization of DAG in Boost graph -- trying again
From: bhattach (bhattach_at_[hidden])
Date: 2015-11-20 15:56:41

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-again-tp4681269p4681688.html
Sent from the Boost - Users mailing list archive at Nabble.com.