# bigworld

compute diameter of flights graph
git clone https://a3nm.net/git/bigworld/
Log | Files | Refs

bigworld.cpp (2959B)

```      1 #include <assert.h>
2 #include <cstdio>
3 #include <iostream>
4 #include <map>
5 #include <string>
6 #include <vector>
7
8 #define NMAX 3200
9 #define INF 20000
10 #define MULTI 200000
11 #define STEP 50
12
13 using namespace std;
14
15 int d[NMAX][NMAX];
16 int nx[NMAX][NMAX];
17 int airline[NMAX][NMAX];
18 vector<string> code;
19 map<string, int> alias;
20
21 inline int regcode(string s) {
22   if (!alias.count(s)) {
23     alias[s] = code.size();
24     code.push_back(s);
25   }
26   return alias[s];
27 }
28
29 // if passed an argument, do the transitive closure
30 // algo is Floyd-Warshall with path reconstruction
31 // https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction
32 int main(int argc, char **argv) {
33   for (unsigned int i = 0; i < NMAX; i++)
34     for (unsigned int j = 0; j < NMAX; j++) {
35       d[i][j] = (i == j) ? 0 : INF;
36       nx[i][j] = -1;
37     }
38   while (1) {
39     int a;
40     int ret = scanf("%d", &a);
41     if (ret < 1)
42       break;
43     string fs, ts;
44     cin >> fs >> ts;
45     int f = regcode(fs), t = regcode(ts);
46     assert(f < NMAX && t < NMAX && a < MULTI);
47     assert(a != 0);
48     airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a;
49     d[f][t] = 1;
50     nx[f][t] = t;
51   }
52   unsigned int n = code.size();
53   if (argc >= 2) {
54     // transitive closure within each company on non-MULTI segments
55     for (unsigned int k = 0; k < n; k++) {
56       if (!(k % STEP))
57         fprintf(stderr, "closing: %d of %d\n", k, n);
58       for (unsigned int i = 0; i < n; i++)
59         for (unsigned int j = 0; j < n; j++)
60           // if both have edges with same non-multi airline then close
61           if (d[i][k] == 1 && d[k][j] == 1 && airline[i][k] == airline[k][j]
62               && airline[i][k] != MULTI) {
63             d[i][j] = 1;
64             // add airline to new edge, can make it MULTI
65             airline[i][j] = (airline[i][j] && airline[i][j] != airline[i][k]) ? MULTI : airline[i][k];
66             nx[i][j] = j;
67           }
68     }
69   }
70   for (unsigned int k = 0; k < n; k++) {
71     if (!(k % STEP))
72       fprintf(stderr, "computing: %d of %d\n", k, n);
73     for (unsigned int i = 0; i < n; i++)
74       for (unsigned int j = 0; j < n; j++)
75         if (d[i][j] > d[i][k] + d[k][j]) {
76           d[i][j] = d[i][k] + d[k][j];
77           nx[i][j] = nx[i][k];
78         }
79   }
80   int best = 0;
81   for (unsigned int i = 0; i < n; i++)
82     for (unsigned int j = 0; j < n; j++) {
83       if (d[i][j] == INF)
84         continue;
85       best = max(d[i][j], best);
86       /* if (d[i][j] == best)
87         printf("%d: %s -> %s\n", best, code[i].c_str(), code[j].c_str()); */
88     }
89   for (unsigned int i = 0; i < n; i++)
90     for (unsigned int j = 0; j < n; j++)
91       if (d[i][j] == best) {
92         printf("%d: %s -> %s: ", d[i][j], code[i].c_str(), code[j].c_str());
93         printf("%s ", code[i].c_str());
94         int u = i, v = j;
95         while (u != v) {
96           assert(u >= 0);
97           u = nx[u][v];
98           printf("%s ", code[u].c_str());
99         }
100         printf("\n");
101       }
102   return 0;
103 }
104
```