Update.

[mtp.git] / mtp_graph.cc

diff --git a/mtp_graph.cc b/mtp_graph.cc
index 4d142cd..4608b82 100644 (file)
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -46,8 +46,8 @@ public:
   int iteration; // Used in find_shortest_path to know if we already
                  // added this vertex to the front
   Vertex();
-  inline void add_edge(Edge *e);
-  inline void del_edge(Edge *e);
+  inline void add_leaving_edge(Edge *e);
+  inline void del_leaving_edge(Edge *e);
 };
 
 //////////////////////////////////////////////////////////////////////
@@ -55,8 +55,8 @@ public:
 void Edge::invert() {
   length = - length;
   positivized_length = 0;
-  origin_vertex->del_edge(this);
-  terminal_vertex->add_edge(this);
+  origin_vertex->del_leaving_edge(this);
+  terminal_vertex->add_leaving_edge(this);
   Vertex *t = terminal_vertex;
   terminal_vertex = origin_vertex;
   origin_vertex = t;
@@ -68,17 +68,23 @@ Vertex::Vertex() {
   leaving_edges = 0;
 }
 
-void Vertex::add_edge(Edge *e) {
+void Vertex::add_leaving_edge(Edge *e) {
   e->next_leaving_edge = leaving_edges;
   e->pred_leaving_edge = 0;
   if(leaving_edges) { leaving_edges->pred_leaving_edge = e; }
   leaving_edges = e;
 }
 
-void Vertex::del_edge(Edge *e) {
-  if(e == leaving_edges) { leaving_edges = e->next_leaving_edge; }
-  if(e->pred_leaving_edge) { e->pred_leaving_edge->next_leaving_edge = e->next_leaving_edge; }
-  if(e->next_leaving_edge) { e->next_leaving_edge->pred_leaving_edge = e->pred_leaving_edge; }
+void Vertex::del_leaving_edge(Edge *e) {
+  if(e == leaving_edges) {
+    leaving_edges = e->next_leaving_edge;
+  }
+  if(e->pred_leaving_edge) {
+    e->pred_leaving_edge->next_leaving_edge = e->next_leaving_edge;
+  }
+  if(e->next_leaving_edge) {
+    e->next_leaving_edge->pred_leaving_edge = e->pred_leaving_edge;
+  }
 }
 
 //////////////////////////////////////////////////////////////////////
@@ -102,7 +108,7 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges,
   }
 
   for(int e = 0; e < nb_edges; e++) {
-    _vertices[from[e]].add_edge(_edges + e);
+    _vertices[from[e]].add_leaving_edge(_edges + e);
     _edges[e].occupied = 0;
     _edges[e].id = e;
     _edges[e].origin_vertex = _vertices + from[e];
@@ -257,12 +263,11 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
   // We use one iteration of find_shortest_path simply to propagate
   // the distance to make all the edge lengths positive.
   find_shortest_path();
-  update_positivized_lengths();
 
   do {
+    update_positivized_lengths();
     force_positivized_lengths();
     find_shortest_path();
-    update_positivized_lengths();
 
     total_length = 0.0;
 
@@ -302,16 +307,20 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
   }
 }
 
-int MTPGraph::retrieve_one_path(Edge *e, int *nodes) {
+int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
   Edge *f, *next = 0;
   int l = 0;
 
-  if(nodes) { nodes[l++] = e->origin_vertex->id; }
-  else l++;
+  if(path) {
+    path->nodes[l++] = e->origin_vertex->id;
+    path->length = e->length;
+  } else l++;
 
   while(e->terminal_vertex != _sink) {
-    if(nodes) { nodes[l++] = e->terminal_vertex->id; }
-    else l++;
+    if(path) {
+      path->nodes[l++] = e->terminal_vertex->id;
+      path->length += e->length;
+    } else l++;
     int nb_choices = 0;
     for(f = e->terminal_vertex->leaving_edges; f; f = f->next_leaving_edge) {
       if(f->occupied) { nb_choices++; next = f; }
@@ -327,8 +336,10 @@ int MTPGraph::retrieve_one_path(Edge *e, int *nodes) {
     e = next;
   }
 
-  if(nodes) { nodes[l++] = e->terminal_vertex->id; }
-  else l++;
+  if(path) {
+    path->nodes[l++] = e->terminal_vertex->id;
+    path->length += e->length;
+  } else l++;
 
   return l;
 }
@@ -351,7 +362,7 @@ void MTPGraph::retrieve_disjoint_paths() {
     if(e->occupied) {
       int l = retrieve_one_path(e, 0);
       paths[p] = new Path(l);
-      retrieve_one_path(e, paths[p]->nodes);
+      retrieve_one_path(e, paths[p]);
       p++;
     }
   }