X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?a=blobdiff_plain;f=mtp_graph.cc;h=f94cec7edc4bd57a670c3630b62dfc821a3f721a;hb=d88b0404a88b446020f9ad749ec9aff971679e4a;hp=b83871d4df3d7065a325fb552760987d009df5cb;hpb=340972b07aa40e812a99ecd2bced570cdd5eed84;p=mtp.git diff --git a/mtp_graph.cc b/mtp_graph.cc index b83871d..f94cec7 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -20,6 +20,7 @@ #include #include +#include using namespace std; @@ -82,6 +83,17 @@ void Vertex::del_edge(Edge *e) { ////////////////////////////////////////////////////////////////////// +Path::Path(int l) { + length = l; + nodes = new int[length]; +} + +Path::~Path() { + delete[] nodes; +} + +////////////////////////////////////////////////////////////////////// + MTPGraph::MTPGraph(int nb_vertices, int nb_edges, int *from, int *to, int source, int sink) { @@ -123,35 +135,38 @@ MTPGraph::~MTPGraph() { ////////////////////////////////////////////////////////////////////// -void MTPGraph::print() { +void MTPGraph::print(ostream *os) { for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; - cout << e->origin_vertex->id + (*os) << e->origin_vertex->id << " -> " << e->terminal_vertex->id << " " << e->length; if(e->occupied) { - cout << " *"; + (*os) << " *"; } - cout << endl; + (*os) << endl; } } -void MTPGraph::print_dot() { - cout << "digraph {" << endl; - cout << " node[shape=circle];" << endl; +void MTPGraph::print_dot(ostream *os) { + (*os) << "digraph {" << endl; + (*os) << " node[shape=circle];" << endl; for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; + // (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id + // << ";" + // << endl; if(e->occupied) { - cout << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id - << " [style=bold,color=black,label=\"" << -e->length << "\"];" << endl; + (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id + << " [style=bold,color=black,label=\"" << e->length << "\"];" << endl; } else { - cout << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id + (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id << " [color=gray,label=\"" << e->length << "\"];" << endl; } } - cout << "}" << endl; + (*os) << "}" << endl; } ////////////////////////////////////////////////////////////////////// @@ -173,26 +188,29 @@ void MTPGraph::initialize_positivized_lengths_with_min() { void MTPGraph::update_positivized_lengths() { for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; - e->positivized_length += e->terminal_vertex->distance_from_source - e->terminal_vertex->distance_from_source; + e->positivized_length += + e->origin_vertex->distance_from_source - e->terminal_vertex->distance_from_source; } } void MTPGraph::force_positivized_lengths() { #ifdef VERBOSE scalar_t residual_error = 0.0; + scalar_t max_error = 0.0; #endif for(int n = 0; n < _nb_vertices; n++) { for(Edge *e = _vertices[n].leaving_edges; e; e = e->next_leaving_edge) { if(e->positivized_length < 0) { #ifdef VERBOSE residual_error -= e->positivized_length; + max_error = max(max_error, fabs(e->positivized_length)); #endif e->positivized_length = 0.0; } } } #ifdef VERBOSE - cerr << "residual_error " << residual_error << endl; + cerr << "residual_error " << residual_error << " max_error " << residual_error << endl; #endif } @@ -220,6 +238,7 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { do { _new_front_size = 0; iteration++; + for(int f = 0; f < _front_size; f++) { v = _front[f]; for(e = v->leaving_edges; e; e = e->next_leaving_edge) { @@ -243,16 +262,18 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { tmp_front_size = _new_front_size; _new_front_size = _front_size; _front_size = tmp_front_size; + cout << "_front_size = " << _front_size << endl; } while(_front_size > 0); } -void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { +void MTPGraph::find_best_paths(scalar_t *lengths) { scalar_t total_length; Vertex *v; Edge *e; for(int e = 0; e < _nb_edges; e++) { _edges[e].length = lengths[e]; + _edges[e].occupied = 0; _edges[e].positivized_length = _edges[e].length; } @@ -282,7 +303,7 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { // If that length is negative if(total_length < 0.0) { #ifdef VERBOSE - cout << "Found a path of length " << total_length << endl; + cerr << "Found a path of length " << total_length << endl; #endif // Invert all the edges along the best path v = _sink; @@ -302,11 +323,41 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { for(int k = 0; k < _nb_edges; k++) { Edge *e = _edges + k; if(e->occupied) { e->revert(); } - result_edge_occupation[k] = e->occupied; } } -void MTPGraph::retrieve_paths() { +int MTPGraph::retrieve_one_path(Edge *e, int *nodes) { + Edge *f, *next = 0; + int l = 0; + + if(nodes) { nodes[l++] = e->origin_vertex->id; } + else l++; + + while(e->terminal_vertex != _sink) { + if(nodes) { nodes[l++] = e->terminal_vertex->id; } + else l++; + int nb_choices = 0; + for(f = e->terminal_vertex->leaving_edges; f; f = f->next_leaving_edge) { + if(f->occupied) { nb_choices++; next = f; } + if(nb_choices == 0) { + cerr << "Non-sink path end point?!" << endl; + abort(); + } + if(nb_choices > 1) { + cerr << "Non node-disjoint path, can not retrieve." << endl; + abort(); + } + } + e = next; + } + + if(nodes) { nodes[l++] = e->terminal_vertex->id; } + else l++; + + return l; +} + +void MTPGraph::retrieve_disjoint_paths() { Edge *e; for(int p = 0; p < nb_paths; p++) delete paths[p]; @@ -322,10 +373,10 @@ void MTPGraph::retrieve_paths() { int p = 0; for(e = _source->leaving_edges; e; e = e->next_leaving_edge) { if(e->occupied) { - paths[p] = new Path(); + int l = retrieve_one_path(e, 0); + paths[p] = new Path(l); + retrieve_one_path(e, paths[p]->nodes); p++; } } - - cout << "NB_PATHS " << nb_paths << endl; }