From 0428b7ae98e49c2ed98a24868f4ca2da8f3ab6e6 Mon Sep 17 00:00:00 2001
From: Francois Fleuret <francois@fleuret.org>
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 <http://www.gnu.org/licenses/>.  #
+# 								        #
+# Written by Francois Fleuret			                        #
+# Copyright (C) Idiap Research Institute                                #
+# Contact <francois.fleuret@idiap.ch> 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 <francois.fleuret@idiap.ch> for comments & bug reports //
+//                                                                //
+// END_IP_HEADER                                                  //
+////////////////////////////////////////////////////////////////////
+
+#include <iostream>
+#include <fstream>
+#include <cmath>
+#include <stdio.h>
+#include <stdlib.h>
+#include <float.h>
+
+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