From 3ac56b682d7afe7700964639968cd0554e45e8b3 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Tue, 21 Aug 2012 15:26:29 -0700 Subject: [PATCH] Update. --- Makefile | 6 ++++- mtp.cc | 25 +++++++++++++------- random-graph.cc | 62 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 84 insertions(+), 9 deletions(-) create mode 100644 random-graph.cc diff --git a/Makefile b/Makefile index 38d5110..5f2807e 100644 --- a/Makefile +++ b/Makefile @@ -35,11 +35,15 @@ endif CXXFLAGS = -Wall -I/usr/include/cairo $(OPTIMIZE_FLAG) $(PROFILE_FLAG) $(CXXGLPK) -all: mtp +all: mtp random-graph TAGS: *.cc *.h etags --members -l c++ *.cc *.h +random-graph: \ + random-graph.o + $(CXX) $(CXXFLAGS) -o $@ $^ $(LDFLAGS) + mtp: \ mtp.o $(CXX) $(CXXFLAGS) -o $@ $^ $(LDFLAGS) diff --git a/mtp.cc b/mtp.cc index b400650..88e6557 100644 --- a/mtp.cc +++ b/mtp.cc @@ -22,7 +22,7 @@ // EXAMPLE: ./mtp ./graph2.txt | dot -T pdf -o- | xpdf - -// #define VERBOSE +#define VERBOSE #include #include @@ -167,16 +167,25 @@ void Graph::find_shortest_path(Vertex **front, Vertex **new_front) { Vertex *v, *tv; scalar_t d; +#ifdef VERBOSE + cout << "find_shortest_path" << endl; +#endif + #ifdef DEBUG + scalar_t residual_error = 0.0; +#endif for(int n = 0; n < nb_vertices; n++) { for(Edge *e = vertices[n].root_edge; e; e = e->next) { if(e->work_length < 0) { - cerr << "DEBUG error in find_shortest_path: Edge work lengths have to be positive." - << endl; - abort(); +#ifdef DEBUG + residual_error -= e->work_length; +#endif + e->work_length = 0.0; } } } +#ifdef DEBUG + cout << "DEBUG residual_error " << residual_error << endl; #endif for(int v = 0; v < nb_vertices; v++) { @@ -327,10 +336,10 @@ int main(int argc, char **argv) { source, sink, result_edge_occupation); - dot_print(nb_vertices, nb_edges, - vertex_from, vertex_to, edge_lengths, - source, sink, - result_edge_occupation); + // dot_print(nb_vertices, nb_edges, + // vertex_from, vertex_to, edge_lengths, + // source, sink, + // result_edge_occupation); delete[] result_edge_occupation; delete[] edge_lengths; diff --git a/random-graph.cc b/random-graph.cc new file mode 100644 index 0000000..9d9409a --- /dev/null +++ b/random-graph.cc @@ -0,0 +1,62 @@ + +//////////////////////////////////////////////////////////////////// +// START_IP_HEADER // +// // +// Written by Francois Fleuret // +// Contact for comments & bug reports // +// // +// END_IP_HEADER // +//////////////////////////////////////////////////////////////////// + +#include +#include +#include +#include +#include + +using namespace std; + +int main(int argc, char **argv) { + int nb_locations = 20; + int nb_time_steps = 20; + + int nb_vertices = nb_time_steps * nb_locations + 2; + int nb_edges = 2 * nb_locations + (nb_time_steps - 1) * (nb_locations * nb_locations); + int source = 0; + int sink = nb_vertices - 1; + + cout << nb_vertices << " " << nb_edges << endl; + cout << source << " " << sink << endl; + cout << endl; + + for(int l = 0; l < nb_locations; l++) { + cout << source + << " " + << l + 1 + << " " + << drand48() * 2 - 1 + << endl; + } + + for(int t = 0; t < nb_time_steps - 1; t++) { + for(int l = 0; l < nb_locations; l++) { + for(int m = 0; m < nb_locations; m++) { + cout << 1 + (t * nb_locations + l) + << " " + << 1 + ((t+1) * nb_locations + m) + << " " + << drand48() * 2 - 1 + << endl; + } + } + } + + for(int l = 0; l < nb_locations; l++) { + cout << 1 + ((nb_time_steps-1) * nb_locations + l) + << " " + << sink + << " " + << drand48() * 2 - 1 + << endl; + } +} -- 2.39.5