miniksp.cc

   1
   2 ////////////////////////////////////////////////////////////////////
   3 // START_IP_HEADER                                                //
   4 //                                                                //
   5 // Written by Francois Fleuret                                    //
   6 // Contact <francois.fleuret@idiap.ch> for comments & bug reports //
   7 //                                                                //
   8 // END_IP_HEADER                                                  //
   9 ////////////////////////////////////////////////////////////////////
  10
  11 #include <iostream>
  12 #include <fstream>
  13 #include <cmath>
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <float.h>
  17
  18 using namespace std;
  19
  20 typedef float scalar_t;
  21
  22 #ifdef DEBUG
  23 #define ASSERT(x) if(!(x)) { \
  24   std::cerr << "ASSERT FAILED IN " << __FILE__ << ":" << __LINE__ << endl; \
  25   abort(); \
  26 }
  27 #else
  28 #define ASSERT(x)
  29 #endif
  30
  31 void raise_es(int nb_edges, scalar_t *es) {
  32   scalar_t min_es = es[0];
  33   for(int e = 1; e < nb_edges; e++) {
  34     min_es = min(min_es, es[e]);
  35   }
  36   for(int e = 0; e < nb_edges; e++) {
  37     es[e] -= min_es;
  38   }
  39 }
  40
  41 void add_dpsi_es(int nb_edges, scalar_t *es, int *ea, int *eb, scalar_t *psi) {
  42   for(int e = 0; e < nb_edges; e++) {
  43     es[e] += psi[ea[e]] - psi[eb[e]];
  44   }
  45 }
  46
  47 void find_shortest(int nb_vertices,
  48                    int nb_edges, scalar_t *es, int *ea, int *eb,
  49                    int source, int sink,
  50                    int *pred, scalar_t *dist) {
  51   for(int v = 0; v < nb_vertices; v++) {
  52     dist[v] = FLT_MAX;
  53   }
  54
  55   dist[source] = 0;
  56
  57   for(int e = 0; e < nb_edges; e++) {
  58     pred[e] = -1;
  59   }
  60
  61   int nb_changes;
  62   scalar_t d;
  63   do {
  64     nb_changes = 0;
  65     for(int e = 0; e < nb_edges; e++) {
  66       d = dist[ea[e]] + es[e];
  67       if(d < dist[eb[e]]) {
  68         nb_changes++;
  69         dist[eb[e]] = d;
  70         pred[eb[e]] = ea[e];
  71       }
  72     }
  73   } while(nb_changes > 0);
  74
  75   ASSERT(pred[sink] >= 0);
  76 }
  77
  78 void find_best_paths(int nb_vertices,
  79                      int nb_edges, scalar_t *es, int *ea, int *eb,
  80                      int source, int sink) {
  81   scalar_t *dist = new scalar_t[nb_vertices];
  82   int *pred = new int[nb_vertices];
  83
  84   raise_es(nb_edges, es);
  85
  86   do {
  87     find_shortest(nb_vertices, nb_edges, es, ea, eb, source, sink, dist, pred);
  88     add_dpsi_es(nb_edges, es, ea, eb, dist);
  89     for(int v = 0; v < nb_edges; v++) {
  90
  91     }
  92   } while();
  93
  94   delete[] dist;
  95   delete[] pred;
  96 }
  97
  98 int main(int argc, char **argv) {
  99   int nb_time_steps = 4;
 100   int nb_locations = 10;
 101   int nb_neighbors = 3;
 102   // Add the source and sink
 103   int nb_vertices = nb_time_steps * nb_locations + 2;
 104   int nb_edges = nb_locations + (nb_time_steps - 1) * nb_locations
 105 }