Source code for pocketpartition.core.genus

__all__ = ['WithGenus', 'WithMaxGenus']

from collections import deque
from ..core.numerical_semigroup import NumericalSemigroup

def bfs_to_depth(root, depth):
    """
    Yield every node in a rooted tree that sits at exactly ``depth`` levels
    below ``root``.

    The tree is traversed breadth-first so that nodes at shallower depths are
    visited before nodes at deeper ones, although only nodes at the target
    depth are actually yielded.

    Parameters
    ----------
    root : NumericalSemigroup
        The root of the semigroup tree (typically ``NumericalSemigroup({1})``).
    depth : int
        The target depth.  Nodes at ``depth == 0`` means only ``root`` is
        yielded.  Negative values produce no output.

    Yields
    ------
    NumericalSemigroup
        Each numerical semigroup at exactly ``depth`` levels from ``root``.
    """
    if depth < 0:
        return

    queue = deque([(root, 0)])

    while queue:
        node, current_depth = queue.popleft()

        if current_depth == depth:
            yield node
        elif current_depth < depth:
            for child in node.get_children():
                queue.append((child, current_depth + 1))

def bfs_up_to_depth(root, depth):
    """
    Yield every node in a rooted tree that is at most ``depth`` levels below
    ``root``, including ``root`` itself.

    The tree is traversed breadth-first, so nodes are yielded in non-decreasing
    order of depth.

    Parameters
    ----------
    root : NumericalSemigroup
        The root of the semigroup tree (typically ``NumericalSemigroup({1})``).
    depth : int
        The maximum depth to explore.  Negative values produce no output.

    Yields
    ------
    NumericalSemigroup
        Each numerical semigroup at depth ``0, 1, ..., depth`` from ``root``.
    """
    if depth < 0:
        return

    queue = deque([(root, 0)])

    while queue:
        node, current_depth = queue.popleft()

        yield node
        if current_depth < depth:
            for child in node.get_children():
                queue.append((child, current_depth + 1))



def WithGenus(g):
    """
    Yield all numerical semigroups of genus exactly ``g``.

    This is a thin wrapper around :func:`bfs_to_depth` rooted at the semigroup
    ``N`` (generated by ``{1}``), which is the unique semigroup of genus 0 and
    the root of the semigroup tree.

    Parameters
    ----------
    g : int
        The target genus.  Must be non-negative; negative values produce no
        output.

    Yields
    ------
    NumericalSemigroup
        Each numerical semigroup whose genus equals ``g``.

    Examples
    --------
    >>> from pocketpartition import WithGenus
    >>> semigroups = list(WithGenus(3))
    >>> len(semigroups)
    4
    >>> all(S.genus == 3 for S in semigroups)
    True
    """
    yield from bfs_to_depth(NumericalSemigroup(generators={1}), g)




def WithMaxGenus(g):
    """
    Yield all numerical semigroups of genus at most ``g``.

    This is a thin wrapper around :func:`bfs_up_to_depth` rooted at the
    semigroup ``N`` (generated by ``{1}``), which is the unique semigroup of
    genus 0 and the root of the semigroup tree.

    Parameters
    ----------
    g : int
        The maximum genus to include.  Must be non-negative; negative values
        produce no output.

    Yields
    ------
    NumericalSemigroup
        Each numerical semigroup whose genus is in ``{0, 1, ..., g}``.

    Examples
    --------
    >>> from pocketpartition import WithMaxGenus
    >>> semigroups = list(WithMaxGenus(2))
    >>> all(S.genus <= 2 for S in semigroups)
    True
    >>> {S.genus for S in semigroups} == {0, 1, 2}
    True
    """
    yield from bfs_up_to_depth(NumericalSemigroup(generators={1}), g)