From 6afe91234d7807ce82b96a071087decb2f7aead3 Mon Sep 17 00:00:00 2001 From: Francois Fleuret 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 -// #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