From f72214033cc9a12fb40470a5122f3c4686cdc2d1 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Wed, 22 Aug 2012 11:01:56 -0700 Subject: [PATCH] Cosmetics. --- mtp.cc | 1 + mtp_graph.cc | 104 +++++++++++++++++++++++++++++++++------------------ 2 files changed, 68 insertions(+), 37 deletions(-) diff --git a/mtp.cc b/mtp.cc index ce9e56b..13cfad7 100644 --- a/mtp.cc +++ b/mtp.cc @@ -42,6 +42,7 @@ void find_best_paths(int nb_vertices, int *result_edge_occupation) { MTPGraph graph(nb_vertices, nb_edges, ea, eb, source, sink); graph.find_best_paths(el, result_edge_occupation); + graph.print_dot(); } ////////////////////////////////////////////////////////////////////// diff --git a/mtp_graph.cc b/mtp_graph.cc index 04b84aa..1dd6ff2 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -27,7 +27,7 @@ class Edge { public: int id, occupied; scalar_t length, work_length; - Vertex *terminal_vertex; + Vertex *origin_vertex, *terminal_vertex; Edge *next, *pred; }; @@ -56,29 +56,31 @@ public: }; void MTPGraph::print() { - for(int n = 0; n < _nb_vertices; n++) { - for(Edge *e = vertices[n].root_edge; e; e = e->next) { - cout << n << " -> " << e->terminal_vertex->id << " " << e->length; - if(e->occupied) { - cout << " *"; - } - cout << endl; + 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 n = 0; n < _nb_vertices; n++) { - int a = vertices[n].id; - for(Edge *e = vertices[n].root_edge; e; e = e->next) { - int b = e->terminal_vertex->id; - if(e->occupied) { - cout << " " << b << " -> " << a << " [style=bold,color=black,label=\"" << -e->length << "\"];" << endl; - } else { - cout << " " << a << " -> " << b << " [color=gray,label=\"" << e->length << "\"];" << 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; @@ -106,6 +108,7 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges, vertices[from[e]].add_edge(&edges[e]); edges[e].occupied = 0; edges[e].id = e; + edges[e].origin_vertex = &vertices[from[e]]; edges[e].terminal_vertex = &vertices[to[e]]; } @@ -133,11 +136,9 @@ void MTPGraph::initialize_work_lengths() { } void MTPGraph::update_work_lengths() { - for(int n = 0; n < _nb_vertices; n++) { - scalar_t d = vertices[n].distance_from_source; - for(Edge *e = vertices[n].root_edge; e; e = e->next) { - e->work_length += d - e->terminal_vertex->distance_from_source; - } + for(int k = 0; k < _nb_edges; k++) { + Edge *e = edges + k; + e->work_length += e->terminal_vertex->distance_from_source - e->terminal_vertex->distance_from_source; } } @@ -217,10 +218,11 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { edges[e].work_length = edges[e].length; } - find_shortest_path(_front, _new_front); - update_work_lengths(); +#warning + // find_shortest_path(_front, _new_front); + // update_work_lengths(); - // initialize_work_lengths(); + initialize_work_lengths(); do { force_positive_work_lengths(); @@ -233,39 +235,67 @@ void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) { if(_sink->pred_edge) { // If yes, compute the length of the best path - for(Vertex *v = _sink; v->pred_edge; v = v->pred_vertex) { + for(Vertex *v = _sink; v->pred_vertex; v = v->pred_vertex) { total_length += v->pred_edge->length; } // If that length is negative if(total_length < 0.0) { +#ifdef VERBOSE + cout << "Found a path of length " << total_length << endl; +#endif // Invert all the edges along the best path for(Vertex *v = _sink; v->pred_edge; v = v->pred_vertex) { Edge *e = v->pred_edge; - e->terminal_vertex = v->pred_vertex; e->occupied = 1 - e->occupied; e->length = - e->length; e->work_length = - e->work_length; - v->pred_vertex->del_edge(e); - v->add_edge(e); + e->origin_vertex->del_edge(e); + e->terminal_vertex->add_edge(e); + Vertex *t = e->terminal_vertex; + e->terminal_vertex = e->origin_vertex; + e->origin_vertex = t; } } } } while(total_length < 0.0); - for(Edge *e = _sink->root_edge; e; e = e->next) { + for(int k = 0; k < _nb_edges; k++) { + Edge *e = edges + k; if(e->occupied) { - Edge *f = e; - cout << "PATH " << _sink->id; - while(f) { - cout << " " << f->terminal_vertex->id; - for(f = f->terminal_vertex->root_edge; f && !f->occupied; f = f->next); - } - cout << endl; + e->length = - e->length; + e->work_length = 0; + e->origin_vertex->del_edge(e); + e->terminal_vertex->add_edge(e); + Vertex *t = e->terminal_vertex; + e->terminal_vertex = e->origin_vertex; + e->origin_vertex = t; } } + // for(Edge *e = _sink->root_edge; e; e = e->next) { + // if(e->occupied) { + // Edge *f = e; + // cout << "PATH " << _sink->id; + // while(f) { + // cout << " " << f->terminal_vertex->id; + // for(f = f->terminal_vertex->root_edge; f && !f->occupied; f = f->next); + // } + // cout << endl; + // } + // } + + // int nb_occupied = 0; + // for(int e = 0; e < _nb_edges; e++) { + // for(int n = 0; n < _nb_vertices; n++) { + // Vertex *v = &vertices[n]; + // for(Edge *e = v->root_edge; e; e = e->next) { + // if(e->occupied) nb_occupied++; + // } + // } + // } + for(int n = 0; n < _nb_vertices; n++) { Vertex *v = &vertices[n]; for(Edge *e = v->root_edge; e; e = e->next) { -- 2.39.5