X-Git-Url: https://www.fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=mtp.git;a=blobdiff_plain;f=mtp_graph.cc;h=2cbb33848a3589007528a6e3b1098357dbf3d3df;hp=a7b942d2cf0870259cbbafbfd3341579280761f2;hb=HEAD;hpb=92097e3a0db0c86ebb26b3a38a0247c6803a12ae

diff --git a/mtp_graph.cc b/mtp_graph.cc
index a7b942d..2cbb338 100644
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -241,7 +241,7 @@ void MTPGraph::force_positivized_lengths() {
     }
   }
 #ifdef VERBOSE
-  cerr << __FILE__ << ": residual_error " << residual_error << " max_error " << residual_error << endl;
+  cerr << __FILE__ << ": residual_error " << residual_error << " max_error " << max_error << endl;
 #endif
 }
 
@@ -379,7 +379,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
   }
 }
 
-int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
+int MTPGraph::retrieve_one_path(Edge *e, Path *path, int *used_edges) {
   Edge *f, *next = 0;
   int l = 0, nb_occupied_next;
 
@@ -396,7 +396,9 @@ int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
 
     nb_occupied_next = 0;
     for(f = e->terminal_vertex->leaving_edge_list_root; f; f = f->next_leaving_edge) {
-      if(f->occupied) { nb_occupied_next++; next = f; }
+      if(f->occupied && !used_edges[f - _edges]) {
+        nb_occupied_next++; next = f;
+      }
     }
 
 #ifdef DEBUG
@@ -404,13 +406,10 @@ int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
       cerr << __FILE__ << ": retrieve_one_path: Non-sink end point." << endl;
       abort();
     }
-
-    else if(nb_occupied_next > 1) {
-      cerr << __FILE__ << ": retrieve_one_path: Non node-disjoint paths." << endl;
-      abort();
-    }
 #endif
 
+    if(path) { used_edges[next - _edges] = 1; }
+
     e = next;
   }
 
@@ -459,7 +458,9 @@ void MTPGraph::compute_dp_ordering() {
   while(already_processed < front) {
     // Here, nodes before already_processed can be ignored, nodes
     // before front were set to 0 predecessors during the previous
-    // iteration. We will add the 
+    // iteration. During this new iteration, we have to visit the
+    // successors of these ones only, since they are the only ones
+    // which may end up with no predecessors.
     new_front = front;
     while(already_processed < front) {
       v = *(already_processed++);
@@ -488,6 +489,7 @@ void MTPGraph::compute_dp_ordering() {
 void MTPGraph::retrieve_disjoint_paths() {
   Edge *e;
   int p, l;
+  int *used_edges;
 
   for(int p = 0; p < nb_paths; p++) delete paths[p];
   delete[] paths;
@@ -498,14 +500,21 @@ void MTPGraph::retrieve_disjoint_paths() {
   }
 
   paths = new Path *[nb_paths];
+  used_edges = new int[_nb_edges];
+  for(int e = 0; e < _nb_edges; e++) {
+    used_edges[e] = 0;
+  }
 
   p = 0;
   for(e = _source->leaving_edge_list_root; e; e = e->next_leaving_edge) {
-    if(e->occupied) {
-      l = retrieve_one_path(e, 0);
+    if(e->occupied && !used_edges[e - _edges]) {
+      l = retrieve_one_path(e, 0, used_edges);
       paths[p] = new Path(l);
-      retrieve_one_path(e, paths[p]);
+      retrieve_one_path(e, paths[p], used_edges);
+      used_edges[e - _edges] = 1;
       p++;
     }
   }
+
+  delete[] used_edges;
 }