From 425acf9068dac38bccb97b12f1b423db5787e294 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Tue, 21 Aug 2012 13:45:32 -0700 Subject: [PATCH] Renamed from KSP to MTP (Multi-tracked paths) --- Makefile | 8 ++++++-- ksp.cc => mtp.cc | 30 ++++++++++++++---------------- 2 files changed, 20 insertions(+), 18 deletions(-) rename ksp.cc => mtp.cc (90%) diff --git a/Makefile b/Makefile index be7e0a9..d7c5225 100644 --- a/Makefile +++ b/Makefile @@ -35,11 +35,15 @@ endif CXXFLAGS = -Wall -I/usr/include/cairo $(OPTIMIZE_FLAG) $(PROFILE_FLAG) $(CXXGLPK) -all: miniksp +all: mtp miniksp TAGS: *.cc *.h etags --members -l c++ *.cc *.h +mtp: \ + mtp.o + $(CXX) $(CXXFLAGS) -o $@ $^ $(LDFLAGS) + miniksp: \ miniksp.o $(CXX) $(CXXFLAGS) -o $@ $^ $(LDFLAGS) @@ -48,6 +52,6 @@ Makefile.depend: *.h *.cc Makefile $(CC) $(CXXFLAGS) -M *.cc > Makefile.depend clean: - \rm -f miniksp *.o Makefile.depend TAGS + \rm -f mtp miniksp *.o Makefile.depend TAGS -include Makefile.depend diff --git a/ksp.cc b/mtp.cc similarity index 90% rename from ksp.cc rename to mtp.cc index 1e55a33..529ba80 100644 --- a/ksp.cc +++ b/mtp.cc @@ -1,7 +1,5 @@ /////////////////////////////////////////////////////////////////////////// -// 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. // @@ -16,10 +14,10 @@ // // // Written by and Copyright (C) Francois Fleuret // // Contact for comments & bug reports // -// // -// END_IP_HEADER // /////////////////////////////////////////////////////////////////////////// +// Multi-Tracked Path + // #define VERBOSE #include @@ -47,7 +45,7 @@ class Vertex; class Edge { public: int occupied; - scalar_t length, fixed_length; + scalar_t length, work_length; Vertex *terminal_vertex; Edge *next, *pred; }; @@ -89,8 +87,8 @@ public: int source, int sink); ~Graph(); - void initialize_fixed_lengths(); - void update_fixed_length(); + void initialize_work_lengths(); + void update_work_length(); void find_shortest_path(); void find_best_paths(); void print(); @@ -145,7 +143,7 @@ Graph::~Graph() { delete[] edge_heap; } -void Graph::initialize_fixed_lengths() { +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) { @@ -154,16 +152,16 @@ void Graph::initialize_fixed_lengths() { } 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; + e->work_length = e->length - length_min; } } } -void Graph::update_fixed_length() { +void Graph::update_work_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; + e->work_length += d - e->terminal_vertex->distance; } } } @@ -179,7 +177,7 @@ void Graph::find_shortest_path() { #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) { + if(e->work_length < 0) { cerr << "DEBUG error in find_shortest_path: Edge fixed lengths have to be positive." << endl; abort(); @@ -203,7 +201,7 @@ void Graph::find_shortest_path() { 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; + d = v->distance + e->work_length; tv = e->terminal_vertex; if(d < tv->distance) { tv->distance = d; @@ -230,7 +228,7 @@ void Graph::find_shortest_path() { void Graph::find_best_paths() { scalar_t total_length; - initialize_fixed_lengths(); + initialize_work_lengths(); do { #ifdef VERBOSE @@ -239,7 +237,7 @@ void Graph::find_best_paths() { total_length = 0.0; find_shortest_path(); - update_fixed_length(); + update_work_length(); // Do we reach the sink? if(sink->pred_edge) { @@ -265,7 +263,7 @@ void Graph::find_best_paths() { e->terminal_vertex = v->pred_vertex; e->occupied = 1 - e->occupied; e->length = - e->length; - e->fixed_length = - e->fixed_length; + e->work_length = - e->work_length; v->pred_vertex->del_edge(e); v->add_edge(e); } -- 2.39.5