X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?a=blobdiff_plain;f=miniksp.cc;h=513da0e0ce5b3ebfdbff4a0ff7dfefbeb8fd3aa9;hb=b6200435a7d9cabb7d2616f603846d99b2805a97;hp=c6e83542004b49fc542b5928e8bbf32d660e8965;hpb=0428b7ae98e49c2ed98a24868f4ca2da8f3ab6e6;p=mtp.git

diff --git a/miniksp.cc b/miniksp.cc
index c6e8354..513da0e 100644
--- a/miniksp.cc
+++ b/miniksp.cc
@@ -56,6 +56,7 @@ void find_shortest(int nb_vertices,
 
   for(int e = 0; e < nb_edges; e++) {
     pred[e] = -1;
+    ASSERT(se[e] >= 0);
   }
 
   int nb_changes;
@@ -83,23 +84,51 @@ void find_best_paths(int nb_vertices,
 
   raise_es(nb_edges, es);
 
+  scalar_t s;
   do {
-    find_shortest(nb_vertices, nb_edges, es, ea, eb, source, sink, dist, pred);
+    find_shortest(nb_vertices, nb_edges, es, ea, eb, source, sink, pred, dist);
     add_dpsi_es(nb_edges, es, ea, eb, dist);
-    for(int v = 0; v < nb_edges; v++) {
-      
+    s = 0.0;
+    for(int e = 0; e < nb_edges; e++) {
+      if(pred[eb[e]] == ea[e]) {
+        s += es[e];
+        int k = eb[e];
+        eb[e] = ea[e];
+        ea[e] = k;
+        es[e] = - es[e];
+      }
     }
-  } while();
+  } while(s < 0);
 
   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 
+  ifstream file(argv[1]);
+  int nb_edges, nb_vertices;
+  int source, sink;
+
+  if(file.good()) {
+    file >> nb_vertices >> nb_edges;
+    file >> source >> sink;
+  }
+
+  cout << "nb_edges = " << nb_edges << endl;
+  cout << "nb_vertices = " << nb_vertices << endl;
+  cout << "source = " << source << endl;
+  cout << "sink = " << sink << endl;
+
+  scalar_t *es = new scalar_t[nb_edges];
+  int *ea = new int[nb_edges];
+  int *eb = new int[nb_edges];
+
+  for(int e = 0; e < nb_edges; e++) {
+    file >> ea[e] >> eb[e] >> es[e];
+    cout << ea[e] << " -> " << eb[e] << " [" << es[e] << "]" << endl;
+  }
+
+  delete[] es;
+  delete[] ea;
+  delete[] eb;
 }