r"""
Rank function matroids
The easiest way to define arbitrary matroids in Sage might be through the
class ``RankMatroid``. All that is required is a groundset and a function that
computes the rank for each given subset.
Of course, since the rank function is used as black box, matroids so defined
cannot take advantage of any extra structure your class might have, and rely
on default implementations. Besides this, matroids in this class can't be
saved.
Constructions
=============
Any function can be used, but no checks are performed, so be careful.
EXAMPLES::
sage: def f(X):
....: return min(len(X), 3)
....:
sage: M = Matroid(groundset=range(6), rank_function=f)
sage: M.is_valid()
True
sage: M.is_isomorphic(matroids.Uniform(3, 6))
True
sage: def g(X):
....: if len(X) >= 3:
....: return 1
....: else:
....: return 0
....:
sage: N = Matroid(groundset='abc', rank_function=g)
sage: N.is_valid()
False
See :class:`below <sage.matroids.rank_matroid.RankMatroid>` for more. It is
recommended to use the :func:`Matroid() <sage.matroids.constructor.Matroid>`
function for easy construction of a ``RankMatroid``. For direct access to the
``RankMatroid`` constructor, run::
sage: from sage.matroids.advanced import *
AUTHORS:
- Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version
Methods
=======
"""
from matroid import Matroid
class RankMatroid(Matroid):
"""
Matroid specified by its rank function.
INPUT:
- ``groundset`` -- the groundset of a matroid.
- ``rank_function`` -- a function mapping subsets of ``groundset`` to
nonnegative integers.
OUTPUT:
A matroid on ``groundset`` whose rank function equals ``rank_function``
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: def f(X):
....: return min(len(X), 3)
....:
sage: M = RankMatroid(groundset=range(6), rank_function=f)
sage: M.is_valid()
True
sage: M.is_isomorphic(matroids.Uniform(3, 6))
True
"""
def __init__(self, groundset, rank_function):
"""
Initialize the rank matroid.
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: M = RankMatroid(range(6),
....: rank_function=matroids.Uniform(3, 6).rank)
sage: M
Matroid of rank 3 on 6 elements
"""
self._groundset = frozenset(groundset)
self._rank_function = rank_function
def groundset(self):
r"""
Return the groundset of ``self``.
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: M = RankMatroid(range(6),
....: rank_function=matroids.Uniform(3, 6).rank)
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5]
"""
return self._groundset
def _rank(self, X):
r"""
Return the rank of set `X`.
Internal function without any sanity checks. May assume that ``X``
has Python's ``frozenset`` interface and is a subset of
self.groundset().
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: M = RankMatroid(range(6),
....: rank_function=matroids.Uniform(3, 6).rank)
sage: M._rank([0, 2, 4, 5])
3
"""
return self._rank_function(X)
def __hash__(self):
r"""
Return a string invariant of the matroid.
This function is called when matroids are added to a set. It is very
desirable to override it so it can distinguish matroids on the same
groundset, which is a very typical use case!
.. WARNING::
This method is linked to __richcmp__ (in Cython) and __cmp__ or
__eq__/__ne__ (in Python). If you override one, you should (and in
Cython: MUST) override the other!
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: M = Matroid(groundset=range(10),
....: rank_function=lambda X: min(len(X), 4))
sage: N = Matroid(groundset=range(10),
....: rank_function=lambda X: min(len(X), 4))
sage: O = Matroid(groundset=range(10),
....: rank_function=lambda X: min(len(X), 3))
sage: hash(M) == hash(N)
True
sage: hash(M) == hash(O)
False
"""
return hash((self.groundset(), self.full_rank()))
def __eq__(self, other):
"""
Compare two matroids.
INPUT:
- ``other`` -- A matroid.
OUTPUT:
``True`` if ``self`` and ``other have the same groundset and the same
rank function; ``False`` otherwise.
.. NOTE::
Note that rank functions ``f`` and ``g`` are normally deemed equal
only if ``f is g``. It would be too time-consuming to check all
their values.
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: def f(X):
....: return min(len(X), 3)
....:
sage: def g(X):
....: return min(len(X), 3)
....:
sage: M1 = RankMatroid(groundset=range(6), rank_function=f)
sage: M2 = RankMatroid(groundset=range(6), rank_function=g)
sage: M3 = RankMatroid(groundset=range(7), rank_function=f)
sage: M4 = RankMatroid(groundset=range(6), rank_function=f)
sage: M1 == M2 # indirect doctest
False
sage: M1 == M3
False
sage: M1 == M4
True
"""
if not isinstance(other, RankMatroid):
return False
return (self.groundset() == other.groundset()) and (self._rank_function == other._rank_function)
def __ne__(self, other):
"""
Compare two matroids.
INPUT:
- ``other`` -- A matroid.
OUTPUT:
``False`` if ``self`` and ``other have the same groundset and the
same rank function; ``True`` otherwise.
.. NOTE::
Rank functions ``f`` and ``g`` are normally deemed equal only if
``f is g``. It would be too time-consuming to check all their
values.
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: def f(X):
....: return min(len(X), 3)
....:
sage: def g(X):
....: return min(len(X), 3)
....:
sage: M1 = RankMatroid(groundset=range(6), rank_function=f)
sage: M2 = RankMatroid(groundset=range(6), rank_function=g)
sage: M3 = RankMatroid(groundset=range(7), rank_function=f)
sage: M4 = RankMatroid(groundset=range(6), rank_function=f)
sage: M1 != M2 # indirect doctest
True
sage: M1 != M3
True
sage: M1 != M4
False
"""
return not self.__eq__(other)
def __copy__(self):
"""
Create a shallow copy.
EXAMPLES::
sage: from sage.matroids.advanced import *
sage: M = Matroid(groundset=range(10),
....: rank_function=lambda X: min(len(X), 4))
sage: N = copy(M) # indirect doctest
sage: M == N
True
sage: M.groundset() is N.groundset()
True
"""
from copy import copy
N = RankMatroid(groundset=[], rank_function=None)
N._groundset = self._groundset
N._rank_function = self._rank_function
if getattr(self, '__custom_name') is not None:
N.rename(getattr(self, '__custom_name'))
return N
def __deepcopy__(self, memo={}):
"""
Create a deep copy.
.. NOTE::
Since matroids are immutable, a shallow copy normally suffices.
EXAMPLES::
sage: M = Matroid(groundset=range(10),
....: rank_function=lambda X: min(len(X), 4))
sage: N = deepcopy(M) # indirect doctest
sage: M == N
True
sage: M.groundset() is N.groundset()
False
"""
from copy import deepcopy
N = RankMatroid(groundset=deepcopy(self._groundset), rank_function=deepcopy(self._rank_function))
if getattr(self, '__custom_name') is not None:
N.rename(deepcopy(getattr(self, '__custom_name'), memo))
return N
def __reduce__(self):
"""
Save the matroid for later reloading.
.. NOTE::
Unfortunately, functions cannot be pickled reliably, so this class
doesn't have load/save support
EXAMPLES::
sage: M = Matroid(groundset=range(10),
....: rank_function=lambda X: min(len(X), 4))
sage: M == loads(dumps(M)) # indirect doctest
Traceback (most recent call last):
...
TypeError: unfortunately, functions cannot be saved reliably, so
this class doesn't have load/save support. Convert to another
class, such as BasisMatroid, instead.
"""
raise TypeError("unfortunately, functions cannot be saved reliably, so this class doesn't have load/save support. Convert to another class, such as BasisMatroid, instead.")
