From 6da7394e095ec264738cd222b75dab01af453d8c Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Mon, 20 Aug 2012 21:00:24 -0700 Subject: [PATCH] Added comments. --- miniksp.cc | 58 +++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 40 insertions(+), 18 deletions(-) diff --git a/miniksp.cc b/miniksp.cc index 4ec9423..0598afe 100644 --- a/miniksp.cc +++ b/miniksp.cc @@ -20,7 +20,7 @@ // END_IP_HEADER // /////////////////////////////////////////////////////////////////////////// -// #define VERBOSE +#define VERBOSE #include #include @@ -42,6 +42,12 @@ typedef float scalar_t; #define ASSERT(x) #endif +// In all the code: +// +// * el[e] is the length of edge e +// * ea[e] is its starting node +// * eb[e] is its destination node. + // Adds to all the edge length the length of the shortest (which can // be negative) void raise_es(int nb_edges, scalar_t *el) { @@ -54,27 +60,28 @@ void raise_es(int nb_edges, scalar_t *el) { } } -// Add to every edge length the differential of the psi function on it +// Adds to every edge length the differential of the psi function on +// it void add_dpsi_es(int nb_edges, scalar_t *el, int *ea, int *eb, scalar_t *psi) { for(int e = 0; e < nb_edges; e++) { el[e] += psi[ea[e]] - psi[eb[e]]; } } -// Find the shortest path in the graph and return in return_edge_back, -// for each vertex the edge to follow back from it to reach the source -// with the shortest path, and in return_dist the distance to the -// source. The edge lengths have to be positive. +// Finds the shortest path in the graph and return in +// result_edge_back, for each vertex the edge to follow back from it +// to reach the source with the shortest path, and in result_dist the +// distance to the source. The edge lengths have to be positive. void find_shortest(int nb_vertices, int nb_edges, scalar_t *el, int *ea, int *eb, int source, int sink, - int *return_edge_back, scalar_t *return_dist) { + int *result_edge_back, scalar_t *result_dist) { for(int v = 0; v < nb_vertices; v++) { - dist[v] = FLT_MAX; - edge_back[v] = -1; + result_dist[v] = FLT_MAX; + result_edge_back[v] = -1; } - dist[source] = 0; + result_dist[source] = 0; #ifdef DEBUG for(int e = 0; e < nb_edges; e++) { @@ -87,20 +94,23 @@ void find_shortest(int nb_vertices, do { nb_changes = 0; for(int e = 0; e < nb_edges; e++) { - d = dist[ea[e]] + el[e]; - if(d < dist[eb[e]]) { + d = result_dist[ea[e]] + el[e]; + if(d < result_dist[eb[e]]) { nb_changes++; - dist[eb[e]] = d; - edge_back[eb[e]] = e; + result_dist[eb[e]] = d; + result_edge_back[eb[e]] = e; } } } while(nb_changes > 0); } +// Iterates find_shortest as long as it finds paths of negative +// lengths. Notes which edges are occupied by the superposition of +// paths in result_edge_occupation void find_best_paths(int nb_vertices, int nb_edges, scalar_t *el, int *ea, int *eb, int source, int sink, - int *edge_occupation) { + int *result_edge_occupation) { scalar_t *dist = new scalar_t[nb_vertices]; int *edge_back = new int[nb_vertices]; scalar_t *positive_el = new scalar_t[nb_edges]; @@ -109,7 +119,7 @@ void find_best_paths(int nb_vertices, for(int e = 0; e < nb_edges; e++) { positive_el[e] = el[e]; - edge_occupation[e] = 0; + result_edge_occupation[e] = 0; } raise_es(nb_edges, positive_el); @@ -133,7 +143,8 @@ void find_best_paths(int nb_vertices, } // We found a good path (score < 0), we revert the edges along - // the path and note that they are occupied + // the path and invert their occupation (since adding a path on + // a path already occupied means removing flow on it) if(s < 0) { v = sink; @@ -152,7 +163,7 @@ void find_best_paths(int nb_vertices, ea[e] = k; positive_el[e] = - positive_el[e]; el[e] = - el[e]; - edge_occupation[e] = 1 - edge_occupation[e]; + result_edge_occupation[e] = 1 - result_edge_occupation[e]; } } } @@ -198,6 +209,17 @@ int main(int argc, char **argv) { find_best_paths(nb_vertices, nb_edges, el, ea, eb, source, sink, edge_occupation); +#ifdef VERBOSE + // Sanity check on the overall resulting score (the edge lengths + // have been changed, hence should be the opposite of the sum of + // the path lengths) + scalar_t s = 0; + for(int e = 0; e < nb_edges; e++) { + if(edge_occupation[e]) s += el[e]; + } + cout << "RESULT_SANITY_CHECK_SCORE " << s << endl; +#endif + for(int e = 0; e < nb_edges; e++) { if(edge_occupation[e]) { cout << "RESULT_OCCUPIED_EDGE " << ea[e] << " " << eb[e] << endl; -- 2.39.5