From abbaf6b4b4b8d10ee8e9054a3b8d262a2f242920 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 29 Aug 2012 17:07:13 +0200 Subject: [PATCH] Cosmetics + added a full check in find_shortest_path when compiling in DEBUG. --- mtp_graph.cc | 43 +++++++++++++++++++++---------------------- 1 file changed, 21 insertions(+), 22 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index 7781fc1..d3b921b 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -205,7 +205,7 @@ void MTPGraph::force_positivized_lengths() { } int MTPGraph::is_dag() { - Vertex *v, *tv; + Vertex *v; Edge *e; // We put everybody in the front @@ -214,35 +214,31 @@ int MTPGraph::is_dag() { _front[k] = &_vertices[k]; } - int front_size = _nb_vertices, nb_with_incoming; int iteration = 0; - int new_front_size, pred_front_size; + int front_size = _nb_vertices, pred_front_size; do { iteration++; - nb_with_incoming = 0; // We set the iteration field of all vertex with incoming edges to // the current iteration value for(int f = 0; f < front_size; f++) { v = _front[f]; for(e = v->leaving_edges; e; e = e->next_leaving_edge) { - tv = e->terminal_vertex; - tv->iteration = iteration; + e->terminal_vertex->iteration = iteration; } } - new_front_size = 0; + pred_front_size = front_size; + front_size = 0; + // We remove all the vertices without incoming edge - for(int f = 0; f < front_size; f++) { + for(int f = 0; f < pred_front_size; f++) { v = _front[f]; if(v->iteration == iteration) { - _front[new_front_size++] = v; + _front[front_size++] = v; } } - - pred_front_size = front_size; - front_size = new_front_size; } while(front_size < pred_front_size); return front_size == 0; @@ -254,11 +250,21 @@ int MTPGraph::is_dag() { void MTPGraph::find_shortest_path() { Vertex **tmp_front; - int tmp_front_size; Vertex *v, *tv; 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; @@ -291,13 +297,9 @@ void MTPGraph::find_shortest_path() { } } - tmp_front = _new_front; - _new_front = _front; - _front = tmp_front; + tmp_front = _new_front; _new_front = _front; _front = tmp_front; - tmp_front_size = new_front_size; - new_front_size = front_size; - front_size = tmp_front_size; + front_size = new_front_size; } while(front_size > 0); } @@ -312,9 +314,6 @@ void MTPGraph::find_best_paths(scalar_t *lengths) { _edges[e].positivized_length = _edges[e].length; } - // Let's be a bit paranoid - ASSERT(is_dag()); - // 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. -- 2.39.5