+ } while(nb_active < pred_nb_active);
+
+ delete[] active;
+
+ return nb_active == 0;
+}
+
+#ifdef DEBUG
+void print_heap(int first, int heap_size, Vertex **heap, int depth, Vertex *vertices) {
+ // if(depth == 0) cout << "** START_HEAP ********************************************************" << endl;
+ // if(first < heap_size) {
+ // print_heap((first + 1) * 2 - 1, heap_size, heap, depth + 1, vertices);
+ // for(int d = 0; d < depth; d++) cout << " ";
+ // cout << "[" << heap[first] - vertices << "] ";
+ // if(heap[first]->distance_from_source == FLT_MAX) cout << "inf";
+ // else cout << heap[first]->distance_from_source;
+ // cout << endl;
+ // print_heap((first + 1) * 2, heap_size, heap, depth + 1, vertices);
+ // }
+ // if(depth == 0) cout << "** END_HEAP **********************************************************" << endl;
+}
+
+void check_heap(Vertex **heap, int heap_size, Vertex *vertices, int nb_vertices) {
+ Vertex **p, **h;
+ int *used = new int[nb_vertices];
+ for(int v = 0; v < nb_vertices; v++) used[v] = 0;
+ for(int k = 0; k < heap_size; k++) {
+ used[heap[k] - vertices]++;
+ h = heap + k;
+ if(h != (*h)->heap_position) abort();
+ if(k > 0) {
+ p = heap + (h - heap + 1) / 2 - 1;
+ if((*h)->distance_from_source < (*p)->distance_from_source) abort();
+ }
+ }
+ for(int v = 0; v < nb_vertices; v++) {
+ cout << used[v];
+ if(used[v] > 1) abort();
+ }
+ cout << endl;
+ delete[] used;
+}
+#endif
+
+void MTPGraph::decrease_distance_in_heap(Vertex *v) {
+#ifdef DEBUG
+ // cout << "START decrease_distance_in_heap" << endl;
+ // print_heap(0, _heap_size, _heap, 0, _vertices);
+#endif
+ Vertex **p, **h;
+ // There is some beauty in that
+ h = v->heap_position;
+ while(h > _heap &&
+ (p = _heap + (h - _heap + 1) / 2 - 1,
+ (*p)->distance_from_source > (*h)->distance_from_source)) {
+// #warning REMOVE
+ // cout << "SWAP [" << (*p) - _vertices << " | " << (*h) - _vertices << "]" << endl;
+ // if((*p) - _vertices == 6 && (*h) - _vertices == 96) abort();
+ swap(*p, *h);
+ swap((*p)->heap_position, (*h)->heap_position);
+ h = p;
+ }
+#ifdef DEBUG
+ // check_heap(_heap, _heap_size, _vertices, _nb_vertices);
+ // print_heap(0, _heap_size, _heap, 0, _vertices);
+#endif
+}
+
+void MTPGraph::increase_distance_in_heap(Vertex *v) {
+#ifdef DEBUG
+ // cout << "START increase_distance_in_heap" << endl;
+ // print_heap(0, _heap_size, _heap, 0, _vertices);
+#endif
+ Vertex **c1, **c2, **h;
+ // There is some beauty in that
+ h = v->heap_position;
+ while(c1 = _heap + 2 * (h - _heap + 1) - 1, c2 = c1 + 1,
+ (c1 < _heap + _heap_size &&
+ (*c1)->distance_from_source < (*h)->distance_from_source)
+ ||
+ (c2 < _heap + _heap_size &&
+ (*c2)->distance_from_source < (*h)->distance_from_source)
+ ) {
+ if(c1 < _heap + _heap_size &&
+ !(c2 < _heap + _heap_size &&
+ (*c2)->distance_from_source < (*c1)->distance_from_source)){
+ swap(*c1, *h);
+ swap((*c1)->heap_position, (*h)->heap_position);
+ h = c1;
+ } else {
+ swap(*c2, *h);
+ swap((*c2)->heap_position, (*h)->heap_position);
+ h = c2;
+ }
+ }
+#ifdef DEBUG
+ // check_heap(_heap, _heap_size, _vertices, _nb_vertices);
+ // print_heap(0, _heap_size, _heap, 0, _vertices);
+#endif
+}
+
+void MTPGraph::dp_distance_propagation() {
+ Vertex *v, *tv;
+ Edge *e;
+ scalar_t d;
+
+ for(int k = 0; k < _nb_vertices; k++) {
+ _vertices[k].distance_from_source = FLT_MAX;
+ _vertices[k].pred_edge_toward_source = 0;
+ }
+
+ _source->distance_from_source = 0;
+
+ for(int k = 0; k < _nb_vertices; k++) {
+ v = _dp_order[k];
+ for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
+ d = v->distance_from_source + e->positivized_length;
+ tv = e->terminal_vertex;
+ if(d < tv->distance_from_source) {
+ tv->distance_from_source = d;
+ tv->pred_edge_toward_source = e;
+ decrease_distance_in_heap(tv);