From af5339cd0eb42ef3fc1c09d3662cf9fdc900ed38 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Tue, 21 Aug 2012 14:33:17 -0700 Subject: [PATCH] Removed miniksp, cosmetics on mtp. --- miniksp.cc | 248 ----------------------------------------------------- mtp.cc | 147 +++++++++++++++---------------- 2 files changed, 67 insertions(+), 328 deletions(-) delete mode 100644 miniksp.cc diff --git a/miniksp.cc b/miniksp.cc deleted file mode 100644 index 92e9de5..0000000 --- a/miniksp.cc +++ /dev/null @@ -1,248 +0,0 @@ - -/////////////////////////////////////////////////////////////////////////// -// START_IP_HEADER // -// // -// This program is free software: you can redistribute it and/or modify // -// it under the terms of the version 3 of the GNU General Public License // -// as published by the Free Software Foundation. // -// // -// This program is distributed in the hope that it will be useful, but // -// WITHOUT ANY WARRANTY; without even the implied warranty of // -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // -// General Public License for more details. // -// // -// You should have received a copy of the GNU General Public License // -// along with this program. If not, see . // -// // -// Written by and Copyright (C) Francois Fleuret // -// Contact for comments & bug reports // -// // -// END_IP_HEADER // -/////////////////////////////////////////////////////////////////////////// - -// #define VERBOSE - -#include -#include -#include -#include -#include -#include - -using namespace std; - -typedef float scalar_t; - -#ifdef DEBUG -#define ASSERT(x) if(!(x)) { \ - std::cerr << "ASSERT FAILED IN " << __FILE__ << ":" << __LINE__ << endl; \ - abort(); \ -} -#else -#define ASSERT(x) -#endif - -// In all the code: -// -// * el[e] is the length of edge e -// * ea[e] is its starting node -// * eb[e] is its destination node. - -// Adds to all the edge length the length of the shortest (which can -// be negative) -void raise_es(int nb_edges, scalar_t *el) { - scalar_t min_es = el[0]; - for(int e = 1; e < nb_edges; e++) { - min_es = min(min_es, el[e]); - } - for(int e = 0; e < nb_edges; e++) { - el[e] -= min_es; - } -} - -// Adds to every edge length the differential of the psi function on -// it -void add_dpsi_es(int nb_edges, scalar_t *el, int *ea, int *eb, scalar_t *psi) { - for(int e = 0; e < nb_edges; e++) { - el[e] += psi[ea[e]] - psi[eb[e]]; - } -} - -// Finds the shortest path in the graph and returns in -// result_edge_back, for each vertex, the edge to follow back from it -// to reach the source with the shortest path, and in result_dist the -// distance to the source. The edge lengths have to be positive. -void find_shortest(int nb_vertices, - int nb_edges, scalar_t *el, int *ea, int *eb, - int source, int sink, - int *result_edge_back, scalar_t *result_dist) { - for(int v = 0; v < nb_vertices; v++) { - result_dist[v] = FLT_MAX; - result_edge_back[v] = -1; - } - - result_dist[source] = 0; - -#ifdef DEBUG - for(int e = 0; e < nb_edges; e++) { - if(el[e] < 0) abort(); - } -#endif - - int nb_changes; - scalar_t d; - do { - nb_changes = 0; - for(int e = 0; e < nb_edges; e++) { - d = result_dist[ea[e]] + el[e]; - if(d < result_dist[eb[e]]) { - nb_changes++; - result_dist[eb[e]] = d; - result_edge_back[eb[e]] = e; - } - } - } while(nb_changes > 0); -} - -// Iterates find_shortest as long as it finds paths of negative -// lengths. Returns which edges are occupied by the superposition of -// paths in result_edge_occupation. -// -// **WARNING** this routine changes the values of el, ea, and eb -// (i.e. the occupied edges are inverted). -void find_best_paths(int nb_vertices, - int nb_edges, scalar_t *el, int *ea, int *eb, - int source, int sink, - int *result_edge_occupation) { - scalar_t *dist = new scalar_t[nb_vertices]; - int *edge_back = new int[nb_vertices]; - scalar_t *positive_el = new scalar_t[nb_edges]; - scalar_t s; - int v; - - for(int e = 0; e < nb_edges; e++) { - positive_el[e] = el[e]; - result_edge_occupation[e] = 0; - } - - raise_es(nb_edges, positive_el); - - do { - find_shortest(nb_vertices, nb_edges, positive_el, ea, eb, source, sink, edge_back, dist); - add_dpsi_es(nb_edges, positive_el, ea, eb, dist); - s = 0.0; - - // If the new path reaches the sink, we will backtrack on it to - // compute its score and invert edges - - if(edge_back[sink] >= 0) { - - v = sink; - while(v != source) { - int e = edge_back[v]; - ASSERT(eb[e] == v); - v = ea[e]; - s += el[e]; - } - - // We found a good path (score < 0), we revert the edges along - // the path and invert their occupation (since adding a path on - // a path already occupied means removing flow on it) - - if(s < 0) { - v = sink; -#ifdef VERBOSE - cout << "FOUND A PATH OF LENGTH " << s << endl; -#endif - while(v != source) { - int e = edge_back[v]; - ASSERT(eb[e] == v); - v = ea[e]; -#ifdef VERBOSE - cout << "INVERTING " << ea[e] << " -> " << eb[e] << " [" << el[e] << "]" << endl; -#endif - int k = eb[e]; - eb[e] = ea[e]; - ea[e] = k; - positive_el[e] = - positive_el[e]; - el[e] = - el[e]; - result_edge_occupation[e] = 1 - result_edge_occupation[e]; - } - } - } - } while(s < 0); - - delete[] positive_el; - delete[] dist; - delete[] edge_back; -} - -int main(int argc, char **argv) { - - if(argc < 2) { - cerr << argv[0] << " " << endl; - exit(EXIT_FAILURE); - } - - ifstream *file = new ifstream(argv[1]); - - int nb_edges, nb_vertices; - int source, sink; - - if(file->good()) { - - (*file) >> nb_vertices >> nb_edges; - (*file) >> source >> sink; - - cout << "INPUT nb_edges " << nb_edges << endl; - cout << "INPUT nb_vertices " << nb_vertices << endl; - cout << "INPUT source " << source << endl; - cout << "INPUT sink " << sink << endl; - - scalar_t *el = new scalar_t[nb_edges]; - int *ea = new int[nb_edges]; - int *eb = new int[nb_edges]; - int *edge_occupation = new int[nb_edges]; - - for(int e = 0; e < nb_edges; e++) { - (*file) >> ea[e] >> eb[e] >> el[e]; - cout << "INPUT_EDGE " << ea[e] << " " << eb[e] << " " << el[e] << endl; - } - - find_best_paths(nb_vertices, nb_edges, el, ea, eb, source, sink, - edge_occupation); - -#ifdef VERBOSE - // Sanity check on the overall resulting score (the edge lengths - // have been changed, hence should be the opposite of the sum of - // the path lengths) - scalar_t s = 0; - for(int e = 0; e < nb_edges; e++) { - if(edge_occupation[e]) s += el[e]; - } - cout << "RESULT_SANITY_CHECK_SCORE " << s << endl; -#endif - - for(int e = 0; e < nb_edges; e++) { - if(edge_occupation[e]) { - cout << "RESULT_OCCUPIED_EDGE " << ea[e] << " " << eb[e] << endl; - } - } - - delete[] edge_occupation; - delete[] el; - delete[] ea; - delete[] eb; - - } else { - - cerr << "Can not open " << argv[1] << endl; - - delete file; - exit(EXIT_FAILURE); - - } - - delete file; - exit(EXIT_SUCCESS); -} diff --git a/mtp.cc b/mtp.cc index 94dde64..307da22 100644 --- a/mtp.cc +++ b/mtp.cc @@ -44,7 +44,7 @@ class Vertex; class Edge { public: - int occupied; + int id, occupied; scalar_t length, work_length; Vertex *terminal_vertex; Edge *next, *pred; @@ -54,23 +54,23 @@ class Vertex { public: int id; - Edge *first_edge; + Edge *root_edge; scalar_t distance_from_source; Vertex *pred_vertex; Edge *pred_edge; - Vertex() { first_edge = 0; } + Vertex() { root_edge = 0; } inline void add_edge(Edge *e) { - e->next = first_edge; + e->next = root_edge; e->pred = 0; - if(first_edge) { first_edge->pred = e; } - first_edge = e; + if(root_edge) { root_edge->pred = e; } + root_edge = e; } inline void del_edge(Edge *e) { - if(e == first_edge) { first_edge = e->next; } + if(e == root_edge) { root_edge = e->next; } if(e->pred) { e->pred->next = e->next; } if(e->next) { e->next->pred = e->pred; } } @@ -92,49 +92,22 @@ public: ~Graph(); - void find_best_paths(); + void find_best_paths(int *result_edge_occupation); void print(); - void print_occupied_edges(); - void dot_print(); }; void Graph::print() { for(int n = 0; n < nb_vertices; n++) { - for(Edge *e = vertices[n].first_edge; e; e = e->next) { - cout << n << " -> " << e->terminal_vertex->id << " " << e->length << endl; - } - } -} - -void Graph::print_occupied_edges() { - for(int n = 0; n < nb_vertices; n++) { - for(Edge *e = vertices[n].first_edge; e; e = e->next) { + for(Edge *e = vertices[n].root_edge; e; e = e->next) { + cout << n << " -> " << e->terminal_vertex->id << " " << e->length; if(e->occupied) { - int a = n, b = e->terminal_vertex->id; - if(a > b) { int c = a; a = b; b = c; } - cout << a << " " << b << endl; + cout << " *"; } + cout << endl; } } } -void Graph::dot_print() { - cout << "digraph {" << endl; - cout << " node[shape=circle];" << endl; - for(int n = 0; n < nb_vertices; n++) { - for(Edge *e = vertices[n].first_edge; e; e = e->next) { - int a = n, b = e->terminal_vertex->id; - if(e->occupied) { - int c = a; a = b; b = c; - cout << " " << a << " -> " << b << " [style=bold,color=black,label=\"" << -e->length << "\"];" << endl; - } else { - cout << " " << a << " -> " << b << " [color=gray,label=\"" << e->length << "\"];" << endl; - } - } - } - cout << "}" << endl; -} - Graph::Graph(int nb_vrt, int nb_edges, int *from, int *to, scalar_t *lengths, int src, int snk) { @@ -153,6 +126,7 @@ Graph::Graph(int nb_vrt, int nb_edges, for(int e = 0; e < nb_edges; e++) { vertices[from[e]].add_edge(&edge_heap[e]); edge_heap[e].occupied = 0; + edge_heap[e].id = e; edge_heap[e].length = lengths[e]; edge_heap[e].terminal_vertex = &vertices[to[e]]; } @@ -166,12 +140,12 @@ Graph::~Graph() { void Graph::initialize_work_lengths() { scalar_t length_min = 0; for(int n = 0; n < nb_vertices; n++) { - for(Edge *e = vertices[n].first_edge; e; e = e->next) { + for(Edge *e = vertices[n].root_edge; e; e = e->next) { length_min = min(e->length, length_min); } } for(int n = 0; n < nb_vertices; n++) { - for(Edge *e = vertices[n].first_edge; e; e = e->next) { + for(Edge *e = vertices[n].root_edge; e; e = e->next) { e->work_length = e->length - length_min; } } @@ -180,7 +154,7 @@ void Graph::initialize_work_lengths() { void Graph::update_work_length() { for(int n = 0; n < nb_vertices; n++) { scalar_t d = vertices[n].distance_from_source; - for(Edge *e = vertices[n].first_edge; e; e = e->next) { + for(Edge *e = vertices[n].root_edge; e; e = e->next) { e->work_length += d - e->terminal_vertex->distance_from_source; } } @@ -194,7 +168,7 @@ void Graph::find_shortest_path(Vertex **front, Vertex **new_front) { #ifdef DEBUG for(int n = 0; n < nb_vertices; n++) { - for(Edge *e = vertices[n].first_edge; e; e = e->next) { + for(Edge *e = vertices[n].root_edge; e; e = e->next) { if(e->work_length < 0) { cerr << "DEBUG error in find_shortest_path: Edge fixed lengths have to be positive." << endl; @@ -218,7 +192,7 @@ void Graph::find_shortest_path(Vertex **front, Vertex **new_front) { new_front_size = 0; for(int f = 0; f < front_size; f++) { v = front[f]; - for(Edge *e = v->first_edge; e; e = e->next) { + for(Edge *e = v->root_edge; e; e = e->next) { d = v->distance_from_source + e->work_length; tv = e->terminal_vertex; if(d < tv->distance_from_source) { @@ -240,7 +214,7 @@ void Graph::find_shortest_path(Vertex **front, Vertex **new_front) { } while(front_size > 0); } -void Graph::find_best_paths() { +void Graph::find_best_paths(int *result_edge_occupation) { Vertex **front = new Vertex *[nb_vertices]; Vertex **new_front = new Vertex *[nb_vertices]; @@ -277,23 +251,39 @@ void Graph::find_best_paths() { } } while(total_length < 0.0); - // // We put all occupied edges back to their original orientations - // for(int n = 0; n < nb_vertices; n++) { - // Vertex *v = &vertices[n]; - // for(Edge *e = v->first_edge; e; e = e->next) { - // if(e->occupied) { - // e->terminal_vertex = v->pred_vertex; - // e->length = - e->length; - // e->work_length = 0; - // v->pred_vertex->del_edge(e); - // v->add_edge(e); - // } - // } - // } - - delete[] front; delete[] new_front; + + for(int n = 0; n < nb_vertices; n++) { + Vertex *v = &vertices[n]; + for(Edge *e = v->root_edge; e; e = e->next) { + result_edge_occupation[e->id] = e->occupied; + } + } +} + +void find_best_paths(int nb_vertices, + int nb_edges, int *ea, int *eb, scalar_t *el, + int source, int sink, + int *result_edge_occupation) { + Graph graph(nb_vertices, nb_edges, ea, eb, el, source, sink); + graph.find_best_paths(result_edge_occupation); +} + +void dot_print(int nb_vertices, + int nb_edges, int *ea, int *eb, scalar_t *el, + int source, int sink, + int *edge_occupation) { + cout << "digraph {" << endl; + cout << " node[shape=circle];" << endl; + for(int e = 0; e < nb_edges; e++) { + if(edge_occupation[e]) { + cout << " " << ea[e] << " -> " << eb[e] << " [style=bold,color=black,label=\"" << el[e] << "\"];" << endl; + } else { + cout << " " << ea[e] << " -> " << eb[e] << " [color=gray,label=\"" << el[e] << "\"];" << endl; + } + } + cout << "}" << endl; } ////////////////////////////////////////////////////////////////////// @@ -315,32 +305,29 @@ int main(int argc, char **argv) { (*file) >> nb_vertices >> nb_edges; (*file) >> source >> sink; - // cout << "INPUT nb_edges " << nb_edges << endl; - // cout << "INPUT nb_vertices " << nb_vertices << endl; - // cout << "INPUT source " << source << endl; - // cout << "INPUT sink " << sink << endl; - - scalar_t *el = new scalar_t[nb_edges]; - int *ea = new int[nb_edges]; - int *eb = new int[nb_edges]; + scalar_t *edge_lengths = new scalar_t[nb_edges]; + int *vertex_from = new int[nb_edges]; + int *vertex_to = new int[nb_edges]; + int *result_edge_occupation = new int[nb_edges]; for(int e = 0; e < nb_edges; e++) { - (*file) >> ea[e] >> eb[e] >> el[e]; + (*file) >> vertex_from[e] >> vertex_to[e] >> edge_lengths[e]; } - // for(int e = 0; e < nb_edges; e++) { - // cout << "INPUT_EDGE " << ea[e] << " " << eb[e] << " " << el[e] << endl; - // } - - Graph graph(nb_vertices, nb_edges, ea, eb, el, source, sink); + find_best_paths(nb_vertices, nb_edges, + vertex_from, vertex_to, edge_lengths, + source, sink, + result_edge_occupation); - graph.find_best_paths(); - // graph.print_occupied_edges(); - graph.dot_print(); + dot_print(nb_vertices, nb_edges, + vertex_from, vertex_to, edge_lengths, + source, sink, + result_edge_occupation); - delete[] el; - delete[] ea; - delete[] eb; + delete[] result_edge_occupation; + delete[] edge_lengths; + delete[] vertex_from; + delete[] vertex_to; } else { -- 2.39.5