Lattice¶

The galactic.algebras.lattice module defines essential types for representing lattices and their elements.

class galactic.algebras.lattice.Element¶

Bases: galactic.algebras.lattice.meet_semi_lattices.Meetable, galactic.algebras.lattice.join_semi_lattices.Joinable

The Element class describes elements that can be member of a lattice.

class galactic.algebras.lattice.Joinable¶

Bases: galactic.algebras.poset.elements.PartiallyOrdered

The:class:Joinable <galactic.algebras.lattice.Joinable> type sets for each pair of elements a, b an unique supremum c = a | b (also called a least upper bound or join).

A class implementing the:class:Joinable <galactic.algebras.lattice.Joinable> abstract class must be declared by inheriting from:class:Joinable <galactic.algebras.lattice.Joinable> with itself as a parameter and must implement the methods:

__lt__()
__gt__()
__eq__()
__or__()

Example

Let the integers ordered by the relation \(a \leq b\): is \(a\) a divisor of \(b\)?

implemented by the Integer class:

>>> from galactic.examples.arithmetic import Integer
>>> Integer(24) | Integer(36)
Integer(72)
>>> Integer(24).union(Integer(36), Integer(10))
Integer(360)

abstract __or__(other: Any) → galactic.algebras.lattice.join_semi_lattices.Joinable¶

Return the join of this element and the other.

Parameters: other – the other element
Returns: the join of this element and the other
Return type: Joinable

union(*args: Any) → galactic.algebras.lattice.join_semi_lattices.Joinable¶

Returns the union of this element and the others.

Parameters: *args (Joinable) – the others elements
Returns: the join of this element and the others
Return type: Joinable
Raises: TypeError – if one of the other elements is not an instance of this element class.

class galactic.algebras.lattice.Meetable¶

Bases: galactic.algebras.poset.elements.PartiallyOrdered

The Meetable type sets for each pair of elements a, b an unique infimum c = a & b (also called a greatest lower bound or meet).

A class implementing the Meetable abstract class must be declared by inheriting from Meetable with itself as a parameter and must implement the methods:

__lt__()
__gt__()
__eq__()
__and__()

Example

Let the integers ordered by the relation \(a \leq b\): is \(a\) a divisor of \(b\)?

implemented by the Integer class:

>>> from galactic.examples.arithmetic import Integer
>>> Integer(24) & Integer(36)
Integer(12)
>>> Integer(24).intersection(Integer(36), Integer(10))
Integer(2)

abstract __and__(other: Any) → galactic.algebras.lattice.meet_semi_lattices.Meetable¶

Return the meet of this element and the other.

Parameters: other – the other element
Returns: the meet of this element and the other
Return type: Meetable

intersection(*args: Any) → galactic.algebras.lattice.meet_semi_lattices.Meetable¶

Returns the intersection of this element and the others.

Parameters: *args (Meetable) – the others elements
Returns: the meet of this element and the others
Return type: Meetable
Raises: TypeError – if one of the other elements is not an instance of this element class.

galactic.algebras.lattice.infimum(iterable: Optional[Iterable[galactic.algebras.lattice.meet_semi_lattices.Meetable]] = None, default: Optional[galactic.algebras.lattice.meet_semi_lattices.Meetable] = None) → Optional[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

Computes the infimum of meetable elements.

Keyword Arguments

iterable (Optional[Iterable[Meetable]]) – An iterable collection of meetable elements.
default (Meetable) – The default value when the iterable is empty.

Returns

Return type

The intersection of all elements from the iterable collection.

galactic.algebras.lattice.supremum(iterable: Optional[Iterable[galactic.algebras.lattice.join_semi_lattices.Joinable]] = None, default: Optional[galactic.algebras.lattice.join_semi_lattices.Joinable] = None) → Optional[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

Computes the supremum of joinable elements.

Keyword Arguments

iterable (Iterable[joinable]) – An iterable collection of joinable elements.
default (Joinable) – The default value when the iterable is empty.

Returns

Return type

The union of all elements from the iterable collection.

galactic.algebras.lattice.infimum_generators(iterable: Iterable[galactic.algebras.lattice.meet_semi_lattices.Meetable]) → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

The infimum_generators() function produces the infimum generators from an iterable of meetable elements.

Keyword Arguments: iterable (Iterable[Meetable]) – The iterable collection of elements.
Returns: An iterator over the infimum generators.
Return type: Iterator[Meetable]

galactic.algebras.lattice.supremum_generators(iterable: Iterable[galactic.algebras.lattice.join_semi_lattices.Joinable]) → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

The supremum_generators() function produces the supremum generators from an iterable of joinable elements.

Keyword Arguments: iterable (Iterable[Joinable]) – The iterable collection of elements.
Returns: An iterator over the supremum generators.
Return type: Iterator[Joinable]

class galactic.algebras.lattice.JoinSemiLattice¶

Bases: galactic.algebras.poset.collections.PartiallyOrderedSet

JoinSemiLattice class describes finite join semi-lattices.

abstract maximum() → galactic.algebras.lattice.join_semi_lattices.Joinable¶

Get the maximum element of this join semi-lattice.

Returns: the maximum element
Return type: Joinable

abstract co_atoms() → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

Get the atoms of this join semi-lattice.

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

abstract join_irreducible() → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

Get the join irreducible elements of this join semi-lattice.

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

abstract is_join_irreducible(element: galactic.algebras.lattice.join_semi_lattices.Joinable) → 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: galactic.algebras.lattice.join_semi_lattices.Joinable) → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

Get the greatest join irreducible smaller than an element of this join semi-lattice.

Parameters: element (Joinable) – The element whose greatest join irreducible are requested
Returns: An iterator over the greatest join irreducible smaller than the element.
Return type: Iterator[Joinable]

class galactic.algebras.lattice.AbstractJoinSemiLattice¶

Bases: galactic.algebras.lattice.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[galactic.algebras.poset.elements.PartiallyOrdered]¶

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[Joinable]

bottom() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

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[PartiallyOrdered]

co_atoms() → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

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[PartiallyOrdered]

greatest_join_irreducible(element: galactic.algebras.lattice.join_semi_lattices.Joinable) → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

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 (Joinable) – The element whose greatest join irreducible are requested
Returns: An iterator over the greatest join irreducible smaller than the element.
Return type: Iterator[Joinable]
Raises: ValueError – If the element does not belong to the join semi-lattice.

join_irreducible() → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

Get the join irreducible elements.

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

is_join_irreducible(element: galactic.algebras.lattice.join_semi_lattices.Joinable) → 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.BasicJoinSemiLattice(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None)¶

Bases: galactic.algebras.lattice.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 import CompactJoinSemiLattice
>>> from galactic.examples.arithmetic 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() → galactic.algebras.lattice.join_semi_lattices.Joinable¶

Get the maximum element of join semi-lattice. This operation is in \(O(n)\).

Returns: the maximum element
Return type: Joinable

join_irreducible() → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

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[Joinable]

is_join_irreducible(element: galactic.algebras.lattice.join_semi_lattices.Joinable) → 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.CompactJoinSemiLattice(iterable: Optional[Iterable[galactic.algebras.lattice.join_semi_lattices.Joinable]] = None)¶

Bases: galactic.algebras.lattice.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 import CompactJoinSemiLattice
>>> from galactic.examples.arithmetic 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: Optional[Iterable[galactic.algebras.lattice.join_semi_lattices.Joinable]] = None)¶

Initialise a CompactJoinSemiLattice instance.

Keyword Arguments: iterable (Iterable[Joinable]) – An iterable of elements

__len__() → int ¶

Get the number of elements.

Returns: the number of elements
Return type: int

__iter__() → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

Get an iterator over the elements.

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

__contains__(element: Any) → bool ¶

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

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

__copy__() → galactic.algebras.lattice.join_semi_lattices.CompactJoinSemiLattice¶

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[galactic.algebras.lattice.join_semi_lattices.Joinable]) → galactic.algebras.lattice.join_semi_lattices.CompactJoinSemiLattice¶

In-place enlarge the join semi-lattice with an iterable of elements.

Keyword Arguments: iterable (Iterable[Joinable]) – An iterable of elements

upper_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the elements lesser than a limit.

Parameters

limit (PartiallyOrdered) – The upper limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[PartiallyOrdered]

lower_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the elements greater than a limit.

Parameters

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

Returns

An iterator over the selected elements.

Return type

Iterator[PartiallyOrdered]

maximum() → galactic.algebras.lattice.join_semi_lattices.Joinable¶

Get the minimum element of this join semi-lattice. This operation is in \(O(j)\).

Returns: The maximum element
Return type: Joinable

greatest_meet_irreducible(element: galactic.algebras.lattice.join_semi_lattices.Joinable) → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

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 (Joinable) – The element whose greatest join irreducible are requested
Returns: An iterator over the greatest join irreducible smaller than the element.
Return type: Iterator[Joinable]
Raises: ValueError – If the element does not belong to the join semi-lattice.

join_irreducible() → Iterator[galactic.algebras.lattice.join_semi_lattices.Joinable]¶

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[Joinable]

is_join_irreducible(element: galactic.algebras.lattice.join_semi_lattices.Joinable) → 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.MeetSemiLattice¶

Bases: galactic.algebras.poset.collections.PartiallyOrderedSet

The MeetSemiLattice class describes finite meet semi-lattices.

abstract minimum() → galactic.algebras.lattice.meet_semi_lattices.Meetable¶

Get the minimum element of this meet semi-lattice.

Returns: The minimum element
Return type: Meetable

abstract atoms() → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

Get the atoms of this meet semi-lattice.

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

abstract meet_irreducible() → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

Get the meet-irreducible elements of this meet semi-lattice.

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

abstract is_meet_irreducible(element: galactic.algebras.lattice.meet_semi_lattices.Meetable) → 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: galactic.algebras.lattice.meet_semi_lattices.Meetable) → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

Get the smallest meet irreducible greater than an element of this meet semi-lattice.

Parameters: element (Meetable) – The element whose smallest meet irreducible are requested
Returns: An iterator over the smallest meet irreducible greater than the element.
Return type: Iterator[Meetable]

class galactic.algebras.lattice.AbstractMeetSemiLattice¶

Bases: galactic.algebras.lattice.meet_semi_lattices.MeetSemiLattice, galactic.algebras.poset.collections.AbstractPartiallyOrderedSet

The AbstractMeetSemiLattice class defines essential methods useful in sub-classes.

top() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

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[PartiallyOrdered]

bottom() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

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[PartiallyOrdered]

atoms() → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

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[Meetable]

smallest_meet_irreducible(element: galactic.algebras.lattice.meet_semi_lattices.Meetable) → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

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 (Meetable) – The element whose smallest meet irreducible are requested
Returns: An iterator over the smallest meet irreducible greater than the element.
Return type: Iterator[Meetable]
Raises: ValueError – If the element does not belong to the meet semi-lattice.

meet_irreducible() → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

Get the meet irreducible elements.

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

is_meet_irreducible(element: galactic.algebras.lattice.meet_semi_lattices.Meetable) → 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.BasicMeetSemiLattice(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None)¶

Bases: galactic.algebras.lattice.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 import BasicMeetSemiLattice
>>> from galactic.examples.arithmetic 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() → galactic.algebras.lattice.meet_semi_lattices.Meetable¶

Get the minimum element of this meet semi-lattice. This operation is in \(O(n)\).

Returns: The minimum element
Return type: Meetable

meet_irreducible() → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

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[Meetable]

is_meet_irreducible(element: galactic.algebras.lattice.meet_semi_lattices.Meetable) → 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.CompactMeetSemiLattice(iterable: Optional[Iterable[galactic.algebras.lattice.meet_semi_lattices.Meetable]] = None)¶

Bases: galactic.algebras.lattice.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 import CompactMeetSemiLattice
>>> from galactic.examples.arithmetic 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: Optional[Iterable[galactic.algebras.lattice.meet_semi_lattices.Meetable]] = None)¶

Initialise a CompactMeetSemiLattice instance.

Keyword Arguments: iterable (Iterable[Meetable]) – An iterable of elements

__len__() → int ¶

Get the number of elements.

Returns: the number of elements
Return type: int

__iter__() → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

Get an iterator over the elements.

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

__contains__(element: Any) → bool ¶

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

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

__copy__() → galactic.algebras.lattice.meet_semi_lattices.CompactMeetSemiLattice¶

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[galactic.algebras.lattice.meet_semi_lattices.Meetable]) → galactic.algebras.lattice.meet_semi_lattices.CompactMeetSemiLattice¶

In-place enlarge the partially ordered set with an iterable of elements.

Keyword Arguments: iterable (Iterable[Meetable]) – An iterable of elements

upper_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the elements lesser than a limit.

Parameters

limit (PartiallyOrdered) – The upper limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[PartiallyOrdered]

lower_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the elements greater than a limit.

Parameters

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

Returns

An iterator over the selected elements.

Return type

Iterator[PartiallyOrdered]

minimum() → galactic.algebras.lattice.meet_semi_lattices.Meetable¶

Get the minimum element of this meet semi-lattice. This operation is in \(O(m)\).

Returns: The minimum element
Return type: Meetable

smallest_meet_irreducible(element: galactic.algebras.lattice.meet_semi_lattices.Meetable) → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

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 (Meetable) – The element whose smallest meet irreducible are requested
Returns: An iterator over the smallest meet irreducible greater than the element.
Return type: Iterator[Meetable]
Raises: ValueError – If the element does not belong to the meet semi-lattice.

meet_irreducible() → Iterator[galactic.algebras.lattice.meet_semi_lattices.Meetable]¶

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[Meetable]

is_meet_irreducible(element: galactic.algebras.lattice.meet_semi_lattices.Meetable) → 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.Lattice¶

Bases: galactic.algebras.lattice.join_semi_lattices.JoinSemiLattice, galactic.algebras.lattice.meet_semi_lattices.MeetSemiLattice

The Lattice class describes finite lattices.

abstract irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get the irreducible elements.

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

class galactic.algebras.lattice.AbstractLattice¶

Bases: galactic.algebras.lattice.lattices.Lattice, galactic.algebras.lattice.join_semi_lattices.AbstractJoinSemiLattice, galactic.algebras.lattice.meet_semi_lattices.AbstractMeetSemiLattice

The AbstractLattice implements some basic methods of the Lattice class.

top() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get an iterator over the top elements. Its a proxy to AbstractJoinSemiLattice.top().

Returns: An iterator over the top elements.
Return type: Iterator[PartiallyOrdered]

bottom() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get an iterator over the bottom elements. Its a proxy to AbstractMeetSemiLattice.bottom().

Returns: An iterator over the bottom elements.
Return type: Iterator[PartiallyOrdered]

join_irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get the join irreducible elements.

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

meet_irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get the meet irreducible elements.

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

irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get the irreducible elements.

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

class galactic.algebras.lattice.BasicLattice(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None)¶

Bases: galactic.algebras.lattice.lattices.AbstractLattice, galactic.algebras.lattice.meet_semi_lattices.BasicMeetSemiLattice, galactic.algebras.lattice.join_semi_lattices.BasicJoinSemiLattice

The BasicLattice class implements basic lattices.

Its memory complexity is in \(O(n^2)\)

join_irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

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[Element]

meet_irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

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[Element]

class galactic.algebras.lattice.CompactLattice(iterable: Optional[Iterable[galactic.algebras.lattice.lattices.Element]] = None)¶

Bases: galactic.algebras.lattice.lattices.AbstractLattice, galactic.algebras.lattice.join_semi_lattices.CompactJoinSemiLattice, galactic.algebras.lattice.meet_semi_lattices.CompactMeetSemiLattice

The CompactLattice store a compact version of a lattice using its join irreducible and meet irreducible elements.

__init__(iterable: Optional[Iterable[galactic.algebras.lattice.lattices.Element]] = None)¶

Initialise a GeneratedBasicLattice instance.

Parameters: iterable (Iterable[Element]) – An iterable of elements
Raises: TypeError – If the iterable argument is not an instance of Iterable

__contains__(element: Any) → bool ¶

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

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

successors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

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 (PartiallyOrdered) – The element whose successors are requested
Returns: An iterator over the successors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

predecessors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

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 (Element) – The element whose predecessors are requested
Returns: An iterator over the predecessors.
Return type: Iterator[Element]
Raises: ValueError: – If the element does not belong to the poset.

__copy__() → galactic.algebras.lattice.lattices.CompactLattice¶

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[galactic.algebras.lattice.lattices.Element]) → galactic.algebras.lattice.lattices.CompactLattice¶

In-place enlarge the lattice with an iterable of elements.

Keyword Arguments: iterable (Iterable[Element]) – An iterable of elements

__imatmul__(other: Any) → galactic.algebras.lattice.lattices.CompactLattice¶

In-place combine the lattice with another lattice.

Parameters: other (CompactLattice) – The lattice

__matmul__(other: Any) → galactic.algebras.lattice.lattices.CompactLattice¶

Combine the lattice with another lattice.

Parameters: other (CompactLattice) – The other lattice

maximum() → galactic.algebras.lattice.lattices.Element¶

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

Returns: the maximum element
Return type: Element

minimum() → galactic.algebras.lattice.lattices.Element¶

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

Returns: The minimum element
Return type: Element

co_atoms() → Iterator[galactic.algebras.lattice.lattices.Element]¶

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

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

atoms() → Iterator[galactic.algebras.lattice.lattices.Element]¶

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

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

meet_irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get the meet irreducible elements. The operation is in \(O(1)\).

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

join_irreducible() → Iterator[galactic.algebras.lattice.lattices.Element]¶

Get the join irreducible elements. The operation is in \(O(1)\).

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

is_join_irreducible(element: galactic.algebras.lattice.lattices.Element) → 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: galactic.algebras.lattice.lattices.Element) → 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.ReducedContext(lattice: galactic.algebras.lattice.lattices.Lattice, renderer: galactic.algebras.context.main.ContextRenderer = <galactic.algebras.context.main.ContextRenderer object>)¶

Bases: galactic.algebras.context.main.Context

The ReducedContext class represents a binary relation between 2 sets of lattice elements.

objects() → Iterator[Any]¶

The objects() method returns an iterator overs the objects.

Returns: An iterator over the objects
Return type: Iterator[Element]

attributes() → Iterator[Any]¶

The attributes() method returns an iterator overs the attributes.

Returns: An iterator over the attributes
Return type: Iterator[Element]