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: J

abstract co_atoms() → Iterator[J]¶

Get the atoms of this join semi-lattice.

Returns: An iterator over the co-atoms
Return type: Iterator[J]

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: Iterator[J]

abstract is_join_irreducible(element: J) → bool¶

Return True if the element is a join-irreducible of this join semi-lattice.

Returns: Return True if the element is a join-irreducible of this join semi-lattice.
Return type: bool

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: Iterator[J]

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: Iterator[J]

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: Iterator[J]

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: Iterator[J]

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: Iterator[J]
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: Iterator[J]

is_join_irreducible(element: J) → bool¶

Return True if the element is a join-irreducible of this join semi-lattice.

Returns: Return True if the element is a join-irreducible of this join semi-lattice.
Return type: bool

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 of JoinSemiLattice.

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: Iterator[J]

is_join_irreducible(element: J) → bool¶

Return True if the element is a join-irreducible of this join semi-lattice.

Returns: Return True if the element is a join-irreducible of this join semi-lattice.
Return type: bool

class galactic.algebras.lattice.collections.CompactJoinSemiLattice(iterable: Iterable[J] = None)¶

Bases: galactic.algebras.lattice.collections.join_semi_lattices.AbstractJoinSemiLattice

The CompactJoinSemiLattice class implements methods of JoinSemiLattice.

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: Iterator[J]

__contains__(element: J) → bool¶

Get the membership of an element. This operation is in \(O(j^2)\).

Parameters: element (J) – The element whose membership is requested.
Returns: True if the element belongs to the partially ordered set.
Return type: bool

__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: CompactJoinSemiLattice

__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 limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[J]

lower_limit(limit: J, strict: bool = False) → Iterator[J]¶

Get an iterator over the elements greater than a limit.

Parameters

limit (J) – The lower limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[J]

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: Iterator[J]

is_join_irreducible(element: J) → bool¶

Return True if the element is a join-irreducible of this join semi-lattice.

Returns: Return True if the element is a join-irreducible of this join semi-lattice.
Return type: bool

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: Iterator[E]

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 the Lattice 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: Iterator[E]

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: Iterator[E]

join_irreducible() → Iterator[E]¶

Get the join irreducible elements.

Returns: An iterator over the join irreducible elements
Return type: Iterator[E]

meet_irreducible() → Iterator[E]¶

Get the meet irreducible elements.

Returns: An iterator over the meet irreducible elements
Return type: Iterator[E]

irreducible() → Iterator[E]¶

Get the irreducible elements.

Returns: An iterator over the irreducible elements
Return type: Iterator[E]

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: Iterator[E]

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: Iterator[E]

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 of Iterable

__contains__(element: E) → bool¶

Get the membership of an element. The operation is in \(O(j+m)\)

Parameters: element (E) – The element whose membership is requested.
Returns: True if the element belongs to the partially ordered set.
Return type: bool

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: Iterator[E]
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: Iterator[E]
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: Lattice

__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: E

minimum() → E¶

Get the minimum element of this lattice. The operation is in \(O(j+m)\).

Returns: The minimum element
Return type: E

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: Iterator[E]

atoms() → Iterator[E]¶

Get the atoms of this lattice. The operation is in \(O(j^2)\).

Returns: An iterator over the atoms
Return type: Iterator[E]

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: Iterator[E]

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: Iterator[E]

is_join_irreducible(element: E) → bool¶

Return True if the element is a join-irreducible of this lattice.

Returns: Return True if the element is a join-irreducible of this lattice.
Return type: bool

is_meet_irreducible(element: E) → bool¶

Return True if the element is a meet-irreducible of this lattice.

Returns: Return True if the element is a meet-irreducible of this lattice.
Return type: bool

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: M

abstract atoms() → Iterator[M]¶

Get the atoms of this meet semi-lattice.

Returns: An iterator over the atoms
Return type: Iterator[M]

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: Iterator[M]

abstract is_meet_irreducible(element: M) → bool¶

Return True if the element is a meet-irreducible of this meet semi-lattice.

Returns: Return True if the element is a meet-irreducible of this meet semi-lattice.
Return type: bool

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: Iterator[M]

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: Iterator[M]

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: Iterator[M]

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: Iterator[M]

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: Iterator[M]
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: Iterator[M]

is_meet_irreducible(element: M) → bool¶

Return True if the element is a meet-irreducible of this meet semi-lattice.

Returns: Return True if the element is a meet-irreducible of this meet semi-lattice.
Return type: bool

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 of MeetSemiLattice.

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: Iterator[M]

is_meet_irreducible(element: M) → bool¶

Return True if the element is a meet-irreducible of this meet semi-lattice.

Returns: Return True if the element is a meet-irreducible of this meet semi-lattice.
Return type: bool

class galactic.algebras.lattice.collections.CompactMeetSemiLattice(iterable: Iterable[M] = None)¶

Bases: galactic.algebras.lattice.collections.meet_semi_lattices.AbstractMeetSemiLattice

The CompactMeetSemiLattice class implements methods of MeetSemiLattice.

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

__len__() → int¶

Get the number of elements.

Returns: the number of elements
Return type: int

__iter__() → Iterator[M]¶

Get an iterator over the elements.

Returns: an iterator over the elements
Return type: Iterator[M]

__contains__(element: M) → bool¶

Get the membership of an element. This operation is in \(O(m^2)\).

Parameters: element (M) – The element whose membership is requested.
Returns: True if the element belongs to the partially ordered set.
Return type: bool

__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: CompactMeetSemiLattice

__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 limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[M]

lower_limit(limit: M, strict: bool = False) → Iterator[M]¶

Get an iterator over the elements greater than a limit.

Parameters

limit (M) – The lower limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[M]

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: Iterator[M]

is_meet_irreducible(element: M) → bool¶

Return True if the element is a meet-irreducible of this meet semi-lattice.

Returns: Return True if the element is a meet-irreducible of this meet semi-lattice.
Return type: bool