Coverage for local/lib/python2.7/site-packages/sage/matroids/basis_exchange_matroid.pyx : 84%
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
|
""" Basis exchange matroids
:class:`BasisExchangeMatroid <sage.matroids.basis_exchange_matroid.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 :mod:`Matroid <sage.matroids.matroid>`.
- :func:`bases_count() <sage.matroids.basis_exchange_matroid.BasisExchangeMatroid.bases_count>` - :func:`groundset_list() <sage.matroids.basis_exchange_matroid.BasisExchangeMatroid.groundset_list>`
AUTHORS:
- Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version
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.
Methods ======= """ #***************************************************************************** # Copyright (C) 2013 Rudi Pendavingh <rudi.pendavingh@gmail.com> # Copyright (C) 2013 Stefan van Zwam <stefanvanzwam@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import absolute_import
include 'sage/data_structures/bitset.pxi'
from .matroid cimport Matroid from .set_system cimport SetSystem
cdef class BasisExchangeMatroid(Matroid): r""" Class BasisExchangeMatroid is a virtual class that derives from Matroid. It implements each of the elementary matroid methods (:meth:`rank() <sage.matroids.matroid.Matroid.rank>`, :meth:`max_independent() <sage.matroids.matroid.Matroid.max_independent>`, :meth:`circuit() <sage.matroids.matroid.Matroid.circuit>`, :meth:`closure() <sage.matroids.matroid.Matroid.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``:
- :class:`BasisMatroid <sage.matroids.basis_matroid.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.
- :class:`LinearMatroid <sage.matroids.linear_matroid.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. """
def __init__(self, groundset, basis=None, rank=None): """ Construct a BasisExchangeMatroid.
A BasisExchangeMatroid is a virtual class. It is unlikely that you want to create a BasisExchangeMatroid from the command line. See the class docstring for :class:`BasisExchangeMatroid <sage.matroids.basis_exchange_matroid.BasisExchangeMatroid>`.
INPUT:
- ``groundset`` -- a set. - ``basis`` -- (default: ``None``) a subset of groundset. - ``rank`` -- (default: ``None``) an integer.
This initializer sets up a correspondance between elements of ``groundset`` and ``range(len(groundset))``. ``BasisExchangeMatroid`` uses this correspondence for encoding of subsets of the groundset as bitpacked sets of integers --- see ``__pack()`` and ``__unpack()``. In general, methods of ``BasisExchangeMatroid`` having a name starting with two underscores deal with such encoded subsets.
A second task of this initializer is to store the rank and initialize the 'current' basis.
EXAMPLES::
sage: from sage.matroids.basis_exchange_matroid import BasisExchangeMatroid sage: M = BasisExchangeMatroid(groundset='abcdef', basis='abc') sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f'] sage: sorted(M.basis()) ['a', 'b', 'c'] """ else:
else: cdef long i
def __dealloc__(self):
cdef __relabel(self, l): """ Relabel each element `e` as `l[e]`, where `l` is a given injective map.
INPUT:
- `l`, a python object such that `l[e]` is the new label of e.
OUTPUT:
``None``.
NOTE: For internal use. Matroids are immutable but this method does modify the matroid. The use this method will only be safe in very limited circumstances, such as perhaps on a fresh copy of a matroid.
""" cdef long i else:
self._weak_partition_var._relabel(l)
self._strong_partition_var._relabel(l) self._heuristic_partition_var._relabel(l)
# the engine cdef __pack(self, bitset_t I, F): """ Encode a subset F of the groundset into a bitpacked set of integers """
cdef __unpack(self, bitset_t I): """ Unencode a bitpacked set of integers to a subset of the groundset. """ cdef long i
# this method needs to be overridden by child class cdef bint __is_exchange_pair(self, long x, long y) except -1: """ Test if current_basis-x + y is a basis """ raise NotImplementedError
# if this method is overridden by a child class, the child class needs to call this method cdef int __exchange(self, long x, long y) except -1: """ put current_basis <-- current_basis-x + y """
cdef int __move(self, bitset_t X, bitset_t Y) except -1: """ Change current_basis to minimize intersection with ``X``, maximize intersection with ``Y``. """ cdef long x, y else:
cdef __fundamental_cocircuit(self, bitset_t C, long x): """ Return the unique cocircuit that meets ``self._current_basis`` in exactly element ``x``. """ cdef long y
cdef __fundamental_circuit(self, bitset_t C, long y): """ Return the unique circuit contained in ``self._current_basis`` union ``y``. """ cdef long x
cdef __max_independent(self, bitset_t R, bitset_t F): """ Bitpacked version of ``max_independent``. """
cdef __circuit(self, bitset_t R, bitset_t F): """ Bitpacked version of ``circuit``. """ cdef long x, y raise ValueError('no circuit in independent set.') raise ValueError('no circuit in independent set.') else:
cdef __closure(self, bitset_t R, bitset_t F): """ Bitpacked version of ``closure``. """
cdef __max_coindependent(self, bitset_t R, bitset_t F): """ Bitpacked version of ``max_coindependent``. """
cdef __cocircuit(self, bitset_t R, bitset_t F): """ Bitpacked version of ``cocircuit``. """ cdef long x, y raise ValueError('no cocircuit in coindependent set.') raise ValueError('no cocircuit in coindependent set.') else:
cdef __coclosure(self, bitset_t R, bitset_t F): """ Bitpacked version of ``closure``. """
cdef __augment(self, bitset_t R, bitset_t X, bitset_t Y): """ Bitpacked version of ``augment``. """
cdef bint __is_independent(self, bitset_t F) except -1: """ Bitpacked version of ``is_independent``. """
cdef __move_current_basis(self, bitset_t X, bitset_t Y): """ Bitpacked version of ``_move_current_basis``. """
# functions for derived classes and for parent class cdef bint _set_current_basis(self, F): """ Set _current_basis to subset of the groundset ``F``. """
# groundset and full_rank 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: M = matroids.named_matroids.Fano() sage: sorted(M.groundset()) ['a', 'b', 'c', 'd', 'e', 'f', 'g'] """
cpdef groundset_list(self): """ Return a list of elements of the groundset of the matroid.
The order of the list does not change between calls.
OUTPUT:
A list.
.. SEEALSO::
:meth:`M.groundset() <sage.matroids.basis_exchange_matroid.BasisExchangeMatroid.groundset>`
EXAMPLES::
sage: M = matroids.named_matroids.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'] """
def __len__(self): """ Return the size of the groundset.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: len(M) 7 sage: len(M.groundset()) 7
"""
cpdef full_rank(self): r""" 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 """
cpdef full_corank(self): r""" 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.
.. SEEALSO::
:meth:`M.dual() <sage.matroids.matroid.Matroid.dual>`, :meth:`M.full_rank() <sage.matroids.basis_exchange_matroid.BasisExchangeMatroid.full_rank>`
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: M.full_corank() 4 sage: M.dual().full_corank() 3 """
# matroid oracles
cpdef basis(self): r""" 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']
"""
cpdef _move_current_basis(self, X, Y): """ Change current basis so that intersection with X is maximized, intersection with Y is minimized.
INPUT:
- ``X`` -- an object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``. - ``Y`` -- an object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
Nothing.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(M.basis()) ['a', 'b', 'c', 'e'] sage: M._move_current_basis('ef', 'a') sage: sorted(M.basis()) ['b', 'c', 'e', 'f']
"""
cpdef _max_independent(self, F): """ Compute a maximal independent subset.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
A subset of ``F``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(M._max_independent(set(['a', 'c', 'd', 'e', 'f']))) ['a', 'c', 'd', 'e']
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.max_independent>`.
"""
cpdef _rank(self, F): """ Compute the rank of a subset of the ground set.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
Integer.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: M._rank(set(['a', 'c', 'd', 'e', 'f'])) 4
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.rank>`.
"""
cpdef _circuit(self, F): """ Return a minimal dependent subset.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
A circuit contained in ``F``, if it exists. Otherwise an error is raised.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(sage.matroids.matroid.Matroid._circuit(M, ....: set(['a', 'c', 'd', 'e', 'f']))) ['c', 'd', 'e', 'f'] sage: sorted(sage.matroids.matroid.Matroid._circuit(M, ....: set(['a', 'c', 'd']))) Traceback (most recent call last): ... ValueError: no circuit in independent set.
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.circuit>`. """
cpdef _fundamental_circuit(self, B, e): r""" Return the `B`-fundamental circuit using `e`.
Internal version that does no input checking.
INPUT:
- ``B`` -- a basis of the matroid. - ``e`` -- an element not in ``B``.
OUTPUT:
A set of elements.
EXAMPLES::
sage: M = matroids.named_matroids.P8() sage: sorted(M._fundamental_circuit('abcd', 'e')) ['a', 'b', 'c', 'e'] """
cpdef _closure(self, F): """ Return the closure of a set.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
The smallest closed set containing ``F``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(M._closure(set(['a', 'b', 'c']))) ['a', 'b', 'c', 'd']
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.closure>`.
"""
cpdef _max_coindependent(self, F): """ Compute a maximal coindependent subset.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
A maximal coindependent subset of ``F``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(M._max_coindependent(set(['a', 'c', 'd', 'e', 'f']))) ['a', 'c', 'd', 'f']
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.max_coindependent>`.
"""
cpdef _corank(self, F): """ Return the corank of a set.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
Integer, the corank of ``F``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: M._corank(set(['a', 'e', 'g', 'd', 'h'])) 4
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.corank>`. """
cpdef _cocircuit(self, F): """ Return a minimal codependent subset.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
A cocircuit contained in ``F``, if it exists. Otherwise an error is raised.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(sage.matroids.matroid.Matroid._cocircuit(M, ....: set(['a', 'c', 'd', 'e', 'f']))) ['c', 'd', 'e', 'f'] sage: sorted(sage.matroids.matroid.Matroid._cocircuit(M, ....: set(['a', 'c', 'd']))) Traceback (most recent call last): ... ValueError: no cocircuit in coindependent set.
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.cocircuit>`. """
cpdef _fundamental_cocircuit(self, B, e): r""" Return the `B`-fundamental circuit using `e`.
Internal version that does no input checking.
INPUT:
- ``B`` -- a basis of the matroid. - ``e`` -- an element of ``B``.
OUTPUT:
A set of elements.
EXAMPLES::
sage: M = matroids.named_matroids.P8() sage: sorted(M._fundamental_cocircuit('efgh', 'e')) ['b', 'c', 'd', 'e'] """
cpdef _coclosure(self, F): """ Return the coclosure of a set.
INPUT:
- ``X`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
The smallest coclosed set containing ``X``.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(M._coclosure(set(['a', 'b', 'c']))) ['a', 'b', 'c', 'd']
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.coclosure>`.
"""
cpdef _augment(self, X, Y): r""" Return a maximal subset `I` of `Y` such that `r(X + I)=r(X) + r(I)`.
This version of ``augment`` does no type checking. In particular, ``Y`` is assumed to be disjoint from ``X``.
INPUT:
- ``X`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``. - ``Y`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``, and disjoint from ``X``.
OUTPUT:
A subset `I` of ``Y`` such that `r(X + I)=r(X) + r(I)`.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: sorted(M._augment(set(['a']), set(['e', 'f', 'g', 'h']))) ['e', 'f', 'g']
"""
cpdef _is_independent(self, F): """ Test if input is independent.
INPUT:
- ``F`` -- An object with Python's ``frozenset`` interface containing a subset of ``self.groundset()``.
OUTPUT:
Boolean.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: M._is_independent(set(['a', 'b', 'c'])) True sage: M._is_independent(set(['a', 'b', 'c', 'd'])) False
.. NOTE::
This is an unguarded method. For the version that verifies if the input is indeed a subset of the ground set, see :meth:`<sage.matroids.matroid.Matroid.is_independent>`. """
# connectivity
cpdef components(self): """ 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 :meth:`connected <sage.matroids.matroid.Matroid.is_connected>`.
OUTPUT:
A list of subsets.
.. SEEALSO::
:meth:`M.is_connected() <sage.matroids.matroid.Matroid.is_connected>`, :meth:`M.delete() <sage.matroids.matroid.Matroid.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}] """ return SetSystem(self._E) cdef bitset_t *comp
cdef bitset_t active_rows
cdef bitset_t loop, loops
bitset_add(loop, e) res._append(loop) bitset_discard(loop, e) e = bitset_next(loops, e+1)
cpdef _link(self, S, T): r""" Given disjoint subsets `S` and `T`, return a connector `I` and a separation `X`, which are optimal dual solutions in Tutte's Linking Theorem:
.. MATH::
\max \{ r_N(S) + r_N(T) - r(N) \mid N = M/I\setminus J, E(N) = S\cup T\}=\\ \min \{ r_M(X) + r_M(Y) - r_M(E) \mid X \subseteq S, Y \subseteq T, E = X\cup Y, X\cap Y = \emptyset \}.
Here `M` denotes this matroid.
Internal version that does not verify that ``S`` and ``T`` are sets, are disjoint, are subsets of the groundset.
INPUT:
- ``S`` -- a subset of the ground set - ``T`` -- a subset of the ground set disjoint from ``S``
OUTPUT:
A tuple ``(I, X)`` containing a frozenset ``I`` and a frozenset ``X``.
ALGORITHM:
Compute a maximum-cardinality common independent set `I` of of `M / S \setminus T` and `M \setminus S / T`.
EXAMPLES::
sage: M = matroids.named_matroids.BetsyRoss() sage: S = set('ab') sage: T = set('cd') sage: I, X = M._link(S, T) sage: M.connectivity(X) 2 sage: J = M.groundset()-(S|T|I) sage: N = M/I\J sage: N.connectivity(S) 2 """ # compute maximal common independent set of self\S/T and self/T\S cdef bitset_t SS, TT #F = set(self.groundset()) - (S | T) cdef bitset_t F, I #I = self._augment(S|T, F) cdef bitset_t X, X1, X2, next_layer, todo, out_neighbors, R cdef long* predecessor cdef long e, u, y #X = F - I #X1 = X - self._closure(T|I) #X2 = X - self._closure(S|I) #predecessor = {x: None for x in X1} #next_layer = set(X1) #todo = next_layer #next_layer = {} #out_neighbors = self._circuit(I|S.union([u])) - S.union([u]) else: #out_neighbors = X - self._closure(I|T - set([u])) bitset_union(self._input, I, TT) bitset_discard(self._input, u) self.__closure(out_neighbors, self._input) bitset_difference(out_neighbors, X, out_neighbors) predecessor[y] = u if bitset_in(X2, y): found_path = True while y>=0: bitset_flip(I, y) y = predecessor[y] break bitset_add(R, y) bitset_add(next_layer, y) y = bitset_next(out_neighbors, y+1)
# enumeration
cpdef f_vector(self): r""" 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.named_matroids.S8() sage: M.f_vector() [1, 8, 22, 14, 1]
""" cdef bitset_t *flats cdef bitset_t *todo return [0]
cdef _f_vector_rec(self, object f_vec, bitset_t* flats, bitset_t* todo, long elt, long i): """ Recursion for the f_vector method. """ cdef long e
cpdef flats(self, 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``.
.. SEEALSO::
:meth:`Matroid.closure() <sage.matroids.matroid.Matroid.closure>`
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 """ cdef bitset_t *flats cdef bitset_t *todo
cdef _flats_rec(self, SetSystem Rflats, long R, bitset_t* flats, bitset_t* todo, long elt, long i): """ Recursion for the ``flats`` method. """ cdef long e
cpdef coflats(self, 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``.
.. SEEALSO::
:meth:`Matroid.coclosure() <sage.matroids.matroid.Matroid.coclosure>`
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 """ cdef bitset_t *coflats cdef bitset_t *todo
cdef _coflats_rec(self, SetSystem Rcoflats, long R, bitset_t* coflats, bitset_t* todo, long elt, long i): """ Recursion for the ``coflats`` method. """ cdef long e
cdef _flat_element_inv(self, long k): """ Compute a flat-element invariant of the matroid. """ cdef bitset_t *flats cdef bitset_t *todo return {}, tuple()
else:
cdef _flat_element_inv_rec(self, object f_inc, long R, bitset_t* flats, bitset_t* todo, long elt, long i): """ Recursion for ``_flat_element_inv``. """ cdef long e, k
cpdef bases_count(self): """ Return the number of bases of the matroid.
A *basis* is an inclusionwise maximal independent set.
.. SEEALSO::
:meth:`M.basis() <sage.matroids.matroid.Matroid.basis>`.
OUTPUT:
Integer.
EXAMPLES::
sage: M = matroids.named_matroids.N1() sage: M.bases_count() 184 """ return self._bcount
cpdef independent_sets(self): r""" Return the list of independent subsets of the matroid.
OUTPUT:
An iterable containing all independent subsets of the matroid.
EXAMPLES::
sage: M = matroids.named_matroids.Fano() sage: I = M.independent_sets() sage: len(I) 57 """ cdef bitset_t *I cdef bitset_t *T cdef long i, e, r
return res
else:
cpdef independent_r_sets(self, long 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.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]
""" cdef SetSystem BB return BB
cpdef bases(self): """ 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 """
cpdef dependent_r_sets(self, long 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.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]
""" cdef SetSystem NB return NB while repeat: NB._append(self._input) repeat = nxksrd(self._input, self._groundset_size, r, True) else:
cpdef nonbases(self): """ 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.
.. SEEALSO::
:meth:`Matroid.basis() <sage.matroids.matroid.Matroid.basis>`
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 """
cpdef nonspanning_circuits(self): """ 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.
.. SEEALSO::
:meth:`Matroid.circuit() <sage.matroids.matroid.Matroid.circuit>`, :meth:`Matroid.rank() <sage.matroids.matroid.Matroid.rank>`
EXAMPLES::
sage: M = matroids.named_matroids.N1() sage: len(M.nonspanning_circuits()) 23 """ cdef SetSystem NSC return NSC cdef long e, f
cpdef noncospanning_cocircuits(self): """ 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.
.. SEEALSO::
:meth:`Matroid.cocircuit() <sage.matroids.matroid.Matroid.cocircuit>`, :meth:`Matroid.corank() <sage.matroids.matroid.Matroid.corank>`
EXAMPLES::
sage: M = matroids.named_matroids.N1() sage: len(M.noncospanning_cocircuits()) 23 """ cdef SetSystem NSC return NSC cdef long e, f, corank
cpdef cocircuits(self): """ Return the list of cocircuits of the matroid.
OUTPUT:
An iterable containing all cocircuits.
.. SEEALSO::
:meth:`Matroid.cocircuit() <sage.matroids.matroid.Matroid.cocircuit>`
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']] """ cdef SetSystem NSC return NSC cdef long e, f, corank
cpdef circuits(self): """ Return the list of circuits of the matroid.
OUTPUT:
An iterable containing all circuits.
.. SEEALSO::
:meth:`M.circuit() <sage.matroids.matroid.Matroid.circuit>`
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']] """ cdef SetSystem NSC cdef long e, f
# isomorphism
cpdef _characteristic_setsystem(self): r""" Return a characteristic set-system for this matroid, on the same ground set.
OUTPUT:
A :class:`<sage.matroids.set_system.SetSystem>` instance.
EXAMPLES::
sage: M = matroids.named_matroids.N1() sage: M._characteristic_setsystem() Iterator over a system of subsets sage: len(M._characteristic_setsystem()) 23 """ else:
cpdef _weak_invariant(self): """ Return an isomorphism invariant of the matroid.
Compared to BasisExchangeMatroid._strong_invariant() this invariant distinguishes less frequently between nonisomorphic matroids but takes less time to compute. See also :meth:`<BasisExchangeMatroid._weak_partition>`.
OUTPUT:
An integer isomorphism invariant.
EXAMPLES::
sage: M = Matroid(bases=matroids.named_matroids.Fano().bases()) sage: N = Matroid(matroids.named_matroids.NonFano().bases()) sage: M._weak_invariant() == N._weak_invariant() False """ self._weak_invariant_var = 0 self._weak_partition_var = SetSystem(self._E, [self.groundset()]) else:
cpdef _weak_partition(self): """ Return an ordered partition based on the incidences of elements with low-dimensional flats.
EXAMPLES::
sage: M = Matroid(matroids.named_matroids.Vamos().bases()) sage: [sorted(p) for p in M._weak_partition()] [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']] """
cpdef _strong_invariant(self): """ Return an isomorphism invariant of the matroid.
Compared to BasisExchangeMatroid._weak_invariant() this invariant distinguishes more frequently between nonisomorphic matroids but takes more time to compute. See also :meth:`<BasisExchangeMatroid._strong_partition>`.
OUTPUT:
An integer isomorphism invariant.
EXAMPLES::
sage: M = Matroid(matroids.named_matroids.Fano().bases()) sage: N = Matroid(matroids.named_matroids.NonFano().bases()) sage: M._strong_invariant() == N._strong_invariant() False """
cpdef _strong_partition(self): """ Return an equitable partition which refines _weak_partition().
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: [sorted(p) for p in M._strong_partition()] [['a', 'b', 'e', 'f'], ['c', 'd', 'g', 'h']] """
cpdef _heuristic_invariant(self): """ Return a number characteristic for the construction of _heuristic_partition().
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: N = BasisMatroid(matroids.named_matroids.Vamos()) sage: M._heuristic_invariant() == N._heuristic_invariant() True """
cpdef _heuristic_partition(self): """ Return an ordered partition into singletons which refines an equitable partition of the matroid.
The purpose of this partition is to heuristically find an isomorphism between two matroids, by lining up their respective heuristic_partitions.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: N = BasisMatroid(matroids.named_matroids.Vamos()) sage: PM = M._heuristic_partition() sage: PN = N._heuristic_partition() sage: morphism = {} sage: for i in range(len(M)): morphism[min(PM[i])] = min(PN[i]) sage: M._is_isomorphism(N, morphism) True """
cdef _flush(self): """ Delete all invariants. """
cpdef _equitable_partition(self, P=None): """ Return the equitable refinement of a given ordered partition.
The coarsest equitable partition of the ground set of this matroid that refines P.
INPUT:
- ``P`` -- (default: ``None``) an ordered partition of the groundset. If ``None``, the trivial partition is used.
OUTPUT:
A SetSystem.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = BasisMatroid(matroids.named_matroids.Vamos()) sage: [sorted(p) for p in M._equitable_partition()] [['a', 'b', 'e', 'f'], ['c', 'd', 'g', 'h']] sage: [sorted(p) for p in M._equitable_partition(['a', 'bcdefgh'])] [['a'], ['b'], ['e', 'f'], ['c', 'd', 'g', 'h']] """ else:
cpdef _is_isomorphism(self, other, morphism): """ Version of is_isomorphism() that does no type checking.
INPUT:
- ``other`` -- A matroid instance. - ``morphism`` -- a dictionary mapping the groundset of ``self`` to the groundset of ``other``
OUTPUT:
Boolean.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M = matroids.named_matroids.Pappus() sage: N = BasisMatroid(matroids.named_matroids.NonPappus()) sage: N._is_isomorphism(M, {e:e for e in M.groundset()}) False
sage: M = matroids.named_matroids.Fano() \ ['g'] sage: N = matroids.Wheel(3) sage: morphism = {'a':0, 'b':1, 'c': 2, 'd':4, 'e':5, 'f':3} sage: M._is_isomorphism(N, morphism) True
TESTS:
Check that :trac:`23300` was fixed::
sage: def f(X): ....: return min(len(X), 2) ....: sage: M = Matroid(groundset='abcd', rank_function=f) sage: N = Matroid(field=GF(3), reduced_matrix=[[1,1],[1,-1]]) sage: N._is_isomorphism(M, {0:'a', 1:'b', 2:'c', 3:'d'}) True """ else:
cdef bint __is_isomorphism(self, BasisExchangeMatroid other, morphism): """ Bitpacked version of ``is_isomorphism``. """ cdef long i
cpdef _isomorphism(self, other): """ Returns an isomorphism form ``self`` to ``other``, if one exists.
Internal version that performs no checks on input.
INPUT:
- ``other`` -- A matroid.
OUTPUT:
A dictionary, or ``None``
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M1 = matroids.Wheel(3) sage: M2 = matroids.CompleteGraphic(4) sage: morphism = M1._isomorphism(M2) sage: M1._is_isomorphism(M2, morphism) True sage: M1 = matroids.named_matroids.Fano() sage: M2 = matroids.named_matroids.NonFano() sage: M1._isomorphism(M2) is None True
TESTS:
Check that :trac:`23300` was fixed::
sage: def f(X): ....: return min(len(X), 2) ....: sage: M = Matroid(groundset='abcd', rank_function=f) sage: N = Matroid(field=GF(3), reduced_matrix=[[1,1],[1,-1]]) sage: N._isomorphism(M) is not None True """ return {e:e for e in self.groundset()} return None return {self.groundset_list()[i]: other.groundset_list()[i] for i in xrange(len(self))}
morphism = {} for i in xrange(len(self)): morphism[min(PS[i])] = min(PO[i]) if self.__is_isomorphism(other, morphism): return morphism else: return None
return False morphism = {} for i in xrange(len(self)): morphism[min(PS[i])] = min(PO[i]) if self.__is_isomorphism(other, morphism): return morphism else: return None
return self._characteristic_setsystem()._isomorphism(other._characteristic_setsystem(), PS, PO)
cpdef _is_isomorphic(self, other, certificate=False): """ Test if ``self`` is isomorphic to ``other``.
Internal version that performs no checks on input.
INPUT:
- ``other`` -- A matroid, - optional parameter ``certificate`` -- Boolean.
OUTPUT:
Boolean, and, if certificate = True, a dictionary giving the isomorphism or None
.. NOTE::
Internal version that does no input checking.
EXAMPLES::
sage: from sage.matroids.advanced import * sage: M1 = BasisMatroid(matroids.Wheel(3)) sage: M2 = matroids.CompleteGraphic(4) sage: M1._is_isomorphic(M2) True sage: M1._is_isomorphic(M2, certificate=True) (True, {0: 0, 1: 1, 2: 2, 3: 3, 4: 5, 5: 4}) sage: M1 = BasisMatroid(matroids.named_matroids.Fano()) sage: M2 = matroids.named_matroids.NonFano() sage: M1._is_isomorphic(M2) False sage: M1._is_isomorphic(M2, certificate=True) (False, None)
""" return self._is_isomorphic(other), self._isomorphism(other) # Either generic test, which converts other to BasisMatroid, # or overridden method. return True return False return True return len(self.loops()) == len(other.loops()) return len(self.coloops()) == len(other.coloops())
morphism = {} for i in xrange(len(self)): morphism[min(PS[i])] = min(PO[i]) return self.__is_isomorphism(other, morphism)
morphism = {} for i in xrange(len(self)): morphism[min(PS[i])] = min(PO[i]) return self.__is_isomorphism(other, morphism)
return self._characteristic_setsystem()._isomorphism(other._characteristic_setsystem(), PS, PO) is not None
cpdef is_valid(self): r""" 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.named_matroids.Fano()) sage: M.is_valid() True sage: M = Matroid(groundset='abcd', bases=['ab', 'cd']) sage: M.is_valid() False
TESTS:
Verify that :trac:`20172` was fixed::
sage: M=Matroid(groundset='1234',bases=['12','13','23','34']) sage: M.is_valid() False """ cdef long pointerX, pointerY, x, y, ln cdef bint foundpair cdef SetSystem BB # Set current basis to Y # We failed to set the current basis to Y through basis exchanges. # Therefore, the exchange axioms are violated! else: return False
cdef bint nxksrd(bitset_s* b, long n, long k, bint succ): """ Next size-k subset of a size-n set in a revolving-door sequence. It will cycle through all such sets, returning each set exactly once. Each successive set differs from the last in exactly one element.
Returns ``True`` if there is a next set, ``False`` otherwise. """ # next k-subset of n-set in a revolving-door sequence else: else: else: else: else: else: else: |