Set systems#

Many matroid methods return a collection of subsets. In this module a class SetSystem is defined to do just this. The class is intended for internal use, so all you can do as a user is iterate over its members.

The class is equipped with partition refinement methods to help with matroid isomorphism testing.

AUTHORS:

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

class sage.matroids.set_system.SetSystem[source]#

Bases: object

A SetSystem is an enumerator of a collection of subsets of a given fixed and finite groundset. It offers the possibility to enumerate its contents. One is most likely to encounter these as output from some Matroid methods:

sage: M = matroids.catalog.Fano()
sage: M.circuits()
SetSystem of 14 sets over 7 elements

>>> from sage.all import *
>>> M = matroids.catalog.Fano()
>>> M.circuits()
SetSystem of 14 sets over 7 elements

To access the sets in this structure, simply iterate over them. The simplest way must be:

sage: from sage.matroids.set_system import SetSystem
sage: S = SetSystem([1, 2, 3, 4], [[1, 2], [3, 4], [1, 2, 4]])
sage: T = list(S)

>>> from sage.all import *
>>> from sage.matroids.set_system import SetSystem
>>> S = SetSystem([Integer(1), Integer(2), Integer(3), Integer(4)], [[Integer(1), Integer(2)], [Integer(3), Integer(4)], [Integer(1), Integer(2), Integer(4)]])
>>> T = list(S)

Or immediately use it to iterate:

sage: from sage.matroids.set_system import SetSystem
sage: S = SetSystem([1, 2, 3, 4], [[1, 2], [3, 4], [1, 2, 4]])
sage: [min(X) for X in S]
[1, 3, 1]

>>> from sage.all import *
>>> from sage.matroids.set_system import SetSystem
>>> S = SetSystem([Integer(1), Integer(2), Integer(3), Integer(4)], [[Integer(1), Integer(2)], [Integer(3), Integer(4)], [Integer(1), Integer(2), Integer(4)]])
>>> [min(X) for X in S]
[1, 3, 1]

Note that this class is intended for runtime, so no loads/dumps mechanism was implemented.

Warning

The only guaranteed behavior of this class is that it is iterable. It is expected that M.circuits(), M.bases(), and so on will in the near future return actual iterators. All other methods (which are already hidden by default) are only for internal use by the Sage matroid code.

is_connected()[source]#

Test if the SetSystem is connected.

A SetSystem is connected if there is no nonempty proper subset X of the groundset so the each subset is either contained in X or disjoint from X.

EXAMPLES:

sage: from sage.matroids.set_system import SetSystem
sage: S = SetSystem([1, 2, 3, 4], [[1, 2], [3, 4], [1, 2, 4]])
sage: S.is_connected()
True
sage: S = SetSystem([1, 2, 3, 4], [[1, 2], [3, 4]])
sage: S.is_connected()
False
sage: S = SetSystem([1], [])
sage: S.is_connected()
True

>>> from sage.all import *
>>> from sage.matroids.set_system import SetSystem
>>> S = SetSystem([Integer(1), Integer(2), Integer(3), Integer(4)], [[Integer(1), Integer(2)], [Integer(3), Integer(4)], [Integer(1), Integer(2), Integer(4)]])
>>> S.is_connected()
True
>>> S = SetSystem([Integer(1), Integer(2), Integer(3), Integer(4)], [[Integer(1), Integer(2)], [Integer(3), Integer(4)]])
>>> S.is_connected()
False
>>> S = SetSystem([Integer(1)], [])
>>> S.is_connected()
True
class sage.matroids.set_system.SetSystemIterator[source]#

Bases: object

Create an iterator for a SetSystem.

Called internally when iterating over the contents of a SetSystem.

EXAMPLES:

sage: from sage.matroids.set_system import SetSystem
sage: S = SetSystem([1, 2, 3, 4], [[1, 2], [3, 4], [1, 2, 4]])
sage: type(S.__iter__())
<... 'sage.matroids.set_system.SetSystemIterator'>

>>> from sage.all import *
>>> from sage.matroids.set_system import SetSystem
>>> S = SetSystem([Integer(1), Integer(2), Integer(3), Integer(4)], [[Integer(1), Integer(2)], [Integer(3), Integer(4)], [Integer(1), Integer(2), Integer(4)]])
>>> type(S.__iter__())
<... 'sage.matroids.set_system.SetSystemIterator'>