bigworld

commit dc5c5b815c865a0e9053417fc78ee93147e3d7bf
parent f4ffc500c2d246399433221904b6ab74cbacf4a9
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 20 May 2015 23:53:51 +0200

comments and tests

Diffstat:
smallworld.cpp
 | 
5
+++++
smallworld.sh
 | 
4
++--

2 files changed, 7 insertions(+), 2 deletions(-)
diff --git a/smallworld.cpp b/smallworld.cpp
@@ -27,6 +27,8 @@ inline int regcode(string s) {
 }
 
 // if passed an argument, do the transitive closure
+// algo is Floyd-Warshall with path reconstruction
+// https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction
 int main(int argc, char **argv) {
   for (unsigned int i = 0; i < NMAX; i++)
     for (unsigned int j = 0; j < NMAX; j++) {
@@ -42,6 +44,7 @@ int main(int argc, char **argv) {
     cin >> fs >> ts;
     int f = regcode(fs), t = regcode(ts);
     assert(f < NMAX && t < NMAX && a < MULTI);
+    assert(a != 0);
     airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a;
     d[f][t] = 1;
     nx[f][t] = t;
@@ -54,9 +57,11 @@ int main(int argc, char **argv) {
         fprintf(stderr, "closing: %d of %d\n", k, n);
       for (unsigned int i = 0; i < n; i++)
         for (unsigned int j = 0; j < n; j++)
+          // if both have edges with same non-multi airline then close
           if (d[i][k] == 1 && d[k][j] == 1 && airline[i][k] == airline[k][j]
               && airline[i][k] != MULTI) {
             d[i][j] = 1;
+            // add airline to new edge, can make it MULTI
             airline[i][j] = (airline[i][j] && airline[i][j] != airline[i][k]) ? MULTI : airline[i][k];
             nx[i][j] = j;
           }
diff --git a/smallworld.sh b/smallworld.sh
@@ -31,6 +31,6 @@ join routesb.dat active.dat |
   } }' > routesc.dat
 
 g++ -Wall -o smallworld -O3 smallworld.cpp
-./smallworld close < routesc.dat > pairs.out
-./smallworld < routesc.dat > pairs_close.out
+./smallworld close < routesc.dat | tee pairs.out
+./smallworld < routesc.dat | tee pairs_close.out