+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::dp_compute_distances() {