Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
from __future__ import absolute_import
from .matroid cimport Matroid
cdef class MatroidUnion(Matroid): r""" Matroid Union.
The matroid union of a set of matroids `\{(E_1,I_1),\ldots,(E_n,I_n)\}` is a matroid `(E,I)` where `E= \bigcup_{i=1}^n E_i` and
`I= \{\bigcup_{i=1}^n J_i | J_i \in I_i \}`.
INPUT:
- ``matroids`` -- a iterator of matroids.
OUTPUT:
A ``MatroidUnion`` instance, it's a matroid union of all matroids in ``matroids``. """ def __init__(self, matroids): """ See class definition for full documentation.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: MatroidUnion([matroids.Uniform(2,4),matroids.Uniform(5,8)]) Matroid of rank 7 on 8 elements as matroid union of Matroid of rank 2 on 4 elements with circuit-closures {2: {{0, 1, 2, 3}}} Matroid of rank 5 on 8 elements with circuit-closures {5: {{0, 1, 2, 3, 4, 5, 6, 7}}} """
cpdef groundset(self): """ Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT:
A set.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: M = MatroidUnion([matroids.Uniform(2,4),matroids.Uniform(5,8)]) sage: sorted(M.groundset()) [0, 1, 2, 3, 4, 5, 6, 7] """
cpdef _rank(self, X): r""" Return the rank of a set ``X``.
This method does no checking on ``X``, and ``X`` may be assumed to have the same interface as ``frozenset``.
INPUT:
- ``X`` -- an object with Python's ``frozenset`` interface.
OUTPUT:
Integer.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: M = MatroidSum([matroids.Uniform(2,4),matroids.Uniform(2,4)]) sage: M._rank([(0,0),(1,0)]) 2 sage: M._rank([(0,0),(0,1),(0,2),(1,0),(1,1)]) 4
ALGORITHM:
Matroid intersection of a matroid sum and partition matroid.
"""
def _repr_(self): """ Return a string representation of the matroid.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: MatroidUnion([matroids.Uniform(2,4),matroids.Uniform(5,8)]) Matroid of rank 7 on 8 elements as matroid union of Matroid of rank 2 on 4 elements with circuit-closures {2: {{0, 1, 2, 3}}} Matroid of rank 5 on 8 elements with circuit-closures {5: {{0, 1, 2, 3, 4, 5, 6, 7}}} """
cdef class MatroidSum(Matroid): r""" Matroid Sum.
The matroid sum of a list of matroids `(E_1,I_1),\ldots,(E_n,I_n)` is a matroid `(E,I)` where `E= \bigsqcup_{i=1}^n E_i` and `I= \bigsqcup_{i=1}^n I_i`.
INPUT:
- ``matroids`` -- a iterator of matroids.
OUTPUT:
A ``MatroidSum`` instance, it's a matroid sum of all matroids in ``matroids``. """ def __init__(self, summands): """ See class definition for full documentation.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: MatroidSum([matroids.Uniform(2,4),matroids.Uniform(5,8)]) Matroid of rank 7 on 12 elements as matroid sum of Matroid of rank 2 on 4 elements with circuit-closures {2: {{0, 1, 2, 3}}} Matroid of rank 5 on 8 elements with circuit-closures {5: {{0, 1, 2, 3, 4, 5, 6, 7}}} """
def _repr_(self): """ Return a string representation of the matroid.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: MatroidSum([matroids.Uniform(2,4),matroids.Uniform(2,4)]) Matroid of rank 4 on 8 elements as matroid sum of Matroid of rank 2 on 4 elements with circuit-closures {2: {{0, 1, 2, 3}}} Matroid of rank 2 on 4 elements with circuit-closures {2: {{0, 1, 2, 3}}} """
cpdef groundset(self): """ Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT:
A set.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: M = MatroidSum([matroids.Uniform(2,4),matroids.Uniform(2,4)]) sage: sorted(M.groundset()) [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)] """
cpdef _rank(self, X): r""" Return the rank of a set ``X``.
This method does no checking on ``X``, and ``X`` may be assumed to have the same interface as ``frozenset``.
INPUT:
- ``X`` -- an object with Python's ``frozenset`` interface.
OUTPUT:
Integer.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: M = MatroidSum([matroids.Uniform(2,4),matroids.Uniform(2,4)]) sage: M._rank([(0,0),(1,0)]) 2 sage: M._rank([(0,0),(0,1),(0,2),(1,0),(1,1)]) 4 """
cdef class PartitionMatroid(Matroid): r""" Partition Matroid.
Given a set of disjoint sets `S=\{S_1,\ldots,S_n\}`, the partition matroid on `S` is `(E,I)` where `E=\bigcup_{i=1}^n S_i` and
`I= \{X| |X\cap S_i|\leq 1,X\subset E \}`.
INPUT:
- ``partition`` -- an iterator of disjoint sets.
OUTPUT:
A ``PartitionMatroid`` instance, it's partition matroid of the ``partition``. """ def __init__(self, partition): """ See class definition for full documentation.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: PartitionMatroid([[1,2,3],[4,5,6]]) Partition Matroid of rank 2 on 6 elements sage: PartitionMatroid([[1,2],[2,3]]) Traceback (most recent call last): ... ValueError: not an iterator of disjoint sets sage: PartitionMatroid([]) Partition Matroid of rank 0 on 0 elements """
cpdef groundset(self): """ Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT:
A set.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: M = PartitionMatroid([[1,2,3],[4,5,6]]) sage: sorted(M.groundset()) [1, 2, 3, 4, 5, 6] """
cpdef _rank(self, X): r""" Return the rank of a set ``X``.
This method does no checking on ``X``, and ``X`` may be assumed to have the same interface as ``frozenset``.
INPUT:
- ``X`` -- an object with Python's ``frozenset`` interface.
OUTPUT:
Integer.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: M = PartitionMatroid([[1,2,3],[4,5,6]]) sage: M._rank([1,5]) 2 sage: M._rank([1,2]) 1 """
def _repr_(self): """ Return a string representation of the matroid.
EXAMPLES::
sage: from sage.matroids.union_matroid import * sage: PartitionMatroid([[1,2,3],[4,5,6]]) Partition Matroid of rank 2 on 6 elements """ |