X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?a=blobdiff_plain;f=mtp_graph.cc;h=473d13ecb5a99bf6ec713fc9aca3500591ed3bbd;hb=513b8c10f328e5868082f09063c7e51669c952c7;hp=49b97f7595c2d78fb37fe9ad93c751856c1f01e8;hpb=cdf649aeef318cc5c3dae231d9b1c16352d13515;p=mtp.git

diff --git a/mtp_graph.cc b/mtp_graph.cc
index 49b97f7..473d13e 100644
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -1,7 +1,7 @@
 
 /*
- *  mtp is the ``Multi Tracked Path'', an implementation of the
- *  k-shortest path algorithm for multi-target tracking.
+ *  mtp is the ``Multi Tracked Paths'', an implementation of the
+ *  k-shortest paths algorithm for multi-target tracking.
  *
  *  Copyright (c) 2012 Idiap Research Institute, http://www.idiap.ch/
  *  Written by Francois Fleuret <francois.fleuret@idiap.ch>
@@ -109,8 +109,8 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges,
   _source = &_vertices[source];
   _sink = &_vertices[sink];
 
-  for(int v = 0; v < _nb_vertices; v++) {
-    _vertices[v].id = v;
+  for(int k = 0; k < _nb_vertices; k++) {
+    _vertices[k].id = k;
   }
 
   for(int e = 0; e < nb_edges; e++) {
@@ -157,8 +157,6 @@ void MTPGraph::print_dot(ostream *os) {
   (*os) << "        edge [color=gray,arrowhead=open]" << endl;
   (*os) << "        " << _source->id << " [peripheries=2];" << endl;
   (*os) << "        " << _sink->id << " [peripheries=2];" << endl;
-  // (*os) << "        " << _source->id << " [style=bold,color=red];" << endl;
-  // (*os) << "        " << _sink->id << " [style=bold,color=green];" << endl;
   for(int k = 0; k < _nb_edges; k++) {
     Edge *e = _edges + k;
     // (*os) << "  " << e->origin_vertex->id << " -> " << e->terminal_vertex->id
@@ -205,8 +203,54 @@ void MTPGraph::force_positivized_lengths() {
 #endif
 }
 
-// This method does not change the edge occupation. It update
-// distance_from_source and pred_edge_toward_source.
+int MTPGraph::is_dag() {
+  Vertex *v, *tv;
+  Edge *e;
+
+  // We put everybody in the front
+  for(int k = 0; k < _nb_vertices; k++) {
+    _vertices[k].iteration = 0;
+    _front[k] = &_vertices[k];
+  }
+
+  int front_size = _nb_vertices, nb_with_incoming;
+  int iteration = 0;
+  int new_front_size, pred_front_size;
+
+  do {
+    iteration++;
+    nb_with_incoming = 0;
+
+    // We set the iteration field of all vertex with incoming edges to
+    // the current iteration value
+    for(int f = 0; f < front_size; f++) {
+      v = _front[f];
+      for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
+        tv = e->terminal_vertex;
+        tv->iteration = iteration;
+      }
+    }
+
+    new_front_size = 0;
+    // We remove all the vertices without incoming edge
+    for(int f = 0; f < front_size; f++) {
+      v = _front[f];
+      if(v->iteration == iteration) {
+        _front[new_front_size++] = v;
+      }
+    }
+
+    pred_front_size = front_size;
+    front_size = new_front_size;
+  } while(front_size < pred_front_size);
+
+  return front_size == 0;
+}
+
+// This method does not change the edge occupation. It only set
+// properly for every vertex the fields distance_from_source and
+// pred_edge_toward_source.
+
 void MTPGraph::find_shortest_path() {
   Vertex **tmp_front;
   int tmp_front_size;
@@ -214,23 +258,23 @@ void MTPGraph::find_shortest_path() {
   Edge *e;
   scalar_t d;
 
-  for(int v = 0; v < _nb_vertices; v++) {
-    _vertices[v].distance_from_source = FLT_MAX;
-    _vertices[v].pred_edge_toward_source = 0;
-    _vertices[v].iteration = 0;
+  for(int k = 0; k < _nb_vertices; k++) {
+    _vertices[k].distance_from_source = FLT_MAX;
+    _vertices[k].pred_edge_toward_source = 0;
+    _vertices[k].iteration = 0;
   }
 
   int iteration = 0;
 
-  int _front_size = 0, _new_front_size;
-  _front[_front_size++] = _source;
+  int front_size = 0, new_front_size;
+  _front[front_size++] = _source;
   _source->distance_from_source = 0;
 
   do {
-    _new_front_size = 0;
+    new_front_size = 0;
     iteration++;
 
-    for(int f = 0; f < _front_size; f++) {
+    for(int f = 0; f < front_size; f++) {
       v = _front[f];
       for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
         d = v->distance_from_source + e->positivized_length;
@@ -239,7 +283,7 @@ void MTPGraph::find_shortest_path() {
           tv->distance_from_source = d;
           tv->pred_edge_toward_source = e;
           if(tv->iteration < iteration) {
-            _new_front[_new_front_size++] = tv;
+            _new_front[new_front_size++] = tv;
             tv->iteration = iteration;
           }
         }
@@ -250,10 +294,10 @@ void MTPGraph::find_shortest_path() {
     _new_front = _front;
     _front = tmp_front;
 
-    tmp_front_size = _new_front_size;
-    _new_front_size = _front_size;
-    _front_size = tmp_front_size;
-  } while(_front_size > 0);
+    tmp_front_size = new_front_size;
+    new_front_size = front_size;
+    front_size = tmp_front_size;
+  } while(front_size > 0);
 }
 
 void MTPGraph::find_best_paths(scalar_t *lengths) {
@@ -267,8 +311,12 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
     _edges[e].positivized_length = _edges[e].length;
   }
 
-  // We use one iteration of find_shortest_path simply to propagate
-  // the distance to make all the edge lengths positive.
+  // Let's be a bit paranoid
+  ASSERT(is_dag());
+
+  // We use call find_shortest_path here to set properly the distance,
+  // so that we can make all the edge lengths positive at the first
+  // iteration.
   find_shortest_path();
 
   do {
@@ -278,7 +326,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) {
 
     total_length = 0.0;
 
-    // Do we reach the _sink?
+    // Do we reach the sink?
     if(_sink->pred_edge_toward_source) {
       // If yes, compute the length of the best path
       v = _sink;