Fixed retrieve_disjoint_paths to deal with non-node-disjoint situations.

diff --git a/mtp_graph.cc b/mtp_graph.cc
index e69d4d6..8849acd 100644 (file)
--- 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;
 
   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) {
 
     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
     }
 
 #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();
     }
       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
 
 #endif
 

+    if(path) { used_edges[next - _edges] = 1; }
+

     e = next;
   }
 
     e = next;
   }
 


@@ -490,6 +489,7 @@ void MTPGraph::compute_dp_ordering() {
 void MTPGraph::retrieve_disjoint_paths() {
   Edge *e;
   int p, l;
 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;
 
   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];
   }
 
   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) {
 
   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);
       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++;
     }
   }
       p++;
     }
   }

+
+  delete[] used_edges;

 }
 }

diff --git a/mtp_graph.h b/mtp_graph.h
index 33a29f5..64308b9 100644 (file)
--- a/mtp_graph.h
+++ b/mtp_graph.h
@@ -61,7 +61,7 @@ class MTPGraph {
   // Follows the path starting on edge e and returns the number of
   // nodes to reach the sink. If path is non-null, stores in it the
   // nodes met along the path, and computes path->length properly.
   // Follows the path starting on edge e and returns the number of
   // nodes to reach the sink. If path is non-null, stores in it the
   // nodes met along the path, and computes path->length properly.

-  int retrieve_one_path(Edge *e, Path *path);
+  int retrieve_one_path(Edge *e, Path *path, int *used_edges);

 
   int _nb_vertices, _nb_edges;
   Vertex *_source, *_sink;
 
   int _nb_vertices, _nb_edges;
   Vertex *_source, *_sink;


@@ -94,7 +94,10 @@ public:
   void find_best_paths(scalar_t *lengths);
 
   // Retrieve the paths corresponding to the occupied edges, and save
   void find_best_paths(scalar_t *lengths);
 
   // Retrieve the paths corresponding to the occupied edges, and save

-  // the result in the nb_paths and paths fields.
+  // the result in the nb_paths and paths fields. If the paths are not
+  // node-disjoint, there are multiple families of paths that
+  // "explain" the edge occupancies, and this method picks one of them
+  // arbitrarily.

   void retrieve_disjoint_paths();
 
   void print(ostream *os);
   void retrieve_disjoint_paths();
 
   void print(ostream *os);