Collections¶
The galactic.algebras.lattice.collections
module defines essential type for
representing lattices and their
derivatives.
-
class
galactic.algebras.lattice.collections.
JoinSemiLattice
¶ Bases:
galactic.algebras.poset.collections.PartiallyOrderedSet
The
JoinSemiLattice
class describes finite join semi-lattices.-
abstract
maximum
() → J¶ Get the maximum element of this join semi-lattice.
- Returns
the maximum element
- Return type
-
abstract
co_atoms
() → Iterator[J]¶ Get the atoms of this join semi-lattice.
- Returns
An iterator over the co-atoms
- Return type
-
abstract
join_irreducible
() → Iterator[J]¶ Get the join irreducible elements of this join semi-lattice.
- Returns
An iterator over the join irreducible elements
- Return type
-
abstract
is_join_irreducible
(element: J) → bool¶ Return
True
if the element is a join-irreducible of this join semi-lattice.
-
abstract
greatest_join_irreducible
(element: J) → Iterator[J]¶ Get the greatest join irreducible smaller than an element of this join semi-lattice.
- Parameters
element (
J
) – The element whose greatest join irreducible are requested- Returns
An iterator over the greatest join irreducible smaller than the element.
- Return type
-
abstract
-
class
galactic.algebras.lattice.collections.
AbstractJoinSemiLattice
¶ Bases:
galactic.algebras.lattice.collections.join_semi_lattices.JoinSemiLattice
,galactic.algebras.poset.collections.AbstractPartiallyOrderedSet
The
AbstractJoinSemiLattice
class defines essential methods useful in sub-classes.It is not designed to be directly instantiated.
-
top
() → Iterator[J]¶ Get an iterator over the top elements. The iteration return an iterator over only one element, the maximum element.
- Returns
An iterator over the top elements.
- Return type
-
bottom
() → Iterator[J]¶ Get an iterator over the bottom elements. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.
- Returns
An iterator over the bottom elements.
- Return type
-
co_atoms
() → Iterator[J]¶ Get the co-atoms of this join semi-lattice. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.
- Returns
An iterator over the atoms
- Return type
-
greatest_join_irreducible
(element: J) → Iterator[J]¶ Get the greatest join irreducible smaller than an element of this join semi-lattice. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.
- Parameters
element (
J
) – The element whose greatest join irreducible are requested- Returns
An iterator over the greatest join irreducible smaller than the element.
- Return type
- Raises
ValueError – If the element does not belong to the join semi-lattice.
-
join_irreducible
() → Iterator[J]¶ Get the join irreducible elements.
- Returns
An iterator over the join irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
BasicJoinSemiLattice
(iterable: Iterable[P] = None)¶ Bases:
galactic.algebras.lattice.collections.join_semi_lattices.AbstractJoinSemiLattice
,galactic.algebras.poset.collections.BasicPartiallyOrderedSet
The
BasicJoinSemiLattice
class implements methods ofJoinSemiLattice
.Its memory complexity is in \(O(n^2)\)
Example
>>> from galactic.algebras.lattice.collections import CompactJoinSemiLattice >>> from galactic.examples.arithmetic.algebras import Integer >>> j = BasicJoinSemiLattice([ ... Integer(2*3*5), ... Integer(3*5*7), ... Integer(5*7*11) ... ]) >>>
It’s possible to get the maximum element.
Example
>>> int(j.maximum()) 2310
It’s possible to iterate over the co-atoms.
Example
>>> sorted([int(element) for element in j.co_atoms()]) [210, 1155]
It’s possible to iterate over the join irreducible.
Example
>>> sorted([int(element) for element in j.join_irreducible()]) [30, 105, 385]
It’s possible to iterate over the generators of an element.
Example
>>> sorted([int(element) for element in j.greatest_join_irreducible( ... Integer(3*5*7*11) ... )]) [105, 385]
It’s possible to enlarge a join semi-lattice.
Example
>>> j = j + [Integer(13)] >>> sorted([int(element) for element in j]) [13, 30, 105, 210, 385, 390, 1155, 1365, 2310, 2730, 5005, 15015, 30030]
It’s possible to combine two join semi-lattice.
Example
>>> j = j @ BasicJoinSemiLattice([Integer(17)]) >>> from pprint import pprint >>> pprint(sorted([int(element) for element in j])) [13, 17, 30, 105, 210, 221, 385, 390, 510, 1155, 1365, 1785, 2310, 2730, 3570, 5005, 6545, 6630, 15015, 19635, 23205, 30030, 39270, 46410, 85085, 255255, 510510]
-
maximum
() → J¶ Get the maximum element of join semi-lattice. This operation is in \(O(n)\).
- Returns
the maximum element
- Return type
J
-
join_irreducible
() → Iterator[J]¶ Get the join irreducible elements of this join semi-lattice. This operation is in \(O(n)\).
- Returns
An iterator over the join irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
CompactJoinSemiLattice
(iterable: Iterable[J] = None)¶ Bases:
galactic.algebras.lattice.collections.join_semi_lattices.AbstractJoinSemiLattice
The
CompactJoinSemiLattice
class implements methods ofJoinSemiLattice
.A
CompactJoinSemiLattice
instance stores its the irreducible in a dictionary.Its memory complexity is in \(O(j)\)
Example
>>> from galactic.algebras.lattice.collections import CompactJoinSemiLattice >>> from galactic.examples.arithmetic.algebras import Integer >>> j = CompactJoinSemiLattice([ ... Integer(2*3*5), ... Integer(3*5*7), ... Integer(5*7*11) ... ]) >>>
It’s possible to get the maximum element.
Example
>>> int(j.maximum()) 2310
It’s possible to iterate over the co-atoms.
Example
>>> sorted([int(element) for element in j.co_atoms()]) [210, 1155]
It’s possible to iterate over the join irreducible.
Example
>>> sorted([int(element) for element in j.join_irreducible()]) [30, 105, 385]
It’s possible to iterate over the generators of an element.
Example
>>> sorted([int(element) for element in j.greatest_join_irreducible( ... Integer(3*5*7*11) ... )]) [105, 385]
It’s possible to enlarge a join semi-lattice.
Example
>>> j = j + [Integer(13)] >>> sorted([int(element) for element in j]) [13, 30, 105, 210, 385, 390, 1155, 1365, 2310, 2730, 5005, 15015, 30030]
It’s possible to combine two join semi-lattice.
Example
>>> j = j @ CompactJoinSemiLattice([Integer(17)]) >>> from pprint import pprint >>> pprint(sorted([int(element) for element in j])) [13, 17, 30, 105, 210, 221, 385, 390, 510, 1155, 1365, 1785, 2310, 2730, 3570, 5005, 6545, 6630, 15015, 19635, 23205, 30030, 39270, 46410, 85085, 255255, 510510]
-
__init__
(iterable: Iterable[J] = None)¶ Initialise a
CompactJoinSemiLattice
instance.- Keyword Arguments
iterable (
Iterable[J]
) – An iterable of elements
-
__iter__
() → Iterator[J]¶ Get an iterator over the elements.
- Returns
an iterator over the elements
- Return type
-
__contains__
(element: J) → bool¶ Get the membership of an element. This operation is in \(O(j^2)\).
-
__copy__
()¶ Get a copy of the join semi-lattice. This operation is in \(O(j)\).
- Returns
The copy of this join semi-lattice.
- Return type
-
__iadd__
(iterable: Iterable[J])¶ In-place enlarge the join semi-lattice with an iterable of elements.
- Keyword Arguments
iterable (
Iterable[P]
) – An iterable of elements
-
upper_limit
(limit: J, strict: bool = False) → Iterator[J]¶ Get an iterator over the elements lesser than a
limit
.- Parameters
limit (
J
) – The upper limitstrict (
bool
) – Is the comparison strict?
- Returns
An iterator over the selected elements.
- Return type
-
lower_limit
(limit: J, strict: bool = False) → Iterator[J]¶ Get an iterator over the elements greater than a
limit
.- Parameters
limit (
J
) – The lower limitstrict (
bool
) – Is the comparison strict?
- Returns
An iterator over the selected elements.
- Return type
-
maximum
() → J¶ Get the minimum element of this join semi-lattice. This operation is in \(O(j)\).
- Returns
The maximum element
- Return type
J
-
join_irreducible
() → Iterator[J]¶ Get the join irreducible elements of this join semi-lattice. This operation is in \(O(1)\).
- Returns
An iterator over the join irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
Lattice
¶ Bases:
galactic.algebras.lattice.collections.join_semi_lattices.JoinSemiLattice
,galactic.algebras.lattice.collections.meet_semi_lattices.MeetSemiLattice
The
Lattice
class describes finite lattice.-
abstract
irreducible
() → Iterator[E]¶ Get the irreducible elements.
- Returns
An iterator over the irreducible elements
- Return type
-
abstract
-
class
galactic.algebras.lattice.collections.
AbstractLattice
¶ Bases:
galactic.algebras.lattice.collections.lattices.Lattice
,galactic.algebras.lattice.collections.join_semi_lattices.AbstractJoinSemiLattice
,galactic.algebras.lattice.collections.meet_semi_lattices.AbstractMeetSemiLattice
The
AbstractLattice
implements some basic methods of theLattice
class.-
top
() → Iterator[E]¶ Get an iterator over the top elements. Its a proxy to
AbstractJoinSemiLattice.top()
.- Returns
An iterator over the top elements.
- Return type
-
bottom
() → Iterator[E]¶ Get an iterator over the bottom elements. Its a proxy to
AbstractMeetSemiLattice.bottom()
.- Returns
An iterator over the bottom elements.
- Return type
-
join_irreducible
() → Iterator[E]¶ Get the join irreducible elements.
- Returns
An iterator over the join irreducible elements
- Return type
-
meet_irreducible
() → Iterator[E]¶ Get the meet irreducible elements.
- Returns
An iterator over the meet irreducible elements
- Return type
-
irreducible
() → Iterator[E]¶ Get the irreducible elements.
- Returns
An iterator over the irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
BasicLattice
(iterable: Iterable[P] = None)¶ Bases:
galactic.algebras.lattice.collections.lattices.AbstractLattice
,galactic.algebras.lattice.collections.meet_semi_lattices.BasicMeetSemiLattice
,galactic.algebras.lattice.collections.join_semi_lattices.BasicJoinSemiLattice
The
BasicLattice
class implements basic lattices.Its memory complexity is in \(O(n^2)\)
-
join_irreducible
() → Iterator[E]¶ Get the join-irreducible elements of this lattice. This operation is in \(O(n^2)\).
- Returns
An iterator over the join-irreducible elements
- Return type
-
meet_irreducible
() → Iterator[E]¶ Get the meet-irreducible elements of this meet lattice. This operation is in \(O(n^2)\).
- Returns
An iterator over the meet-irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
CompactLattice
(iterable: Iterable[E] = None)¶ Bases:
galactic.algebras.lattice.collections.lattices.AbstractLattice
The
CompactLattice
store a compact version of a lattice using its join irreducible and meet irreducible elements.-
__init__
(iterable: Iterable[E] = None)¶ Initialise a
GeneratedBasicLattice
instance.- Parameters
iterable (
Iterable[E]
) – An iterable of elements- Raises
TypeError – If the
iterable
argument is not an instance ofIterable
-
__contains__
(element: E) → bool¶ Get the membership of an element. The operation is in \(O(j+m)\)
-
successors
(element: E) → Iterator[E]¶ Get an iterator over the successors of an
element
. The operation is in \(O(n^2)\) or in \(O(1)\) when used in an iteration over the lattice.- Parameters
element (
E
) – The element whose successors are requested- Returns
An iterator over the successors.
- Return type
- Raises
ValueError: – If the element does not belong to the poset.
-
predecessors
(element: E) → Iterator[E]¶ Get an iterator over the predecessors of an
element
. The operation is in \(O(n^2)\) or in \(O(1)\) when used in an iteration over the lattice.- Parameters
element (
E
) – The element whose predecessors are requested- Returns
An iterator over the predecessors.
- Return type
- Raises
ValueError: – If the element does not belong to the poset.
-
__copy__
()¶ Get a copy of the lattice. The operation is in \(O(j+m)\).
- Returns
The copy of this lattice.
- Return type
-
__iadd__
(iterable: Iterable[E])¶ In-place enlarge the lattice with an iterable of elements.
- Keyword Arguments
iterable (
Iterable[P]
) – An iterable of elements
-
__imatmul__
(other: galactic.algebras.lattice.collections.lattices.CompactLattice[E])¶ In-place combine the lattice with another lattice.
- Parameters
other (
CompactLattice
) – The lattice
-
__matmul__
(other: galactic.algebras.lattice.collections.lattices.CompactLattice[E])¶ Combine the lattice with another lattice.
- Parameters
other (
CompactLattice
) – The other lattice
-
maximum
() → E¶ Get the maximum element of this lattice. The operation is in \(O(j+m)\).
- Returns
the maximum element
- Return type
-
minimum
() → E¶ Get the minimum element of this lattice. The operation is in \(O(j+m)\).
- Returns
The minimum element
- Return type
-
co_atoms
() → Iterator[E]¶ Get the co-atoms of this lattice. The operation is in \(O(m^2)\).
- Returns
An iterator over the atoms
- Return type
-
atoms
() → Iterator[E]¶ Get the atoms of this lattice. The operation is in \(O(j^2)\).
- Returns
An iterator over the atoms
- Return type
-
meet_irreducible
() → Iterator[E]¶ Get the meet irreducible elements. The operation is in \(O(1)\).
- Returns
An iterator over the meet irreducible elements
- Return type
-
join_irreducible
() → Iterator[E]¶ Get the join irreducible elements. The operation is in \(O(1)\).
- Returns
An iterator over the join irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
MeetSemiLattice
¶ Bases:
galactic.algebras.poset.collections.PartiallyOrderedSet
The
MeetSemiLattice
class describes finite meet semi-lattices.-
abstract
minimum
() → M¶ Get the minimum element of this meet semi-lattice.
- Returns
The minimum element
- Return type
-
abstract
atoms
() → Iterator[M]¶ Get the atoms of this meet semi-lattice.
- Returns
An iterator over the atoms
- Return type
-
abstract
meet_irreducible
() → Iterator[M]¶ Get the meet-irreducible elements of this meet semi-lattice.
- Returns
An iterator over the meet-irreducible elements
- Return type
-
abstract
is_meet_irreducible
(element: M) → bool¶ Return
True
if the element is a meet-irreducible of this meet semi-lattice.
-
abstract
smallest_meet_irreducible
(element: M) → Iterator[M]¶ Get the smallest meet irreducible greater than an element of this meet semi-lattice.
- Parameters
element (
M
) – The element whose smallest meet irreducible are requested- Returns
An iterator over the smallest meet irreducible greater than the element.
- Return type
-
abstract
-
class
galactic.algebras.lattice.collections.
AbstractMeetSemiLattice
¶ Bases:
galactic.algebras.lattice.collections.meet_semi_lattices.MeetSemiLattice
,galactic.algebras.poset.collections.AbstractPartiallyOrderedSet
The
AbstractMeetSemiLattice
class defines essential methods useful in sub-classes.-
top
() → Iterator[M]¶ Get an iterator over the top elements. The iteration is in \(O(n^2)\). sub-classes may have overloaded this operation.
- Returns
An iterator over the top elements.
- Return type
-
bottom
() → Iterator[M]¶ Get an iterator over the bottom elements. The iteration return an iterator over only one element, the minimum element.
- Returns
An iterator over the bottom elements.
- Return type
-
atoms
() → Iterator[M]¶ Get the atoms of this meet semi-lattice. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.
- Returns
An iterator over the atoms
- Return type
-
smallest_meet_irreducible
(element: M) → Iterator[M]¶ Get the smallest meet irreducible greater than an element of this meet semi-lattice. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.
- Parameters
element (
M
) – The element whose smallest meet irreducible are requested- Returns
An iterator over the smallest meet irreducible greater than the element.
- Return type
- Raises
ValueError – If the element does not belong to the meet semi-lattice.
-
meet_irreducible
() → Iterator[M]¶ Get the meet irreducible elements.
- Returns
An iterator over the meet irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
BasicMeetSemiLattice
(iterable: Iterable[P] = None)¶ Bases:
galactic.algebras.lattice.collections.meet_semi_lattices.AbstractMeetSemiLattice
,galactic.algebras.poset.collections.BasicPartiallyOrderedSet
The
BasicMeetSemiLattice
class implements methods ofMeetSemiLattice
.Its memory complexity is in \(O(n^2)\)
Example
>>> from galactic.algebras.lattice.collections import BasicMeetSemiLattice >>> from galactic.examples.arithmetic.algebras import Integer >>> m = BasicMeetSemiLattice([ ... Integer(2*3*5), ... Integer(3*5*7), ... Integer(5*7*11) ... ]) >>>
It’s possible to iterate over the elements.
Example
>>> sorted([int(element) for element in m]) [5, 15, 30, 35, 105, 385]
It’s possible to get the minimum element.
Example
>>> int(m.minimum()) 5
It’s possible to iterate over the atoms.
Example
>>> sorted([int(element) for element in m.atoms()]) [15, 35]
It’s possible to iterate over the meet irreducible.
Example
>>> sorted([int(element) for element in m.meet_irreducible()]) [30, 105, 385]
It’s possible to iterate over the smallest meet irreducible greater than an element.
Example
>>> sorted([int(element) for element in m.smallest_meet_irreducible( ... Integer(35) ... )]) [105, 385]
It’s possible to enlarge a meet semi-lattice.
Example
>>> m = m + [Integer(13)] >>> sorted([int(element) for element in m]) [1, 5, 13, 15, 30, 35, 105, 385]
It’s possible to combine two meet semi-lattice.
Example
>>> m = m @ BasicMeetSemiLattice([Integer(17)]) >>> sorted([int(element) for element in m]) [1, 5, 13, 15, 17, 30, 35, 105, 385]
-
minimum
() → M¶ Get the minimum element of this meet semi-lattice. This operation is in \(O(n)\).
- Returns
The minimum element
- Return type
M
-
meet_irreducible
() → Iterator[M]¶ Get the meet-irreducible elements of this meet semi-lattice. This operation is in \(O(n^2)\).
- Returns
An iterator over the meet-irreducible elements
- Return type
-
-
class
galactic.algebras.lattice.collections.
CompactMeetSemiLattice
(iterable: Iterable[M] = None)¶ Bases:
galactic.algebras.lattice.collections.meet_semi_lattices.AbstractMeetSemiLattice
The
CompactMeetSemiLattice
class implements methods ofMeetSemiLattice
.A
CompactMeetSemiLattice
instance stores its the irreducible in a dictionary.Its memory complexity is in \(O(m)\)
Example
>>> from galactic.algebras.lattice.collections import CompactMeetSemiLattice >>> from galactic.examples.arithmetic.algebras import Integer >>> m = CompactMeetSemiLattice([ ... Integer(2*3*5), ... Integer(3*5*7), ... Integer(5*7*11) ... ]) >>>
It’s possible to iterate over the elements.
Example
>>> sorted([int(element) for element in m]) [5, 15, 30, 35, 105, 385]
It’s possible to get the minimum element.
Example
>>> int(m.minimum()) 5
It’s possible to iterate over the atoms.
Example
>>> sorted([int(element) for element in m.atoms()]) [15, 35]
It’s possible to iterate over the irreducible.
Example
>>> sorted([int(element) for element in m.meet_irreducible()]) [30, 105, 385]
It’s possible to iterate over the smallest meet irreducible greater than an element.
Example
>>> sorted([int(element) for element in m.smallest_meet_irreducible( ... Integer(5*7) ... )]) [105, 385]
It’s possible to enlarge a meet semi-lattice.
Example
>>> m = m + [Integer(13)] >>> sorted([int(element) for element in m]) [1, 5, 13, 15, 30, 35, 105, 385]
It’s possible to combine two meet semi-lattice.
Example
>>> m = m @ CompactMeetSemiLattice([Integer(17)]) >>> sorted([int(element) for element in m]) [1, 5, 13, 15, 17, 30, 35, 105, 385]
-
__init__
(iterable: Iterable[M] = None)¶ Initialise a
CompactMeetSemiLattice
instance.- Keyword Arguments
iterable (
Iterable[M]
) – An iterable of elements
-
__iter__
() → Iterator[M]¶ Get an iterator over the elements.
- Returns
an iterator over the elements
- Return type
-
__contains__
(element: M) → bool¶ Get the membership of an element. This operation is in \(O(m^2)\).
-
__copy__
()¶ Get a copy of the meet semi-lattice. This operation is in \(O(m)\).
- Returns
The copy of this meet semi-lattice.
- Return type
-
__iadd__
(iterable: Iterable[M])¶ In-place enlarge the partially ordered set with an iterable of elements.
- Keyword Arguments
iterable (
Iterable[M]
) – An iterable of elements
-
upper_limit
(limit: M, strict: bool = False) → Iterator[M]¶ Get an iterator over the elements lesser than a
limit
.- Parameters
limit (
M
) – The upper limitstrict (
bool
) – Is the comparison strict?
- Returns
An iterator over the selected elements.
- Return type
-
lower_limit
(limit: M, strict: bool = False) → Iterator[M]¶ Get an iterator over the elements greater than a
limit
.- Parameters
limit (
M
) – The lower limitstrict (
bool
) – Is the comparison strict?
- Returns
An iterator over the selected elements.
- Return type
-
minimum
() → M¶ Get the minimum element of this meet semi-lattice. This operation is in \(O(m)\).
- Returns
The minimum element
- Return type
M
-
meet_irreducible
() → Iterator[M]¶ Get the meet-irreducible elements of this meet semi-lattice. This operation is in \(O(1)\).
- Returns
An iterator over the meet-irreducible elements
- Return type
-