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

class sage.matroids.basis_exchange_matroid.BasisExchangeMatroid[source]

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 groundset as bitsets. It provides optimized methods for enumerating bases, nonbases, flats, circuits, etc.

bases_count()[source]

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

>>> from sage.all import *
>>> M = matroids.catalog.N1()
>>> M.bases_count()
184
basis()[source]

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']

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> sorted(M.basis())
['a', 'b', 'c']
>>> M.rank('cd')
2
>>> sorted(M.basis())
['a', 'c', 'd']
circuits(k=None)[source]

Return the circuits of the matroid.

OUTPUT: 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']]

>>> from sage.all import *
>>> M = Matroid(matroids.catalog.NonFano().bases())
>>> 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()[source]

Return the cocircuits of the matroid.

OUTPUT: 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']]

>>> from sage.all import *
>>> M = Matroid(bases=matroids.catalog.NonFano().bases())
>>> 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(k)[source]

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

A coflat is a coclosed set.

INPUT:

  • k – integer

OUTPUT: iterable containing all coflats of corank \(k\)

See also

Matroid.coclosure()

EXAMPLES:

sage: M = matroids.catalog.S8().dual()
sage: M.whitney_numbers2()
[1, 8, 22, 14, 1]
sage: len(M.coflats(2))
22
sage: len(M.coflats(8))
0
sage: len(M.coflats(4))
1

>>> from sage.all import *
>>> M = matroids.catalog.S8().dual()
>>> M.whitney_numbers2()
[1, 8, 22, 14, 1]
>>> len(M.coflats(Integer(2)))
22
>>> len(M.coflats(Integer(8)))
0
>>> len(M.coflats(Integer(4)))
1
components()[source]

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: 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}]

>>> from sage.all import *
>>> from sage.matroids.advanced import setprint
>>> M = Matroid(ring=QQ, matrix=[[Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0)],
...                              [Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(0)],
...                              [Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1)]])
>>> setprint(M.components())
[{0, 1, 3, 4}, {2, 5}]
dependent_sets(k)[source]

Return the dependent sets of fixed size.

INPUT:

  • k – integer

OUTPUT: iterable containing all dependent sets of size k

EXAMPLES:

sage: M = matroids.catalog.N1()
sage: len(M.nonbases())
68
sage: [len(M.dependent_sets(k)) for k in range(M.full_rank() + 1)]
[0, 0, 0, 0, 9, 68]

>>> from sage.all import *
>>> M = matroids.catalog.N1()
>>> len(M.nonbases())
68
>>> [len(M.dependent_sets(k)) for k in range(M.full_rank() + Integer(1))]
[0, 0, 0, 0, 9, 68]
flats(k)[source]

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

A flat is a closed set.

INPUT:

  • k – integer

OUTPUT: SetSystem

See also

Matroid.closure()

EXAMPLES:

sage: M = matroids.catalog.S8()
sage: M.whitney_numbers2()
[1, 8, 22, 14, 1]
sage: len(M.flats(2))
22
sage: len(M.flats(8))
0
sage: len(M.flats(4))
1

>>> from sage.all import *
>>> M = matroids.catalog.S8()
>>> M.whitney_numbers2()
[1, 8, 22, 14, 1]
>>> len(M.flats(Integer(2)))
22
>>> len(M.flats(Integer(8)))
0
>>> len(M.flats(Integer(4)))
1
full_corank()[source]

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

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> M.full_corank()
4
>>> M.dual().full_corank()
3
full_rank()[source]

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

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> M.full_rank()
3
>>> M.dual().full_rank()
4
groundset()[source]

Return the groundset of the matroid.

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

OUTPUT: set

EXAMPLES:

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

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> sorted(M.groundset())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
groundset_list()[source]

Return a list of elements of the groundset of the matroid.

The order of the list does not change between calls.

OUTPUT: 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']

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

>>> E = M.groundset_list()
>>> E.remove('a')
>>> sorted(M.groundset_list())
['a', 'b', 'c', 'd', 'e', 'f', 'g']
independent_sets(k=-1)[source]

Return the independent sets of the matroid.

INPUT:

  • k – integer (optional); if specified, return the size-\(k\) independent sets of the matroid

OUTPUT: SetSystem

EXAMPLES:

sage: M = matroids.catalog.Fano()
sage: I = M.independent_sets()
sage: len(I)
57
sage: M = matroids.catalog.N1()
sage: M.bases_count()
184
sage: [len(M.independent_sets(k)) for k in range(M.full_rank() + 1)]
[1, 10, 45, 120, 201, 184]

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> I = M.independent_sets()
>>> len(I)
57
>>> M = matroids.catalog.N1()
>>> M.bases_count()
184
>>> [len(M.independent_sets(k)) for k in range(M.full_rank() + Integer(1))]
[1, 10, 45, 120, 201, 184]
is_valid(certificate=False)[source]

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\).

INPUT:

  • certificate – boolean (default: False)

OUTPUT: boolean, or (boolean, dictionary)

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(certificate=True)
(False, {'error': 'exchange axiom failed'})

>>> from sage.all import *
>>> from sage.matroids.advanced import *
>>> M = BasisMatroid(matroids.catalog.Fano())
>>> M.is_valid()
True
>>> M = Matroid(groundset='abcd', bases=['ab', 'cd'])
>>> M.is_valid(certificate=True)
(False, {'error': 'exchange axiom failed'})
noncospanning_cocircuits()[source]

Return the noncospanning cocircuits of the matroid.

A noncospanning cocircuit is a cocircuit whose corank is strictly smaller than the corank of the matroid.

OUTPUT: iterable containing all nonspanning circuits

See also

Matroid.cocircuit(), Matroid.corank()

EXAMPLES:

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

>>> from sage.all import *
>>> M = matroids.catalog.N1()
>>> len(M.noncospanning_cocircuits())
23
nonspanning_circuits()[source]

Return the nonspanning circuits of the matroid.

A nonspanning circuit is a circuit whose rank is strictly smaller than the rank of the matroid.

OUTPUT: iterable containing all nonspanning circuits

See also

Matroid.circuit(), Matroid.rank()

EXAMPLES:

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

>>> from sage.all import *
>>> M = matroids.catalog.N1()
>>> len(M.nonspanning_circuits())
23
whitney_numbers2()[source]

Return the Whitney numbers of the second kind of the matroid.

The Whitney numbers of the second kind are here encoded as a vector \((W_0, \ldots, W_r)\), where \(W_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.whitney_numbers2()
[1, 8, 22, 14, 1]

>>> from sage.all import *
>>> M = matroids.catalog.S8()
>>> M.whitney_numbers2()
[1, 8, 22, 14, 1]