-int MTPGraph::compute_dp_distances() {
- Vertex *v;
- Edge *e;
-
- // 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.
-
- Vertex **active = new Vertex *[_nb_vertices];
-
- // All the nodes are active at first
- for(int k = 0; k < _nb_vertices; k++) {
- _vertices[k].distance_from_source = 0;
- active[k] = &_vertices[k];
- }
-
- scalar_t nb_iterations = 1;
- int nb_active = _nb_vertices, pred_nb_active;
-
- do {
- // We set the distance_from_source field of all the vertices with incoming
- // edges to the current nb_iterations 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->distance_from_source = nb_iterations;
- }
- }
-
- 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->distance_from_source == nb_iterations) {
- active[nb_active++] = v;
- }
- }
-
- nb_iterations++;
- } 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_slot;
- while(h > _heap &&
- (p = _heap + (h - _heap + 1) / 2 - 1,
- (*p)->distance_from_source > (*h)->distance_from_source)) {
- swap(*p, *h);
- swap((*p)->heap_slot, (*h)->heap_slot);
- h = p;
- }
-}
-
-void MTPGraph::increase_distance_in_heap(Vertex *v) {
- Vertex **c1, **c2, **h;
- // omg, that's beautiful
- h = v->heap_slot;
- 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_slot, (*h)->heap_slot);
- h = c1;
- } else {
- swap(*c2, *h);
- swap((*c2)->heap_slot, (*h)->heap_slot);
- h = c2;
- }
- }
-}
-