for(int e = 0; e < nb_edges; e++) {
pred[e] = -1;
+ ASSERT(se[e] >= 0);
}
int nb_changes;
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;
}