X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?a=blobdiff_plain;f=mtp_graph.cc;h=8160211ca6ed0dc9c41587e46c3b72723ed349c3;hb=633971154a478e1a134f38f420655b93a9f2160d;hp=95dc4510af14e4cd8888e943209c8f808235d7dd;hpb=79a4a9ab164a667ecb551078e1cd773e2140e3c2;p=mtp.git diff --git a/mtp_graph.cc b/mtp_graph.cc index 95dc451..8160211 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -20,6 +20,7 @@ #include #include +#include using namespace std; @@ -82,37 +83,6 @@ void Vertex::del_edge(Edge *e) { ////////////////////////////////////////////////////////////////////// -void MTPGraph::print() { - for(int k = 0; k < _nb_edges; k++) { - Edge *e = _edges + k; - cout << e->origin_vertex->id - << " -> " - << e->terminal_vertex->id - << " " - << e->length; - if(e->occupied) { - cout << " *"; - } - cout << endl; - } -} - -void MTPGraph::print_dot() { - cout << "digraph {" << endl; - cout << " node[shape=circle];" << endl; - for(int k = 0; k < _nb_edges; k++) { - Edge *e = _edges + k; - if(e->occupied) { - cout << " " << 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 - << " [color=gray,label=\"" << e->length << "\"];" << endl; - } - } - cout << "}" << endl; -} - MTPGraph::MTPGraph(int nb_vertices, int nb_edges, int *from, int *to, int source, int sink) { @@ -139,6 +109,8 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges, _edges[e].terminal_vertex = _vertices + to[e]; } + paths = 0; + nb_paths = 0; } MTPGraph::~MTPGraph() { @@ -146,8 +118,50 @@ MTPGraph::~MTPGraph() { delete[] _edges; delete[] _front; delete[] _new_front; + for(int p = 0; p < nb_paths; p++) delete paths[p]; + delete[] paths; +} + +////////////////////////////////////////////////////////////////////// + +void MTPGraph::print(ostream *os) { + for(int k = 0; k < _nb_edges; k++) { + Edge *e = _edges + k; + (*os) << e->origin_vertex->id + << " -> " + << e->terminal_vertex->id + << " " + << e->length; + if(e->occupied) { + (*os) << " *"; + } + (*os) << endl; + } } +void MTPGraph::print_dot(ostream *os) { + (*os) << "digraph {" << endl; + // (*os) << " node [shape=circle];" << endl; + (*os) << " " << _source->id << " [peripheries=2];" << endl; + (*os) << " " << _sink->id << " [peripheries=2];" << 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) { + (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id + << " [style=bold,color=black,label=\"" << e->length << "\"];" << endl; + } else { + (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id + << " [color=gray,label=\"" << e->length << "\"];" << endl; + } + } + (*os) << "}" << endl; +} + +////////////////////////////////////////////////////////////////////// + void MTPGraph::initialize_positivized_lengths_with_min() { scalar_t length_min = 0; for(int n = 0; n < _nb_vertices; n++) { @@ -165,26 +179,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 } @@ -212,6 +229,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) { @@ -238,13 +256,14 @@ void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) { } 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; } @@ -274,7 +293,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; @@ -294,6 +313,60 @@ 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; + } +} + +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]; + delete[] paths; + + nb_paths = 0; + for(e = _source->leaving_edges; e; e = e->next_leaving_edge) { + if(e->occupied) { nb_paths++; } + } + + paths = new Path *[nb_paths]; + + int p = 0; + for(e = _source->leaving_edges; e; e = e->next_leaving_edge) { + if(e->occupied) { + int l = retrieve_one_path(e, 0); + paths[p] = new Path(l); + retrieve_one_path(e, paths[p]->nodes); + p++; + } } }