From 7704ecb19140055b21e1012cd0d394f2a6db98eb Mon Sep 17 00:00:00 2001
From: Francois Fleuret <francois@fleuret.org>
Date: Fri, 24 Aug 2012 04:44:27 +0200
Subject: [PATCH] Cosmetics.

---
 mtp_graph.cc | 51 ++++++++++++++++++---------------------------------
 mtp_graph.h  |  5 +++--
 2 files changed, 21 insertions(+), 35 deletions(-)

diff --git a/mtp_graph.cc b/mtp_graph.cc
index a60e532..4d142cd 100644
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -41,7 +41,7 @@ public:
   int id;
   Edge *leaving_edges;
   scalar_t distance_from_source;
-  Edge *best_pred_edge_to_source;
+  Edge *pred_edge_toward_source;
 
   int iteration; // Used in find_shortest_path to know if we already
                  // added this vertex to the front
@@ -163,20 +163,6 @@ void MTPGraph::print_dot(ostream *os) {
 
 //////////////////////////////////////////////////////////////////////
 
-void MTPGraph::initialize_positivized_lengths_with_min() {
-  scalar_t length_min = 0;
-  for(int n = 0; n < _nb_vertices; n++) {
-    for(Edge *e = _vertices[n].leaving_edges; e; e = e->next_leaving_edge) {
-      length_min = min(e->length, length_min);
-    }
-  }
-  for(int n = 0; n < _nb_vertices; n++) {
-    for(Edge *e = _vertices[n].leaving_edges; e; e = e->next_leaving_edge) {
-      e->positivized_length = e->length - length_min;
-    }
-  }
-}
-
 void MTPGraph::update_positivized_lengths() {
   for(int k = 0; k < _nb_edges; k++) {
     Edge *e = _edges + k;
@@ -195,7 +181,7 @@ void MTPGraph::force_positivized_lengths() {
       if(e->positivized_length < 0) {
 #ifdef VERBOSE
         residual_error -= e->positivized_length;
-        max_error = max(max_error, fabs(e->positivized_length));
+        max_error = max(max_error, - e->positivized_length);
 #endif
         e->positivized_length = 0.0;
       }
@@ -207,8 +193,8 @@ void MTPGraph::force_positivized_lengths() {
 }
 
 // This method does not change the edge occupation. It update
-// distance_from_source and best_pred_edge_to_source.
-void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) {
+// distance_from_source and pred_edge_toward_source.
+void MTPGraph::find_shortest_path() {
   Vertex **tmp_front;
   int tmp_front_size;
   Vertex *v, *tv;
@@ -217,7 +203,7 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) {
 
   for(int v = 0; v < _nb_vertices; v++) {
     _vertices[v].distance_from_source = FLT_MAX;
-    _vertices[v].best_pred_edge_to_source = 0;
+    _vertices[v].pred_edge_toward_source = 0;
     _vertices[v].iteration = 0;
   }
 
@@ -238,7 +224,7 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) {
         tv = e->terminal_vertex;
         if(d < tv->distance_from_source) {
           tv->distance_from_source = d;
-          tv->best_pred_edge_to_source = e;
+          tv->pred_edge_toward_source = e;
           if(tv->iteration < iteration) {
             _new_front[_new_front_size++] = tv;
             tv->iteration = iteration;
@@ -270,26 +256,23 @@ 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(_front, _new_front);
+  find_shortest_path();
   update_positivized_lengths();
 
-  // #warning
-  // initialize_positivized_lengths_with_min();
-
   do {
     force_positivized_lengths();
-    find_shortest_path(_front, _new_front);
+    find_shortest_path();
     update_positivized_lengths();
 
     total_length = 0.0;
 
     // Do we reach the _sink?
-    if(_sink->best_pred_edge_to_source) {
+    if(_sink->pred_edge_toward_source) {
       // If yes, compute the length of the best path
       v = _sink;
-      while(v->best_pred_edge_to_source) {
-        total_length += v->best_pred_edge_to_source->length;
-        v = v->best_pred_edge_to_source->origin_vertex;
+      while(v->pred_edge_toward_source) {
+        total_length += v->pred_edge_toward_source->length;
+        v = v->pred_edge_toward_source->origin_vertex;
       }
       // If that length is negative
       if(total_length < 0.0) {
@@ -298,8 +281,8 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
 #endif
         // Invert all the edges along the best path
         v = _sink;
-        while(v->best_pred_edge_to_source) {
-          e = v->best_pred_edge_to_source;
+        while(v->pred_edge_toward_source) {
+          e = v->pred_edge_toward_source;
           v = e->origin_vertex;
           e->invert();
           // This is the only place where we change the occupations of
@@ -311,6 +294,8 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
 
   } while(total_length < 0.0);
 
+  // Put back the graph in its original state (i.e. invert edges which
+  // have been inverted in the process)
   for(int k = 0; k < _nb_edges; k++) {
     Edge *e = _edges + k;
     if(e->occupied) { e->invert(); }
@@ -331,11 +316,11 @@ int MTPGraph::retrieve_one_path(Edge *e, int *nodes) {
     for(f = e->terminal_vertex->leaving_edges; f; f = f->next_leaving_edge) {
       if(f->occupied) { nb_choices++; next = f; }
       if(nb_choices == 0) {
-        cerr << "Non-sink path end point?!" << endl;
+        cerr << "retrieve_one_path: Non-sink end point." << endl;
         abort();
       }
       if(nb_choices > 1) {
-        cerr << "Non node-disjoint path, can not retrieve." << endl;
+        cerr << "retrieve_one_path: Non node-disjoint paths." << endl;
         abort();
       }
     }
diff --git a/mtp_graph.h b/mtp_graph.h
index 7ccbfe3..6b8c181 100644
--- a/mtp_graph.h
+++ b/mtp_graph.h
@@ -31,10 +31,11 @@ class Vertex;
 class Edge;
 
 class MTPGraph {
-  void initialize_positivized_lengths_with_min();
   void update_positivized_lengths();
   void force_positivized_lengths();
-  void find_shortest_path(Vertex **front, Vertex **new_front);
+  void find_shortest_path();
+  // Retrieve the path starting on edge e and return its length. If
+  // nodes is non-null, stores the node met along the path in it.
   int retrieve_one_path(Edge *e, int *nodes);
 
   Vertex **_front, **_new_front;
-- 
2.20.1