-void MTPGraph::compute_dp_ranks() {
- Vertex *v;
- Edge *e;
-
- // This procedure computes for each node the longest link from the
- // source and abort if the graph is not a DAG. It works by removing
- // successively nodes without predecessor: At the first iteration it
- // removes the source, then the nodes with incoming edge only from
- // the source, etc. If it can remove all the nodes that way, the
- // graph is a DAG. If at some point it can not remove node anymore
- // and there are some remaining nodes, the graph is not a DAG. The
- // rank of a node is the iteration at which is it removed, and we
- // set the distance_from_source fields to this value.
-
- Vertex **with_predecessor = new Vertex *[_nb_vertices];
-
- // All the nodes are with_predecessor at first
- for(int k = 0; k < _nb_vertices; k++) {
- _vertices[k].distance_from_source = 0;
- with_predecessor[k] = &_vertices[k];
- }
-
- scalar_t rank = 1;
- int nb_with_predecessor = _nb_vertices, pred_nb_with_predecessor;
-
- do {
- // We set the distance_from_source field of all the vertices with incoming
- // edges to the current rank value
- for(int f = 0; f < nb_with_predecessor; f++) {
- v = with_predecessor[f];
- for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) {
- e->terminal_vertex->distance_from_source = rank;
- }
- }
-
- pred_nb_with_predecessor = nb_with_predecessor;
- nb_with_predecessor = 0;
-
- // We keep all the vertices with incoming nodes
- for(int f = 0; f < pred_nb_with_predecessor; f++) {
- v = with_predecessor[f];
- if(v->distance_from_source == rank) {
- with_predecessor[nb_with_predecessor++] = v;
- }
- }
-
- rank++;
- } while(nb_with_predecessor < pred_nb_with_predecessor);
-
- delete[] with_predecessor;
-
- if(nb_with_predecessor > 0) {
- cerr << __FILE__ << ": The graph is not a DAG." << endl;
- abort();
- }
-}
-
-//////////////////////////////////////////////////////////////////////
-