From 8439be2cf9581730b6a83425451cb9a335b2c715 Mon Sep 17 00:00:00 2001
From: Francois Fleuret <francois@fleuret.org>
Date: Wed, 19 Dec 2012 19:09:06 +0100
Subject: [PATCH] Cosmetics.

---
 mtp_graph.cc | 26 +++++++++++++++++---------
 mtp_graph.h  |  2 +-
 2 files changed, 18 insertions(+), 10 deletions(-)

diff --git a/mtp_graph.cc b/mtp_graph.cc
index aa294b4..660e659 100644
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -227,24 +227,32 @@ int MTPGraph::compute_dp_distances() {
   Vertex *v;
   Edge *e;
 
+  // This procedure computes for each node the longest link from the
+  // source and abort if the graph is not a DAG. It works by removing
+  // successively nodes without predecessor: At the first iteration it
+  // removes the source, then the nodes with incoming edge only from
+  // the source, etc. If it can remove all the nodes that way, the
+  // graph is a DAG. If at some point it can not remove node anymore
+  // and there are some remaining nodes, the graph is not a DAG.
+
   Vertex **active = new Vertex *[_nb_vertices];
 
-  // We put everybody in the active
+  // All the nodes are active at first
   for(int k = 0; k < _nb_vertices; k++) {
     _vertices[k].distance_from_source = 0;
     active[k] = &_vertices[k];
   }
 
-  int iteration = 1;
+  scalar_t nb_iterations = 1;
   int nb_active = _nb_vertices, pred_nb_active;
 
   do {
     // We set the distance_from_source field of all the vertices with incoming
-    // edges to the current iteration value
+    // edges to the current nb_iterations value
     for(int f = 0; f < nb_active; f++) {
       v = active[f];
       for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
-        e->terminal_vertex->distance_from_source = iteration;
+        e->terminal_vertex->distance_from_source = nb_iterations;
       }
     }
 
@@ -254,12 +262,12 @@ int MTPGraph::compute_dp_distances() {
     // We keep all the vertices with incoming nodes
     for(int f = 0; f < pred_nb_active; f++) {
       v = active[f];
-      if(v->distance_from_source == iteration) {
+      if(v->distance_from_source == nb_iterations) {
         active[nb_active++] = v;
       }
     }
 
-    iteration++;
+    nb_iterations++;
   } while(nb_active < pred_nb_active);
 
   delete[] active;
@@ -282,7 +290,7 @@ void MTPGraph::decrease_distance_in_heap(Vertex *v) {
 
 void MTPGraph::increase_distance_in_heap(Vertex *v) {
   Vertex **c1, **c2, **h;
-  // There is some beauty in that
+  // omg, that's beautiful
   h = v->heap_slot;
   while(c1 = _heap + 2 * (h - _heap + 1) - 1, c2 = c1 + 1,
         (c1 < _heap + _heap_size && (*c1)->distance_from_source < (*h)->distance_from_source)
@@ -302,7 +310,7 @@ void MTPGraph::increase_distance_in_heap(Vertex *v) {
   }
 }
 
-void MTPGraph::dp_distance_propagation() {
+void MTPGraph::dp_compute_distances() {
   Vertex *v, *tv;
   Edge *e;
   scalar_t d;
@@ -385,7 +393,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
 
   // Update the distance to the source in "good order"
 
-  dp_distance_propagation();
+  dp_compute_distances();
 
   do {
     update_positivized_lengths();
diff --git a/mtp_graph.h b/mtp_graph.h
index c910520..84c9ce6 100644
--- a/mtp_graph.h
+++ b/mtp_graph.h
@@ -54,7 +54,7 @@ class MTPGraph {
 
   // Visit the vertices according to _dp_order and simply update their
   // distance to the source
-  void dp_distance_propagation();
+  void dp_compute_distances();
 
   // Set in every vertex pred_edge_toward_source correspondingly to
   // the path of shortest length. The current implementation is
-- 
2.20.1