Iterators for linear subclasses#
The classes below are iterators returned by the functions
M.linear_subclasses()
and M.extensions()
.
See the documentation of these methods for more detail.
For direct access to these classes, run:
sage: from sage.matroids.advanced import *
>>> from sage.all import *
>>> from sage.matroids.advanced import *
See also sage.matroids.advanced
.
AUTHORS:
Rudi Pendavingh, Stefan van Zwam (2013-04-01): initial version
Methods#
- class sage.matroids.extension.CutNode[source]#
Bases:
object
An internal class used for creating linear subclasses of a matroids in a depth-first manner.
A linear subclass is a set of hyperplanes \(mc\) with the property that certain sets of hyperplanes must either be fully contained in \(mc\) or intersect \(mc\) in at most 1 element. The way we generate them is by a depth-first search. This class represents a node in the search tree.
It contains the set of hyperplanes selected so far, as well as a collection of hyperplanes whose insertion has been explored elsewhere in the search tree.
The class has methods for selecting a hyperplane to insert, for inserting hyperplanes and closing the set to become a linear subclass again, and for adding a hyperplane to the set of forbidden hyperplanes, and similarly closing that set.
- class sage.matroids.extension.LinearSubclasses[source]#
Bases:
object
An iterable set of linear subclasses of a matroid.
Enumerate linear subclasses of a given matroid. A linear subclass is a collection of hyperplanes (flats of rank \(r - 1\) where \(r\) is the rank of the matroid) with the property that no modular triple of hyperplanes has exactly two members in the linear subclass. A triple of hyperplanes in a matroid of rank \(r\) is modular if its intersection has rank \(r - 2\).
INPUT:
M
– a matroid.line_length
– (default:None
) an integer.subsets
– (default:None
) a set of subsets of the groundset ofM
.splice
– (default:None
) a matroid \(N\) such that for some \(e \in E(N)\) and some \(f \in E(M)\), we have \(N\setminus e= M\setminus f\).
OUTPUT:
An enumerator for the linear subclasses of M.
If
line_length
is notNone
, the enumeration is restricted to linear subclassesmc
so containing at least one of each set ofline_length
hyperplanes which have a common intersection of rank \(r - 2\).If
subsets
is notNone
, the enumeration is restricted to linear subclassesmc
containing all hyperplanes which fully contain some set fromsubsets
.If
splice
is notNone
, then the enumeration is restricted to linear subclasses \(mc\) such that if \(M'\) is the extension of \(M\) by \(e\) that arises from \(mc\), then \(M'\setminus f = N\).EXAMPLES:
sage: from sage.matroids.extension import LinearSubclasses sage: M = matroids.Uniform(3, 6) sage: len([mc for mc in LinearSubclasses(M)]) 83 sage: len([mc for mc in LinearSubclasses(M, line_length=5)]) 22 sage: for mc in LinearSubclasses(M, subsets=[[0, 1], [2, 3], [4, 5]]): ....: print(len(mc)) 3 15
>>> from sage.all import * >>> from sage.matroids.extension import LinearSubclasses >>> M = matroids.Uniform(Integer(3), Integer(6)) >>> len([mc for mc in LinearSubclasses(M)]) 83 >>> len([mc for mc in LinearSubclasses(M, line_length=Integer(5))]) 22 >>> for mc in LinearSubclasses(M, subsets=[[Integer(0), Integer(1)], [Integer(2), Integer(3)], [Integer(4), Integer(5)]]): ... print(len(mc)) 3 15
Note that this class is intended for runtime, internal use, so no loads/dumps mechanism was implemented.
- class sage.matroids.extension.LinearSubclassesIter[source]#
Bases:
object
An iterator for a set of linear subclass.
- class sage.matroids.extension.MatroidExtensions[source]#
Bases:
LinearSubclasses
An iterable set of single-element extensions of a given matroid.
INPUT:
M
– a matroide
– an elementline_length
(default:None
) – an integersubsets
(default:None
) – a set of subsets of the groundset ofM
splice
– a matroid \(N\) such that for some \(f \in E(M)\), we have \(N\setminus e= M\setminus f\).
OUTPUT:
An enumerator for the extensions of
M
to a matroidN
so that \(N\setminus e = M\). Ifline_length
is notNone
, the enumeration is restricted to extensions \(N\) without \(U(2, k)\)-minors, wherek > line_length
.If
subsets
is notNone
, the enumeration is restricted to extensions \(N\) of \(M\) by element \(e\) so that all hyperplanes of \(M\) which fully contain some set fromsubsets
, will also span \(e\).If
splice
is notNone
, then the enumeration is restricted to extensions \(M'\) such that \(M'\setminus f = N\), where \(E(M)\setminus E(N)=\{f\}\).EXAMPLES:
sage: from sage.matroids.advanced import * sage: M = matroids.Uniform(3, 6) sage: len([N for N in MatroidExtensions(M, 'x')]) 83 sage: len([N for N in MatroidExtensions(M, 'x', line_length=5)]) 22 sage: for N in MatroidExtensions(M, 'x', subsets=[[0, 1], [2, 3], ....: [4, 5]]): print(N) Matroid of rank 3 on 7 elements with 32 bases Matroid of rank 3 on 7 elements with 20 bases sage: M = BasisMatroid(matroids.catalog.BetsyRoss()); M Matroid of rank 3 on 11 elements with 140 bases sage: e = 'k'; f = 'h'; Me = M.delete(e); Mf=M.delete(f) sage: for N in MatroidExtensions(Mf, f, splice=Me): print(N) Matroid of rank 3 on 11 elements with 141 bases Matroid of rank 3 on 11 elements with 140 bases sage: for N in MatroidExtensions(Me, e, splice=Mf): print(N) Matroid of rank 3 on 11 elements with 141 bases Matroid of rank 3 on 11 elements with 140 bases
>>> from sage.all import * >>> from sage.matroids.advanced import * >>> M = matroids.Uniform(Integer(3), Integer(6)) >>> len([N for N in MatroidExtensions(M, 'x')]) 83 >>> len([N for N in MatroidExtensions(M, 'x', line_length=Integer(5))]) 22 >>> for N in MatroidExtensions(M, 'x', subsets=[[Integer(0), Integer(1)], [Integer(2), Integer(3)], ... [Integer(4), Integer(5)]]): print(N) Matroid of rank 3 on 7 elements with 32 bases Matroid of rank 3 on 7 elements with 20 bases >>> M = BasisMatroid(matroids.catalog.BetsyRoss()); M Matroid of rank 3 on 11 elements with 140 bases >>> e = 'k'; f = 'h'; Me = M.delete(e); Mf=M.delete(f) >>> for N in MatroidExtensions(Mf, f, splice=Me): print(N) Matroid of rank 3 on 11 elements with 141 bases Matroid of rank 3 on 11 elements with 140 bases >>> for N in MatroidExtensions(Me, e, splice=Mf): print(N) Matroid of rank 3 on 11 elements with 141 bases Matroid of rank 3 on 11 elements with 140 bases
Note that this class is intended for runtime, internal use, so no loads/dumps mechanism was implemented.