From 0428b7ae98e49c2ed98a24868f4ca2da8f3ab6e6 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Mon, 20 Aug 2012 16:49:50 -0700 Subject: [PATCH 1/1] Initial commit --- Makefile | 53 +++++++++++++++++++++++++++ miniksp.cc | 105 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 158 insertions(+) create mode 100644 Makefile create mode 100644 miniksp.cc diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..be7e0a9 --- /dev/null +++ b/Makefile @@ -0,0 +1,53 @@ + +######################################################################### +# 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 Francois Fleuret # +# Copyright (C) Idiap Research Institute # +# Contact for comments & bug reports # +######################################################################### + +ifeq ($(STATIC),yes) + LDFLAGS=-static -lm -ljpeg -lpng -lz -lcairo +else + LDFLAGS=-lm -ljpeg -lpng -lcairo +endif + +ifeq ($(DEBUG),yes) + OPTIMIZE_FLAG = -ggdb3 -DDEBUG -fno-omit-frame-pointer +else + OPTIMIZE_FLAG = -ggdb3 -O3 +endif + +ifeq ($(PROFILE),yes) + PROFILE_FLAG = -pg +endif + +CXXFLAGS = -Wall -I/usr/include/cairo $(OPTIMIZE_FLAG) $(PROFILE_FLAG) $(CXXGLPK) + +all: miniksp + +TAGS: *.cc *.h + etags --members -l c++ *.cc *.h + +miniksp: \ + miniksp.o + $(CXX) $(CXXFLAGS) -o $@ $^ $(LDFLAGS) + +Makefile.depend: *.h *.cc Makefile + $(CC) $(CXXFLAGS) -M *.cc > Makefile.depend + +clean: + \rm -f miniksp *.o Makefile.depend TAGS + +-include Makefile.depend diff --git a/miniksp.cc b/miniksp.cc new file mode 100644 index 0000000..c6e8354 --- /dev/null +++ b/miniksp.cc @@ -0,0 +1,105 @@ + +//////////////////////////////////////////////////////////////////// +// START_IP_HEADER // +// // +// Written by Francois Fleuret // +// Contact for comments & bug reports // +// // +// END_IP_HEADER // +//////////////////////////////////////////////////////////////////// + +#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 + +void raise_es(int nb_edges, scalar_t *es) { + scalar_t min_es = es[0]; + for(int e = 1; e < nb_edges; e++) { + min_es = min(min_es, es[e]); + } + for(int e = 0; e < nb_edges; e++) { + es[e] -= min_es; + } +} + +void add_dpsi_es(int nb_edges, scalar_t *es, int *ea, int *eb, scalar_t *psi) { + for(int e = 0; e < nb_edges; e++) { + es[e] += psi[ea[e]] - psi[eb[e]]; + } +} + +void find_shortest(int nb_vertices, + int nb_edges, scalar_t *es, int *ea, int *eb, + int source, int sink, + int *pred, scalar_t *dist) { + for(int v = 0; v < nb_vertices; v++) { + dist[v] = FLT_MAX; + } + + dist[source] = 0; + + for(int e = 0; e < nb_edges; e++) { + pred[e] = -1; + } + + int nb_changes; + scalar_t d; + do { + nb_changes = 0; + for(int e = 0; e < nb_edges; e++) { + d = dist[ea[e]] + es[e]; + if(d < dist[eb[e]]) { + nb_changes++; + dist[eb[e]] = d; + pred[eb[e]] = ea[e]; + } + } + } while(nb_changes > 0); + + ASSERT(pred[sink] >= 0); +} + +void find_best_paths(int nb_vertices, + int nb_edges, scalar_t *es, int *ea, int *eb, + int source, int sink) { + scalar_t *dist = new scalar_t[nb_vertices]; + int *pred = new int[nb_vertices]; + + raise_es(nb_edges, es); + + do { + find_shortest(nb_vertices, nb_edges, es, ea, eb, source, sink, dist, pred); + add_dpsi_es(nb_edges, es, ea, eb, dist); + for(int v = 0; v < nb_edges; v++) { + + } + } while(); + + delete[] dist; + delete[] pred; +} + +int main(int argc, char **argv) { + int nb_time_steps = 4; + int nb_locations = 10; + int nb_neighbors = 3; + // Add the source and sink + int nb_vertices = nb_time_steps * nb_locations + 2; + int nb_edges = nb_locations + (nb_time_steps - 1) * nb_locations +} -- 2.39.5