- for(int v = 0; v < _nb_vertices; v++) {
- vertices[v].distance_from_source = FLT_MAX;
- vertices[v].pred_vertex = 0;
- vertices[v].pred_edge = 0;
- vertices[v].iteration = 0;
+int MTPGraph::is_dag() {
+ Vertex *v;
+ Edge *e;
+
+ // We put everybody in the front
+ for(int k = 0; k < _nb_vertices; k++) {
+ _vertices[k].last_change = -1;
+ _front[k] = &_vertices[k];
+ }
+
+ int iteration = 0;
+ int front_size = _nb_vertices, pred_front_size;
+
+ do {
+ // We set the iteration field of all vertex with incoming edges to
+ // the current iteration value
+ for(int f = 0; f < front_size; f++) {
+ v = _front[f];
+ for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
+ e->terminal_vertex->last_change = iteration;
+ }
+ }
+
+ pred_front_size = front_size;
+ front_size = 0;
+
+ // We remove all the vertices without incoming edge
+ for(int f = 0; f < pred_front_size; f++) {
+ v = _front[f];
+ if(v->last_change == iteration) {
+ _front[front_size++] = v;
+ }
+ }
+
+ iteration++;
+ } while(front_size < pred_front_size);
+
+ return front_size == 0;
+}
+
+// This method does not change the edge occupation. It only set
+// properly for every vertex the fields distance_from_source and
+// pred_edge_toward_source.
+
+void MTPGraph::find_shortest_path() {
+ Vertex **tmp_front;
+ Vertex *v, *tv;
+ Edge *e;
+ scalar_t d;
+
+#ifdef DEBUG
+ if(is_dag()) {
+ cout << "find_shortest_path: DAG -> ok" << endl;
+ } else {
+ for(int e = 0; e < _nb_edges; e++) {
+ if(_edges[e].positivized_length < 0) abort();
+ }
+ cout << "find_shortest_path: All positivized_length are positive -> ok" << endl;
+ }
+#endif
+
+ for(int k = 0; k < _nb_vertices; k++) {
+ _vertices[k].distance_from_source = FLT_MAX;
+ _vertices[k].pred_edge_toward_source = 0;
+ _vertices[k].last_change = -1;