From 0a78398c86517c7c6224bd8f4f1b3950fed245b9 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Fri, 14 Jun 2013 09:25:14 +0200 Subject: [PATCH] Fixed retrieve_disjoint_paths to deal with non-node-disjoint situations. --- mtp_graph.cc | 27 +++++++++++++++++---------- mtp_graph.h | 7 +++++-- 2 files changed, 22 insertions(+), 12 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index e69d4d6..8849acd 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -379,7 +379,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths) { } } -int MTPGraph::retrieve_one_path(Edge *e, Path *path) { +int MTPGraph::retrieve_one_path(Edge *e, Path *path, int *used_edges) { Edge *f, *next = 0; int l = 0, nb_occupied_next; @@ -396,7 +396,9 @@ int MTPGraph::retrieve_one_path(Edge *e, Path *path) { nb_occupied_next = 0; for(f = e->terminal_vertex->leaving_edge_list_root; f; f = f->next_leaving_edge) { - if(f->occupied) { nb_occupied_next++; next = f; } + if(f->occupied && !used_edges[f - _edges]) { + nb_occupied_next++; next = f; + } } #ifdef DEBUG @@ -404,13 +406,10 @@ int MTPGraph::retrieve_one_path(Edge *e, Path *path) { cerr << __FILE__ << ": retrieve_one_path: Non-sink end point." << endl; abort(); } - - else if(nb_occupied_next > 1) { - cerr << __FILE__ << ": retrieve_one_path: Non node-disjoint paths." << endl; - abort(); - } #endif + if(path) { used_edges[next - _edges] = 1; } + e = next; } @@ -490,6 +489,7 @@ void MTPGraph::compute_dp_ordering() { void MTPGraph::retrieve_disjoint_paths() { Edge *e; int p, l; + int *used_edges; for(int p = 0; p < nb_paths; p++) delete paths[p]; delete[] paths; @@ -500,14 +500,21 @@ void MTPGraph::retrieve_disjoint_paths() { } paths = new Path *[nb_paths]; + used_edges = new int[_nb_edges]; + for(int e = 0; e < _nb_edges; e++) { + used_edges[e] = 0; + } p = 0; for(e = _source->leaving_edge_list_root; e; e = e->next_leaving_edge) { - if(e->occupied) { - l = retrieve_one_path(e, 0); + if(e->occupied && !used_edges[e - _edges]) { + l = retrieve_one_path(e, 0, used_edges); paths[p] = new Path(l); - retrieve_one_path(e, paths[p]); + retrieve_one_path(e, paths[p], used_edges); + used_edges[e - _edges] = 1; p++; } } + + delete[] used_edges; } diff --git a/mtp_graph.h b/mtp_graph.h index 33a29f5..64308b9 100644 --- a/mtp_graph.h +++ b/mtp_graph.h @@ -61,7 +61,7 @@ class MTPGraph { // Follows the path starting on edge e and returns the number of // nodes to reach the sink. If path is non-null, stores in it the // nodes met along the path, and computes path->length properly. - int retrieve_one_path(Edge *e, Path *path); + int retrieve_one_path(Edge *e, Path *path, int *used_edges); int _nb_vertices, _nb_edges; Vertex *_source, *_sink; @@ -94,7 +94,10 @@ public: void find_best_paths(scalar_t *lengths); // Retrieve the paths corresponding to the occupied edges, and save - // the result in the nb_paths and paths fields. + // the result in the nb_paths and paths fields. If the paths are not + // node-disjoint, there are multiple families of paths that + // "explain" the edge occupancies, and this method picks one of them + // arbitrarily. void retrieve_disjoint_paths(); void print(ostream *os); -- 2.39.5