From 8df7c7e77366cb95e9e8e963af9319d9cbac1934 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 22 Aug 2012 11:19:44 -0700 Subject: [PATCH] Cosmetics. --- mtp_graph.cc | 84 ++++++++++++++++++++++++++-------------------------- mtp_graph.h | 11 ++++--- 2 files changed, 49 insertions(+), 46 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index 5100c1d..ee6da31 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -28,6 +28,8 @@ public: int id, occupied; scalar_t length, work_length; Vertex *origin_vertex, *terminal_vertex; + + // These are the links in the origin_vertex leaving edge list Edge *next, *pred; inline void revert(); @@ -38,7 +40,7 @@ public: int id, iteration; Edge *root_edge; scalar_t distance_from_source; - Edge *pred_edge; + Edge *best_pred_edge_to_source; Vertex(); inline void add_edge(Edge *e); @@ -80,7 +82,7 @@ void Vertex::del_edge(Edge *e) { void MTPGraph::print() { for(int k = 0; k < _nb_edges; k++) { - Edge *e = edges + k; + Edge *e = _edges + k; cout << e->origin_vertex->id << " -> " << e->terminal_vertex->id @@ -97,7 +99,7 @@ void MTPGraph::print_dot() { cout << "digraph {" << endl; cout << " node[shape=circle];" << endl; for(int k = 0; k < _nb_edges; k++) { - Edge *e = 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; @@ -111,48 +113,48 @@ void MTPGraph::print_dot() { MTPGraph::MTPGraph(int nb_vertices, int nb_edges, int *from, int *to, - int src, int snk) { + int source, int sink) { _nb_vertices = nb_vertices; _nb_edges = nb_edges; - edges = new Edge[_nb_edges]; - vertices = new Vertex[_nb_vertices]; + _edges = new Edge[_nb_edges]; + _vertices = new Vertex[_nb_vertices]; _front = new Vertex *[_nb_vertices]; _new_front = new Vertex *[_nb_vertices]; - _source = &vertices[src]; - _sink = &vertices[snk]; + _source = &_vertices[source]; + _sink = &_vertices[sink]; for(int v = 0; v < _nb_vertices; v++) { - vertices[v].id = v; + _vertices[v].id = v; } for(int e = 0; e < nb_edges; e++) { - vertices[from[e]].add_edge(&edges[e]); - edges[e].occupied = 0; - edges[e].id = e; - edges[e].origin_vertex = &vertices[from[e]]; - edges[e].terminal_vertex = &vertices[to[e]]; + _vertices[from[e]].add_edge(_edges + e); + _edges[e].occupied = 0; + _edges[e].id = e; + _edges[e].origin_vertex = _vertices + from[e]; + _edges[e].terminal_vertex = _vertices + to[e]; } } MTPGraph::~MTPGraph() { - delete[] vertices; - delete[] edges; + delete[] _vertices; + delete[] _edges; delete[] _front; delete[] _new_front; } -void MTPGraph::initialize_work_lengths() { +void MTPGraph::initialize_work_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].root_edge; e; e = e->next) { 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) { + for(Edge *e = _vertices[n].root_edge; e; e = e->next) { e->work_length = e->length - length_min; } } @@ -160,7 +162,7 @@ void MTPGraph::initialize_work_lengths() { void MTPGraph::update_work_lengths() { for(int k = 0; k < _nb_edges; k++) { - Edge *e = edges + k; + Edge *e = _edges + k; e->work_length += e->terminal_vertex->distance_from_source - e->terminal_vertex->distance_from_source; } } @@ -170,7 +172,7 @@ void MTPGraph::force_positive_work_lengths() { 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) { + for(Edge *e = _vertices[n].root_edge; e; e = e->next) { if(e->work_length < 0) { #ifdef VERBOSE residual_error -= e->work_length; @@ -184,6 +186,8 @@ void MTPGraph::force_positive_work_lengths() { #endif } +// This method does not change the edge occupation. It update +// distance_from_source and best_pred_edge_to_source. void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { Vertex **tmp_front; int tmp_front_size; @@ -191,9 +195,9 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { scalar_t d; for(int v = 0; v < _nb_vertices; v++) { - vertices[v].distance_from_source = FLT_MAX; - vertices[v].pred_edge = 0; - vertices[v].iteration = 0; + _vertices[v].distance_from_source = FLT_MAX; + _vertices[v].best_pred_edge_to_source = 0; + _vertices[v].iteration = 0; } int iteration = 0; @@ -212,7 +216,7 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { tv = e->terminal_vertex; if(d < tv->distance_from_source) { tv->distance_from_source = d; - tv->pred_edge = e; + tv->best_pred_edge_to_source = e; if(tv->iteration < iteration) { _new_front[_new_front_size++] = tv; tv->iteration = iteration; @@ -237,15 +241,17 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { Edge *e; for(int e = 0; e < _nb_edges; e++) { - edges[e].length = lengths[e]; - edges[e].work_length = edges[e].length; + _edges[e].length = lengths[e]; + _edges[e].work_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(); // #warning - // initialize_work_lengths(); + // initialize_work_lengths_with_min(); do { force_positive_work_lengths(); @@ -255,12 +261,12 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { total_length = 0.0; // Do we reach the _sink? - if(_sink->pred_edge) { + if(_sink->best_pred_edge_to_source) { // If yes, compute the length of the best path v = _sink; - while(v->pred_edge) { - total_length += v->pred_edge->length; - v = v->pred_edge->origin_vertex; + while(v->best_pred_edge_to_source) { + total_length += v->best_pred_edge_to_source->length; + v = v->best_pred_edge_to_source->origin_vertex; } // If that length is negative if(total_length < 0.0) { @@ -269,8 +275,8 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { #endif // Invert all the edges along the best path v = _sink; - while(v->pred_edge) { - e = v->pred_edge; + while(v->best_pred_edge_to_source) { + e = v->best_pred_edge_to_source; v = e->origin_vertex; e->revert(); e->occupied = 1 - e->occupied; @@ -281,14 +287,8 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { } while(total_length < 0.0); for(int k = 0; k < _nb_edges; k++) { - Edge *e = edges + k; + Edge *e = _edges + k; if(e->occupied) { e->revert(); } - } - - for(int n = 0; n < _nb_vertices; n++) { - Vertex *v = &vertices[n]; - for(Edge *e = v->root_edge; e; e = e->next) { - result_edge_occupation[e->id] = e->occupied; - } + result_edge_occupation[k] = e->occupied; } } diff --git a/mtp_graph.h b/mtp_graph.h index f12262e..7b0f57d 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -25,17 +25,20 @@ class Vertex; class Edge; class MTPGraph { - void initialize_work_lengths(); + void initialize_work_lengths_with_min(); void update_work_lengths(); void force_positive_work_lengths(); void find_shortest_path(Vertex **front, Vertex **new_front); + Vertex **_front, **_new_front; + int _nb_vertices, _nb_edges; Vertex *_source, *_sink; - Vertex **_front, **_new_front; + + Edge *_edges; + Vertex *_vertices; + public: - Edge *edges; - Vertex *vertices; MTPGraph(int nb_vertices, int nb_edges, int *from, int *to, int source, int sink); -- 2.39.5