From 78b0bdef0b9a3479502c7598fd69a012c297e125 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Thu, 20 Dec 2012 15:40:59 +0100 Subject: [PATCH] Cosmetics. --- mtp_graph.cc | 44 +++++++++++++++++++++----------------------- 1 file changed, 21 insertions(+), 23 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index 5a7da77..682dd80 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -202,44 +202,44 @@ int MTPGraph::compute_dp_ranks() { // rank of a node is the iteration at which is it removed, and we // set the distance_from_source fields to this value. - Vertex **unreached = new Vertex *[_nb_vertices]; + Vertex **with_predecessor = new Vertex *[_nb_vertices]; - // All the nodes are unreached at first + // All the nodes are with_predecessor at first for(int k = 0; k < _nb_vertices; k++) { _vertices[k].distance_from_source = 0; - unreached[k] = &_vertices[k]; + with_predecessor[k] = &_vertices[k]; } scalar_t rank = 1; - int nb_unreached = _nb_vertices, pred_nb_unreached; + int nb_with_predecessor = _nb_vertices, pred_nb_with_predecessor; do { // We set the distance_from_source field of all the vertices with incoming // edges to the current rank value - for(int f = 0; f < nb_unreached; f++) { - v = unreached[f]; + for(int f = 0; f < nb_with_predecessor; f++) { + v = with_predecessor[f]; for(e = v->leaving_edges; e; e = e->next_leaving_edge) { e->terminal_vertex->distance_from_source = rank; } } - pred_nb_unreached = nb_unreached; - nb_unreached = 0; + pred_nb_with_predecessor = nb_with_predecessor; + nb_with_predecessor = 0; // We keep all the vertices with incoming nodes - for(int f = 0; f < pred_nb_unreached; f++) { - v = unreached[f]; + for(int f = 0; f < pred_nb_with_predecessor; f++) { + v = with_predecessor[f]; if(v->distance_from_source == rank) { - unreached[nb_unreached++] = v; + with_predecessor[nb_with_predecessor++] = v; } } rank++; - } while(nb_unreached < pred_nb_unreached); + } while(nb_with_predecessor < pred_nb_with_predecessor); - delete[] unreached; + delete[] with_predecessor; - return nb_unreached == 0; + return nb_with_predecessor == 0; } ////////////////////////////////////////////////////////////////////// @@ -300,7 +300,6 @@ void MTPGraph::force_positivized_lengths() { Edge *e = _edges + k; if(e->positivized_length < 0) { - #ifdef VERBOSE residual_error -= e->positivized_length; max_error = max(max_error, - e->positivized_length); @@ -333,7 +332,6 @@ void MTPGraph::dp_compute_distances() { if(d < tv->distance_from_source) { tv->distance_from_source = d; tv->pred_edge_toward_source = e; - tv->decrease_distance_in_heap(_heap); } } } @@ -344,7 +342,7 @@ void MTPGraph::dp_compute_distances() { // pred_edge_toward_source. void MTPGraph::find_shortest_path() { - Vertex *v, *tv, **a, **b; + Vertex *v, *tv, **last_slot; Edge *e; scalar_t d; @@ -361,15 +359,15 @@ void MTPGraph::find_shortest_path() { // Get the closest to the source v = _heap[0]; - // Remove it from the heap (swap it with the last in the heap, and + // Remove it from the heap (swap it with the last_slot in the heap, and // update the distance of that one) _heap_size--; - a = _heap; - b = _heap + _heap_size; - swap(*a, *b); swap((*a)->heap_slot, (*b)->heap_slot); + last_slot = _heap + _heap_size; + swap(*_heap, *last_slot); swap((*_heap)->heap_slot, (*last_slot)->heap_slot); _heap[0]->increase_distance_in_heap(_heap, _heap + _heap_size); - // Now update the neighbors of the currently closest to the source + // Now update the neighbors of the node 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; @@ -394,7 +392,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) { _edges[e].positivized_length = _edges[e].length; } - // Compute the distance of every node from the source by just + // Compute the distance of all the nodes from the source by just // visiting them in the proper DAG ordering we computed when // building the graph dp_compute_distances(); -- 2.39.5