From fda29b3422f4850d77e4b8f4916251509789d3ac Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 22 Aug 2012 15:20:30 -0700 Subject: [PATCH] Properly puts the edge occupancy back to 0 when starting tracking. --- mtp.cc | 3 ++- mtp_graph.cc | 25 ++++++++++---------- mtp_graph.h | 8 +++++-- tracker.cc | 66 ++++++++++++++++++++++++++++++++++++++-------------- tracker.h | 9 +++++++ 5 files changed, 78 insertions(+), 33 deletions(-) diff --git a/mtp.cc b/mtp.cc index a3f4aa3..e096836 100644 --- a/mtp.cc +++ b/mtp.cc @@ -44,6 +44,8 @@ int main(int argc, char **argv) { } } + tracker->build_graph(); + for(int r = 0; r < 10; r++) { cout << "* ROUND " << r << endl; for(int t = 0; t < nb_time_steps; t++) { @@ -55,7 +57,6 @@ int main(int argc, char **argv) { (drand48() < 0.95 ? 1.0 : -1.0) + drand48() * 0.1 - 0.05); } - tracker->build_graph(); tracker->track(); for(int t = 0; t < tracker->nb_trajectories(); t++) { diff --git a/mtp_graph.cc b/mtp_graph.cc index 32bdfdf..c213a07 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -135,35 +135,35 @@ MTPGraph::~MTPGraph() { ////////////////////////////////////////////////////////////////////// -void MTPGraph::print() { +void MTPGraph::print(ostream *os) { for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; - cout << e->origin_vertex->id + (*os) << e->origin_vertex->id << " -> " << e->terminal_vertex->id << " " << e->length; if(e->occupied) { - cout << " *"; + (*os) << " *"; } - cout << endl; + (*os) << endl; } } -void MTPGraph::print_dot() { - cout << "digraph {" << endl; - cout << " node[shape=circle];" << endl; +void MTPGraph::print_dot(ostream *os) { + (*os) << "digraph {" << endl; + (*os) << " node[shape=circle];" << endl; for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; if(e->occupied) { - cout << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id - << " [style=bold,color=black,label=\"" << -e->length << "\"];" << endl; + (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id + << " [style=bold,color=black,label=\"" << e->length << "\"];" << endl; } else { - cout << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id + (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id << " [color=gray,label=\"" << e->length << "\"];" << endl; } } - cout << "}" << endl; + (*os) << "}" << endl; } ////////////////////////////////////////////////////////////////////// @@ -265,6 +265,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) { for(int e = 0; e < _nb_edges; e++) { _edges[e].length = lengths[e]; + _edges[e].occupied = 0; _edges[e].positivized_length = _edges[e].length; } @@ -294,7 +295,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) { // If that length is negative if(total_length < 0.0) { #ifdef VERBOSE - cout << "Found a path of length " << total_length << endl; + cerr << "Found a path of length " << total_length << endl; #endif // Invert all the edges along the best path v = _sink; diff --git a/mtp_graph.h b/mtp_graph.h index 5feb20f..ddf7162 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -19,6 +19,10 @@ #ifndef MTP_GRAPH_H #define MTP_GRAPH_H +#include + +using namespace std; + #include "misc.h" class Vertex; @@ -60,8 +64,8 @@ public: void find_best_paths(scalar_t *lengths); void retrieve_disjoint_paths(); - void print(); - void print_dot(); + void print(ostream *os); + void print_dot(ostream *os); }; #endif diff --git a/tracker.cc b/tracker.cc index b67ddfb..3a311cd 100644 --- a/tracker.cc +++ b/tracker.cc @@ -25,9 +25,14 @@ using namespace std; Tracker::Tracker(int nb_time_steps, int nb_locations) { _nb_locations = nb_locations; _nb_time_steps = nb_time_steps; - _detection_score = allocate_array(nb_time_steps, nb_locations); - _allowed_motion = allocate_array(nb_locations, nb_locations); + _detection_score = allocate_array(_nb_time_steps, _nb_locations); + _allowed_motion = allocate_array(_nb_locations, _nb_locations); + _entrances = new int[_nb_locations]; + _exits = new int[_nb_locations]; + for(int l = 0; l < nb_locations; l++) { + _entrances[l] = 0; + _exits[l] = 0; for(int m = 0; m < nb_locations; m++) { _allowed_motion[l][m] = 0; } @@ -42,12 +47,22 @@ Tracker::~Tracker() { delete _graph; deallocate_array(_detection_score); deallocate_array(_allowed_motion); + delete[] _exits; + delete[] _entrances; } void Tracker::set_allowed_motion(int from_location, int to_location, int v) { _allowed_motion[from_location][to_location] = v; } +void Tracker::set_as_entrance(int location, int v) { + _entrances[location] = v; +} + +void Tracker::set_as_exit(int location, int v) { + _exits[location] = v; +} + void Tracker::set_detection_score(int time, int location, scalar_t score) { _detection_score[time][location] = score; } @@ -58,17 +73,22 @@ void Tracker::build_graph() { delete[] _edge_lengths; delete _graph; - int nb_motions = 0; + int nb_motions = 0, nb_exits = 0, nb_entrances = 0; for(int l = 0; l < _nb_locations; l++) { + if(_exits[l]) nb_exits++; + if(_entrances[l]) nb_entrances++; for(int m = 0; m < _nb_locations; m++) { if(_allowed_motion[l][m]) nb_motions++; } } int nb_vertices = 2 + 2 * _nb_time_steps * _nb_locations; - int nb_edges = _nb_locations * 2 - + (_nb_time_steps - 1) * nb_motions - + _nb_locations * _nb_time_steps; + + int nb_edges = + _nb_locations * 2 + + _nb_time_steps * (nb_exits + nb_entrances) + + (_nb_time_steps - 1) * nb_motions + + _nb_locations * _nb_time_steps; int source = 0, sink = nb_vertices - 1; int *node_from = new int[nb_edges]; @@ -117,6 +137,23 @@ void Tracker::build_graph() { } } + for(int t = 0; t < _nb_time_steps; t++) { + for(int l = 0; l < _nb_locations; l++) { + if(_entrances[l]) { + node_from[e] = source; + node_to[e] = 1 + (2 * (t + 0) + 0) * _nb_locations + l; + _edge_lengths[e] = 0.0; + e++; + } + if(_exits[l]) { + node_from[e] = 1 + (2 * (t + 0) + 1) * _nb_locations + l; + node_from[e] = sink; + _edge_lengths[e] = 0.0; + e++; + } + } + } + _graph = new MTPGraph(nb_vertices, nb_edges, node_from, node_to, source, sink); @@ -125,27 +162,20 @@ void Tracker::build_graph() { delete[] node_to; } +void Tracker::print_dot_graph(ostream *os) { + _graph->print_dot(os); +} + void Tracker::track() { int e = 0; for(int t = 0; t < _nb_time_steps; t++) { for(int l = 0; l < _nb_locations; l++) { - _edge_lengths[e] = - _detection_score[t][l]; - e++; + _edge_lengths[e++] = - _detection_score[t][l]; } } _graph->find_best_paths(_edge_lengths); _graph->retrieve_disjoint_paths(); - - // 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->nodes[n]; - // } - // cout << endl; - // } - // _graph->print_dot(); } int Tracker::nb_trajectories() { diff --git a/tracker.h b/tracker.h index 1811fb9..2ca731a 100644 --- a/tracker.h +++ b/tracker.h @@ -19,6 +19,10 @@ #ifndef TRACKER_H #define TRACKER_H +#include + +using namespace std; + #include "misc.h" #include "mtp_graph.h" @@ -26,6 +30,7 @@ class Tracker { int _nb_locations, _nb_time_steps; scalar_t **_detection_score; int **_allowed_motion; + int *_entrances, *_exits; MTPGraph *_graph; int *_edge_occupation; @@ -35,7 +40,11 @@ public: ~Tracker(); void set_allowed_motion(int from_location, int to_location, int v); + void set_as_entrance(int location, int v); + void set_as_exit(int location, int v); + void build_graph(); + void print_dot_graph(ostream *os); void set_detection_score(int time, int location, scalar_t score); -- 2.39.5