-void MTPGraph::compute_dp_ranks() {
- Vertex *v;
- Edge *e;
- int tv;
-
- // 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.
-
- int *nb_predecessors = new int[_nb_vertices];
- int *without_predecessors = new int[_nb_vertices];
- int *new_without_predecessors = new int[_nb_vertices];
- int nb_without_predecessors, new_nb_without_predecessors;
-
- for(int k = 0; k < _nb_vertices; k++) {
- nb_predecessors[k] = 0;
- }
-
- for(int k = 0; k < _nb_vertices; k++) {
- v = _vertices + k;
- for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) {
- tv = int(e->terminal_vertex - _vertices);
- nb_predecessors[tv]++;
- }
- }
-
- nb_without_predecessors = 0;
- for(int k = 0; k < _nb_vertices; k++) {
- if(nb_predecessors[k] == 0) {
- without_predecessors[nb_without_predecessors++] = k;
- }
- }
-
- scalar_t rank = 1;
- while(nb_without_predecessors > 0) {
- new_nb_without_predecessors = 0;
- for(int l = 0; l < nb_without_predecessors; l++) {
- v = _vertices + without_predecessors[l];
- v->distance_from_source = rank;
- for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) {
- tv = int(e->terminal_vertex - _vertices);
- nb_predecessors[tv]--;
- ASSERT(nb_predecessors[tv] >= 0);
- if(nb_predecessors[tv] == 0) {
- new_without_predecessors[new_nb_without_predecessors++] = tv;
- }
- }
- }
-
- swap(without_predecessors, new_without_predecessors);
- nb_without_predecessors = new_nb_without_predecessors;
- rank++;
- }
-
- for(int k = 0; k < _nb_vertices; k++) {
- if(nb_predecessors[k] > 0) {
- cerr << __FILE__ << ": The graph is not a DAG." << endl;
- abort();
- }
- }
-
- delete[] nb_predecessors;
- delete[] without_predecessors;
- delete[] new_without_predecessors;
-}
-
-//////////////////////////////////////////////////////////////////////
-