X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?a=blobdiff_plain;f=mtp_graph.cc;h=d3b921b791e6acfc2728702b0b593d0dc2cacdf0;hb=abbaf6b4b4b8d10ee8e9054a3b8d262a2f242920;hp=9a811bba9ae5095b625cd7589c0bfdd024d2c298;hpb=34022d5e987cf13ff6db31a6d7263e9266a8b1c0;p=mtp.git

diff --git a/mtp_graph.cc b/mtp_graph.cc
index 9a811bb..d3b921b 100644
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -153,6 +153,7 @@ void MTPGraph::print(ostream *os) {
 
 void MTPGraph::print_dot(ostream *os) {
   (*os) << "digraph {" << endl;
+  (*os) << "        rankdir=\"LR\";" << endl;
   (*os) << "        node [shape=circle,width=0.75,fixedsize=true];" << endl;
   (*os) << "        edge [color=gray,arrowhead=open]" << endl;
   (*os) << "        " << _source->id << " [peripheries=2];" << endl;
@@ -204,7 +205,7 @@ void MTPGraph::force_positivized_lengths() {
 }
 
 int MTPGraph::is_dag() {
-  Vertex *v, *tv;
+  Vertex *v;
   Edge *e;
 
   // We put everybody in the front
@@ -213,49 +214,57 @@ int MTPGraph::is_dag() {
     _front[k] = &_vertices[k];
   }
 
-  int front_size = _nb_vertices, nb_with_incoming;
   int iteration = 0;
-  int new_front_size, pred_front_size;
+  int front_size = _nb_vertices, pred_front_size;
 
   do {
     iteration++;
-    nb_with_incoming = 0;
 
     // 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) {
-        tv = e->terminal_vertex;
-        tv->iteration = iteration;
+        e->terminal_vertex->iteration = iteration;
       }
     }
 
-    new_front_size = 0;
-    // We remove all vertex without incoming edge
-    for(int f = 0; f < front_size; f++) {
+    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->iteration == iteration) {
-        _front[new_front_size++] = v;
+        _front[front_size++] = v;
       }
     }
-
-    pred_front_size = front_size;
-    front_size = new_front_size;
   } while(front_size < pred_front_size);
 
   return front_size == 0;
 }
 
-// This method does not change the edge occupation. It update
-// distance_from_source and pred_edge_toward_source.
+// 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;
-  int tmp_front_size;
   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;
@@ -288,13 +297,9 @@ void MTPGraph::find_shortest_path() {
       }
     }
 
-    tmp_front = _new_front;
-    _new_front = _front;
-    _front = tmp_front;
+    tmp_front = _new_front; _new_front = _front; _front = tmp_front;
 
-    tmp_front_size = new_front_size;
-    new_front_size = front_size;
-    front_size = tmp_front_size;
+    front_size = new_front_size;
   } while(front_size > 0);
 }
 
@@ -309,11 +314,9 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
     _edges[e].positivized_length = _edges[e].length;
   }
 
-  // Let's be a bit paranoid
-  ASSERT(is_dag());
-
-  // We use one iteration of find_shortest_path simply to propagate
-  // the distance to make all the edge lengths positive.
+  // We call find_shortest_path here to set properly the distances to
+  // the source, so that we can make all the edge lengths positive at
+  // the first iteration.
   find_shortest_path();
 
   do {
@@ -323,7 +326,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
 
     total_length = 0.0;
 
-    // Do we reach the _sink?
+    // Do we reach the sink?
     if(_sink->pred_edge_toward_source) {
       // If yes, compute the length of the best path
       v = _sink;