X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=mtp.git;a=blobdiff_plain;f=mtp_graph.cc;fp=mtp_graph.cc;h=8849acdf05e05dd0720895e60681d0f27ca330ee;hp=e69d4d675a6bdd170e81d5819c9035ddbd0c4710;hb=0a78398c86517c7c6224bd8f4f1b3950fed245b9;hpb=2228dec6631697204466df7e45b7ab3786f6308a

diff --git a/mtp_graph.cc b/mtp_graph.cc
index e69d4d6..8849acd 100644
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -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;
   }
 
@@ -490,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;
@@ -500,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;
 }