+ } while(shortest_path_length < 0.0);
+
+ // Put back the graph in its original state (i.e. invert edges which
+ // have been inverted in the process)
+ for(int k = 0; k < _nb_edges; k++) {
+ e = &_edges[k];
+ if(e->occupied) { e->invert(); }
+ }
+}
+
+int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
+ Edge *f, *next = 0;
+ int l = 0, nb_occupied_next;
+
+ if(path) {
+ path->nodes[l++] = int(e->origin_vertex - _vertices);
+ path->length = e->length;
+ } else l++;
+
+ while(e->terminal_vertex != _sink) {
+ if(path) {
+ path->nodes[l++] = int(e->terminal_vertex - _vertices);
+ path->length += e->length;
+ } else l++;
+
+ nb_occupied_next = 0;
+ for(f = e->terminal_vertex->leaving_edge_list_root; f; f = f->next_leaving_edge) {
+ if(f->occupied) { nb_occupied_next++; next = f; }
+ }
+
+#ifdef DEBUG
+ if(nb_occupied_next == 0) {
+ cerr << __FILE__ << ": retrieve_one_path: Non-sink end point." << endl;
+ abort();
+ }
+
+ else if(nb_occupied_next > 1) {
+ cerr << __FILE__ << ": retrieve_one_path: Non node-disjoint paths." << endl;
+ abort();
+ }
+#endif
+
+ e = next;
+ }
+
+ if(path) {
+ path->nodes[l++] = int(e->terminal_vertex - _vertices);
+ path->length += e->length;
+ } else l++;
+
+ return l;
+}
+
+//////////////////////////////////////////////////////////////////////
+
+static int compare_vertices_on_distance(const void *v1, const void *v2) {
+ scalar_t delta =
+ (*((Vertex **) v1))->distance_from_source -
+ (*((Vertex **) v2))->distance_from_source;
+ if(delta < 0) return -1;
+ else if(delta > 0) return 1;
+ else return 0;
+}
+
+void MTPGraph::compute_dp_ordering() {
+ Vertex *v;
+ Edge *e;
+ int ntv;
+
+ // This method computes for each node the length of the longest link
+ // from the source, and orders the node in _dp_order according to
+ // it. It aborts if the graph is not a DAG.
+
+ int *nb_predecessors = new int[_nb_vertices];
+
+ Vertex **already_processed = _dp_order, **front = _dp_order, **new_front = _dp_order;
+
+ 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) {
+ ntv = int(e->terminal_vertex - _vertices);
+ nb_predecessors[ntv]++;
+ }
+ }
+
+ for(int k = 0; k < _nb_vertices; k++) {
+ if(nb_predecessors[k] == 0) {
+ *(front++) = _vertices + k;
+ }
+ }
+
+ scalar_t rank = 1;
+ while(already_processed < front) {
+ new_front = front;
+ while(already_processed < front) {
+ v = *(already_processed++);
+ v->distance_from_source = rank;
+ for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) {
+ ntv = int(e->terminal_vertex - _vertices);
+ nb_predecessors[ntv]--;
+ ASSERT(nb_predecessors[ntv] >= 0);
+ if(nb_predecessors[ntv] == 0) {
+ *(new_front++) = e->terminal_vertex;
+ }
+ }
+ }
+ front = new_front;
+ rank++;
+ }
+
+ if(already_processed < _dp_order + _nb_vertices) {
+ cerr << __FILE__ << ": The graph is not a DAG." << endl;
+ abort();
+ }
+
+ delete[] nb_predecessors;
+
+ for(int v = 0; v < _nb_vertices; v++) { _dp_order[v] = &_vertices[v]; }
+ qsort(_dp_order, _nb_vertices, sizeof(Vertex *), compare_vertices_on_distance);
+}
+
+//////////////////////////////////////////////////////////////////////
+
+void MTPGraph::retrieve_disjoint_paths() {
+ Edge *e;
+ int p, l;
+
+ for(int p = 0; p < nb_paths; p++) delete paths[p];
+ delete[] paths;
+
+ nb_paths = 0;
+ for(e = _source->leaving_edge_list_root; e; e = e->next_leaving_edge) {
+ if(e->occupied) { nb_paths++; }
+ }
+
+ paths = new Path *[nb_paths];