Generator of finite congruence-uniform lattices in SageMath

Congruence-uniform_lattice_generator.sage

"""A finite lattice is congruence-uniform (CU) if and only if it is constructed from a singleton
by iterating Day's doubling construction by intervals.
Using this fact, we can create a generator `CU_lattices_generator`
which yields finite CU lattices.
- Lattices appear without repetition (up to isomorphism),
- Every finite CU lattice appears by finitely many iterations.
"""

from collections import deque
singleton = LatticePoset({0: []})


def CU_lattices_generator(N=None, return_depth=False):
    """Generator of finite congruence-uniform lattices.

    Args:
        N (default: `None`) : The maximum number of depth = doublings
        (= the number of join-irreducible elements in a lattice).
        If `None`, then there's no limit (so generates infinitely many lattices).

        return_depth (default: `False`):
        If `True`, then this yields tuples (L, depth) of lattice and depth,
        else yields only lattice L.
    """
    results = deque()
    results.append((singleton, 0))
    while results:
        L, depth = results.popleft()
        if return_depth:
            yield L, depth
        else:
            yield L
        if depth == N:
            continue
        for x, y in L.relations():
            L_doubled = L.day_doubling(L.closed_interval(x, y))
            L_doubled = L_doubled.canonical_label()
            if (L_doubled, depth + 1) in results:
                continue
            results.append((L_doubled, depth + 1))