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 int nb_time_steps = 4;
109 int nb_locations = 5;
110 // Add the source and sink
111 int nb_vertices = nb_time_steps * nb_locations + 2;
112 int nb_edges = nb_locations + (nb_time_steps - 1) * nb_locations * nb_locations + nb_locations;
114 int sink = nb_locations - 1;
115 scalar_t *es = new scalar_t[nb_edges];
116 int *ea = new int[nb_edges];
117 int *eb = new int[nb_edges];