From 14e3b33cbe1e0d7deb0b4aa697f6c8b5d43e2963 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 19 Dec 2012 18:58:25 +0100 Subject: [PATCH] Cosmetics. --- mtp_graph.cc | 69 ++++++++++++++++++++++------------------------------ mtp_graph.h | 7 +++--- 2 files changed, 32 insertions(+), 44 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index 9bce055..aa294b4 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -46,11 +46,7 @@ public: Edge *leaving_edges; scalar_t distance_from_source; Edge *pred_edge_toward_source; - - int last_change; // Used to mark which edges have already been - // processed in some methods - - Vertex **heap_position; + Vertex **heap_slot; Vertex(); @@ -98,7 +94,12 @@ void Vertex::del_leaving_edge(Edge *e) { ////////////////////////////////////////////////////////////////////// static int compare_vertex(const void *v1, const void *v2) { - return (*((Vertex **) v1))->last_change - (*((Vertex **) v2))->last_change; + scalar_t delta = + (*((Vertex **) v1))->distance_from_source - + (*((Vertex **) v2))->distance_from_source; + if(delta < 0) return -1; + else if(delta > 0) return 1; + else return 0; } MTPGraph::MTPGraph(int nb_vertices, int nb_edges, @@ -124,16 +125,16 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges, for(int v = 0; v < _nb_vertices; v++) { _heap[v] = &_vertices[v]; - _vertices[v].heap_position = &_heap[v]; + _vertices[v].heap_slot = &_heap[v]; } paths = 0; nb_paths = 0; - if(check_DAG_and_set_last_change()) { - // Here the last_change field of every vertex tells us how many - // iterations of DP we need to reach it. Hence we only have to - // process the vertex in that order. + if(compute_dp_distances()) { + // Here the distance_from_source field of every vertex is the + // number of DP iterations needed to update it. Hence we only have + // to process the vertex in that order. for(int v = 0; v < _nb_vertices; v++) { _dp_order[v] = &_vertices[v]; } qsort(_dp_order, _nb_vertices, sizeof(Vertex *), compare_vertex); } else { @@ -211,17 +212,8 @@ void MTPGraph::force_positivized_lengths() { if(e->positivized_length < 0) { #ifdef VERBOSE - if((e->origin_vertex->last_change < 0 && e->terminal_vertex->last_change >= 0) || - (e->origin_vertex->last_change >= 0 && e->terminal_vertex->last_change < 0)) { - cout << "Inconsistent non-connexity (this should never happen)." << endl; - abort(); - } - if(e->origin_vertex->last_change >= 0 && - e->terminal_vertex->last_change >= 0 && - e->positivized_length < 0) { - residual_error -= e->positivized_length; - max_error = max(max_error, - e->positivized_length); - } + residual_error -= e->positivized_length; + max_error = max(max_error, - e->positivized_length); #endif e->positivized_length = 0.0; } @@ -231,7 +223,7 @@ void MTPGraph::force_positivized_lengths() { #endif } -int MTPGraph::check_DAG_and_set_last_change() { +int MTPGraph::compute_dp_distances() { Vertex *v; Edge *e; @@ -239,7 +231,7 @@ int MTPGraph::check_DAG_and_set_last_change() { // We put everybody in the active for(int k = 0; k < _nb_vertices; k++) { - _vertices[k].last_change = 0; + _vertices[k].distance_from_source = 0; active[k] = &_vertices[k]; } @@ -247,12 +239,12 @@ int MTPGraph::check_DAG_and_set_last_change() { int nb_active = _nb_vertices, pred_nb_active; do { - // We set the last_change field of all the vertices with incoming + // We set the distance_from_source field of all the vertices with incoming // edges to the current iteration value for(int f = 0; f < nb_active; f++) { v = active[f]; for(e = v->leaving_edges; e; e = e->next_leaving_edge) { - e->terminal_vertex->last_change = iteration; + e->terminal_vertex->distance_from_source = iteration; } } @@ -262,7 +254,7 @@ int MTPGraph::check_DAG_and_set_last_change() { // We keep all the vertices with incoming nodes for(int f = 0; f < pred_nb_active; f++) { v = active[f]; - if(v->last_change == iteration) { + if(v->distance_from_source == iteration) { active[nb_active++] = v; } } @@ -278,12 +270,12 @@ int MTPGraph::check_DAG_and_set_last_change() { void MTPGraph::decrease_distance_in_heap(Vertex *v) { Vertex **p, **h; // There is some beauty in that - h = v->heap_position; + h = v->heap_slot; while(h > _heap && (p = _heap + (h - _heap + 1) / 2 - 1, (*p)->distance_from_source > (*h)->distance_from_source)) { swap(*p, *h); - swap((*p)->heap_position, (*h)->heap_position); + swap((*p)->heap_slot, (*h)->heap_slot); h = p; } } @@ -291,23 +283,20 @@ void MTPGraph::decrease_distance_in_heap(Vertex *v) { void MTPGraph::increase_distance_in_heap(Vertex *v) { Vertex **c1, **c2, **h; // There is some beauty in that - h = v->heap_position; + h = v->heap_slot; while(c1 = _heap + 2 * (h - _heap + 1) - 1, c2 = c1 + 1, - (c1 < _heap + _heap_size && - (*c1)->distance_from_source < (*h)->distance_from_source) + (c1 < _heap + _heap_size && (*c1)->distance_from_source < (*h)->distance_from_source) || - (c2 < _heap + _heap_size && - (*c2)->distance_from_source < (*h)->distance_from_source) + (c2 < _heap + _heap_size && (*c2)->distance_from_source < (*h)->distance_from_source) ) { if(c1 < _heap + _heap_size && - !(c2 < _heap + _heap_size && - (*c2)->distance_from_source < (*c1)->distance_from_source)){ + !(c2 < _heap + _heap_size && (*c2)->distance_from_source < (*c1)->distance_from_source)){ swap(*c1, *h); - swap((*c1)->heap_position, (*h)->heap_position); + swap((*c1)->heap_slot, (*h)->heap_slot); h = c1; } else { swap(*c2, *h); - swap((*c2)->heap_position, (*h)->heap_position); + swap((*c2)->heap_slot, (*h)->heap_slot); h = c2; } } @@ -366,7 +355,7 @@ void MTPGraph::find_shortest_path() { _heap_size--; a = _heap; b = _heap + _heap_size; - swap(*a, *b); swap((*a)->heap_position, (*b)->heap_position); + swap(*a, *b); swap((*a)->heap_slot, (*b)->heap_slot); increase_distance_in_heap(_heap[0]); // Now update the neighbors of the currently closest to the source @@ -374,7 +363,7 @@ void MTPGraph::find_shortest_path() { d = v->distance_from_source + e->positivized_length; tv = e->terminal_vertex; if(d < tv->distance_from_source) { - ASSERT(tv->heap_position - _heap < _heap_size); + ASSERT(tv->heap_slot - _heap < _heap_size); tv->distance_from_source = d; tv->pred_edge_toward_source = e; decrease_distance_in_heap(tv); diff --git a/mtp_graph.h b/mtp_graph.h index bad0df5..c910520 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -66,10 +66,9 @@ class MTPGraph { // nodes met along the path, and computes path->length properly. int retrieve_one_path(Edge *e, Path *path); - // Returns if the graph is a DAG, and set the last_change field of - // each vertex to the maximum number of iterations required to reach - // it - int check_DAG_and_set_last_change(); + // Set the distance_from_source fields to the number of DP + // iterations needed to update it. Abort if the graph is not a DAG. + int compute_dp_distances(); int _nb_vertices, _nb_edges; Vertex *_source, *_sink; -- 2.39.5