From 86c860c0f43a9130e4121072620961fc892ed83f Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 19 Dec 2012 21:25:34 +0100 Subject: [PATCH] Moved the heap-related methods in the Vertex class, made them inline. --- mtp_graph.cc | 83 ++++++++++++++++++++++++++-------------------------- mtp_graph.h | 3 -- 2 files changed, 42 insertions(+), 44 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index 660e659..33d5a4f 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -52,6 +52,8 @@ public: inline void add_leaving_edge(Edge *e); inline void del_leaving_edge(Edge *e); + inline void decrease_distance_in_heap(Vertex **heap); + inline void increase_distance_in_heap(Vertex **heap, int heap_size); }; ////////////////////////////////////////////////////////////////////// @@ -91,6 +93,41 @@ void Vertex::del_leaving_edge(Edge *e) { } } +void Vertex::decrease_distance_in_heap(Vertex **heap) { + Vertex **p, **h; + // There is some beauty in that + h = 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_slot, (*h)->heap_slot); + h = p; + } +} + +void Vertex::increase_distance_in_heap(Vertex **heap, int heap_size) { + Vertex **c1, **c2, **h; + // omg, that's beautiful + h = 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) + || + (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)){ + swap(*c1, *h); + swap((*c1)->heap_slot, (*h)->heap_slot); + h = c1; + } else { + swap(*c2, *h); + swap((*c2)->heap_slot, (*h)->heap_slot); + h = c2; + } + } +} + ////////////////////////////////////////////////////////////////////// static int compare_vertex(const void *v1, const void *v2) { @@ -275,41 +312,6 @@ int MTPGraph::compute_dp_distances() { return nb_active == 0; } -void MTPGraph::decrease_distance_in_heap(Vertex *v) { - Vertex **p, **h; - // There is some beauty in that - 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_slot, (*h)->heap_slot); - h = p; - } -} - -void MTPGraph::increase_distance_in_heap(Vertex *v) { - Vertex **c1, **c2, **h; - // omg, that's beautiful - 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) - || - (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)){ - swap(*c1, *h); - swap((*c1)->heap_slot, (*h)->heap_slot); - h = c1; - } else { - swap(*c2, *h); - swap((*c2)->heap_slot, (*h)->heap_slot); - h = c2; - } - } -} - void MTPGraph::dp_compute_distances() { Vertex *v, *tv; Edge *e; @@ -330,7 +332,7 @@ void MTPGraph::dp_compute_distances() { if(d < tv->distance_from_source) { tv->distance_from_source = d; tv->pred_edge_toward_source = e; - decrease_distance_in_heap(tv); + tv->decrease_distance_in_heap(_heap); } } } @@ -352,7 +354,7 @@ void MTPGraph::find_shortest_path() { _heap_size = _nb_vertices; _source->distance_from_source = 0; - decrease_distance_in_heap(_source); + _source->decrease_distance_in_heap(_heap); do { // Get the closest to the source @@ -364,7 +366,7 @@ void MTPGraph::find_shortest_path() { a = _heap; b = _heap + _heap_size; swap(*a, *b); swap((*a)->heap_slot, (*b)->heap_slot); - increase_distance_in_heap(_heap[0]); + _heap[0]->increase_distance_in_heap(_heap, _heap_size); // Now update the neighbors of the currently closest to the source for(e = v->leaving_edges; e; e = e->next_leaving_edge) { @@ -374,7 +376,7 @@ void MTPGraph::find_shortest_path() { ASSERT(tv->heap_slot - _heap < _heap_size); tv->distance_from_source = d; tv->pred_edge_toward_source = e; - decrease_distance_in_heap(tv); + tv->decrease_distance_in_heap(_heap); } } } while(_heap_size > 0); @@ -391,8 +393,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) { _edges[e].positivized_length = _edges[e].length; } - // Update the distance to the source in "good order" - + // Update the distances to the source in "good order" dp_compute_distances(); do { diff --git a/mtp_graph.h b/mtp_graph.h index 84c9ce6..ff15830 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -49,9 +49,6 @@ class MTPGraph { // the total correction when compiled in VERBOSE mode. void force_positivized_lengths(); - void decrease_distance_in_heap(Vertex *v); - void increase_distance_in_heap(Vertex *v); - // Visit the vertices according to _dp_order and simply update their // distance to the source void dp_compute_distances(); -- 2.39.5