From 6afe91234d7807ce82b96a071087decb2f7aead3 Mon Sep 17 00:00:00 2001
From: Francois Fleuret <francois@fleuret.org>
Date: Fri, 24 Aug 2012 05:13:38 +0200
Subject: [PATCH] Update.

---
 misc.h       |  2 +-
 mtp.cc       |  3 ++-
 mtp_graph.cc | 51 +++++++++++++++++++++++++++++++--------------------
 mtp_graph.h  |  8 +++++---
 path.cc      |  6 +++---
 path.h       |  7 +++++--
 tracker.cc   | 10 +++++++---
 tracker.h    |  1 +
 8 files changed, 55 insertions(+), 33 deletions(-)

diff --git a/misc.h b/misc.h
index 51ad326..f95a8db 100644
--- a/misc.h
+++ b/misc.h
@@ -21,7 +21,7 @@
 
 #include <stdlib.h>
 
-// #define VERBOSE
+#define VERBOSE
 
 typedef float scalar_t;
 
diff --git a/mtp.cc b/mtp.cc
index 979915b..dab3292 100644
--- a/mtp.cc
+++ b/mtp.cc
@@ -67,7 +67,8 @@ int main(int argc, char **argv) {
   for(int t = 0; t < tracker->nb_trajectories(); t++) {
     cout << "TRAJECTORY "
          << t
-         << " [starting " << tracker->trajectory_entrance_time(t) << "]";
+         << " [starting " << tracker->trajectory_entrance_time(t)
+         << ", score " << tracker->trajectory_score(t) << "]";
     for(int u = 0; u < tracker->trajectory_duration(t); u++) {
       cout << " " << tracker->trajectory_location(t, u);
     }
diff --git a/mtp_graph.cc b/mtp_graph.cc
index 4d142cd..4608b82 100644
--- 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++;
     }
   }
diff --git a/mtp_graph.h b/mtp_graph.h
index 6b8c181..ae0003a 100644
--- a/mtp_graph.h
+++ b/mtp_graph.h
@@ -33,10 +33,12 @@ class Edge;
 class MTPGraph {
   void update_positivized_lengths();
   void force_positivized_lengths();
+  // Set the edge pred_edge_toward_source correspondingly to the path
+  // of shortest length.
   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);
+  // Follows the path starting on edge e and returns its length. If
+  // nodes is non-null, stores in it the nodes met along the path.
+  int retrieve_one_path(Edge *e, Path *path);
 
   Vertex **_front, **_new_front;
 
diff --git a/path.cc b/path.cc
index 1c5ecd1..ab69018 100644
--- a/path.cc
+++ b/path.cc
@@ -18,9 +18,9 @@
 
 #include "path.h"
 
-Path::Path(int l) {
-  length = l;
-  nodes = new int[length];
+Path::Path(int n) {
+  nb_nodes = n;
+  nodes = new int[nb_nodes];
 }
 
 Path::~Path() {
diff --git a/path.h b/path.h
index 11711a3..f307639 100644
--- a/path.h
+++ b/path.h
@@ -19,12 +19,15 @@
 #ifndef PATH_H
 #define PATH_H
 
+#include "misc.h"
+
 class Path {
 public:
-  Path(int l);
+  Path(int n);
   ~Path();
-  int length;
+  int nb_nodes;
   int *nodes;
+  scalar_t length;
 };
 
 #endif
diff --git a/tracker.cc b/tracker.cc
index f5dffd8..5a0647b 100644
--- a/tracker.cc
+++ b/tracker.cc
@@ -186,8 +186,8 @@ void Tracker::track() {
 #ifdef VERBOSE
   for(int p = 0; p < _graph->nb_paths; p++) {
     Path *path = _graph->paths[p];
-    cout << "PATH " << p << " [length " << path->length << "] " << path->nodes[0];
-    for(int n = 1; n < path->length; n++) {
+    cout << "PATH " << p << " [length " << path->nb_nodes << "] " << path->nodes[0];
+    for(int n = 1; n < path->nb_nodes; n++) {
       cout << " -> " << path->nodes[n];
     }
     cout << endl;
@@ -199,12 +199,16 @@ int Tracker::nb_trajectories() {
   return _graph->nb_paths;
 }
 
+scalar_t Tracker::trajectory_score(int k) {
+  return -_graph->paths[k]->length;
+}
+
 int Tracker::trajectory_entrance_time(int k) {
   return (_graph->paths[k]->nodes[1] - 1) / (2 * _nb_locations);
 }
 
 int Tracker::trajectory_duration(int k) {
-  return (_graph->paths[k]->length - 2) / 2;
+  return (_graph->paths[k]->nb_nodes - 2) / 2;
 }
 
 int Tracker::trajectory_location(int k, int time) {
diff --git a/tracker.h b/tracker.h
index de6ac42..aa1518e 100644
--- a/tracker.h
+++ b/tracker.h
@@ -54,6 +54,7 @@ public:
   // Read-out of the optimal trajectories
 
   int nb_trajectories();
+  scalar_t trajectory_score(int k);
   int trajectory_entrance_time(int k);
   int trajectory_duration(int k);
   int trajectory_location(int k, int time);
-- 
2.39.5