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:
Abstract classes of semi-lattices and lattices:
and their implementations:
It also defines the ReducedContextDiagram
and
ReducedContextDiagramRenderer
classes for drawing sagittal diagram of reduced
context lattices.
- class Element(*args, **kwds)
The
Element
class describes elements that can be member of a lattice.- __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
- 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:Example
Let the integers ordered by the relation \(a \leq b\): is \(a\) a divisor of \(b\)?
implemented by the
PrimeFactors
class:>>> from galactic.examples.arithmetic import PrimeFactors >>> PrimeFactors(24) | PrimeFactors(36) PrimeFactors(72) >>> PrimeFactors(24).union(PrimeFactors(36), PrimeFactors(10)) PrimeFactors(360)
- __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
- 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 fromMeetable
and must implement the methods:Example
Let the integers ordered by the relation \(a \leq b\): is \(a\) a divisor of \(b\)?
implemented by the
PrimeFactors
class:>>> from galactic.examples.arithmetic import PrimeFactors >>> PrimeFactors(24) & PrimeFactors(36) PrimeFactors(12) >>> PrimeFactors(24).intersection(PrimeFactors(36), PrimeFactors(10)) PrimeFactors(2)
- __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
- infimum(iterable: Iterable[_M]) 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:
- Raises:
ValueError – If the iterable is empty.
- supremum(iterable: Iterable[_J]) 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:
- 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:
- 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:
- class AbstractJoinSemiLattice(*args, **kwds)
The
AbstractJoinSemiLattice
class describes finite join semi-lattices.- __iter__() Iterator[Link[_P, _P]]
Get an iterator over the elements.
- Returns:
An iterator over the elements
- Return type:
- abstract property bottom: AbstractSet[_P]
Get the bottom elements.
- Returns:
The bottom elements.
- Return type:
- abstract property co_atoms: AbstractSet[_J]
Get the co-atoms of this join semi-lattice.
- Returns:
The co-atoms.
- Return type:
- property co_domain: AbstractSet[_F]
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:
- abstract property cover: AbstractCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractCoveringRelation[_P]
- property domain: AbstractSet[_E]
Get the domain of this binary relation.
This is a proxy to self.universes[0].
- Returns:
The domain of this binary relation.
- Return type:
- abstract filter(element: _P) 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:
- Raises:
ValueError – If the element does not belong to the join semi-lattice.
- abstract ideal(element: _P) 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: AbstractSet[_J]
Get the join irreducible elements.
- Returns:
The join irreducible elements.
- Return type:
- abstract property maximum: _P
Get the maximum of the poset.
- Returns:
The maximum element.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property sinks: AbstractSet[_E]
Get the sinks of this DAG.
- Returns:
The sinks of this DAG.
- Return type:
- abstract property sources: AbstractSet[_E]
Get the sources of this DAG.
- Returns:
The sources of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property top: AbstractSet[_P]
Get the top elements.
- Returns:
The top elements.
- Return type:
- abstract property universes: Tuple[AbstractSet[_E], AbstractSet[_F]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class AbstractLowerBoundedJoinSemiLattice(*args, **kwds)
The
AbstractLowerBoundedJoinSemiLattice
class.It represents abstract lower bounded join semi-lattices.
- __iter__() Iterator[Link[_P, _P]]
Get an iterator over the elements.
- Returns:
An iterator over the elements
- Return type:
- abstract property bottom: AbstractSet[_P]
Get the bottom elements.
- Returns:
The bottom elements.
- Return type:
- abstract property co_atoms: AbstractSet[_J]
Get the co-atoms of this join semi-lattice.
- Returns:
The co-atoms.
- Return type:
- property co_domain: AbstractSet[_F]
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:
- abstract property cover: AbstractCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractCoveringRelation[_P]
- property domain: AbstractSet[_E]
Get the domain of this binary relation.
This is a proxy to self.universes[0].
- Returns:
The domain of this binary relation.
- Return type:
- abstract filter(element: _P) 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:
- Raises:
ValueError – If the element does not belong to the join semi-lattice.
- abstract ideal(element: _P) 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: AbstractSet[_J]
Get the join irreducible elements.
- Returns:
The join irreducible elements.
- Return type:
- abstract property maximum: _P
Get the maximum of the poset.
- Returns:
The maximum element.
- Return type:
- abstract property minimum: _P
Get the minimum of the poset.
- Returns:
The minimum element.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property sinks: AbstractSet[_E]
Get the sinks of this DAG.
- Returns:
The sinks of this DAG.
- Return type:
- abstract property sources: AbstractSet[_E]
Get the sources of this DAG.
- Returns:
The sources of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property top: AbstractSet[_P]
Get the top elements.
- Returns:
The top elements.
- Return type:
- abstract property universes: Tuple[AbstractSet[_E], AbstractSet[_F]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class JoinSemiLattice(domain: Iterable[_J])
The
JoinSemiLattice
class.It implements methods of
AbstractJoinSemiLattice
.A
JoinSemiLattice
instance stores its irreducible in aPartiallyOrderedSet
.Its memory complexity is in \(O(j)\)
Example
>>> from galactic.algebras.lattice import MeetSemiLattice >>> from galactic.examples.arithmetic import PrimeFactors >>> m = MeetSemiLattice[PrimeFactors]( ... domain = [ ... PrimeFactors(2*3*5), ... PrimeFactors(3*5*7), ... PrimeFactors(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(PrimeFactors(5*7))))) [105, 385]
It’s possible to enlarge a meet semi-lattice.
Example
>>> m.extend([PrimeFactors(13)]) >>> sorted(list(map(int, m.domain))) [1, 5, 13, 15, 30, 35, 105, 385]
- __copy__() 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:
- __init__(domain: Iterable[_J])
Initialise a
JoinSemiLattice
instance.- Parameters:
domain (
Iterable[_J]
) – An initial domain.- Raises:
ValueError – If the iterable is empty.
- __iter__() Iterator[Link[_J, _J]]
Get an iterator over the elements.
- Returns:
an iterator over the elements
- Return type:
- property bottom: AbstractSet[_J]
Get the bottom elements.
- Returns:
The bottom elements.
- Return type:
- property co_atoms: AbstractSet[_J]
Get the co-atoms of this join semi-lattice.
- Returns:
The co-atoms.
- Return type:
- property co_domain: AbstractSet[_J]
Get the co-domain of this semi-lattice.
- Returns:
The co-domain of this semi-lattice.
- Return type:
- property cover: AbstractCoveringRelation[_J]
Get the covering relation of this join semi-lattice.
- Returns:
The covering relation.
- Return type:
- property domain: AbstractSet[_J]
Get the domain of this semi-lattice.
- Returns:
The domain of this semi-lattice.
- Return type:
- extend(iterable: Iterable[_J]) None
Extend this join semi-lattice.
- Parameters:
iterable (
Iterable[_M]
) – An iterable of values.
- filter(element: _J) 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:
- 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:
- Raises:
ValueError – If the element does not belong to the join semi-lattice.
- ideal(element: _J) 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:
- 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: AbstractSet[_J]
Get the join-irreducible elements of this join semi-lattice.
- Returns:
The join-irreducible elements.
- Return type:
- lower_limit(limit: _J, strict: bool = False) AbstractSet[_J]
Get the elements greater than a limit.
- Parameters:
- Returns:
The selected elements.
- Return type:
- property maximum: _J
Get the maximum element of this join semi-lattice.
- Returns:
The maximum element
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the semi-lattice.
- property sinks: AbstractSet[_J]
Get the sink elements.
The collection contains only one element, the maximum element.
- Returns:
The sink elements.
- Return type:
- property sources: AbstractSet[_J]
Get the source elements.
- Returns:
The source elements.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the semi-lattice.
- property top: AbstractSet[_J]
Get the top elements.
The collection contains only one element, the maximum element.
- Returns:
The top elements.
- Return type:
- property universes: Tuple[AbstractSet[_J], AbstractSet[_J]]
Get the universes of this join semi-lattice.
- Returns:
The universes.
- Return type:
- upper_limit(limit: _J, strict: bool = False) AbstractSet[_J]
Get the elements lesser than a limit.
- Parameters:
- Returns:
The selected elements.
- Return type:
- class AbstractMeetSemiLattice(*args, **kwds)
The
AbstractMeetSemiLattice
class describes finite meet semi-lattices.- __iter__() Iterator[Link[_P, _P]]
Get an iterator over the elements.
- Returns:
An iterator over the elements
- Return type:
- abstract property atoms: AbstractSet[_M]
Get the atoms of this meet semi-lattice.
- Returns:
The atoms.
- Return type:
- abstract property bottom: AbstractSet[_P]
Get the bottom elements.
- Returns:
The bottom elements.
- Return type:
- property co_domain: AbstractSet[_F]
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:
- abstract property cover: AbstractCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractCoveringRelation[_P]
- property domain: AbstractSet[_E]
Get the domain of this binary relation.
This is a proxy to self.universes[0].
- Returns:
The domain of this binary relation.
- Return type:
- abstract filter(element: _P) 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) 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: AbstractSet[_M]
Get the meet irreducible elements.
- Returns:
The meet irreducible elements.
- Return type:
- abstract property minimum: _P
Get the minimum of the poset.
- Returns:
The minimum element.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property sinks: AbstractSet[_E]
Get the sinks of this DAG.
- Returns:
The sinks of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the meet semi-lattice.
- abstract property sources: AbstractSet[_E]
Get the sources of this DAG.
- Returns:
The sources of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property top: AbstractSet[_P]
Get the top elements.
- Returns:
The top elements.
- Return type:
- abstract property universes: Tuple[AbstractSet[_E], AbstractSet[_F]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class AbstractUpperBoundedMeetSemiLattice(*args, **kwds)
The
AbstractUpperBoundedMeetSemiLattice
class.It represents abstract upper bounded meet semi-lattices.
- __iter__() Iterator[Link[_P, _P]]
Get an iterator over the elements.
- Returns:
An iterator over the elements
- Return type:
- abstract property atoms: AbstractSet[_M]
Get the atoms of this meet semi-lattice.
- Returns:
The atoms.
- Return type:
- abstract property bottom: AbstractSet[_P]
Get the bottom elements.
- Returns:
The bottom elements.
- Return type:
- property co_domain: AbstractSet[_F]
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:
- abstract property cover: AbstractCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractCoveringRelation[_P]
- property domain: AbstractSet[_E]
Get the domain of this binary relation.
This is a proxy to self.universes[0].
- Returns:
The domain of this binary relation.
- Return type:
- abstract filter(element: _P) 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) 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: _P
Get the maximum of the poset.
- Returns:
The maximum element.
- Return type:
- abstract property meet_irreducible: AbstractSet[_M]
Get the meet irreducible elements.
- Returns:
The meet irreducible elements.
- Return type:
- abstract property minimum: _P
Get the minimum of the poset.
- Returns:
The minimum element.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property sinks: AbstractSet[_E]
Get the sinks of this DAG.
- Returns:
The sinks of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the meet semi-lattice.
- abstract property sources: AbstractSet[_E]
Get the sources of this DAG.
- Returns:
The sources of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property top: AbstractSet[_P]
Get the top elements.
- Returns:
The top elements.
- Return type:
- abstract property universes: Tuple[AbstractSet[_E], AbstractSet[_F]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class MeetSemiLattice(domain: Iterable[_M])
The
MeetSemiLattice
class.It implements methods of
AbstractMeetSemiLattice
.A
MeetSemiLattice
instance stores its irreducible in aPartiallyOrderedSet
.Its memory complexity is in \(O(m)\)
Example
>>> from galactic.algebras.lattice import MeetSemiLattice >>> from galactic.examples.arithmetic import PrimeFactors >>> m = MeetSemiLattice[PrimeFactors]( ... domain = [ ... PrimeFactors(2*3*5), ... PrimeFactors(3*5*7), ... PrimeFactors(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(PrimeFactors(5*7))))) [105, 385]
It’s possible to enlarge a meet semi-lattice.
Example
>>> m.extend([PrimeFactors(13)]) >>> sorted(list(map(int, m.domain))) [1, 5, 13, 15, 30, 35, 105, 385]
- __copy__() 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:
- __init__(domain: Iterable[_M])
Initialise a
MeetSemiLattice
instance.- Parameters:
domain (
Iterable[_M]
) – An initial domain.- Raises:
ValueError – If the iterable is empty.
- __iter__() Iterator[Link[_M, _M]]
Get an iterator over the elements.
- Returns:
an iterator over the elements
- Return type:
- property atoms: AbstractSet[_M]
Get the atoms of this meet semi-lattice.
- Returns:
The atoms.
- Return type:
- property bottom: AbstractSet[_M]
Get the bottom elements.
The collection contains only one element, the minimum element.
- Returns:
The bottom elements.
- Return type:
- property co_domain: AbstractSet[_M]
Get the co-domain of this semi-lattice.
- Returns:
The co-domain of this semi-lattice.
- Return type:
- property cover: AbstractCoveringRelation[_M]
Get the covering relation of this meet semi-lattice.
- Returns:
The covering relation.
- Return type:
- property domain: AbstractSet[_M]
Get the domain of this semi-lattice.
- Returns:
The domain of this semi-lattice.
- Return type:
- extend(iterable: Iterable[_M]) None
Extend this meet semi-lattice.
- Parameters:
iterable (
Iterable[_M]
) – An iterable of values.
- filter(element: _M) 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:
- Raises:
ValueError – If the element does not belong to the poset.
- ideal(element: _M) 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:
- 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:
- Returns:
The selected elements.
- Return type:
- property meet_irreducible: AbstractSet[_M]
Get the meet-irreducible elements of this meet semi-lattice.
- Returns:
The meet-irreducible elements.
- Return type:
- property minimum: _M
Get the minimum element of this meet semi-lattice.
- Returns:
The minimum element
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the semi-lattice.
- property sinks: AbstractSet[_M]
Get the sink elements.
- Returns:
The sink elements.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the meet semi-lattice.
- property sources: AbstractSet[_M]
Get the source elements.
The collection contains only one element, the minimum element.
- Returns:
The source elements.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the semi-lattice.
- property top: AbstractSet[_M]
Get the top elements.
- Returns:
The top elements.
- Return type:
- property universes: Tuple[AbstractSet[_M], AbstractSet[_M]]
Get the universes of this meet semi-lattice.
- Returns:
The universes.
- Return type:
- upper_limit(limit: _M, strict: bool = False) AbstractSet[_M]
Get the elements lesser than a limit.
- Parameters:
- Returns:
The selected elements.
- Return type:
- class AbstractLattice(*args, **kwds)
The
AbstractLattice
class describes finite lattices.- __iter__() Iterator[Link[_P, _P]]
Get an iterator over the elements.
- Returns:
An iterator over the elements
- Return type:
- abstract property atoms: AbstractSet[_M]
Get the atoms of this meet semi-lattice.
- Returns:
The atoms.
- Return type:
- abstract property bottom: AbstractSet[_P]
Get the bottom elements.
- Returns:
The bottom elements.
- Return type:
- abstract property co_atoms: AbstractSet[_J]
Get the co-atoms of this join semi-lattice.
- Returns:
The co-atoms.
- Return type:
- property co_domain: AbstractSet[_F]
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:
- abstract property cover: AbstractCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractCoveringRelation[_P]
- property domain: AbstractSet[_E]
Get the domain of this binary relation.
This is a proxy to self.universes[0].
- Returns:
The domain of this binary relation.
- Return type:
- abstract filter(element: _P) 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:
- Raises:
ValueError – If the element does not belong to the join semi-lattice.
- abstract ideal(element: _P) 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: AbstractSet[_J]
Get the join irreducible elements.
- Returns:
The join irreducible elements.
- Return type:
- abstract property maximum: _P
Get the maximum of the poset.
- Returns:
The maximum element.
- Return type:
- abstract property meet_irreducible: AbstractSet[_M]
Get the meet irreducible elements.
- Returns:
The meet irreducible elements.
- Return type:
- abstract property minimum: _P
Get the minimum of the poset.
- Returns:
The minimum element.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property reduced_context: AbstractBinaryRelation[_E, _E]
Get the reduced context from this lattice.
- Returns:
The reduced context.
- Return type:
- abstract property sinks: AbstractSet[_E]
Get the sinks of this DAG.
- Returns:
The sinks of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the meet semi-lattice.
- abstract property sources: AbstractSet[_E]
Get the sources of this DAG.
- Returns:
The sources of this DAG.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property top: AbstractSet[_P]
Get the top elements.
- Returns:
The top elements.
- Return type:
- abstract property universes: Tuple[AbstractSet[_E], AbstractSet[_F]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- 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 thereversed()
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
PrimeFactors
class:>>> from galactic.examples.arithmetic import PrimeFactors >>> from galactic.algebras.lattice import Lattice >>> lattice = Lattice[PrimeFactors](domain=[PrimeFactors(2), PrimeFactors(3)]) >>> list(map(int, lattice.domain)) [6, 2, 3, 1]
- __copy__() Lattice[_E]
Get a copy of the lattice.
The operation is in \(O(j+m)\).
- Returns:
The copy of this lattice.
- Return type:
- __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[Link[_P, _P]]
Get an iterator over the elements.
- Returns:
An iterator over the elements
- Return type:
- property atoms: AbstractSet[_E]
Get the atoms of this lattice.
- Returns:
The atoms
- Return type:
- property bottom: AbstractSet[_E]
Get the bottom elements.
The collection contains only one element, the minimum element.
- Returns:
The bottom elements.
- Return type:
- property co_atoms: AbstractSet[_E]
Get the co-atoms of this lattice.
- Returns:
The co-atoms.
- Return type:
- property co_domain: AbstractSet[_E]
Get the co-domain of this lattice.
- Returns:
The co-domain of this lattice.
- Return type:
- property cover: AbstractReversibleCoveringRelation[_E]
Get the covering relation of this lattice.
- Returns:
The covering relation.
- Return type:
- property domain: AbstractSet[_E]
Get the domain of this lattice.
- Returns:
The domain of this lattice.
- Return type:
- 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) AbstractLattice[_E]
Get a filter of a lattice.
- Parameters:
element (
_E
) – The lower limit- Returns:
The lower bounded lattice.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the lattice.
- ideal(element: _E) AbstractLattice[_E]
Get an ideal of a lattice.
- Parameters:
element (
_E
) – The upper limit- Returns:
The upper bounded lattice.
- Return type:
- 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: AbstractSet[_E]
Get the join irreducible elements.
- Returns:
The join irreducible elements
- Return type:
- lower_limit(limit: _E, strict: bool = Ellipsis) AbstractSet[_E]
Get the elements greater than a limit.
- Parameters:
- Returns:
The selected elements.
- Return type:
- property maximum: _E
Get the maximum element of this lattice.
- Returns:
the maximum element
- Return type:
- property meet_irreducible: AbstractSet[_E]
Get the meet irreducible elements.
- Returns:
The meet irreducible elements
- Return type:
- property minimum: _E
Get the minimum element of this lattice.
- Returns:
The minimum element
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the poset.
- property reduced_context: AbstractBinaryRelation[_E, _E]
Get the reduced context from this lattice.
- Returns:
The reduced context.
- Return type:
- property sinks: AbstractSet[_E]
Get the sink elements.
The collection contains only one element, the maximum element.
- Returns:
The sink elements.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the lattice.
- property sources: AbstractSet[_E]
Get the source elements.
The collection contains only one element, the minimum element.
- Returns:
The source elements.
- Return type:
- 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:
- Raises:
ValueError – If the element does not belong to the poset.
- property top: AbstractSet[_E]
Get the top elements.
The collection contains only one element, the maximum element.
- Returns:
The top elements.
- Return type:
- property universes: Tuple[AbstractSet[_E], AbstractSet[_E]]
Get the universes of this lattice.
- Returns:
The universes.
- Return type:
- upper_limit(limit: _E, strict: bool = False) AbstractSet[_E]
Get the elements lesser than a limit.
- Parameters:
- Returns:
The selected elements.
- Return type:
- class ReducedContextDiagram(lattice: Lattice[_E], graph_renderer: Optional[ReducedContextDiagramRenderer[_E]] = None, domain_renderer: Optional[NodeRenderer[_E, _E]] = None, co_domain_renderer: Optional[NodeRenderer[_E, _E]] = None, edge_renderer: Optional[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: Lattice[_E], graph_renderer: Optional[ReducedContextDiagramRenderer[_E]] = None, domain_renderer: Optional[NodeRenderer[_E, _E]] = None, co_domain_renderer: Optional[NodeRenderer[_E, _E]] = None, edge_renderer: Optional[EdgeRenderer[_E, _E]] = None) None
Initialise a
ReducedContextDiagram
instance.- Parameters:
lattice (
Lattice[_E]
) – The lattice.- Keyword Arguments:
graph_renderer (
ReducedContextDiagramRenderer[_E]
, optional) – The graph renderer.domain_renderer (
NodeRenderer[_E, _E]
, optional) – The domain renderer.co_domain_renderer (
NodeRenderer[_E, _E]
, optional) – The domain renderer.edge_renderer (
EdgeRenderer[_E, _E]
, optional) – The edge renderer.
- property co_domain_renderer: NodeRenderer[_F, _E]
Get the co-domain renderer.
- Returns:
The co-domain renderer.
- Return type:
NodeRenderer[_F, _E]
- property domain_renderer: NodeRenderer[_E, _F]
Get the domain renderer.
- Returns:
The domain renderer.
- Return type:
NodeRenderer[_E, _F]
- property edge_renderer: EdgeRenderer[_E, _F]
Get the edge renderer.
- Returns:
The edge renderer.
- Return type:
EdgeRenderer[_E, _F]
- property graph_renderer: GraphRenderer[_E, _F]
Get the graph renderer.
- Returns:
The graph renderer.
- Return type:
GraphRenderer[_E, _F]
- property relation: AbstractBinaryRelation[_E, _F]
Get the relation.
- Returns:
The underlying relation.
- Return type:
- class ReducedContextDiagramRenderer(*args, **kwds)
The
ReducedContextDiagramRenderer
class renders attributes.it is used for a reduced context diagram.
Notes
- add_destination(element: _F, index: Optional[int] = None, current: bool = False, successors: Optional[AbstractSet[_E]] = None, predecessors: Optional[AbstractSet[_E]] = None) None
Add a destination to the graph.
- Parameters:
element (
_F
) – The destination to add.- Keyword Arguments:
index (int, optional) – The destination index.
current (bool) – is element the current element?
successors (
AbstractSet[_E]
, optional) – The successors of the destination.predecessors (
AbstractSet[_E]
, optional) – The predecessors of the destination.
- add_edge(source: _E, destination: _F, successors: Optional[AbstractSet[_F]] = None, predecessors: Optional[AbstractSet[_E]] = None) None
Add an edge to the graph.
- Parameters:
- Keyword Arguments:
successors (
AbstractSet[_F]
, optional) – The successors of source (including current destination).predecessors (
AbstractSet[_E]
, optional) – The predecessors of destination (including current source).
- add_source(element: _E, index: Optional[int] = None, current: bool = False, successors: Optional[AbstractSet[_F]] = None, predecessors: Optional[AbstractSet[_F]] = None) None
Add a source to the graph.
- Parameters:
element (
_E
) – The source to add.- Keyword Arguments:
index (int, optional) – The source index.
current (bool) – is element the current element?
successors (
AbstractSet[_F]
, optional) – The successors of the source.predecessors (
AbstractSet[_F]
, optional) – The predecessors of the source.