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:

  • Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version

Methods#

class sage.matroids.basis_exchange_matroid.BasisExchangeMatroid#

Bases: 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 implicitly 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 \(B\). The method _is_exchange_pair(x, y) should return a boolean indicating whether \(B - x + y\) is a basis. The method _exchange(x, y) is called when the current basis \(B\) is replaced by said \(B-x + y\). 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 \(y\) a standard basis vector (and therefore the columns indexed by \(B-x+y\) 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 \(F\) of the groundset, one can step to a basis \(B\) over the edges of the base exchange graph which has maximal intersection with \(F\), in each step increasing the intersection of the current \(B\) with \(F\). Then one computes the rank of \(F\) as the cardinality of the intersection of \(F\) and \(B\).

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 \(B - x + y\) is a basis.

    • _exchange(x, y) has no work to do.

  • LinearMatroid: keeps a matrix representation \(A\) of the matroid so that \(A[B] = I\).

    • _is_exchange_pair(x, y) reduces to testing whether \(A[r, y]\) is nonzero, where \(A[r, x]=1\).

    • _exchange(x, y) should modify the matrix so that \(A[B - x + y]\) becomes \(I\), which means pivoting on \(A[r, y]\).

  • TransversalMatroid (not yet implemented): If \(A\) is a set of subsets of \(E\), then \(I\) is independent if it is a system of distinct representatives of \(A\), i.e. if \(I\) is covered by a matching of an appropriate bipartite graph \(G\), with color classes \(A\) and \(E\) and an edge \((A_i,e)\) if \(e\) is in the subset \(A_i\). At any time you keep a maximum matching \(M\) of \(G\) covering the current basis \(B\).

    • _is_exchange_pair(x, y) checks for the existence of an \(M\)-alternating path \(P\) from \(y\) to \(x\).

    • _exchange(x, y) replaces \(M\) by the symmetric difference of \(M\) and \(E(P)\).

  • AlgebraicMatroid (not yet implemented): keeps a list of polynomials in variables \(E - B + e\) for each variable \(e\) in \(B\).

    • _is_exchange_pair(x, y) checks whether the polynomial that relates \(y\) to \(E-B\) uses \(x\).

    • _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.

bases()#

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.catalog.N1()
sage: M.bases_count()
184
sage: len([B for B in M.bases()])
184
bases_count()#

Return the number of bases of the matroid.

A basis is an inclusionwise maximal independent set.

See also

M.basis().

OUTPUT:

Integer.

EXAMPLES:

sage: M = matroids.catalog.N1()
sage: M.bases_count()
184
basis()#

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.catalog.Fano()
sage: sorted(M.basis())
['a', 'b', 'c']
sage: M.rank('cd')
2
sage: sorted(M.basis())
['a', 'c', 'd']
circuits()#

Return the list of circuits of the matroid.

OUTPUT:

An iterable containing all circuits.

See also

M.circuit()

EXAMPLES:

sage: M = Matroid(matroids.catalog.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']]
cocircuits()#

Return the list of cocircuits of the matroid.

OUTPUT:

An iterable containing all cocircuits.

See also

Matroid.cocircuit()

EXAMPLES:

sage: M = Matroid(bases=matroids.catalog.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']]
coflats(r)#

Return the collection of coflats of the matroid of specified corank.

A coflat is a coclosed set.

INPUT:

  • r – A natural number.

OUTPUT:

An iterable containing all coflats of corank r.

See also

Matroid.coclosure()

EXAMPLES:

sage: M = matroids.catalog.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
components()#

Return an iterable containing the components of the matroid.

A component is an inclusionwise maximal connected subset of the matroid. A subset is connected if the matroid resulting from deleting the complement of that subset is connected.

OUTPUT:

A list of subsets.

See also

M.is_connected(), M.delete()

EXAMPLES:

sage: from sage.matroids.advanced import setprint
sage: M = Matroid(ring=QQ, matrix=[[1, 0, 0, 1, 1, 0],
....:                              [0, 1, 0, 1, 2, 0],
....:                              [0, 0, 1, 0, 0, 1]])
sage: setprint(M.components())
[{0, 1, 3, 4}, {2, 5}]
dependent_r_sets(r)#

Return the list of dependent subsets of fixed size.

INPUT:

  • r – a nonnegative integer.

OUTPUT:

An iterable containing all dependent subsets of size r.

EXAMPLES:

sage: M = matroids.catalog.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]
f_vector()#

Return the \(f\)-vector of the matroid.

The \(f\)-vector is a vector \((f_0, ..., f_r)\), where \(f_i\) is the number of flats of rank \(i\), and \(r\) is the rank of the matroid.

OUTPUT:

List of integers.

EXAMPLES:

sage: M = matroids.catalog.S8()
sage: M.f_vector()
[1, 8, 22, 14, 1]
flats(r)#

Return the collection of flats of the matroid of specified rank.

A flat is a closed set.

INPUT:

  • r – A natural number.

OUTPUT:

An iterable containing all flats of rank r.

See also

Matroid.closure()

EXAMPLES:

sage: M = matroids.catalog.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
full_corank()#

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

M.dual(), M.full_rank()

EXAMPLES:

sage: M = matroids.catalog.Fano()
sage: M.full_corank()
4
sage: M.dual().full_corank()
3
full_rank()#

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.catalog.Fano()
sage: M.full_rank()
3
sage: M.dual().full_rank()
4
groundset()#

Return the groundset of the matroid.

The groundset is the set of elements that comprise the matroid.

OUTPUT:

A set.

EXAMPLES:

sage: M = matroids.catalog.Fano()
sage: sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
groundset_list()#

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

M.groundset()

EXAMPLES:

sage: M = matroids.catalog.Fano()
sage: type(M.groundset())
<... 'frozenset'>
sage: type(M.groundset_list())
<... 'list'>
sage: sorted(M.groundset_list())
['a', 'b', 'c', 'd', 'e', 'f', 'g']

sage: E = M.groundset_list()
sage: E.remove('a')
sage: sorted(M.groundset_list())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
independent_r_sets(r)#

Return the list of size-r independent subsets of the matroid.

INPUT:

  • r – a nonnegative integer.

OUTPUT:

An iterable containing all independent subsets of the matroid of cardinality r.

EXAMPLES:

sage: M = matroids.catalog.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]
independent_sets()#

Return the list of independent subsets of the matroid.

OUTPUT:

An iterable containing all independent subsets of the matroid.

EXAMPLES:

sage: M = matroids.catalog.Fano()
sage: I = M.independent_sets()
sage: len(I)
57
is_valid()#

Test if the data obey the matroid axioms.

This method checks the basis axioms for the class. If \(B\) is the set of bases of a matroid \(M\), then

  • \(B\) is nonempty

  • if \(X\) and \(Y\) are in \(B\), and \(x\) is in \(X - Y\), then there is a \(y\) in \(Y - X\) such that \((X - x) + y\) is again a member of \(B\).

OUTPUT:

Boolean.

EXAMPLES:

sage: from sage.matroids.advanced import *
sage: M = BasisMatroid(matroids.catalog.Fano())
sage: M.is_valid()
True
sage: M = Matroid(groundset='abcd', bases=['ab', 'cd'])
sage: M.is_valid()
False
nonbases()#

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

Matroid.basis()

EXAMPLES:

sage: M = matroids.catalog.N1()
sage: binomial(M.size(), M.full_rank())-M.bases_count()                     # needs sage.symbolic
68
sage: len([B for B in M.nonbases()])
68
noncospanning_cocircuits()#

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

Matroid.cocircuit(), Matroid.corank()

EXAMPLES:

sage: M = matroids.catalog.N1()
sage: len(M.noncospanning_cocircuits())
23
nonspanning_circuits()#

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

Matroid.circuit(), Matroid.rank()

EXAMPLES:

sage: M = matroids.catalog.N1()
sage: len(M.nonspanning_circuits())
23