commit 83e9b6c88f3c53836a089b2bd8fc6c4a2be5e498
parent 92b411360dd50c4769208cb7575820ba9ecbd5c0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 20 May 2015 23:31:02 +0200
new version
Diffstat:
| smallworld.cpp | | | 121 | +++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
| smallworld.sh | | | 19 | ++++++++++++++++--- |
2 files changed, 79 insertions(+), 61 deletions(-)
diff --git a/smallworld.cpp b/smallworld.cpp
@@ -1,90 +1,95 @@
-#include <stdio.h>
+#include <cstdio>
+#include <map>
+#include <vector>
+#include <string>
+#include <iostream>
-#define NMAX 10000
-#define AMAX 20000
+#define NMAX 3100
+//#define AMAX 20000
#define INF 20000
-#define MULTI 20000
+#define MULTI 200000
+#define STEP 50
#define max(a, b) ((a)<(b) ? (b) : (a))
+using namespace std;
+
int d[NMAX][NMAX];
int nx[NMAX][NMAX];
int airline[NMAX][NMAX];
-//bool touchaf[NMAX][AMAX];
-//bool touchat[NMAX][AMAX];
-bool touchf[NMAX];
-bool toucht[NMAX];
-char code[NMAX][10];
+//char code[NMAX][10];
+vector<string> code;
+map<string, int> alias;
+int fresh;
-int main() {
- while (1) {
- int a;
- scanf("%d", &a);
- if (!a)
- break;
- scanf("%s", code[a]);
- }
- for (int i = 0; i < NMAX; i++)
- for (int j = 0; j < NMAX; j++) {
+// if passed an argument, do the transitive closure
+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, f, t;
- scanf("%d%d%d", &a, &f, &t);
- if (!a)
+ int a;
+ //char f[10], t[10];
+ int ret = scanf("%d", &a);
+ if (ret < 1)
break;
+ string fs, ts;
+ cin >> fs >> ts;
+ if (!alias.count(fs)) {
+ alias[fs] = code.size();
+ code.push_back(fs);
+ }
+ if (!alias.count(ts)) {
+ alias[ts] = code.size();
+ code.push_back(ts);
+ }
+ int f = alias[fs], t = alias[ts];
+ airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a;
d[f][t] = 1;
- //touchaf[f][a] = true;
- //touchat[t][a] = true;
- touchf[f] = true;
- toucht[t] = true;
nx[f][t] = t;
- airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a;
}
- int n = 0;
- // transitive closure within each company on non-MULTI segments
- for (int k = 0; k < NMAX; k++) {
- if (!(touchf[k] && toucht[k]))
- continue;
- n++;
- printf ("%d of %d\n", k, NMAX);
- for (int i = 0; i < NMAX; i++)
- for (int j = 0; j < NMAX; j++)
- if (d[i][k] == 1 && d[k][j] == 1 && airline[i][k] == airline[k][j]
- && airline[i][k] != MULTI) {
- d[i][j] = 1;
- airline[i][j] = (airline[i][j] && airline[i][j] != airline[i][k]) ? MULTI : airline[i][k];
- nx[i][j] = j;
- }
+ 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))
+ printf ("closing: %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][k] == 1 && d[k][j] == 1 && airline[i][k] == airline[k][j]
+ && airline[i][k] != MULTI) {
+ d[i][j] = 1;
+ airline[i][j] = (airline[i][j] && airline[i][j] != airline[i][k]) ? MULTI : airline[i][k];
+ nx[i][j] = j;
+ }
+ }
}
- int n2 = 0;
- for (int k = 0; k < NMAX; k++) {
- if (!(touchf[k] && toucht[k]))
- continue;
- n2++;
- printf ("%d of %d\n", n2, n);
- for (int i = 0; i < NMAX; i++)
- for (int j = 0; j < NMAX; j++)
+ for (unsigned int k = 0; k < n; k++) {
+ if (!(k % STEP))
+ printf ("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 (int i = 0; i < NMAX; i++)
- for (int j = 0; j < NMAX; j++) {
+ 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], code[j]);
+ printf("%d: %s -> %s\n", best, code[i].c_str(), code[j].c_str());
}
- for (int i = 0; i < NMAX; i++)
- for (int j = 0; j < NMAX; j++)
+ 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], code[j]);
- printf("%s ", code[i]);
+ 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) {
if (u < 0) {
@@ -92,7 +97,7 @@ int main() {
break;
}
u = nx[u][v];
- printf("%s ", code[u]);
+ printf("%s ", code[u].c_str());
}
printf("\n");
}
diff --git a/smallworld.sh b/smallworld.sh
@@ -1,3 +1,16 @@
-cut -d, -f1,5,6 airports.dat | sed 's/""/"***"/g;s/\\N/"****"/g;s/,/ /;s/,/-/' | tr -d '"'
-cut -d, -f2,4,6,7 routes.dat | grep -v Y | tr ',' ' ' | grep -v '\\N' | sort -k1,1n | sed 's/^5399 /11838 /g' > edges
-cat nodes <(echo 0) edges <(echo 0 0 0) > input
+#!/bin/bash
+cut -d ',' -f1,8 airlines.dat | tr -d '"' | tr ',' ' ' > active
+echo "\\N Y" >> active
+sort -k1,1 active | sponge active
+cut -d, -f2,3,5,7 routes.dat | grep -v 'Y$' | tr ',' ' ' | sort -k1,1 > routesb.dat
+join routesb.dat active|
+ grep -v 'N$' | cut -d ' ' -f1-3 |
+ awk '{if ($1 == "\\N") {
+ print n, $2, $3;
+ n++;
+ } else {
+ print $0;
+ n = n > $1?n:$1;
+ } }' > routesc.dat
+g++ -Wall -o smallworld -O3 smallworld.cpp
+./smallworld close < routesc.dat
