2 ////////////////////////////////////////////////////////////////////
5 // Written by Francois Fleuret //
6 // Contact <francois.fleuret@idiap.ch> for comments & bug reports //
9 ////////////////////////////////////////////////////////////////////
20 typedef float scalar_t;
23 #define ASSERT(x) if(!(x)) { \
24 std::cerr << "ASSERT FAILED IN " << __FILE__ << ":" << __LINE__ << endl; \
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]);
36 for(int e = 0; e < nb_edges; e++) {
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]];
47 void find_shortest(int nb_vertices,
48 int nb_edges, scalar_t *es, int *ea, int *eb,
50 int *pred, scalar_t *dist) {
51 for(int v = 0; v < nb_vertices; v++) {
57 for(int e = 0; e < nb_edges; e++) {
66 for(int e = 0; e < nb_edges; e++) {
67 d = dist[ea[e]] + es[e];
74 } while(nb_changes > 0);
76 ASSERT(pred[sink] >= 0);
79 void find_best_paths(int nb_vertices,
80 int nb_edges, scalar_t *es, int *ea, int *eb,
81 int source, int sink) {
82 scalar_t *dist = new scalar_t[nb_vertices];
83 int *pred = new int[nb_vertices];
85 raise_es(nb_edges, es);
89 find_shortest(nb_vertices, nb_edges, es, ea, eb, source, sink, pred, dist);
90 add_dpsi_es(nb_edges, es, ea, eb, dist);
92 for(int e = 0; e < nb_edges; e++) {
93 if(pred[eb[e]] == ea[e]) {
107 int main(int argc, char **argv) {
108 ifstream file(argv[1]);
109 int nb_edges, nb_vertices;
113 file >> nb_vertices >> nb_edges;
114 file >> source >> sink;
117 cout << "nb_edges = " << nb_edges << endl;
118 cout << "nb_vertices = " << nb_vertices << endl;
119 cout << "source = " << source << endl;
120 cout << "sink = " << sink << endl;
122 scalar_t *es = new scalar_t[nb_edges];
123 int *ea = new int[nb_edges];
124 int *eb = new int[nb_edges];
126 for(int e = 0; e < nb_edges; e++) {
127 file >> ea[e] >> eb[e] >> es[e];
128 cout << ea[e] << " -> " << eb[e] << " [" << es[e] << "]" << endl;