+int MTPGraph::check_DAG_and_set_last_change() {
+ Vertex *v;
+ Edge *e;
+
+ Vertex **active = new Vertex *[_nb_vertices];
+
+ // We put everybody in the active
+ for(int k = 0; k < _nb_vertices; k++) {
+ _vertices[k].last_change = 0;
+ active[k] = &_vertices[k];
+ }
+
+ int iteration = 1;
+ int nb_active = _nb_vertices, pred_nb_active;
+
+ do {
+ // We set the last_change field of all the vertices with incoming
+ // edges to the current iteration value
+ for(int f = 0; f < nb_active; f++) {
+ v = active[f];
+ for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
+ e->terminal_vertex->last_change = iteration;
+ }
+ }
+
+ pred_nb_active = nb_active;
+ nb_active = 0;
+
+ // We keep all the vertices with incoming nodes
+ for(int f = 0; f < pred_nb_active; f++) {
+ v = active[f];
+ if(v->last_change == iteration) {
+ active[nb_active++] = v;
+ }
+ }
+
+ iteration++;
+ } while(nb_active < pred_nb_active);
+
+ delete[] active;
+
+ return nb_active == 0;
+}
+
+void MTPGraph::decrease_distance_in_heap(Vertex *v) {
+ 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)) {
+ swap(*p, *h);
+ swap((*p)->heap_position, (*h)->heap_position);
+ h = p;
+ }
+}
+
+void MTPGraph::increase_distance_in_heap(Vertex *v) {
+ 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;
+ }
+ }
+}
+
+void MTPGraph::dp_distance_propagation() {