Skip to main content
API REFERENCE/omnibias-discrete

omnibias.discrete.matroid

0.1.0a2AlphaPython >=3.10AGPL / commercial

Shared discrete-problem contracts, annealed relaxations, hard decoders, and optimality-gap evidence.

import omnibias.discrete.matroid
Module contract & mathematical conventions

Shared, representation-neutral matroid independence / rank kernel.

The public home of the canonical independence and rank definitions for the three matroid families the stack shares -- **uniform**, **partition**, and **graphic** -- on the mathematical frozenset[int] representation. Both matroid lenses build on it:

  • omnibias.combinatorics (polytope / LP-certification lens) delegates its frozenset independence / rank here directly;
  • omnibias.submodular (greedy / soft-oracle lens) thresholds its 0/1 vectors to the selected index set and delegates the independence question here.

Routing both through one kernel keeps the two graphic matroids from drifting on acyclicity and the two partition matroids from drifting on the capacity rule. The specialized surfaces (rank inequalities, linear-maximization oracle, differentiable soft basis) stay in their own packages.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →
CLASS

MatroidCore​

omnibias.discrete.matroid.MatroidCoreSource ↗
class MatroidCore(Protocol)

The minimal matroid contract on ground set range(ground_size).

A matroid is fully determined for the stack's purposes by its ground-set size, its independence oracle, and its rank function on frozenset[int] subsets. Each lens adds its specialized surface (rank inequalities / linear oracle) on top of this core.

Regression example · independent sets enumerates via protocol

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_independent_sets_enumerates_via_protocol() -> None:
    class _Uniform:
        ground_size = 4

        def is_independent(self, subset: frozenset[int]) -> bool:
            return uniform_independent(subset, 2)

        def rank(self, subset: frozenset[int]) -> int:
            return uniform_rank(subset, 2)

    m = _Uniform()
    assert isinstance(m, MatroidCore)
    enumerated = set(independent_sets(m))
    expected = {s for s in _all_subsets(4) if len(s) <= 2}
    assert enumerated == expected
python -m pytest packages/omnibias-discrete/tests/test_matroid_kernel.py -k test_independent_sets_enumerates_via_protocol -q

Fields & methods

ground_sizeproperty
ground_size(self) -> int

See the class contract above and the exact method implementation below.

Returns: int

Method implementation
    def ground_size(self) -> int: ...
View source ↗
is_independentmethod
is_independent(self, subset: frozenset[int]) -> bool

See the class contract above and the exact method implementation below.

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.

Returns: bool

Method implementation
    def is_independent(self, subset: frozenset[int]) -> bool: ...
View source ↗
rankmethod
rank(self, subset: frozenset[int]) -> int

See the class contract above and the exact method implementation below.

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.

Returns: int

Method implementation
    def rank(self, subset: frozenset[int]) -> int: ...
View source ↗
Read the implementation
class MatroidCore(Protocol):
    r"""The minimal matroid contract on ground set ``range(ground_size)``.

    A matroid is fully determined for the stack's purposes by its ground-set size, its
    independence oracle, and its rank function on ``frozenset[int]`` subsets. Each lens
    adds its specialized surface (rank inequalities / linear oracle) on top of this core.
    """

    @property
    def ground_size(self) -> int: ...

    def is_independent(self, subset: frozenset[int]) -> bool: ...

    def rank(self, subset: frozenset[int]) -> int: ...
FUNCTION

graphic_independent​

omnibias.discrete.matroid.graphic_independentSource ↗
graphic_independent(subset: frozenset[int], edges: Sequence[tuple[int, int]], n_nodes: int) -> bool

Whether the edges indexed by subset form a forest (are acyclic) over n_nodes.

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.
edgespositional-or-keywordSequence[tuple[int, int]]RequiredSee the operation contract and implementation below.
n_nodespositional-or-keywordintRequiredSee the operation contract and implementation below.
Returnsbool
Executed regression · graphic matches acyclicity spec

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_graphic_matches_acyclicity_spec() -> None:
    edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4)]
    n = 5
    for s in _all_subsets(len(edges)):
        ref_forest, ref_rank = _ref_graph(s, edges, n)
        assert graphic_independent(s, edges, n) == ref_forest
        assert graphic_rank(s, edges, n) == ref_rank
python -m pytest "packages/omnibias-discrete/tests/test_matroid_kernel.py::test_graphic_matches_acyclicity_spec" -q
Read the implementation
def graphic_independent(
    subset: frozenset[int], edges: Sequence[tuple[int, int]], n_nodes: int
) -> bool:
    r"""Whether the edges indexed by ``subset`` form a forest (are acyclic) over ``n_nodes``."""
    uf = UnionFind(n_nodes)
    for e in subset:
        u, v = edges[e]
        if not uf.union(u, v):
            return False
    return True
Related APIsomnibias.discrete.UnionFind↗
FUNCTION

graphic_rank​

omnibias.discrete.matroid.graphic_rankSource ↗
graphic_rank(subset: frozenset[int], edges: Sequence[tuple[int, int]], n_nodes: int) -> int

Rank of subset in the graphic matroid (the number of tree edges it contributes).

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.
edgespositional-or-keywordSequence[tuple[int, int]]RequiredSee the operation contract and implementation below.
n_nodespositional-or-keywordintRequiredSee the operation contract and implementation below.
Returnsint
Executed regression · graphic matches acyclicity spec

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_graphic_matches_acyclicity_spec() -> None:
    edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4)]
    n = 5
    for s in _all_subsets(len(edges)):
        ref_forest, ref_rank = _ref_graph(s, edges, n)
        assert graphic_independent(s, edges, n) == ref_forest
        assert graphic_rank(s, edges, n) == ref_rank
python -m pytest "packages/omnibias-discrete/tests/test_matroid_kernel.py::test_graphic_matches_acyclicity_spec" -q
Read the implementation
def graphic_rank(subset: frozenset[int], edges: Sequence[tuple[int, int]], n_nodes: int) -> int:
    r"""Rank of ``subset`` in the graphic matroid (the number of tree edges it contributes)."""
    uf = UnionFind(n_nodes)
    rank = 0
    for e in subset:
        u, v = edges[e]
        if uf.union(u, v):
            rank += 1
    return rank
Related APIsomnibias.discrete.UnionFind↗
FUNCTION

independent_sets​

omnibias.discrete.matroid.independent_setsSource ↗
independent_sets(matroid: MatroidCore) -> Iterator[frozenset[int]]

Enumerate every independent set of *matroid* (exponential; small ground sets only).

Parameters

NameType & defaultContract
matroidpositional-or-keywordMatroidCoreRequiredSee the operation contract and implementation below.
ReturnsIterator[frozenset[int]]
Executed regression · independent sets enumerates via protocol

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_independent_sets_enumerates_via_protocol() -> None:
    class _Uniform:
        ground_size = 4

        def is_independent(self, subset: frozenset[int]) -> bool:
            return uniform_independent(subset, 2)

        def rank(self, subset: frozenset[int]) -> int:
            return uniform_rank(subset, 2)

    m = _Uniform()
    assert isinstance(m, MatroidCore)
    enumerated = set(independent_sets(m))
    expected = {s for s in _all_subsets(4) if len(s) <= 2}
    assert enumerated == expected
python -m pytest "packages/omnibias-discrete/tests/test_matroid_kernel.py::test_independent_sets_enumerates_via_protocol" -q
Read the implementation
def independent_sets(matroid: MatroidCore) -> Iterator[frozenset[int]]:
    r"""Enumerate every independent set of *matroid* (exponential; small ground sets only)."""
    elements = range(matroid.ground_size)
    for size in range(matroid.ground_size + 1):
        for combo in combinations(elements, size):
            subset = frozenset(combo)
            if matroid.is_independent(subset):
                yield subset
FUNCTION

partition_independent​

omnibias.discrete.matroid.partition_independentSource ↗
partition_independent(subset: frozenset[int], groups: Iterable[Iterable[int]], caps: Iterable[int]) -> bool

Whether subset obeys every group capacity (|subset cap group_i| <= caps[i]).

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.
groupspositional-or-keywordIterable[Iterable[int]]RequiredSee the operation contract and implementation below.
capspositional-or-keywordIterable[int]RequiredSee the operation contract and implementation below.
Returnsbool
Executed regression · partition matches capacity spec

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_partition_matches_capacity_spec() -> None:
    groups = ((0, 1, 2), (3, 4), (5, 6))
    caps = (2, 1, 2)
    for s in _all_subsets(7):
        ok = all(len(s & frozenset(g)) <= c for g, c in zip(groups, caps, strict=True))
        rank = sum(min(len(s & frozenset(g)), c) for g, c in zip(groups, caps, strict=True))
        assert partition_independent(s, groups, caps) == ok
        assert partition_rank(s, groups, caps) == rank
python -m pytest "packages/omnibias-discrete/tests/test_matroid_kernel.py::test_partition_matches_capacity_spec" -q
Read the implementation
def partition_independent(
    subset: frozenset[int], groups: Iterable[Iterable[int]], caps: Iterable[int]
) -> bool:
    r"""Whether ``subset`` obeys every group capacity (``|subset cap group_i| <= caps[i]``)."""
    for group, cap in zip(groups, caps, strict=True):
        if len(subset & frozenset(group)) > cap:
            return False
    return True
FUNCTION

partition_rank​

omnibias.discrete.matroid.partition_rankSource ↗
partition_rank(subset: frozenset[int], groups: Iterable[Iterable[int]], caps: Iterable[int]) -> int

Rank of subset in a partition matroid (sum_i min(|subset cap group_i|, caps[i])).

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.
groupspositional-or-keywordIterable[Iterable[int]]RequiredSee the operation contract and implementation below.
capspositional-or-keywordIterable[int]RequiredSee the operation contract and implementation below.
Returnsint
Executed regression · partition matches capacity spec

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_partition_matches_capacity_spec() -> None:
    groups = ((0, 1, 2), (3, 4), (5, 6))
    caps = (2, 1, 2)
    for s in _all_subsets(7):
        ok = all(len(s & frozenset(g)) <= c for g, c in zip(groups, caps, strict=True))
        rank = sum(min(len(s & frozenset(g)), c) for g, c in zip(groups, caps, strict=True))
        assert partition_independent(s, groups, caps) == ok
        assert partition_rank(s, groups, caps) == rank
python -m pytest "packages/omnibias-discrete/tests/test_matroid_kernel.py::test_partition_matches_capacity_spec" -q
Read the implementation
def partition_rank(
    subset: frozenset[int], groups: Iterable[Iterable[int]], caps: Iterable[int]
) -> int:
    r"""Rank of ``subset`` in a partition matroid (``sum_i min(|subset cap group_i|, caps[i])``)."""
    return sum(
        min(len(subset & frozenset(group)), cap)
        for group, cap in zip(groups, caps, strict=True)
    )
FUNCTION

uniform_independent​

omnibias.discrete.matroid.uniform_independentSource ↗
uniform_independent(subset: frozenset[int], k: int) -> bool

Whether subset is independent in the uniform matroid U(n, k) (|subset| <= k).

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.
kpositional-or-keywordintRequiredSee the operation contract and implementation below.
Returnsbool
Executed regression · uniform matches cardinality spec

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_uniform_matches_cardinality_spec() -> None:
    n, k = 7, 3
    for s in _all_subsets(n):
        assert uniform_independent(s, k) == (len(s) <= k)
        assert uniform_rank(s, k) == min(len(s), k)
python -m pytest "packages/omnibias-discrete/tests/test_matroid_kernel.py::test_uniform_matches_cardinality_spec" -q
Regression example · independent sets enumerates via protocol

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_independent_sets_enumerates_via_protocol() -> None:
    class _Uniform:
        ground_size = 4

        def is_independent(self, subset: frozenset[int]) -> bool:
            return uniform_independent(subset, 2)

        def rank(self, subset: frozenset[int]) -> int:
            return uniform_rank(subset, 2)

    m = _Uniform()
    assert isinstance(m, MatroidCore)
    enumerated = set(independent_sets(m))
    expected = {s for s in _all_subsets(4) if len(s) <= 2}
    assert enumerated == expected
python -m pytest packages/omnibias-discrete/tests/test_matroid_kernel.py -k test_independent_sets_enumerates_via_protocol -q
Read the implementation
def uniform_independent(subset: frozenset[int], k: int) -> bool:
    r"""Whether ``subset`` is independent in the uniform matroid ``U(n, k)`` (``|subset| <= k``)."""
    return len(subset) <= k
FUNCTION

uniform_rank​

omnibias.discrete.matroid.uniform_rankSource ↗
uniform_rank(subset: frozenset[int], k: int) -> int

Rank of subset in U(n, k) (min(|subset|, k)).

Parameters

NameType & defaultContract
subsetpositional-or-keywordfrozenset[int]RequiredSee the operation contract and implementation below.
kpositional-or-keywordintRequiredSee the operation contract and implementation below.
Returnsint
Executed regression · uniform matches cardinality spec

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_uniform_matches_cardinality_spec() -> None:
    n, k = 7, 3
    for s in _all_subsets(n):
        assert uniform_independent(s, k) == (len(s) <= k)
        assert uniform_rank(s, k) == min(len(s), k)
python -m pytest "packages/omnibias-discrete/tests/test_matroid_kernel.py::test_uniform_matches_cardinality_spec" -q
Regression example · independent sets enumerates via protocol

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗
def test_independent_sets_enumerates_via_protocol() -> None:
    class _Uniform:
        ground_size = 4

        def is_independent(self, subset: frozenset[int]) -> bool:
            return uniform_independent(subset, 2)

        def rank(self, subset: frozenset[int]) -> int:
            return uniform_rank(subset, 2)

    m = _Uniform()
    assert isinstance(m, MatroidCore)
    enumerated = set(independent_sets(m))
    expected = {s for s in _all_subsets(4) if len(s) <= 2}
    assert enumerated == expected
python -m pytest packages/omnibias-discrete/tests/test_matroid_kernel.py -k test_independent_sets_enumerates_via_protocol -q
Read the implementation
def uniform_rank(subset: frozenset[int], k: int) -> int:
    r"""Rank of ``subset`` in ``U(n, k)`` (``min(|subset|, k)``)."""
    return min(len(subset), k)
← Package overviewRunnable learning examples →