1/* Exhaustive zero-forcing oracle for P(n,k), 2n <= 64 vertices.2 *3 * usage: brute_force n k s [m0]4 * Enumerates every s-subset S of V(P(n,k)) (optionally only those whose5 * lowest vertex id is m0, for parallel splitting), keeps only the subsets6 * that are the minimum of their orbit under the dihedral group D_n acting7 * by rotations and reflections (Proposition P3: orbit reduction loses no8 * zero-forcing set), computes the closure by the colour-change rule, and9 * reports how many representatives were tested and how many force the10 * whole graph; the first forcing representative is printed as a witness.11 *12 * Vertex ids: u_i -> i, v_i -> n+i. Independent of the Python code: the13 * graph is rebuilt here from definition D1.14 */15#include <stdio.h>16#include <stdlib.h>17#include <stdint.h>18#include <string.h>1920typedef uint64_t mask;2122static int n, k, N;23static mask adj[64];24static int perm[128][64]; /* 2n group elements */25static int G;2627static void build(void) {28 N = 2 * n;29 for (int i = 0; i < N; i++) adj[i] = 0;30 for (int i = 0; i < n; i++) {31 int u = i, u1 = (i + 1) % n, v = n + i, vk = n + (i + k) % n;32 adj[u] |= (mask)1 << u1; adj[u1] |= (mask)1 << u;33 adj[u] |= (mask)1 << v; adj[v] |= (mask)1 << u;34 adj[v] |= (mask)1 << vk; adj[vk] |= (mask)1 << v;35 }36 G = 0;37 for (int a = 0; a < n; a++) {38 for (int i = 0; i < n; i++) {39 perm[G][i] = (i + a) % n; perm[G][n + i] = n + (i + a) % n;40 perm[G + 1][i] = ((a - i) % n + n) % n; perm[G + 1][n + i] = n + ((a - i) % n + n) % n;41 }42 G += 2;43 }44}4546static inline mask closure(mask B) {47 mask full = (N == 64) ? ~(mask)0 : (((mask)1 << N) - 1);48 int changed = 1;49 while (changed) {50 changed = 0;51 mask rest = B;52 while (rest) {53 int b = __builtin_ctzll(rest);54 rest &= rest - 1;55 mask white = adj[b] & ~B;56 if (white && !(white & (white - 1))) { B |= white; changed = 1; }57 }58 if (B == full) return B;59 }60 return B;61}6263static inline int canonical(mask m) {64 /* m is canonical iff no image under a nontrivial group element is smaller */65 for (int g = 1; g < G; g++) {66 mask img = 0, rest = m;67 while (rest) { int v = __builtin_ctzll(rest); rest &= rest - 1; img |= (mask)1 << perm[g][v]; }68 if (img < m) return 0;69 }70 return 1;71}7273static void print_mask(mask m) {74 int first = 1;75 for (int w = 0; w < N; w++) if (m >> w & 1) {76 printf("%s%c%d", first ? "" : ",", w < n ? 'u' : 'v', w < n ? w : w - n);77 first = 0;78 }79}8081int main(int argc, char **argv) {82 if (argc < 4) { fprintf(stderr, "usage: brute_force n k s [m0]\n"); return 2; }83 n = atoi(argv[1]); k = atoi(argv[2]); int s = atoi(argv[3]);84 int m0 = argc > 4 ? atoi(argv[4]) : -1;85 build();86 mask full = (N == 64) ? ~(mask)0 : (((mask)1 << N) - 1);87 unsigned long long enumerated = 0, tested = 0, forcing = 0;88 mask witness = 0;89 /* Gosper enumeration of t-subsets of the vertices > m0 (or all s-subsets) */90 int lo = (m0 >= 0) ? m0 + 1 : 0;91 int t = (m0 >= 0) ? s - 1 : s;92 int width = N - lo;93 if (t > width || t < 0) { printf("n=%d k=%d s=%d m0=%d enumerated=0 tested=0 forcing=0\n", n, k, s, m0); return 0; }94 mask base = (m0 >= 0) ? ((mask)1 << m0) : 0;95 mask sub = (t == 0) ? 0 : (((mask)1 << t) - 1);96 mask limit = (width == 64) ? ~(mask)0 : (((mask)1 << width) - 1);97 while (1) {98 mask m = base | (sub << lo);99 enumerated++;100 if (canonical(m)) {101 tested++;102 if (closure(m) == full) { if (!forcing) witness = m; forcing++; }103 }104 if (t == 0) break;105 /* next Gosper */106 mask c = sub & -sub, r = sub + c;107 if (r > limit || r == 0) break;108 sub = (((r ^ sub) >> 2) / c) | r;109 if (sub > limit) break;110 }111 printf("n=%d k=%d s=%d m0=%d enumerated=%llu tested=%llu forcing=%llu", n, k, s, m0, enumerated, tested, forcing);112 if (forcing) { printf(" witness="); print_mask(witness); }113 printf("\n");114 return 0;115}116