From 7f847d18f82e92c8af842f50e0ea16fa66bf9584 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 19 Dec 2012 14:34:28 +0100 Subject: [PATCH] Update with the Dijkstra using a Binary Heap for the min-priority queue. --- README.txt | 5 ++- mtp_graph.cc | 118 ++++++--------------------------------------------- mtp_graph.h | 6 +-- 3 files changed, 18 insertions(+), 111 deletions(-) diff --git a/README.txt b/README.txt index 026f508..a20e23d 100644 --- a/README.txt +++ b/README.txt @@ -14,7 +14,8 @@ in 2011. This implementation is not the reference implementation used for the -experiments presented in this article. +experiments presented in this article. It uses a Dijkstra with a +Binary Heap for the min-queue, and not the optimal Fibonacci heap. * INSTALLATION @@ -131,4 +132,4 @@ structure -- François Fleuret -October 2012 +December 2012 diff --git a/mtp_graph.cc b/mtp_graph.cc index 12017c2..4a73a43 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -130,7 +130,7 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges, paths = 0; nb_paths = 0; - if(is_dag()) { + 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. @@ -231,7 +231,7 @@ void MTPGraph::force_positivized_lengths() { #endif } -int MTPGraph::is_dag() { +int MTPGraph::check_DAG_and_set_last_change() { Vertex *v; Edge *e; @@ -275,72 +275,20 @@ int MTPGraph::is_dag() { return nb_active == 0; } -#ifdef DEBUG -void print_heap(int first, int heap_size, Vertex **heap, int depth, Vertex *vertices) { - // if(depth == 0) cout << "** START_HEAP ********************************************************" << endl; - // if(first < heap_size) { - // print_heap((first + 1) * 2 - 1, heap_size, heap, depth + 1, vertices); - // for(int d = 0; d < depth; d++) cout << " "; - // cout << "[" << heap[first] - vertices << "] "; - // if(heap[first]->distance_from_source == FLT_MAX) cout << "inf"; - // else cout << heap[first]->distance_from_source; - // cout << endl; - // print_heap((first + 1) * 2, heap_size, heap, depth + 1, vertices); - // } - // if(depth == 0) cout << "** END_HEAP **********************************************************" << endl; -} - -void check_heap(Vertex **heap, int heap_size, Vertex *vertices, int nb_vertices) { - Vertex **p, **h; - int *used = new int[nb_vertices]; - for(int v = 0; v < nb_vertices; v++) used[v] = 0; - for(int k = 0; k < heap_size; k++) { - used[heap[k] - vertices]++; - h = heap + k; - if(h != (*h)->heap_position) abort(); - if(k > 0) { - p = heap + (h - heap + 1) / 2 - 1; - if((*h)->distance_from_source < (*p)->distance_from_source) abort(); - } - } - for(int v = 0; v < nb_vertices; v++) { - cout << used[v]; - if(used[v] > 1) abort(); - } - cout << endl; - delete[] used; -} -#endif - void MTPGraph::decrease_distance_in_heap(Vertex *v) { -#ifdef DEBUG - // cout << "START decrease_distance_in_heap" << endl; - // print_heap(0, _heap_size, _heap, 0, _vertices); -#endif Vertex **p, **h; // There is some beauty in that h = v->heap_position; while(h > _heap && (p = _heap + (h - _heap + 1) / 2 - 1, (*p)->distance_from_source > (*h)->distance_from_source)) { -// #warning REMOVE - // cout << "SWAP [" << (*p) - _vertices << " | " << (*h) - _vertices << "]" << endl; - // if((*p) - _vertices == 6 && (*h) - _vertices == 96) abort(); swap(*p, *h); swap((*p)->heap_position, (*h)->heap_position); h = p; } -#ifdef DEBUG - // check_heap(_heap, _heap_size, _vertices, _nb_vertices); - // print_heap(0, _heap_size, _heap, 0, _vertices); -#endif } void MTPGraph::increase_distance_in_heap(Vertex *v) { -#ifdef DEBUG - // cout << "START increase_distance_in_heap" << endl; - // print_heap(0, _heap_size, _heap, 0, _vertices); -#endif Vertex **c1, **c2, **h; // There is some beauty in that h = v->heap_position; @@ -363,10 +311,6 @@ void MTPGraph::increase_distance_in_heap(Vertex *v) { h = c2; } } -#ifdef DEBUG - // check_heap(_heap, _heap_size, _vertices, _nb_vertices); - // print_heap(0, _heap_size, _heap, 0, _vertices); -#endif } void MTPGraph::dp_distance_propagation() { @@ -393,34 +337,17 @@ void MTPGraph::dp_distance_propagation() { } } } - -#ifdef DEBUG - for(int k = 0; k < _nb_vertices; k++) { - if(_vertices[k].distance_from_source == FLT_MAX) abort(); - } -#endif } -// This method does not change the edge occupation. It only set +// This method does not change the edge occupation. It only sets // properly, for every vertex, the fields distance_from_source and // pred_edge_toward_source. void MTPGraph::find_shortest_path() { - Vertex *v, *tv; + Vertex *v, *tv, **a, **b; Edge *e; scalar_t d; -#ifdef DEBUG - if(is_dag()) { - cout << "find_shortest_path: DAG -> ok" << endl; - } else { - for(int e = 0; e < _nb_edges; e++) { - if(_edges[e].positivized_length < 0) abort(); - } - cout << "find_shortest_path: All positivized_length are positive -> ok" << endl; - } -#endif - for(int k = 0; k < _nb_vertices; k++) { _vertices[k].distance_from_source = FLT_MAX; _vertices[k].pred_edge_toward_source = 0; @@ -431,19 +358,18 @@ void MTPGraph::find_shortest_path() { decrease_distance_in_heap(_source); do { -#ifdef DEBUG - for(int k = 0; k < _heap_size; k++) { - if(_heap[0]->distance_from_source > _heap[k]->distance_from_source) abort(); - } - // cout << "OK!" << endl; -#endif - + // Get the closest to the source v = _heap[0]; + + // Remove it from the heap (swap it with the last in the heap, and + // update the distance of that one) _heap_size--; - Vertex **a = _heap, **b = _heap + _heap_size; + a = _heap; + b = _heap + _heap_size; swap(*a, *b); swap((*a)->heap_position, (*b)->heap_position); increase_distance_in_heap(_heap[0]); + // Now update the neighbors of the currently closest to the source for(e = v->leaving_edges; e; e = e->next_leaving_edge) { d = v->distance_from_source + e->positivized_length; tv = e->terminal_vertex; @@ -453,25 +379,8 @@ void MTPGraph::find_shortest_path() { tv->pred_edge_toward_source = e; decrease_distance_in_heap(tv); } -#ifdef DEBUG - for(int k = 0; k < _heap_size; k++) { - if(_heap[0]->distance_from_source > _heap[k]->distance_from_source) abort(); - } -#endif } } while(_heap_size > 0); - -#ifdef DEBUG - for(int k = 0; k < _nb_vertices; k++) { - v = &_vertices[k]; - 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) abort(); - } - } -#endif - cout << "DONE!" << endl; } void MTPGraph::find_best_paths(scalar_t *lengths) { @@ -485,10 +394,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) { _edges[e].positivized_length = _edges[e].length; } - // // We call find_shortest_path here to set properly the distances to - // // the source, so that we can make all the edge lengths positive at - // // the first iteration. - // find_shortest_path(); + // Update the distance to the source in "good order" dp_distance_propagation(); diff --git a/mtp_graph.h b/mtp_graph.h index 5842671..2bc5933 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -57,8 +57,8 @@ class MTPGraph { void dp_distance_propagation(); // Set in every vertex pred_edge_toward_source correspondingly to - // the path of shortest length. The current implementation is not - // Dijkstra's! + // the path of shortest length. The current implementation is + // Dijkstra with a Binary Heap (and not with Fibonnaci heap (yet)) void find_shortest_path(); // Follows the path starting on edge e and returns the number of @@ -69,7 +69,7 @@ class MTPGraph { // 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 is_dag(); + int check_DAG_and_set_last_change(); int _nb_vertices, _nb_edges; Vertex *_source, *_sink; -- 2.20.1