-int MTPGraph::is_dag() {
- 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;
-}
-
-#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() {