-void MTPGraph::print() {
- for(int k = 0; k < _nb_edges; k++) {
- Edge *e = _edges + k;
- cout << e->origin_vertex->id
- << " -> "
- << e->terminal_vertex->id
- << " "
- << e->length;
- if(e->occupied) {
- cout << " *";
+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]++;