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++) {
65 for(int e = 0; e < nb_edges; e++) {
66 d = dist[ea[e]] + es[e];
73 } while(nb_changes > 0);
75 ASSERT(pred[sink] >= 0);
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];
84 raise_es(nb_edges, es);
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++) {
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