From 6da7394e095ec264738cd222b75dab01af453d8c Mon Sep 17 00:00:00 2001
From: Francois Fleuret <francois@fleuret.org>
Date: Mon, 20 Aug 2012 21:00:24 -0700
Subject: [PATCH] Added comments.

---
 miniksp.cc | 58 +++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 40 insertions(+), 18 deletions(-)

diff --git a/miniksp.cc b/miniksp.cc
index 4ec9423..0598afe 100644
--- a/miniksp.cc
+++ b/miniksp.cc
@@ -20,7 +20,7 @@
 // END_IP_HEADER                                                         //
 ///////////////////////////////////////////////////////////////////////////
 
-// #define VERBOSE
+#define VERBOSE
 
 #include <iostream>
 #include <fstream>
@@ -42,6 +42,12 @@ typedef float scalar_t;
 #define ASSERT(x)
 #endif
 
+// In all the code:
+//
+//  * el[e] is the length of edge e
+//  * ea[e] is its starting node
+//  * eb[e] is its destination node.
+
 // Adds to all the edge length the length of the shortest (which can
 // be negative)
 void raise_es(int nb_edges, scalar_t *el) {
@@ -54,27 +60,28 @@ void raise_es(int nb_edges, scalar_t *el) {
   }
 }
 
-// Add to every edge length the differential of the psi function on it
+// Adds to every edge length the differential of the psi function on
+// it
 void add_dpsi_es(int nb_edges, scalar_t *el, int *ea, int *eb, scalar_t *psi) {
   for(int e = 0; e < nb_edges; e++) {
     el[e] += psi[ea[e]] - psi[eb[e]];
   }
 }
 
-// Find the shortest path in the graph and return in return_edge_back,
-// for each vertex the edge to follow back from it to reach the source
-// with the shortest path, and in return_dist the distance to the
-// source. The edge lengths have to be positive.
+// Finds the shortest path in the graph and return in
+// result_edge_back, for each vertex the edge to follow back from it
+// to reach the source with the shortest path, and in result_dist the
+// distance to the source. The edge lengths have to be positive.
 void find_shortest(int nb_vertices,
                    int nb_edges, scalar_t *el, int *ea, int *eb,
                    int source, int sink,
-                   int *return_edge_back, scalar_t *return_dist) {
+                   int *result_edge_back, scalar_t *result_dist) {
   for(int v = 0; v < nb_vertices; v++) {
-    dist[v] = FLT_MAX;
-    edge_back[v] = -1;
+    result_dist[v] = FLT_MAX;
+    result_edge_back[v] = -1;
   }
 
-  dist[source] = 0;
+  result_dist[source] = 0;
 
 #ifdef DEBUG
   for(int e = 0; e < nb_edges; e++) {
@@ -87,20 +94,23 @@ void find_shortest(int nb_vertices,
   do {
     nb_changes = 0;
     for(int e = 0; e < nb_edges; e++) {
-      d = dist[ea[e]] + el[e];
-      if(d < dist[eb[e]]) {
+      d = result_dist[ea[e]] + el[e];
+      if(d < result_dist[eb[e]]) {
         nb_changes++;
-        dist[eb[e]] = d;
-        edge_back[eb[e]] = e;
+        result_dist[eb[e]] = d;
+        result_edge_back[eb[e]] = e;
       }
     }
   } while(nb_changes > 0);
 }
 
+// Iterates find_shortest as long as it finds paths of negative
+// lengths. Notes which edges are occupied by the superposition of
+// paths in result_edge_occupation
 void find_best_paths(int nb_vertices,
                      int nb_edges, scalar_t *el, int *ea, int *eb,
                      int source, int sink,
-                     int *edge_occupation) {
+                     int *result_edge_occupation) {
   scalar_t *dist = new scalar_t[nb_vertices];
   int *edge_back = new int[nb_vertices];
   scalar_t *positive_el = new scalar_t[nb_edges];
@@ -109,7 +119,7 @@ void find_best_paths(int nb_vertices,
 
   for(int e = 0; e < nb_edges; e++) {
     positive_el[e] = el[e];
-    edge_occupation[e] = 0;
+    result_edge_occupation[e] = 0;
   }
 
   raise_es(nb_edges, positive_el);
@@ -133,7 +143,8 @@ void find_best_paths(int nb_vertices,
       }
 
       // We found a good path (score < 0), we revert the edges along
-      // the path and note that they are occupied
+      // the path and invert their occupation (since adding a path on
+      // a path already occupied means removing flow on it)
 
       if(s < 0) {
         v = sink;
@@ -152,7 +163,7 @@ void find_best_paths(int nb_vertices,
           ea[e] = k;
           positive_el[e] = - positive_el[e];
           el[e] = - el[e];
-          edge_occupation[e] = 1 - edge_occupation[e];
+          result_edge_occupation[e] = 1 - result_edge_occupation[e];
         }
       }
     }
@@ -198,6 +209,17 @@ int main(int argc, char **argv) {
     find_best_paths(nb_vertices, nb_edges, el, ea, eb, source, sink,
                     edge_occupation);
 
+#ifdef VERBOSE
+    // Sanity check on the overall resulting score (the edge lengths
+    // have been changed, hence should be the opposite of the sum of
+    // the path lengths)
+    scalar_t s = 0;
+    for(int e = 0; e < nb_edges; e++) {
+      if(edge_occupation[e]) s += el[e];
+    }
+    cout << "RESULT_SANITY_CHECK_SCORE " << s << endl;
+#endif
+
     for(int e = 0; e < nb_edges; e++) {
       if(edge_occupation[e]) {
         cout << "RESULT_OCCUPIED_EDGE " << ea[e] << " " << eb[e] << endl;
-- 
2.39.5