trees.py

import networkx as nx
import sys

def enc_tup(t):
    return str(len(t)) + ''.join(sorted(enc_tup(s) for s in t))

def unr_tup(g):
    c = nx.center(g)
    if len(c) == 1:
        return enc_tup(nx.to_nested_tuple(g, c[0]))
    else:
        t1 = enc_tup(nx.to_nested_tuple(g, c[0]))
        t2 = enc_tup(nx.to_nested_tuple(g, c[1]))
        return t1 if t1 <= t2 else t2

gl_prev = {'0': nx.empty_graph(1)}
n = 1
tot = 0

while True:
    for t in sorted(gl_prev.keys()):
        print(t, flush=True)
    tot += len(gl_prev)
    print(tot, file=sys.stderr)
    gl_cur = {}
    for gold in gl_prev.values():
        for k, deg in gold.degree:
            if deg == 4:
                continue
            gnew = gold.copy()
            gnew.add_edge(k, n)
            tnew = unr_tup(gnew)
            if tnew not in gl_cur:
                gl_cur[tnew] = gnew
    gl_prev = gl_cur
    n += 1