+
+////////////////////////////////////////////////////////////////////
+// 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
+}