Skip to content

void_and_cluster

void_and_cluster #

Void & cluster sampling for distribution-aware session selection.

Select a subset of candidate items that maximize diversity relative to a set of existing items, using a user-provided distance metric. Adapted from the Void & Cluster dithering algorithm, the sampler works over a coverage field — every candidate's energy from the capture history plus the picks so far — in two steps per iteration: the void step adds the least-covered candidate, and the cluster step releases the most-covered pick unless that is the one just added (a stable set), so a pick that later became crowded is re-placed.

EnergyMode = Literal['sum', 'max'] #

How the energies a candidate draws from several points fold into one.

select_sessions(potential_sessions, previous_sessions, distance_fn, energy_fn=_DEFAULT_ENERGY_FN, energy_mode='sum', selections=10) #

Select diverse sessions with a Void & Cluster sampler.

Each iteration fills the largest "void": it computes every unselected candidate's energy — its similarity to the previous sessions plus the selections made so far — and selects the candidate with the lowest energy. It then finds the tightest "cluster" — the selected point with the highest energy — and, unless that is the point just added (a stable set), releases it so a later iteration can place it in a better void. The first pick is the candidate least covered by previous_sessions; with no previous sessions it is uniformly random. Total releases are bounded by len(potential_sessions) to guarantee termination.

Energy functions are applied to whole numpy distance matrices, so custom energy_fn callables must be numpy-vectorized. Ties are broken with the global numpy RNG; seed np.random for reproducibility.

Parameters:

Name Type Description Default
potential_sessions Array[T]

Candidate sessions to select from. A candidate the metric cannot compare — every dimension missing — is never offered.

required
previous_sessions Array[T]

Already-captured sessions. New selections are spread away from these; one the metric cannot compare covers nothing.

required
distance_fn Callable[[T, T], float]

Statistical distance between two sessions. A cgr.scheduling.distance.* metric is evaluated vectorized; a plain (session_a, session_b) -> float callable is evaluated pair by pair.

required
energy_fn EnergyFunction

Converts distance to coverage energy. Default is Gaussian with sigma=1.

_DEFAULT_ENERGY_FN
energy_mode EnergyMode

How to combine energies from multiple sources — "sum" totals every contribution, "max" keeps the largest.

'sum'
selections int

Number of sessions to select. Clamped to the number of comparable candidates.

10

Returns:

Type Description
Array[T]

Array of selected sessions, in potential_sessions index order

Array[T]

(not selection order).

Raises:

Type Description
ValueError

If energy_mode is not "sum" or "max".

Source code in capturegraph-recipes/capturegraph_recipes/scheduling/void_and_cluster.py
def select_sessions[T](
    potential_sessions: cg.Array[T],
    previous_sessions: cg.Array[T],
    distance_fn: Callable[[T, T], float],
    energy_fn: EnergyFunction = _DEFAULT_ENERGY_FN,
    energy_mode: EnergyMode = "sum",
    selections: int = 10,
) -> cg.Array[T]:
    """Select diverse sessions with a Void & Cluster sampler.

    Each iteration fills the largest "void": it computes every unselected
    candidate's energy — its similarity to the previous sessions plus the
    selections made so far — and selects the candidate with the lowest
    energy. It then finds the tightest "cluster" — the selected point with
    the highest energy — and, unless that is the point just added (a stable
    set), releases it so a later iteration can place it in a better void.
    The first pick is the candidate least covered by `previous_sessions`;
    with no previous sessions it is uniformly random. Total releases are
    bounded by `len(potential_sessions)` to guarantee termination.

    Energy functions are applied to whole numpy distance matrices, so
    custom `energy_fn` callables must be numpy-vectorized. Ties are broken
    with the global numpy RNG; seed `np.random` for reproducibility.

    Args:
        potential_sessions: Candidate sessions to select from. A candidate the
            metric cannot compare — every dimension missing — is never offered.
        previous_sessions: Already-captured sessions. New selections are spread
            away from these; one the metric cannot compare covers nothing.
        distance_fn: Statistical distance between two sessions. A
            `cgr.scheduling.distance.*` metric is evaluated vectorized; a plain
            `(session_a, session_b) -> float` callable is evaluated pair by pair.
        energy_fn: Converts distance to coverage energy. Default is Gaussian
            with sigma=1.
        energy_mode: How to combine energies from multiple sources — `"sum"`
            totals every contribution, `"max"` keeps the largest.
        selections: Number of sessions to select. Clamped to the number of
            comparable candidates.

    Returns:
        Array of selected sessions, in `potential_sessions` index order
        (not selection order).

    Raises:
        ValueError: If energy_mode is not "sum" or "max".
    """
    if energy_mode not in _COMBINERS:
        raise ValueError(f"Unknown energy mode: {energy_mode}")
    metric = as_distance(distance_fn)
    candidates = _comparable(potential_sessions, metric)
    field = _CoverageField(candidates, previous_sessions, metric, energy_fn, energy_mode)
    selected = _sample(field, min(selections, len(candidates)))
    return cg.Array(candidates[int(index)] for index in np.flatnonzero(selected))