From: Francois Fleuret Date: Tue, 21 Aug 2012 19:54:58 +0000 (-0700) Subject: Initial commit. X-Git-Url: https://www.fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=mtp.git;a=commitdiff_plain;h=cc12bb0e70079b8bad11d22282c3e662913034f6 Initial commit. --- diff --git a/ksp.cc b/ksp.cc new file mode 100644 index 0000000..c40856f --- /dev/null +++ b/ksp.cc @@ -0,0 +1,313 @@ + +/////////////////////////////////////////////////////////////////////////// +// 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 + +class Vertex; + +class Edge { +public: + int occupied; + scalar_t length, fixed_length; + Vertex *terminal_vertex; + Edge *next, *pred; +}; + +class Vertex { +public: + // These are the leaving edges + Edge *first_edge; + scalar_t distance; + + Vertex *pred_vertex; + Edge *pred_edge; + + Vertex() { first_edge = 0; } + + inline void add_edge(Edge *e) { + if(first_edge) { first_edge->pred = e; } + e->next = first_edge; + e->pred = 0; + first_edge = e; + } + + inline void del_edge(Edge *e) { + if(e == first_edge) { first_edge = e->next; } + if(e->pred) { e->pred->next = e->next; } + if(e->next) { e->next->pred = e->pred; } + } +}; + +class Graph { +public: + int nb_vertices; + Edge *edge_heap; + Vertex *vertices; + Vertex *source, *sink; + + Graph(int nb_vertices, int nb_edges, int *from, int *to, scalar_t *lengths, + int source, int sink); + ~Graph(); + + void initialize_fixed_lengths(); + void update_fixed_length(); + void find_shortest_path(); + void find_best_paths(); + void print(); +}; + +void Graph::print() { + for(int n = 0; n < nb_vertices; n++) { + cout << "VERTEX [" << n << "] "; + for(Edge *e = vertices[n].first_edge; e; e = e->next) { + cout << " " << e->length; + } + cout << endl; + } +} + +Graph::Graph(int nb_vrt, int nb_edges, + int *from, int *to, scalar_t *lengths, + int src, int snk) { + nb_vertices = nb_vrt; + + edge_heap = new Edge[nb_edges]; + vertices = new Vertex[nb_vertices]; + + source = &vertices[src]; + sink = &vertices[snk]; + + for(int e = 0; e < nb_edges; e++) { + vertices[from[e]].add_edge(&edge_heap[e]); + edge_heap[e].occupied = 0; + edge_heap[e].length = lengths[e]; + edge_heap[e].terminal_vertex = &vertices[to[e]]; + } +} + +Graph::~Graph() { + delete[] vertices; + delete[] edge_heap; +} + +void Graph::initialize_fixed_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) { + 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) { + e->fixed_length = e->length - length_min; + } + } +} + +void Graph::update_fixed_length() { + for(int n = 0; n < nb_vertices; n++) { + scalar_t d = vertices[n].distance; + for(Edge *e = vertices[n].first_edge; e; e = e->next) { + e->fixed_length += d - e->terminal_vertex->distance; + } + } +} + +void Graph::find_shortest_path() { + Vertex **front = new Vertex *[nb_vertices]; + Vertex **new_front = new Vertex *[nb_vertices]; + Vertex **tmp_front; + int tmp_front_size; + Vertex *v, *tv; + scalar_t d; + +#ifdef DEBUG + for(int n = 0; n < nb_vertices; n++) { + for(Edge *e = vertices[n].first_edge; e; e = e->next) { + if(e->fixed_length < 0) { + cerr << "DEBUG error in find_shortest_path: Edge fixed lengths have to be positive." + << endl; + abort(); + } + } + } +#endif + + for(int v = 0; v < nb_vertices; v++) { + vertices[v].distance = FLT_MAX; + vertices[v].pred_vertex = 0; + vertices[v].pred_edge = 0; + } + + int front_size = 0, new_front_size; + front[front_size++] = source; + source->distance = 0; + + do { + 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) { + d = v->distance + e->fixed_length; + tv = e->terminal_vertex; + if(d < tv->distance) { + tv->distance = d; + tv->pred_vertex = v; + tv->pred_edge = e; + new_front[new_front_size++] = tv; + } + } + } + + tmp_front = new_front; + new_front = front; + front = tmp_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); + + delete[] front; + delete[] new_front; +} + +void Graph::find_best_paths() { + scalar_t total_length; + + initialize_fixed_lengths(); + + do { + print(); + + total_length = 0.0; + find_shortest_path(); + update_fixed_length(); + + // Do we reach the sink? + if(sink->pred_edge) { + +#ifdef VERBOSE + cout << "VERBOSE there is a path reaching the sink" << endl; +#endif + + // If yes, compute the length of the best path + for(Vertex *v = sink; v->pred_edge; v = v->pred_vertex) { + total_length += v->pred_edge->length; + } + +#ifdef VERBOSE + cout << "VERBOSE total_length " << total_length << endl; +#endif + + // If that length is negative + if(total_length < 0.0) { + // 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->fixed_length = - e->fixed_length; + v->pred_vertex->del_edge(e); + v->add_edge(e); + cout << "INVERT!" << endl; + } + } + } + } while(total_length < 0.0); +} + +////////////////////////////////////////////////////////////////////// + +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]; + + 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; + } + + Graph graph(nb_vertices, nb_edges, ea, eb, el, source, sink); + + graph.find_best_paths(); + + delete[] el; + delete[] ea; + delete[] eb; + + } else { + + cerr << "Can not open " << argv[1] << endl; + + delete file; + exit(EXIT_FAILURE); + + } + + delete file; + exit(EXIT_SUCCESS); +}