commit 035bbab3e28a1b8483926f19a840710f14f2b0a7
parent 51913afdd8ba6957915521b8625dd85007eed47a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 21 May 2015 22:30:54 +0200
bigworld
Diffstat:
| .gitignore | | | 2 | +- |
| bigworld.cpp | | | 104 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| bigworld.sh | | | 34 | ++++++++++++++++++++++++++++++++++ |
| smallworld.cpp | | | 104 | ------------------------------------------------------------------------------- |
| smallworld.sh | | | 34 | ---------------------------------- |
5 files changed, 139 insertions(+), 139 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -1,4 +1,4 @@
-smallworld
+bigworld
old/*
routes.dat
routesb.dat
diff --git a/bigworld.cpp b/bigworld.cpp
@@ -0,0 +1,104 @@
+#include <assert.h>
+#include <cstdio>
+#include <iostream>
+#include <map>
+#include <string>
+#include <vector>
+
+#define NMAX 3200
+#define INF 20000
+#define MULTI 200000
+#define STEP 50
+
+using namespace std;
+
+int d[NMAX][NMAX];
+int nx[NMAX][NMAX];
+int airline[NMAX][NMAX];
+vector<string> code;
+map<string, int> alias;
+
+inline int regcode(string s) {
+ if (!alias.count(s)) {
+ alias[s] = code.size();
+ code.push_back(s);
+ }
+ return alias[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++) {
+ d[i][j] = (i == j) ? 0 : INF;
+ nx[i][j] = -1;
+ }
+ while (1) {
+ int a;
+ int ret = scanf("%d", &a);
+ if (ret < 1)
+ break;
+ string fs, ts;
+ 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;
+ }
+ unsigned int n = code.size();
+ if (argc >= 2) {
+ // transitive closure within each company on non-MULTI segments
+ for (unsigned int k = 0; k < n; k++) {
+ if (!(k % STEP))
+ 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;
+ }
+ }
+ }
+ for (unsigned int k = 0; k < n; k++) {
+ if (!(k % STEP))
+ fprintf(stderr, "computing: %d of %d\n", k, n);
+ for (unsigned int i = 0; i < n; i++)
+ for (unsigned int j = 0; j < n; j++)
+ if (d[i][j] > d[i][k] + d[k][j]) {
+ d[i][j] = d[i][k] + d[k][j];
+ nx[i][j] = nx[i][k];
+ }
+ }
+ int best = 0;
+ for (unsigned int i = 0; i < n; i++)
+ for (unsigned int j = 0; j < n; j++) {
+ if (d[i][j] == INF)
+ continue;
+ best = max(d[i][j], best);
+ /* if (d[i][j] == best)
+ printf("%d: %s -> %s\n", best, code[i].c_str(), code[j].c_str()); */
+ }
+ for (unsigned int i = 0; i < n; i++)
+ for (unsigned int j = 0; j < n; j++)
+ if (d[i][j] == best) {
+ printf("%d: %s -> %s: ", d[i][j], code[i].c_str(), code[j].c_str());
+ printf("%s ", code[i].c_str());
+ int u = i, v = j;
+ while (u != v) {
+ assert(u >= 0);
+ u = nx[u][v];
+ printf("%s ", code[u].c_str());
+ }
+ printf("\n");
+ }
+ return 0;
+}
+
diff --git a/bigworld.sh b/bigworld.sh
@@ -0,0 +1,34 @@
+#!/bin/bash
+
+if [ ! -f airlines.dat ]
+then
+ wget -O airlines.dat 'https://sourceforge.net/p/openflights/code/HEAD/tree/openflights/data/airlines.dat?format=raw'
+fi
+
+if [ ! -f routes.dat ]
+then
+ wget -O routes.dat 'https://sourceforge.net/p/openflights/code/HEAD/tree/openflights/data/routes.dat?format=raw'
+fi
+
+cut -d ',' -f1,8 airlines.dat | tr -d '"' | tr ',' ' ' > active.dat
+echo "\\N Y" >> active.dat
+# sponge from moreutils
+sort -k1,1 active.dat | sponge active.dat
+
+cut -d, -f2,3,5,7 routes.dat | grep -v 'Y$' | tr ',' ' ' |
+ sort -k1,1 | join - active.dat |
+ grep -v 'N$' | cut -d ' ' -f1-3 > routes_active.dat
+
+sort -k1,1 routes_active.dat |
+ ./number.sh > routes_naive.dat
+cat routes_active.dat <(sed 's/#.*//' routes_add) |
+ sed "`cat changes | sed 's/\(...\) \(...\)/s_\1_\2_g;/'`" |
+ grep -vE `cat forbidden | grep -v '#' | tr '\n' '|' | sed 's/|$//'` |
+ sort -k1,1 |
+ ./number.sh > routes_fix.dat
+
+g++ -Wall -o bigworld -O3 bigworld
+./bigworld < routes_naive.dat | tee pairs_naive.out
+#./bigworld close < routes_fix.dat | tee pairs_close.out
+./bigworld < routes_fix.dat | tee pairs.out
+
diff --git a/smallworld.cpp b/smallworld.cpp
@@ -1,104 +0,0 @@
-#include <assert.h>
-#include <cstdio>
-#include <iostream>
-#include <map>
-#include <string>
-#include <vector>
-
-#define NMAX 3200
-#define INF 20000
-#define MULTI 200000
-#define STEP 50
-
-using namespace std;
-
-int d[NMAX][NMAX];
-int nx[NMAX][NMAX];
-int airline[NMAX][NMAX];
-vector<string> code;
-map<string, int> alias;
-
-inline int regcode(string s) {
- if (!alias.count(s)) {
- alias[s] = code.size();
- code.push_back(s);
- }
- return alias[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++) {
- d[i][j] = (i == j) ? 0 : INF;
- nx[i][j] = -1;
- }
- while (1) {
- int a;
- int ret = scanf("%d", &a);
- if (ret < 1)
- break;
- string fs, ts;
- 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;
- }
- unsigned int n = code.size();
- if (argc >= 2) {
- // transitive closure within each company on non-MULTI segments
- for (unsigned int k = 0; k < n; k++) {
- if (!(k % STEP))
- 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;
- }
- }
- }
- for (unsigned int k = 0; k < n; k++) {
- if (!(k % STEP))
- fprintf(stderr, "computing: %d of %d\n", k, n);
- for (unsigned int i = 0; i < n; i++)
- for (unsigned int j = 0; j < n; j++)
- if (d[i][j] > d[i][k] + d[k][j]) {
- d[i][j] = d[i][k] + d[k][j];
- nx[i][j] = nx[i][k];
- }
- }
- int best = 0;
- for (unsigned int i = 0; i < n; i++)
- for (unsigned int j = 0; j < n; j++) {
- if (d[i][j] == INF)
- continue;
- best = max(d[i][j], best);
- /* if (d[i][j] == best)
- printf("%d: %s -> %s\n", best, code[i].c_str(), code[j].c_str()); */
- }
- for (unsigned int i = 0; i < n; i++)
- for (unsigned int j = 0; j < n; j++)
- if (d[i][j] == best) {
- printf("%d: %s -> %s: ", d[i][j], code[i].c_str(), code[j].c_str());
- printf("%s ", code[i].c_str());
- int u = i, v = j;
- while (u != v) {
- assert(u >= 0);
- u = nx[u][v];
- printf("%s ", code[u].c_str());
- }
- printf("\n");
- }
- return 0;
-}
-
diff --git a/smallworld.sh b/smallworld.sh
@@ -1,34 +0,0 @@
-#!/bin/bash
-
-if [ ! -f airlines.dat ]
-then
- wget -O airlines.dat 'https://sourceforge.net/p/openflights/code/HEAD/tree/openflights/data/airlines.dat?format=raw'
-fi
-
-if [ ! -f routes.dat ]
-then
- wget -O routes.dat 'https://sourceforge.net/p/openflights/code/HEAD/tree/openflights/data/routes.dat?format=raw'
-fi
-
-cut -d ',' -f1,8 airlines.dat | tr -d '"' | tr ',' ' ' > active.dat
-echo "\\N Y" >> active.dat
-# sponge from moreutils
-sort -k1,1 active.dat | sponge active.dat
-
-cut -d, -f2,3,5,7 routes.dat | grep -v 'Y$' | tr ',' ' ' |
- sort -k1,1 | join - active.dat |
- grep -v 'N$' | cut -d ' ' -f1-3 > routes_active.dat
-
-sort -k1,1 routes_active.dat |
- ./number.sh > routes_naive.dat
-cat routes_active.dat <(sed 's/#.*//' routes_add) |
- sed "`cat changes | sed 's/\(...\) \(...\)/s_\1_\2_g;/'`" |
- grep -vE `cat forbidden | grep -v '#' | tr '\n' '|' | sed 's/|$//'` |
- sort -k1,1 |
- ./number.sh > routes_fix.dat
-
-g++ -Wall -o smallworld -O3 smallworld.cpp
-./smallworld < routes_naive.dat | tee pairs_naive.out
-#./smallworld close < routes_fix.dat | tee pairs_close.out
-./smallworld < routes_fix.dat | tee pairs.out
-
