Basis exchange matroids
BasisExchangeMatroid is an abstract class implementing default matroid functionality in terms of basis exchange. Several concrete matroid classes are subclasses of this. They have the following methods in addition to the ones provided by the parent class Matroid.
AUTHORS:
TESTS:
sage: from sage.matroids.advanced import *
sage: import sage.matroids.basis_exchange_matroid
sage: M = sage.matroids.basis_exchange_matroid.BasisExchangeMatroid(
....: groundset=[1, 2, 3], rank=2)
sage: TestSuite(M).run(skip="_test_pickling")
Note that this is an abstract base class, without data structure, so no pickling mechanism was implemented.
Bases: sage.matroids.matroid.Matroid
Class BasisExchangeMatroid is a virtual class that derives from Matroid. It implements each of the elementary matroid methods (rank(), max_independent(), circuit(), closure() etc.), essentially by crawling the base exchange graph of the matroid. This is the graph whose vertices are the bases of the matroid, two bases being adjacent in the graph if their symmetric difference has 2 members.
This base exchange graph is not stored as such, but should be provided
implicity by the child class in the form of two methods
__is_exchange_pair(x, y) and __exchange(x, y), as well as an
initial basis. At any moment, BasisExchangeMatroid keeps a current basis
. The method __is_exchange_pair(x, y) should return a boolean
indicating whether
is a basis. The method __exchange(x, y)
is called when the current basis
is replaced by said
. It is
up to the child class to update its internal data structure to make
information relative to the new basis more accessible. For instance, a
linear matroid would perform a row reduction to make the column labeled by
a standard basis vector (and therefore the columns indexed by
would form an identity matrix).
Each of the elementary matroid methods has a straightforward greedy-type
implementation in terms of these two methods. For example, given a subset
of the groundset, one can step to a basis
over the edges of the
base exchange graph which has maximal intersection with
, in each step
increasing the intersection of the current
with
. Then one computes
the rank of
as the cardinality of the intersection of
and
.
The following matroid classes can/will implement their oracle efficiently by deriving from BasisExchangeMatroid:
BasisMatroid: keeps a list of all bases.
- __is_exchange_pair(x, y) reduces to a query whether
is a basis.
- __exchange(x, y) has no work to do.
LinearMatroid:
keeps a matrix representation of the matroid so that
.
- __is_exchange_pair(x, y) reduces to testing whether
is nonzero, where
.
- __exchange(x, y) should modify the matrix so that
becomes
, which means pivoting on
.
TransversalMatroid (not yet implemented): If is a set of subsets
of
, then
is independent if it is a system of distinct
representatives of
, i.e. if
is covered by a matching of an
appropriate bipartite graph
, with color classes
and
and an
edge
if
is in the subset
. At any time you keep a
maximum matching
of
covering the current basis
.
- __is_exchange_pair(x, y) checks for the existence of an
-alternating path
from
to
.
- __exchange(x, y) replaces
by the symmetric difference of
and
.
AlgebraicMatroid (not yet implemented): keeps a list of polynomials
in variables for each variable
in
.
- __is_exchange_pair(x, y) checks whether the polynomial that relates
to
uses
.
- __exchange(x, y) make new list of polynomials by computing resultants.
All but the first of the above matroids are algebraic, and all implementations specializations of the algebraic one.
BasisExchangeMatroid internally renders subsets of the ground set as bitsets. It provides optimized methods for enumerating bases, nonbases, flats, circuits, etc.
Return the list of bases of the matroid.
A basis is a maximal independent set.
OUTPUT:
An iterable containing all bases of the matroid.
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: M.bases_count()
184
sage: len([B for B in M.bases()])
184
Return the number of bases of the matroid.
A basis is an inclusionwise maximal independent set.
See also
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: M.bases_count()
184
Return an arbitrary basis of the matroid.
A basis is an inclusionwise maximal independent set.
Note
The output of this method can change in between calls. It reflects the internal state of the matroid. This state is updated by lots of methods, including the method M._move_current_basis().
OUTPUT:
Set of elements.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted(M.basis())
['a', 'b', 'c']
sage: M.rank('cd')
2
sage: sorted(M.basis())
['a', 'c', 'd']
Return the list of circuits of the matroid.
OUTPUT:
An iterable containing all circuits.
See also
EXAMPLES:
sage: M = Matroid(matroids.named_matroids.NonFano().bases())
sage: sorted([sorted(C) for C in M.circuits()])
[['a', 'b', 'c', 'g'], ['a', 'b', 'd', 'e'], ['a', 'b', 'f'],
['a', 'c', 'd', 'f'], ['a', 'c', 'e'], ['a', 'd', 'e', 'f'],
['a', 'd', 'g'], ['a', 'e', 'f', 'g'], ['b', 'c', 'd'],
['b', 'c', 'e', 'f'], ['b', 'd', 'e', 'f'], ['b', 'd', 'f', 'g'],
['b', 'e', 'g'], ['c', 'd', 'e', 'f'], ['c', 'd', 'e', 'g'],
['c', 'f', 'g'], ['d', 'e', 'f', 'g']]
Return the list of cocircuits of the matroid.
OUTPUT:
An iterable containing all cocircuits.
See also
EXAMPLES:
sage: M = Matroid(bases=matroids.named_matroids.NonFano().bases())
sage: sorted([sorted(C) for C in M.cocircuits()])
[['a', 'b', 'c', 'd', 'g'], ['a', 'b', 'c', 'e', 'g'],
['a', 'b', 'c', 'f', 'g'], ['a', 'b', 'd', 'e'],
['a', 'c', 'd', 'f'], ['a', 'e', 'f', 'g'], ['b', 'c', 'e', 'f'],
['b', 'd', 'f', 'g'], ['c', 'd', 'e', 'g']]
Return the collection of coflats of the matroid of specified corank.
A coflat is a coclosed set.
INPUT:
OUTPUT:
An iterable containing all coflats of corank r.
See also
EXAMPLES:
sage: M = matroids.named_matroids.S8().dual()
sage: M.f_vector()
[1, 8, 22, 14, 1]
sage: len(M.coflats(2))
22
sage: len(M.coflats(8))
0
sage: len(M.coflats(4))
1
Return the list of dependent subsets of fixed size.
INPUT:
OUTPUT:
An iterable containing all dependent subsets of size r.
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: len(M.nonbases())
68
sage: [len(M.dependent_r_sets(r)) for r in range(M.full_rank() + 1)]
[0, 0, 0, 0, 9, 68]
Return the -vector of the matroid.
The -vector is a vector
, where
is the
number of flats of rank
, and
is the rank of the matroid.
OUTPUT:
List of integers.
EXAMPLES:
sage: M = matroids.named_matroids.S8()
sage: M.f_vector()
[1, 8, 22, 14, 1]
Return the collection of flats of the matroid of specified rank.
A flat is a closed set.
INPUT:
OUTPUT:
An iterable containing all flats of rank r.
See also
EXAMPLES:
sage: M = matroids.named_matroids.S8()
sage: M.f_vector()
[1, 8, 22, 14, 1]
sage: len(M.flats(2))
22
sage: len(M.flats(8))
0
sage: len(M.flats(4))
1
Return the corank of the matroid.
The corank of the matroid equals the rank of the dual matroid. It is given by M.size() - M.full_rank().
OUTPUT:
Integer.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.full_corank()
4
sage: M.dual().full_corank()
3
Return the rank of the matroid.
The rank of the matroid is the size of the largest independent subset of the groundset.
OUTPUT:
Integer.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: M.full_rank()
3
sage: M.dual().full_rank()
4
Return the groundset of the matroid.
The groundset is the set of elements that comprise the matroid.
OUTPUT:
A set.
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
Return a list of elements of the groundset of the matroid.
The order of the list does not change between calls.
OUTPUT:
A list.
See also
EXAMPLES:
sage: M = matroids.named_matroids.Fano()
sage: type(M.groundset())
<type 'frozenset'>
sage: type(M.groundset_list())
<type 'list'>
sage: sorted(M.groundset_list())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
Return the list of size-r independent subsets of the matroid.
INPUT:
OUTPUT:
An iterable containing all independent subsets of the matroid of cardinality r.
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: M.bases_count()
184
sage: [len(M.independent_r_sets(r)) for r in range(M.full_rank() + 1)]
[1, 10, 45, 120, 201, 184]
Test if the data obey the matroid axioms.
This method checks the basis axioms for the class. If is the set
of bases of a matroid
, then
OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.matroids.advanced import *
sage: M = BasisMatroid(matroids.named_matroids.Fano())
sage: M.is_valid()
True
sage: M = Matroid(groundset='abcd', bases=['ab', 'cd'])
sage: M.is_valid()
False
Return the list of nonbases of the matroid.
A nonbasis is a set with cardinality self.full_rank() that is not a basis.
OUTPUT:
An iterable containing the nonbases of the matroid.
See also
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: binomial(M.size(), M.full_rank())-M.bases_count()
68
sage: len([B for B in M.nonbases()])
68
Return the list of noncospanning cocircuits of the matroid.
A noncospanning cocircuit is a cocircuit whose corank is strictly smaller than the corank of the matroid.
OUTPUT:
An iterable containing all nonspanning circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: len(M.noncospanning_cocircuits())
23
Return the list of nonspanning circuits of the matroid.
A nonspanning circuit is a circuit whose rank is strictly smaller than the rank of the matroid.
OUTPUT:
An iterable containing all nonspanning circuits.
See also
EXAMPLES:
sage: M = matroids.named_matroids.N1()
sage: len(M.nonspanning_circuits())
23