projects
/
mtp.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
82e08a1
)
Added comments.
author
Francois Fleuret
<francois@fleuret.org>
Tue, 21 Aug 2012 04:00:24 +0000
(21:00 -0700)
committer
Francois Fleuret
<francois@fleuret.org>
Tue, 21 Aug 2012 04:00:24 +0000
(21:00 -0700)
miniksp.cc
patch
|
blob
|
history
diff --git
a/miniksp.cc
b/miniksp.cc
index
4ec9423
..
0598afe
100644
(file)
--- a/
miniksp.cc
+++ b/
miniksp.cc
@@
-20,7
+20,7
@@
// END_IP_HEADER //
///////////////////////////////////////////////////////////////////////////
// END_IP_HEADER //
///////////////////////////////////////////////////////////////////////////
-
//
#define VERBOSE
+#define VERBOSE
#include <iostream>
#include <fstream>
#include <iostream>
#include <fstream>
@@
-42,6
+42,12
@@
typedef float scalar_t;
#define ASSERT(x)
#endif
#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) {
// 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]];
}
}
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.
+// Find
s 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,
void find_shortest(int nb_vertices,
int nb_edges, scalar_t *el, int *ea, int *eb,
int source, int sink,
- int *re
turn_edge_back, scalar_t *return
_dist) {
+ int *re
sult_edge_back, scalar_t *result
_dist) {
for(int v = 0; v < nb_vertices; v++) {
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++) {
#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++) {
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++;
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);
}
}
}
} 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,
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];
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];
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);
}
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
}
// 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;
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];
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);
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;
for(int e = 0; e < nb_edges; e++) {
if(edge_occupation[e]) {
cout << "RESULT_OCCUPIED_EDGE " << ea[e] << " " << eb[e] << endl;