From 34022d5e987cf13ff6db31a6d7263e9266a8b1c0 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Sun, 26 Aug 2012 08:26:23 +0200 Subject: [PATCH] Added is_dag + an ASSERT using it. --- mtp_graph.cc | 79 +++++++++++++++++++++++++++++++++++++++++----------- mtp_graph.h | 2 ++ 2 files changed, 64 insertions(+), 17 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index 92e3875..9a811bb 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -109,8 +109,8 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges, _source = &_vertices[source]; _sink = &_vertices[sink]; - for(int v = 0; v < _nb_vertices; v++) { - _vertices[v].id = v; + for(int k = 0; k < _nb_vertices; k++) { + _vertices[k].id = k; } for(int e = 0; e < nb_edges; e++) { @@ -157,8 +157,6 @@ void MTPGraph::print_dot(ostream *os) { (*os) << " edge [color=gray,arrowhead=open]" << endl; (*os) << " " << _source->id << " [peripheries=2];" << endl; (*os) << " " << _sink->id << " [peripheries=2];" << endl; - // (*os) << " " << _source->id << " [style=bold,color=red];" << endl; - // (*os) << " " << _sink->id << " [style=bold,color=green];" << endl; for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; // (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id @@ -205,6 +203,50 @@ void MTPGraph::force_positivized_lengths() { #endif } +int MTPGraph::is_dag() { + Vertex *v, *tv; + Edge *e; + + // We put everybody in the front + for(int k = 0; k < _nb_vertices; k++) { + _vertices[k].iteration = 0; + _front[k] = &_vertices[k]; + } + + int front_size = _nb_vertices, nb_with_incoming; + int iteration = 0; + int new_front_size, 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; + } + } + + new_front_size = 0; + // We remove all vertex without incoming edge + for(int f = 0; f < front_size; f++) { + v = _front[f]; + if(v->iteration == iteration) { + _front[new_front_size++] = v; + } + } + + pred_front_size = front_size; + front_size = new_front_size; + } while(front_size < pred_front_size); + + return front_size == 0; +} + // This method does not change the edge occupation. It update // distance_from_source and pred_edge_toward_source. void MTPGraph::find_shortest_path() { @@ -214,23 +256,23 @@ void MTPGraph::find_shortest_path() { Edge *e; scalar_t d; - for(int v = 0; v < _nb_vertices; v++) { - _vertices[v].distance_from_source = FLT_MAX; - _vertices[v].pred_edge_toward_source = 0; - _vertices[v].iteration = 0; + for(int k = 0; k < _nb_vertices; k++) { + _vertices[k].distance_from_source = FLT_MAX; + _vertices[k].pred_edge_toward_source = 0; + _vertices[k].iteration = 0; } int iteration = 0; - int _front_size = 0, _new_front_size; - _front[_front_size++] = _source; + int front_size = 0, new_front_size; + _front[front_size++] = _source; _source->distance_from_source = 0; do { - _new_front_size = 0; + new_front_size = 0; iteration++; - for(int f = 0; f < _front_size; f++) { + for(int f = 0; f < front_size; f++) { v = _front[f]; for(e = v->leaving_edges; e; e = e->next_leaving_edge) { d = v->distance_from_source + e->positivized_length; @@ -239,7 +281,7 @@ void MTPGraph::find_shortest_path() { tv->distance_from_source = d; tv->pred_edge_toward_source = e; if(tv->iteration < iteration) { - _new_front[_new_front_size++] = tv; + _new_front[new_front_size++] = tv; tv->iteration = iteration; } } @@ -250,10 +292,10 @@ void MTPGraph::find_shortest_path() { _new_front = _front; _front = tmp_front; - tmp_front_size = _new_front_size; - _new_front_size = _front_size; - _front_size = tmp_front_size; - } while(_front_size > 0); + tmp_front_size = new_front_size; + new_front_size = front_size; + front_size = tmp_front_size; + } while(front_size > 0); } void MTPGraph::find_best_paths(scalar_t *lengths) { @@ -267,6 +309,9 @@ 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 use one iteration of find_shortest_path simply to propagate // the distance to make all the edge lengths positive. find_shortest_path(); diff --git a/mtp_graph.h b/mtp_graph.h index 916b604..945f387 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -45,6 +45,8 @@ class MTPGraph { // Follows the path starting on edge e and returns its length. If // nodes is non-null, stores in it the nodes met along the path. int retrieve_one_path(Edge *e, Path *path); + // Returns if the graph is a DAG + int is_dag(); Vertex **_front, **_new_front; -- 2.39.5