Lattices¶

The galactic.algebras.lattice module defines types for representing lattices.

Elements of semi-lattices and lattices:

Joinable for joinable elements;
Meetable for meetable elements;
Element for joinable and meetable elements.

Function on elements of semi-lattices and lattices:

supremum()
supremum_generators()
infimum()
infimum_generators()

Abstract classes of semi-lattices and lattices:

AbstractJoinSemiLattice
AbstractMeetSemiLattice
AbstractLattice

and their implementations:

JoinSemiLattice
MeetSemiLattice
Lattice

It also defines the ReducedContextDiagram class for drawing sagittal diagram of reduced context lattices.

class Element(*args, **kwds)¶

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

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

Return the meet of this element and the other.

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

abstract __eq__(other: Any) → bool ¶

Test if this element is equal to the other.

Parameters: other – the other element
Returns: True if this element is equal to the other.
Return type: bool

__ge__(other: Any) → bool ¶

Test if this element is greater than or equal to the other.

Parameters

other – the other element

Returns

True – if this element is greater than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __gt__(other: Any) → bool ¶

Test if this element is greater than the other.

Parameters

other – the other element

Returns

True – if this element is greater than the other.
NotImplemented – if the operation is not implemented between the two objects

__le__(other: Any) → bool ¶

Test if this element is lesser than or equal to the other.

Parameters

other – the other element

Returns

True – if this element is lesser than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __lt__(other: Any) → bool ¶

Test if this element is lesser than the other.

Parameters

other – the other element

Returns

True – if this element is lesser than the other.
NotImplemented – if the operation is not implemented between the two objects

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

Return the join of this element and the other.

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

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

Return the intersection of this element and the others.

Parameters: *args (object) – 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.

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

Return the union of this element and the others.

Parameters: *args (object) – 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 Joinable(*args, **kwds)¶

The Joinable class.

This class sets for each pair of elements a, b an unique supremum \(c = a \vee b\) (also called a least upper bound or join).

A class implementing the:class:Joinable abstract class must be declared by inheriting from Joinable 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 __eq__(other: Any) → bool ¶

Test if this element is equal to the other.

Parameters: other – the other element
Returns: True if this element is equal to the other.
Return type: bool

__ge__(other: Any) → bool ¶

Test if this element is greater than or equal to the other.

Parameters

other – the other element

Returns

True – if this element is greater than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __gt__(other: Any) → bool ¶

Test if this element is greater than the other.

Parameters

other – the other element

Returns

True – if this element is greater than the other.
NotImplemented – if the operation is not implemented between the two objects

__le__(other: Any) → bool ¶

Test if this element is lesser than or equal to the other.

Parameters

other – the other element

Returns

True – if this element is lesser than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __lt__(other: Any) → bool ¶

Test if this element is lesser than the other.

Parameters

other – the other element

Returns

True – if this element is lesser than the other.
NotImplemented – if the operation is not implemented between the two objects

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

Return the join of this element and the other.

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

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

Return the union of this element and the others.

Parameters: *args (object) – 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 Meetable(*args, **kwds)¶

The Meetable class.

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

A class implementing the Meetable abstract class must be declared by inheriting from Meetable 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.Meetable ¶

Return the meet of this element and the other.

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

abstract __eq__(other: Any) → bool ¶

Test if this element is equal to the other.

Parameters: other – the other element
Returns: True if this element is equal to the other.
Return type: bool

__ge__(other: Any) → bool ¶

Test if this element is greater than or equal to the other.

Parameters

other – the other element

Returns

True – if this element is greater than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __gt__(other: Any) → bool ¶

Test if this element is greater than the other.

Parameters

other – the other element

Returns

True – if this element is greater than the other.
NotImplemented – if the operation is not implemented between the two objects

__le__(other: Any) → bool ¶

Test if this element is lesser than or equal to the other.

Parameters

other – the other element

Returns

True – if this element is lesser than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __lt__(other: Any) → bool ¶

Test if this element is lesser than the other.

Parameters

other – the other element

Returns

True – if this element is lesser than the other.
NotImplemented – if the operation is not implemented between the two objects

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

Return the intersection of this element and the others.

Parameters: *args (object) – 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.

infimum(iterable: Iterable[_M]) → galactic.algebras.lattice.Meetable ¶

Compute the infimum of meetable elements.

Parameters: iterable (Iterable[_M]) – An iterable collection of meetable elements.
Returns: The intersection of all elements from the iterable collection.
Return type: Joinable
Raises: ValueError – If the iterable is empty.

supremum(iterable: Iterable[_J]) → galactic.algebras.lattice.Joinable ¶

Compute the supremum of joinable elements.

Parameters: iterable (Iterable[_J]) – An iterable collection of joinable elements.
Returns: The union of all elements from the iterable collection.
Return type: Joinable
Raises: ValueError – If the iterable is empty.

infimum_generators(iterable: Iterable[_M]) → Iterator[_M]¶

Produce the infimum generators from an iterable of meetable elements.

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

supremum_generators(iterable: Iterable[_J]) → Iterator[_J]¶

Produce the supremum generators from an iterable of joinable elements.

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

class AbstractJoinSemiLattice(*args, **kwds)¶

The AbstractJoinSemiLattice class describes finite join semi-lattices.

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__iter__() → Iterator[Tuple[_P, _P]]¶

Get an iterator over the elements.

Returns: An iterator over the elements
Return type: Iterator[Tuple[_P, _P]]

abstract property bottom¶

Get the bottom elements.

Returns: The bottom elements.
Return type: AbstractSet[_P]

abstract property co_atoms¶

Get the co-atoms of this join semi-lattice.

Returns: The co-atoms.
Return type: AbstractSet[_J]

property co_domain¶

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns: The co-domain of this binary relation.
Return type: AbstractSet[_F]

abstract property cover¶

Get the covering relation.

Returns: The covering relation.
Return type: AbstractCoveringRelation[_P]

property domain¶

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns: The domain of this binary relation.
Return type: AbstractSet[_E]

abstract filter(element: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_P]¶

Get a filter of a poset.

Parameters: element (_P) – The lower limit
Returns: The lower bounded poset.
Return type: AbstractLowerBoundedSet[_P]
Raises: ValueError – If the element does not belong to the poset.

abstract greatest_join_irreducible(element: _J) → AbstractSet[_J]¶

Get the greatest join irreducible smaller than an element.

Parameters: element (_J) – The element whose greatest join irreducible are requested
Returns: The greatest join irreducible smaller than the element.
Return type: AbstractSet[_J]
Raises: ValueError – If the element does not belong to the join semi-lattice.

abstract ideal(element: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_P]¶

Get an ideal of the poset.

Parameters: element (_P) – The upper limit
Returns: The upper bounded set.
Return type: AbstractUpperBoundedSet[_P]

isdisjoint(other)¶: Return True if two sets have a null intersection.

abstract property join_irreducible¶

Get the join irreducible elements.

Returns: The join irreducible elements.
Return type: AbstractSet[_J]

abstract property maximum¶

Get the maximum of the poset.

Returns: The maximum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

Parameters: element (_F) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the relation.

abstract property sinks¶

Get the sinks of this DAG.

Returns: The sinks of this DAG.
Return type: AbstractSet[_E]

abstract property sources¶

Get the sources of this DAG.

Returns: The sources of this DAG.
Return type: AbstractSet[_E]

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

Parameters: element (_E) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_F]
Raises: ValueError – If the element does not belong to the relation.

abstract property top¶

Get the top elements.

Returns: The top elements.
Return type: AbstractSet[_P]

abstract property universes¶

Get the universes of this relation.

Returns: The universes of this relation.
Return type: Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractLowerBoundedJoinSemiLattice(*args, **kwds)¶

The AbstractLowerBoundedJoinSemiLattice class.

It represents abstract lower bounded join semi-lattices.

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__iter__() → Iterator[Tuple[_P, _P]]¶

Get an iterator over the elements.

Returns: An iterator over the elements
Return type: Iterator[Tuple[_P, _P]]

abstract property bottom¶

Get the bottom elements.

Returns: The bottom elements.
Return type: AbstractSet[_P]

abstract property co_atoms¶

Get the co-atoms of this join semi-lattice.

Returns: The co-atoms.
Return type: AbstractSet[_J]

property co_domain¶

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns: The co-domain of this binary relation.
Return type: AbstractSet[_F]

abstract property cover¶

Get the covering relation.

Returns: The covering relation.
Return type: AbstractCoveringRelation[_P]

property domain¶

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns: The domain of this binary relation.
Return type: AbstractSet[_E]

abstract filter(element: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_P]¶

Get a filter of a poset.

Parameters: element (_P) – The lower limit
Returns: The lower bounded poset.
Return type: AbstractLowerBoundedSet[_P]
Raises: ValueError – If the element does not belong to the poset.

abstract greatest_join_irreducible(element: _J) → AbstractSet[_J]¶

Get the greatest join irreducible smaller than an element.

Parameters: element (_J) – The element whose greatest join irreducible are requested
Returns: The greatest join irreducible smaller than the element.
Return type: AbstractSet[_J]
Raises: ValueError – If the element does not belong to the join semi-lattice.

abstract ideal(element: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_P]¶

Get an ideal of the poset.

Parameters: element (_P) – The upper limit
Returns: The upper bounded set.
Return type: AbstractUpperBoundedSet[_P]

isdisjoint(other)¶: Return True if two sets have a null intersection.

abstract property join_irreducible¶

Get the join irreducible elements.

Returns: The join irreducible elements.
Return type: AbstractSet[_J]

abstract property maximum¶

Get the maximum of the poset.

Returns: The maximum element.
Return type: _P

abstract property minimum¶

Get the minimum of the poset.

Returns: The minimum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

Parameters: element (_F) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the relation.

abstract property sinks¶

Get the sinks of this DAG.

Returns: The sinks of this DAG.
Return type: AbstractSet[_E]

abstract property sources¶

Get the sources of this DAG.

Returns: The sources of this DAG.
Return type: AbstractSet[_E]

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

Parameters: element (_E) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_F]
Raises: ValueError – If the element does not belong to the relation.

abstract property top¶

Get the top elements.

Returns: The top elements.
Return type: AbstractSet[_P]

abstract property universes¶

Get the universes of this relation.

Returns: The universes of this relation.
Return type: Tuple[AbstractSet[_E], AbstractSet[_F]]

class JoinSemiLattice(domain: Iterable[_J])¶

The JoinSemiLattice class.

It implements methods of AbstractJoinSemiLattice.

A JoinSemiLattice instance stores its irreducible in a PartiallyOrderedSet.

Its memory complexity is in \(O(j)\)

Example

>>> from galactic.algebras.lattice import MeetSemiLattice
>>> from galactic.examples.arithmetic import Integer
>>> m = MeetSemiLattice[Integer](
...     domain = [
...         Integer(2*3*5),
...         Integer(3*5*7),
...         Integer(5*7*11)
...     ]
... )
>>>

It’s possible to get the minimum element.

Example

>>> int(m.minimum)
5

It’s possible to iterate over the elements.

Example

>>> sorted(list(map(int, m.domain)))
[5, 15, 30, 35, 105, 385]

It’s possible to iterate over the atoms.

Example

>>> sorted(list(map(int, m.atoms)))
[15, 35]

It’s possible to iterate over the meet irreducible.

Example

>>> sorted(list(map(int, m.meet_irreducible)))
[30, 105, 385]

It’s possible to iterate over the smallest meet irreducible greater than an element.

Example

>>> sorted(list(map(int, m.smallest_meet_irreducible(Integer(5*7)))))
[105, 385]

It’s possible to enlarge a meet semi-lattice.

Example

>>> m.extend([Integer(13)])
>>> sorted(list(map(int, m.domain)))
[1, 5, 13, 15, 30, 35, 105, 385]

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__copy__() → galactic.algebras.lattice.JoinSemiLattice[_J]¶

Get a copy of the join semi-lattice.

This operation is in \(O(j)\).

Returns: The copy of this join semi-lattice.
Return type: JoinSemiLattice[_J]

__init__(domain: Iterable[_J])¶

Initialise a JoinSemiLattice instance.

Parameters: domain (Optional[Iterable[_J]]) – An initial domain.
Raises: ValueError – If the iterable is empty.

__iter__() → Iterator[Tuple[_J, _J]]¶

Get an iterator over the elements.

Returns: an iterator over the elements
Return type: Iterator[Tuple[_J, _J]]

property bottom¶

Get the bottom elements.

Returns: The bottom elements.
Return type: AbstractSet[_J]

property co_atoms¶

Get the co-atoms of this join semi-lattice.

Returns: The co-atoms.
Return type: AbstractSet[_J]

property co_domain¶

Get the co-domain of this semi-lattice.

Returns: The co-domain of this semi-lattice.
Return type: AbstractSet[_J]

property cover¶

Get the covering relation of this join semi-lattice.

Returns: The covering relation.
Return type: AbstractCoveringRelation[_J]

property domain¶

Get the domain of this semi-lattice.

Returns: The domain of this semi-lattice.
Return type: AbstractSet[_J]

extend(iterable: Iterable[_J]) → None ¶

Extend this join semi-lattice.

Parameters: iterable (Iterable[_M]) – An iterable of values.

filter(element: _J) → galactic.algebras.lattice.AbstractLowerBoundedJoinSemiLattice[_J]¶

Get a filter of a join semi-lattice.

Parameters: element (_J) – The lower limit
Returns: The lower bounded join semi-lattice.
Return type: AbstractLowerBoundedJoinSemiLattice[_J]
Raises: ValueError – If the element does not belong to the poset.

greatest_join_irreducible(element: _J) → AbstractSet[_J]¶

Get the greatest join irreducible smaller than an element.

Parameters: element (_J) – The element whose greatest join irreducible are requested
Returns: The greatest join irreducible smaller than the element.
Return type: AbstractSet[_J]
Raises: ValueError – If the element does not belong to the join semi-lattice.

ideal(element: _J) → galactic.algebras.lattice.AbstractJoinSemiLattice[_J]¶

Get an ideal of a join semi-lattice.

Parameters: element (_J) – The upper limit
Returns: The upper bounded join semi-lattice.
Return type: AbstractJoinSemiLattice[_J]
Raises: ValueError – If the element does not belong to the poset.

isdisjoint(other)¶: Return True if two sets have a null intersection.

property join_irreducible¶

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

Returns: The join-irreducible elements.
Return type: AbstractSet[_J]

lower_limit(limit: _J, strict: bool = False) → AbstractSet[_J]¶

Get the elements greater than a limit.

Parameters

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

Returns

The selected elements.

Return type

AbstractSet[_J]

property maximum¶

Get the maximum element of this join semi-lattice.

Returns: The maximum element
Return type: _J

predecessors(element: _J) → AbstractSet[_J]¶

Get the predecessors of an element.

Parameters: element (_J) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_J]
Raises: ValueError – If the element does not belong to the semi-lattice.

property sinks¶

Get the sink elements.

The collection contains only one element, the maximum element.

Returns: The sink elements.
Return type: AbstractSet[_J]

property sources¶

Get the source elements.

Returns: The source elements.
Return type: AbstractSet[_J]

successors(element: _J) → AbstractSet[_J]¶

Get the successors of an element.

Parameters: element (_J) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_J]
Raises: ValueError – If the element does not belong to the semi-lattice.

property top¶

Get the top elements.

The collection contains only one element, the maximum element.

Returns: The top elements.
Return type: AbstractSet[_J]

property universes¶

Get the universes of this join semi-lattice.

Returns: The universes.
Return type: Tuple[AbstractSet[_J], AbstractSet[_J]]

upper_limit(limit: _J, strict: bool = False) → AbstractSet[_J]¶

Get the elements lesser than a limit.

Parameters

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

Returns

The selected elements.

Return type

AbstractSet[_J]

class AbstractMeetSemiLattice(*args, **kwds)¶

The AbstractMeetSemiLattice class describes finite meet semi-lattices.

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__iter__() → Iterator[Tuple[_P, _P]]¶

Get an iterator over the elements.

Returns: An iterator over the elements
Return type: Iterator[Tuple[_P, _P]]

abstract property atoms¶

Get the atoms of this meet semi-lattice.

Returns: The atoms.
Return type: AbstractSet[_M]

abstract property bottom¶

Get the bottom elements.

Returns: The bottom elements.
Return type: AbstractSet[_P]

property co_domain¶

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns: The co-domain of this binary relation.
Return type: AbstractSet[_F]

abstract property cover¶

Get the covering relation.

Returns: The covering relation.
Return type: AbstractCoveringRelation[_P]

property domain¶

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns: The domain of this binary relation.
Return type: AbstractSet[_E]

abstract filter(element: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_P]¶

Get a filter of a poset.

Parameters: element (_P) – The lower limit
Returns: The lower bounded poset.
Return type: AbstractLowerBoundedSet[_P]
Raises: ValueError – If the element does not belong to the poset.

abstract ideal(element: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_P]¶

Get an ideal of the poset.

Parameters: element (_P) – The upper limit
Returns: The upper bounded set.
Return type: AbstractUpperBoundedSet[_P]

isdisjoint(other)¶: Return True if two sets have a null intersection.

abstract property meet_irreducible¶

Get the meet irreducible elements.

Returns: The meet irreducible elements.
Return type: AbstractSet[_M]

abstract property minimum¶

Get the minimum of the poset.

Returns: The minimum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

Parameters: element (_F) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the relation.

abstract property sinks¶

Get the sinks of this DAG.

Returns: The sinks of this DAG.
Return type: AbstractSet[_E]

abstract smallest_meet_irreducible(element: _M) → AbstractSet[_M]¶

Get the smallest meet irreducible greater than an element.

Parameters: element (_M) – The element whose smallest meet irreducible are requested
Returns: The smallest meet irreducible greater than the element.
Return type: AbstractSet[_M]
Raises: ValueError – If the element does not belong to the meet semi-lattice.

abstract property sources¶

Get the sources of this DAG.

Returns: The sources of this DAG.
Return type: AbstractSet[_E]

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

Parameters: element (_E) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_F]
Raises: ValueError – If the element does not belong to the relation.

abstract property top¶

Get the top elements.

Returns: The top elements.
Return type: AbstractSet[_P]

abstract property universes¶

Get the universes of this relation.

Returns: The universes of this relation.
Return type: Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractUpperBoundedMeetSemiLattice(*args, **kwds)¶

The AbstractUpperBoundedMeetSemiLattice class.

It represents abstract upper bounded meet semi-lattices.

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__iter__() → Iterator[Tuple[_P, _P]]¶

Get an iterator over the elements.

Returns: An iterator over the elements
Return type: Iterator[Tuple[_P, _P]]

abstract property atoms¶

Get the atoms of this meet semi-lattice.

Returns: The atoms.
Return type: AbstractSet[_M]

abstract property bottom¶

Get the bottom elements.

Returns: The bottom elements.
Return type: AbstractSet[_P]

property co_domain¶

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns: The co-domain of this binary relation.
Return type: AbstractSet[_F]

abstract property cover¶

Get the covering relation.

Returns: The covering relation.
Return type: AbstractCoveringRelation[_P]

property domain¶

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns: The domain of this binary relation.
Return type: AbstractSet[_E]

abstract filter(element: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_P]¶

Get a filter of a poset.

Parameters: element (_P) – The lower limit
Returns: The lower bounded poset.
Return type: AbstractLowerBoundedSet[_P]
Raises: ValueError – If the element does not belong to the poset.

abstract ideal(element: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_P]¶

Get an ideal of the poset.

Parameters: element (_P) – The upper limit
Returns: The upper bounded set.
Return type: AbstractUpperBoundedSet[_P]

isdisjoint(other)¶: Return True if two sets have a null intersection.

abstract property maximum¶

Get the maximum of the poset.

Returns: The maximum element.
Return type: _P

abstract property meet_irreducible¶

Get the meet irreducible elements.

Returns: The meet irreducible elements.
Return type: AbstractSet[_M]

abstract property minimum¶

Get the minimum of the poset.

Returns: The minimum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

Parameters: element (_F) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the relation.

abstract property sinks¶

Get the sinks of this DAG.

Returns: The sinks of this DAG.
Return type: AbstractSet[_E]

abstract smallest_meet_irreducible(element: _M) → AbstractSet[_M]¶

Get the smallest meet irreducible greater than an element.

Parameters: element (_M) – The element whose smallest meet irreducible are requested
Returns: The smallest meet irreducible greater than the element.
Return type: AbstractSet[_M]
Raises: ValueError – If the element does not belong to the meet semi-lattice.

abstract property sources¶

Get the sources of this DAG.

Returns: The sources of this DAG.
Return type: AbstractSet[_E]

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

Parameters: element (_E) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_F]
Raises: ValueError – If the element does not belong to the relation.

abstract property top¶

Get the top elements.

Returns: The top elements.
Return type: AbstractSet[_P]

abstract property universes¶

Get the universes of this relation.

Returns: The universes of this relation.
Return type: Tuple[AbstractSet[_E], AbstractSet[_F]]

class MeetSemiLattice(domain: Iterable[_M])¶

The MeetSemiLattice class.

It implements methods of AbstractMeetSemiLattice.

A MeetSemiLattice instance stores its irreducible in a PartiallyOrderedSet.

Its memory complexity is in \(O(m)\)

Example

>>> from galactic.algebras.lattice import MeetSemiLattice
>>> from galactic.examples.arithmetic import Integer
>>> m = MeetSemiLattice[Integer](
...     domain = [
...         Integer(2*3*5),
...         Integer(3*5*7),
...         Integer(5*7*11)
...     ]
... )
>>>

It’s possible to get the minimum element.

Example

>>> int(m.minimum)
5

It’s possible to iterate over the elements.

Example

>>> sorted(list(map(int, m.domain)))
[5, 15, 30, 35, 105, 385]

It’s possible to iterate over the atoms.

Example

>>> sorted(list(map(int, m.atoms)))
[15, 35]

It’s possible to iterate over the meet irreducible.

Example

>>> sorted(list(map(int, m.meet_irreducible)))
[30, 105, 385]

It’s possible to iterate over the smallest meet irreducible greater than an element.

Example

>>> sorted(list(map(int, m.smallest_meet_irreducible(Integer(5*7)))))
[105, 385]

It’s possible to enlarge a meet semi-lattice.

Example

>>> m.extend([Integer(13)])
>>> sorted(list(map(int, m.domain)))
[1, 5, 13, 15, 30, 35, 105, 385]

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__copy__() → galactic.algebras.lattice.MeetSemiLattice[_M]¶

Get a copy of the meet semi-lattice.

This operation is in \(O(m)\).

Returns: The copy of this meet semi-lattice.
Return type: MeetSemiLattice[_M]

__init__(domain: Iterable[_M])¶

Initialise a MeetSemiLattice instance.

Parameters: domain (Optional[Iterable[_M]]) – An initial domain.
Raises: ValueError – If the iterable is empty.

__iter__() → Iterator[Tuple[_M, _M]]¶

Get an iterator over the elements.

Returns: an iterator over the elements
Return type: Iterator[Tuple[_M, _M]]

property atoms¶

Get the atoms of this meet semi-lattice.

Returns: The atoms.
Return type: AbstractSet[_M]

property bottom¶

Get the bottom elements.

The collection contains only one element, the minimum element.

Returns: The bottom elements.
Return type: AbstractSet[_M]

property co_domain¶

Get the co-domain of this semi-lattice.

Returns: The co-domain of this semi-lattice.
Return type: AbstractSet[_M]

property cover¶

Get the covering relation of this meet semi-lattice.

Returns: The covering relation.
Return type: AbstractCoveringRelation[_M]

property domain¶

Get the domain of this semi-lattice.

Returns: The domain of this semi-lattice.
Return type: AbstractSet[_M]

extend(iterable: Iterable[_M]) → None ¶

Extend this meet semi-lattice.

Parameters: iterable (Iterable[_M]) – An iterable of values.

filter(element: _M) → galactic.algebras.lattice.AbstractMeetSemiLattice[_M]¶

Get a filter of a meet semi-lattice.

Parameters: element (_M) – The lower limit
Returns: The lower bounded join semi-lattice.
Return type: AbstractMeetSemiLattice[_M]
Raises: ValueError – If the element does not belong to the poset.

ideal(element: _M) → galactic.algebras.lattice.AbstractUpperBoundedMeetSemiLattice[_M]¶

Get an ideal of a meet semi-lattice.

Parameters: element (_M) – The upper limit
Returns: The upper bounded meet semi-lattice.
Return type: AbstractUpperBoundedMeetSemiLattice[_M]
Raises: ValueError – If the element does not belong to the poset.

isdisjoint(other)¶: Return True if two sets have a null intersection.

lower_limit(limit: _M, strict: bool = False) → AbstractSet[_M]¶

Get the elements greater than a limit.

Parameters

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

Returns

The selected elements.

Return type

AbstractSet[_M]

property meet_irreducible¶

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

Returns: The meet-irreducible elements.
Return type: AbstractSet[_M]

property minimum¶

Get the minimum element of this meet semi-lattice.

Returns: The minimum element
Return type: _M

predecessors(element: _M) → AbstractSet[_M]¶

Get the predecessors of an element.

Parameters: element (_M) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_M]
Raises: ValueError – If the element does not belong to the semi-lattice.

property sinks¶

Get the sink elements.

Returns: The sink elements.
Return type: AbstractSet[_M]

smallest_meet_irreducible(element: _M) → AbstractSet[_M]¶

Get the smallest meet irreducible greater than an element.

Parameters: element (_M) – The element whose smallest meet irreducible are requested
Returns: The smallest meet irreducible greater than the element.
Return type: AbstractSet[_M]
Raises: ValueError – If the element does not belong to the meet semi-lattice.

property sources¶

Get the source elements.

The collection contains only one element, the minimum element.

Returns: The source elements.
Return type: AbstractSet[_M]

successors(element: _M) → AbstractSet[_M]¶

Get the successors of an element.

Parameters: element (_M) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_M]
Raises: ValueError – If the element does not belong to the semi-lattice.

property top¶

Get the top elements.

Returns: The top elements.
Return type: AbstractSet[_M]

property universes¶

Get the universes of this meet semi-lattice.

Returns: The universes.
Return type: Tuple[AbstractSet[_M], AbstractSet[_M]]

upper_limit(limit: _M, strict: bool = False) → AbstractSet[_M]¶

Get the elements lesser than a limit.

Parameters

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

Returns

The selected elements.

Return type

AbstractSet[_M]

class AbstractLattice(*args, **kwds)¶

The AbstractLattice class describes finite lattices.

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__iter__() → Iterator[Tuple[_P, _P]]¶

Get an iterator over the elements.

Returns: An iterator over the elements
Return type: Iterator[Tuple[_P, _P]]

abstract property atoms¶

Get the atoms of this meet semi-lattice.

Returns: The atoms.
Return type: AbstractSet[_M]

abstract property bottom¶

Get the bottom elements.

Returns: The bottom elements.
Return type: AbstractSet[_P]

abstract property co_atoms¶

Get the co-atoms of this join semi-lattice.

Returns: The co-atoms.
Return type: AbstractSet[_J]

property co_domain¶

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns: The co-domain of this binary relation.
Return type: AbstractSet[_F]

abstract property cover¶

Get the covering relation.

Returns: The covering relation.
Return type: AbstractCoveringRelation[_P]

property domain¶

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns: The domain of this binary relation.
Return type: AbstractSet[_E]

abstract filter(element: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_P]¶

Get a filter of a poset.

Parameters: element (_P) – The lower limit
Returns: The lower bounded poset.
Return type: AbstractLowerBoundedSet[_P]
Raises: ValueError – If the element does not belong to the poset.

abstract greatest_join_irreducible(element: _J) → AbstractSet[_J]¶

Get the greatest join irreducible smaller than an element.

Parameters: element (_J) – The element whose greatest join irreducible are requested
Returns: The greatest join irreducible smaller than the element.
Return type: AbstractSet[_J]
Raises: ValueError – If the element does not belong to the join semi-lattice.

abstract ideal(element: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_P]¶

Get an ideal of the poset.

Parameters: element (_P) – The upper limit
Returns: The upper bounded set.
Return type: AbstractUpperBoundedSet[_P]

isdisjoint(other)¶: Return True if two sets have a null intersection.

abstract property join_irreducible¶

Get the join irreducible elements.

Returns: The join irreducible elements.
Return type: AbstractSet[_J]

abstract property maximum¶

Get the maximum of the poset.

Returns: The maximum element.
Return type: _P

abstract property meet_irreducible¶

Get the meet irreducible elements.

Returns: The meet irreducible elements.
Return type: AbstractSet[_M]

abstract property minimum¶

Get the minimum of the poset.

Returns: The minimum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

Parameters: element (_F) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the relation.

abstract property reduced_context¶

Get the reduced context from this lattice.

Returns: The reduced context.
Return type: AbstractBinaryRelation[_E, _E]

abstract property sinks¶

Get the sinks of this DAG.

Returns: The sinks of this DAG.
Return type: AbstractSet[_E]

abstract smallest_meet_irreducible(element: _M) → AbstractSet[_M]¶

Get the smallest meet irreducible greater than an element.

Parameters: element (_M) – The element whose smallest meet irreducible are requested
Returns: The smallest meet irreducible greater than the element.
Return type: AbstractSet[_M]
Raises: ValueError – If the element does not belong to the meet semi-lattice.

abstract property sources¶

Get the sources of this DAG.

Returns: The sources of this DAG.
Return type: AbstractSet[_E]

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

Parameters: element (_E) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_F]
Raises: ValueError – If the element does not belong to the relation.

abstract property top¶

Get the top elements.

Returns: The top elements.
Return type: AbstractSet[_P]

abstract property universes¶

Get the universes of this relation.

Returns: The universes of this relation.
Return type: Tuple[AbstractSet[_E], AbstractSet[_F]]

class Lattice(domain: Iterable[_E])¶

The Lattice store a compact version of a lattice.

It uses its join irreducible and meet irreducible elements.

The domain elements of a Lattice can be iterated from the maximum element to the minimum element or from the minimum element to the maximum element using the reversed built-in function. It is not guaranteed that the order will be exactly the reverse order, but it is guaranteed that an element will always be iterated before its successors.

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
>>> from galactic.algebras.lattice import Lattice
>>> lattice = Lattice[Integer](domain=[Integer(2), Integer(3)])
>>> list(map(int, lattice.domain))
[6, 2, 3, 1]

__contains__(item: Any) → bool ¶

Get the membership of an element.

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

__copy__() → galactic.algebras.lattice.Lattice[_E]¶

Get a copy of the lattice.

The operation is in \(O(j+m)\).

Returns: The copy of this lattice.
Return type: Lattice[_E]

__init__(domain: Iterable[_E])¶

Initialise a Lattice> instance.

Parameters: domain (Iterable[_E]) – An iterable of elements
Raises: ValueError – If the iterable is empty.

__iter__() → Iterator[Tuple[_P, _P]]¶

Get an iterator over the elements.

Returns: An iterator over the elements
Return type: Iterator[Tuple[_P, _P]]

property atoms¶

Get the atoms of this lattice.

Returns: The atoms
Return type: AbstractSet[_E]

property bottom¶

Get the bottom elements.

The collection contains only one element, the minimum element.

Returns: The bottom elements.
Return type: AbstractSet[_E]

property co_atoms¶

Get the co-atoms of this lattice.

Returns: The co-atoms.
Return type: AbstractSet[_E]

property co_domain¶

Get the co-domain of this lattice.

Returns: The co-domain of this lattice.
Return type: AbstractSet[_E]

property cover¶

Get the covering relation of this lattice.

Returns: The covering relation.
Return type: AbstractReversibleCoveringRelation[_E]

property domain¶

Get the domain of this lattice.

Returns: The domain of this lattice.
Return type: AbstractSet[_E]

extend(iterable: Iterable[_E]) → None ¶

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

Parameters: iterable (Iterable[_E]) – An iterable of elements

filter(element: _E) → galactic.algebras.lattice.AbstractLattice[_E]¶

Get a filter of a lattice.

Parameters: element (_E) – The lower limit
Returns: The lower bounded lattice.
Return type: AbstractLattice[_E]
Raises: ValueError – If the element does not belong to the poset.

greatest_join_irreducible(element: _E) → AbstractSet[_E]¶

Get the greatest join irreducible smaller than an element.

Parameters: element (_E) – The element whose greatest join irreducible are requested
Returns: The greatest join irreducible smaller than the element.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the lattice.

ideal(element: _E) → galactic.algebras.lattice.AbstractLattice[_E]¶

Get an ideal of a lattice.

Parameters: element (_E) – The upper limit
Returns: The upper bounded lattice.
Return type: AbstractLattice[_E]
Raises: ValueError – If the element does not belong to the poset.

isdisjoint(other)¶: Return True if two sets have a null intersection.

property join_irreducible¶

Get the join irreducible elements.

Returns: The join irreducible elements
Return type: AbstractSet[_E]

lower_limit(limit: _E, strict: bool = Ellipsis) → AbstractSet[_E]¶

Get the elements greater than a limit.

Parameters

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

Returns

The selected elements.

Return type

AbstractSet[_E]

property maximum¶

Get the maximum element of this lattice.

Returns: the maximum element
Return type: _E

property meet_irreducible¶

Get the meet irreducible elements.

Returns: The meet irreducible elements
Return type: AbstractSet[_E]

property minimum¶

Get the minimum element of this lattice.

Returns: The minimum element
Return type: _E

predecessors(element: _E) → AbstractSet[_E]¶

Get the predecessors of an element.

Parameters: element (_E) – The element whose predecessors are requested
Returns: The predecessors.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the poset.

property reduced_context¶

Get the reduced context from this lattice.

Returns: The reduced context.
Return type: AbstractBinaryRelation[_E, _E]

property sinks¶

Get the sink elements.

The collection contains only one element, the maximum element.

Returns: The sink elements.
Return type: AbstractSet[_E]

smallest_meet_irreducible(element: _E) → AbstractSet[_E]¶

Get the smallest meet irreducible greater than an element.

Parameters: element (_E) – The element whose greatest join irreducible are requested
Returns: The smallest meet irreducible smaller than the element.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the lattice.

property sources¶

Get the source elements.

The collection contains only one element, the minimum element.

Returns: The source elements.
Return type: AbstractSet[_E]

successors(element: _E) → AbstractSet[_E]¶

Get the successors of an element.

Parameters: element (_E) – The element whose successors are requested
Returns: The successors.
Return type: AbstractSet[_E]
Raises: ValueError – If the element does not belong to the poset.

property top¶

Get the top elements.

The collection contains only one element, the maximum element.

Returns: The top elements.
Return type: AbstractSet[_E]

property universes¶

Get the universes of this lattice.

Returns: The universes.
Return type: Tuple[AbstractSet[_E], AbstractSet[_E]]

upper_limit(limit: _E, strict: bool = False) → AbstractSet[_E]¶

Get the elements lesser than a limit.

Parameters

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

Returns

The selected elements.

Return type

AbstractSet[_E]

class ReducedContextDiagram(lattice: galactic.algebras.lattice.Lattice[_E], domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_E, _E]] = None, co_domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_E, _E]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_E, _E]] = None)¶

The ReducedContextDiagram class is used for drawing sagittal diagrams.

It is useful for drawing sagittal diagrams of lattice reduced context in jupyter notebooks.

__init__(lattice: galactic.algebras.lattice.Lattice[_E], domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_E, _E]] = None, co_domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_E, _E]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_E, _E]] = None) → None ¶

Initialise a ReducedContextDiagram instance.

Parameters

lattice (Lattice[_E]) – The lattice.
domain_renderer (NodeRenderer[_E, _E]) – The domain renderer.
co_domain_renderer (NodeRenderer[_E, _E]) – The domain renderer.
edge_renderer (EdgeRenderer[_E, _E]) – The edge renderer.

attributes() → Dict[str, str]¶: Return a dictionary of graphviz attributes for the graph.

property co_domain_renderer¶

Get the co-domain renderer.

Returns: The co-domain renderer.
Return type: NodeRenderer[_F, _E]

property domain_renderer¶

Get the domain renderer.

Returns: The domain renderer.
Return type: NodeRenderer[_E, _F]

property edge_renderer¶

Get the edge renderer.

Returns: The edge renderer.
Return type: EdgeRenderer[_E, _F]

property relation¶

Get the relation.

Returns: The underlying relation.
Return type: AbstractBinaryRelation[_E, _F]

property source¶

Get the graphviz source for this partially ordered set.

Returns: The graphviz output for this partially ordered set.
Return type: str