From 79a4a9ab164a667ecb551078e1cd773e2140e3c2 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 22 Aug 2012 11:30:48 -0700 Subject: [PATCH] Cosmetics. --- mtp.cc | 52 ++++++++++++++++++++-------------------- mtp_graph.cc | 67 ++++++++++++++++++++++++++++------------------------ mtp_graph.h | 6 ++--- tracker.cc | 3 ++- 4 files changed, 67 insertions(+), 61 deletions(-) diff --git a/mtp.cc b/mtp.cc index 13cfad7..286597d 100644 --- a/mtp.cc +++ b/mtp.cc @@ -48,32 +48,32 @@ void find_best_paths(int nb_vertices, ////////////////////////////////////////////////////////////////////// int main(int argc, char **argv) { - // int nb_locations = 6; - // int nb_time_steps = 5; - - // { - // Tracker tracker(nb_time_steps, nb_locations); - - // for(int l = 0; l < nb_locations; l++) { - // for(int k = 0; k < nb_locations; k++) { - // tracker.set_allowed_motion(l, k, abs(l - k) <= 1); - // } - // } - - // for(int t = 0; t < nb_time_steps; t++) { - // for(int l = 0; l < nb_locations; l++) { - // tracker.set_detection_score(t, l, - // (drand48() < 0.9 ? -1.0 : 1.0) + drand48() * 0.1 - 0.05); - // } - // tracker.set_detection_score(t, 0, - // (drand48() < 0.9 ? 1.0 : -1.0) + drand48() * 0.1 - 0.05); - // } - - // tracker.build_graph(); - // tracker.track(); - // } - - // exit(0); + int nb_locations = 6; + int nb_time_steps = 5; + + { + Tracker tracker(nb_time_steps, nb_locations); + + for(int l = 0; l < nb_locations; l++) { + for(int k = 0; k < nb_locations; k++) { + tracker.set_allowed_motion(l, k, abs(l - k) <= 1); + } + } + + for(int t = 0; t < nb_time_steps; t++) { + for(int l = 0; l < nb_locations; l++) { + tracker.set_detection_score(t, l, + (drand48() < 0.9 ? -1.0 : 1.0) + drand48() * 0.1 - 0.05); + } + tracker.set_detection_score(t, 0, + (drand48() < 0.9 ? 1.0 : -1.0) + drand48() * 0.1 - 0.05); + } + + tracker.build_graph(); + tracker.track(); + } + + exit(0); if(argc < 2) { cerr << argv[0] << " " << endl; diff --git a/mtp_graph.cc b/mtp_graph.cc index ee6da31..95dc451 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -26,22 +26,24 @@ using namespace std; class Edge { public: int id, occupied; - scalar_t length, work_length; + scalar_t length, positivized_length; Vertex *origin_vertex, *terminal_vertex; // These are the links in the origin_vertex leaving edge list - Edge *next, *pred; + Edge *next_leaving_edge, *pred_leaving_edge; inline void revert(); }; class Vertex { public: - int id, iteration; - Edge *root_edge; + int id; + Edge *leaving_edges; scalar_t distance_from_source; Edge *best_pred_edge_to_source; + 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); @@ -51,7 +53,7 @@ public: void Edge::revert() { length = - length; - work_length = 0; + positivized_length = 0; origin_vertex->del_edge(this); terminal_vertex->add_edge(this); Vertex *t = terminal_vertex; @@ -62,20 +64,20 @@ void Edge::revert() { ////////////////////////////////////////////////////////////////////// Vertex::Vertex() { - root_edge = 0; + leaving_edges = 0; } void Vertex::add_edge(Edge *e) { - e->next = root_edge; - e->pred = 0; - if(root_edge) { root_edge->pred = e; } - root_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 == root_edge) { root_edge = e->next; } - if(e->pred) { e->pred->next = e->next; } - if(e->next) { e->next->pred = e->pred; } + 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; } } ////////////////////////////////////////////////////////////////////// @@ -146,38 +148,38 @@ MTPGraph::~MTPGraph() { delete[] _new_front; } -void MTPGraph::initialize_work_lengths_with_min() { +void MTPGraph::initialize_positivized_lengths_with_min() { scalar_t length_min = 0; for(int n = 0; n < _nb_vertices; n++) { - for(Edge *e = _vertices[n].root_edge; e; e = e->next) { + for(Edge *e = _vertices[n].leaving_edges; e; e = e->next_leaving_edge) { length_min = min(e->length, length_min); } } for(int n = 0; n < _nb_vertices; n++) { - for(Edge *e = _vertices[n].root_edge; e; e = e->next) { - e->work_length = e->length - length_min; + for(Edge *e = _vertices[n].leaving_edges; e; e = e->next_leaving_edge) { + e->positivized_length = e->length - length_min; } } } -void MTPGraph::update_work_lengths() { +void MTPGraph::update_positivized_lengths() { for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; - e->work_length += e->terminal_vertex->distance_from_source - e->terminal_vertex->distance_from_source; + e->positivized_length += e->terminal_vertex->distance_from_source - e->terminal_vertex->distance_from_source; } } -void MTPGraph::force_positive_work_lengths() { +void MTPGraph::force_positivized_lengths() { #ifdef VERBOSE scalar_t residual_error = 0.0; #endif for(int n = 0; n < _nb_vertices; n++) { - for(Edge *e = _vertices[n].root_edge; e; e = e->next) { - if(e->work_length < 0) { + for(Edge *e = _vertices[n].leaving_edges; e; e = e->next_leaving_edge) { + if(e->positivized_length < 0) { #ifdef VERBOSE - residual_error -= e->work_length; + residual_error -= e->positivized_length; #endif - e->work_length = 0.0; + e->positivized_length = 0.0; } } } @@ -192,6 +194,7 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { Vertex **tmp_front; int tmp_front_size; Vertex *v, *tv; + Edge *e; scalar_t d; for(int v = 0; v < _nb_vertices; v++) { @@ -211,8 +214,8 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { iteration++; for(int f = 0; f < _front_size; f++) { v = _front[f]; - for(Edge *e = v->root_edge; e; e = e->next) { - d = v->distance_from_source + e->work_length; + for(e = v->leaving_edges; e; e = e->next_leaving_edge) { + d = v->distance_from_source + e->positivized_length; tv = e->terminal_vertex; if(d < tv->distance_from_source) { tv->distance_from_source = d; @@ -242,21 +245,21 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { for(int e = 0; e < _nb_edges; e++) { _edges[e].length = lengths[e]; - _edges[e].work_length = _edges[e].length; + _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. find_shortest_path(_front, _new_front); - update_work_lengths(); + update_positivized_lengths(); // #warning - // initialize_work_lengths_with_min(); + // initialize_positivized_lengths_with_min(); do { - force_positive_work_lengths(); + force_positivized_lengths(); find_shortest_path(_front, _new_front); - update_work_lengths(); + update_positivized_lengths(); total_length = 0.0; @@ -279,6 +282,8 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { e = v->best_pred_edge_to_source; v = e->origin_vertex; e->revert(); + // This is the only place where we change the occupations of + // edges e->occupied = 1 - e->occupied; } } diff --git a/mtp_graph.h b/mtp_graph.h index 7b0f57d..f2bedd4 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -25,9 +25,9 @@ class Vertex; class Edge; class MTPGraph { - void initialize_work_lengths_with_min(); - void update_work_lengths(); - void force_positive_work_lengths(); + void initialize_positivized_lengths_with_min(); + void update_positivized_lengths(); + void force_positivized_lengths(); void find_shortest_path(Vertex **front, Vertex **new_front); Vertex **_front, **_new_front; diff --git a/tracker.cc b/tracker.cc index 8490d6f..e6d5d0e 100644 --- a/tracker.cc +++ b/tracker.cc @@ -55,6 +55,8 @@ void Tracker::set_detection_score(int time, int location, scalar_t score) { } void Tracker::build_graph() { + + // Delete existing graph delete[] _edge_lengths; delete[] _graph; delete[] _edge_occupation; @@ -137,7 +139,6 @@ void Tracker::track() { } _graph->find_best_paths(_edge_lengths, _edge_occupation); - _graph->print_dot(); } -- 2.39.5