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
Element
describes elements that can be member of a lattice.- abstract __eq__(other: object) bool
Test if this element is equal to the other.
- Parameters:
other (object) – the other element
- Returns:
True
– if this element is equal to the other.NotImplemented
– if the operation is not implemented between the two objects
- __ge__(other: object) bool
Test if this element is greater than or equal to the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is greater than the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is lesser than or equal to the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is lesser than the other.
- Parameters:
other (object) – 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
The
Joinable
class.This class sets for each pair of elements a, b a unique supremum \(c = a \vee b\) (also called a least upper bound or join).
A class implementing the
Joinable
abstract class must be declared by inheriting from galactic.s: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.algebras.examples.arithmetic import PrimeFactors >>> PrimeFactors(24) | PrimeFactors(36) PrimeFactors(72) >>> PrimeFactors(24).join(PrimeFactors(36), PrimeFactors(10)) PrimeFactors(360)
- abstract __eq__(other: object) bool
Test if this element is equal to the other.
- Parameters:
other (object) – the other element
- Returns:
True
– if this element is equal to the other.NotImplemented
– if the operation is not implemented between the two objects
- __ge__(other: object) bool
Test if this element is greater than or equal to the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is greater than the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is lesser than or equal to the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is lesser than the other.
- Parameters:
other (object) – 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
The
Meetable
class.This type sets for each pair of elements a, b a unique infimum \(c = a \wedge b\) (also called one of the greatest lower bound or meet).
A class implementing the
Meetable
abstract class must be declared by inheriting from galactic.s:Meetable 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.algebras.examples.arithmetic import PrimeFactors >>> PrimeFactors(24) & PrimeFactors(36) PrimeFactors(12) >>> PrimeFactors(24).meet(PrimeFactors(36), PrimeFactors(10)) PrimeFactors(2)
- abstract __eq__(other: object) bool
Test if this element is equal to the other.
- Parameters:
other (object) – the other element
- Returns:
True
– if this element is equal to the other.NotImplemented
– if the operation is not implemented between the two objects
- __ge__(other: object) bool
Test if this element is greater than or equal to the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is greater than the other.
- Parameters:
other (object) – 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: object) bool
Test if this element is lesser than or equal to the other.
- Parameters:
other (object) – 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
- infimum(iterable: Iterable[_M]) _M
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]) _J
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 galactic.erable of meetable elements.
- Parameters:
iterable (
Iterable[_M]
) – The iterable collection of elements.- Yields:
_M – An infimum generator.
- supremum_generators(iterable: Iterable[_J]) Iterator[_J]
Produce the supremum generators from galactic.erable of joinable elements.
- Parameters:
iterable (
Iterable[_J]
) – The iterable collection of elements.- Yields:
_J – A supremum generator.
- class AbstractFiniteJoinSemiLattice
AbstractFiniteJoinSemiLattice
describes finite join semi-lattices.- __iter__() Iterator[Tuple[_P, _P]]
Get an iterator over the elements.
- Yields:
Tuple[_P, _P]
– A couple of the relation.
- 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: AbstractFiniteCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractFiniteCoveringRelation[_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) AbstractFiniteLowerBoundedSet[_P]
Get a filter of a poset.
- Parameters:
element (_P) – The lower limit
- Returns:
The lower bounded poset.
- Return type:
AbstractFiniteLowerBoundedSet[_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) AbstractFiniteUpperBoundedSet[_P]
Get an ideal of the poset.
- Parameters:
element (_P) – The upper limit
- Returns:
The upper bounded set.
- Return type:
AbstractFiniteUpperBoundedSet[_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:
_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:
- 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[_J], AbstractSet[_J]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class AbstractFiniteLowerBoundedJoinSemiLattice
The
AbstractFiniteLowerBoundedJoinSemiLattice
class.It represents abstract lower bounded join semi-lattices.
- __iter__() Iterator[Tuple[_P, _P]]
Get an iterator over the elements.
- Yields:
Tuple[_P, _P]
– A couple of the relation.
- 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: AbstractFiniteCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractFiniteCoveringRelation[_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) AbstractFiniteLowerBoundedSet[_P]
Get a filter of a poset.
- Parameters:
element (_P) – The lower limit
- Returns:
The lower bounded poset.
- Return type:
AbstractFiniteLowerBoundedSet[_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) AbstractFiniteUpperBoundedSet[_P]
Get an ideal of the poset.
- Parameters:
element (_P) – The upper limit
- Returns:
The upper bounded set.
- Return type:
AbstractFiniteUpperBoundedSet[_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:
_P
- abstract property minimum: _P
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:
- 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[_J], AbstractSet[_J]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class FiniteJoinSemiLattice(domain: Iterable[_J])
The
FiniteJoinSemiLattice
class.It implements methods of
AbstractFiniteJoinSemiLattice
.A
FiniteJoinSemiLattice
instance stores its irreducible in aFinitePartiallyOrderedSet
.Its memory complexity is in \(O(j)\)
Example
>>> from galactic.algebras.lattice import FiniteMeetSemiLattice >>> from galactic.algebras.examples.arithmetic import PrimeFactors >>> m = FiniteMeetSemiLattice[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__() FiniteJoinSemiLattice[_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:
FiniteJoinSemiLattice[_J]
- __init__(domain: Iterable[_J]) None
Initialise a
FiniteJoinSemiLattice
instance.- Parameters:
domain (
Iterable[_J]
) – An initial domain.- Raises:
ValueError – If the iterable is empty.
- __iter__() Iterator[Tuple[_J, _J]]
Get an iterator over the elements.
- Yields:
Tuple[_J, _J]
– A couple of the relation.
- 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: AbstractFiniteCoveringRelation[_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) AbstractFiniteLowerBoundedJoinSemiLattice[_J]
Get a filter of a join semi-lattice.
- Parameters:
element (_J) – The lower limit
- Raises:
ValueError – If the element does not belong to the poset.
NotImplementedError – For the moment.
- 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) AbstractFiniteJoinSemiLattice[_J]
Get an ideal of a join semi-lattice.
- Parameters:
element (_J) – The upper limit
- Raises:
ValueError – If the element does not belong to the poset.
NotImplementedError – For the moment.
- 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:
limit (_J) – The lower limit
strict (bool) – Is the comparison strict?
- Returns:
The selected elements.
- Return type:
- property maximum: _J
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:
- 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:
limit (_J) – The upper limit
strict (bool) – Is the comparison strict?
- Returns:
The selected elements.
- Return type:
- class AbstractFiniteMeetSemiLattice
AbstractFiniteMeetSemiLattice
describes finite meet semi-lattices.- __iter__() Iterator[Tuple[_P, _P]]
Get an iterator over the elements.
- Yields:
Tuple[_P, _P]
– A couple of the relation.
- 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: AbstractFiniteCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractFiniteCoveringRelation[_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) AbstractFiniteLowerBoundedSet[_P]
Get a filter of a poset.
- Parameters:
element (_P) – The lower limit
- Returns:
The lower bounded poset.
- Return type:
AbstractFiniteLowerBoundedSet[_P]
- Raises:
ValueError – If the element does not belong to the poset.
- abstract ideal(element: _P) AbstractFiniteUpperBoundedSet[_P]
Get an ideal of the poset.
- Parameters:
element (_P) – The upper limit
- Returns:
The upper bounded set.
- Return type:
AbstractFiniteUpperBoundedSet[_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:
_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:
- 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[_M], AbstractSet[_M]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class AbstractFiniteUpperBoundedMeetSemiLattice
The
AbstractFiniteUpperBoundedMeetSemiLattice
class.It represents abstract upper bounded meet semi-lattices.
- __iter__() Iterator[Tuple[_P, _P]]
Get an iterator over the elements.
- Yields:
Tuple[_P, _P]
– A couple of the relation.
- 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: AbstractFiniteCoveringRelation[_P]
Get the covering relation.
- Returns:
The covering relation.
- Return type:
AbstractFiniteCoveringRelation[_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) AbstractFiniteLowerBoundedSet[_P]
Get a filter of a poset.
- Parameters:
element (_P) – The lower limit
- Returns:
The lower bounded poset.
- Return type:
AbstractFiniteLowerBoundedSet[_P]
- Raises:
ValueError – If the element does not belong to the poset.
- abstract ideal(element: _P) AbstractFiniteUpperBoundedSet[_P]
Get an ideal of the poset.
- Parameters:
element (_P) – The upper limit
- Returns:
The upper bounded set.
- Return type:
AbstractFiniteUpperBoundedSet[_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:
_P
- 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:
_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:
- 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[_M], AbstractSet[_M]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class FiniteMeetSemiLattice(domain: Iterable[_M])
The
FiniteMeetSemiLattice
class.It implements methods of
AbstractFiniteMeetSemiLattice
.A
FiniteMeetSemiLattice
instance stores its irreducible in aFinitePartiallyOrderedSet
.Its memory complexity is in \(O(m)\)
Example
>>> from galactic.algebras.lattice import FiniteMeetSemiLattice >>> from galactic.algebras.examples.arithmetic import PrimeFactors >>> m = FiniteMeetSemiLattice[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__() FiniteMeetSemiLattice[_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:
FiniteMeetSemiLattice[_M]
- __init__(domain: Iterable[_M]) None
Initialise a
FiniteMeetSemiLattice
instance.- Parameters:
domain (
Iterable[_M]
) – An initial domain.- Raises:
ValueError – If the iterable is empty.
- __iter__() Iterator[Tuple[_M, _M]]
Get an iterator over the elements.
- Yields:
Tuple[_M, _M]
– A couple of the relation.
- 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: AbstractFiniteCoveringRelation[_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) AbstractFiniteMeetSemiLattice[_M]
Get a filter of a meet semi-lattice.
- Parameters:
element (_M) – The lower limit
- Raises:
ValueError – If the element does not belong to the poset.
NotImplementedError – For the moment.
- ideal(element: _M) AbstractFiniteUpperBoundedMeetSemiLattice[_M]
Get an ideal of a meet semi-lattice.
- Parameters:
element (_M) – The upper limit
- Raises:
ValueError – If the element does not belong to the poset.
NotImplementedError – For the moment.
- 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:
- 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:
_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:
- 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:
limit (_M) – The upper limit
strict (bool) – Is the comparison strict?
- Returns:
The selected elements.
- Return type:
- class AbstractFiniteLattice
AbstractFiniteLattice
describes finite lattices.- __iter__() Iterator[Tuple[_P, _P]]
Get an iterator over the elements.
- Yields:
Tuple[_P, _P]
– A couple of the relation.
- 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: AbstractFiniteReversibleCoveringRelation[_E]
Get the covering relation of this lattice.
- Returns:
The covering relation.
- Return type:
- 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) AbstractFiniteLowerBoundedSet[_P]
Get a filter of a poset.
- Parameters:
element (_P) – The lower limit
- Returns:
The lower bounded poset.
- Return type:
AbstractFiniteLowerBoundedSet[_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) AbstractFiniteUpperBoundedSet[_P]
Get an ideal of the poset.
- Parameters:
element (_P) – The upper limit
- Returns:
The upper bounded set.
- Return type:
AbstractFiniteUpperBoundedSet[_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:
_P
- 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:
_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:
- Raises:
ValueError – If the element does not belong to the relation.
- abstract property reduced_context: AbstractFiniteBinaryRelation[_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[_E]]
Get the universes of this relation.
- Returns:
The universes of this relation.
- Return type:
- class FiniteLattice(domain: Iterable[_E])
FiniteLattice
stores a compact version of a lattice.It uses its join irreducible and meet irreducible elements.
The domain elements of a
FiniteLattice
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.algebras.examples.arithmetic import PrimeFactors >>> from galactic.algebras.lattice import FiniteLattice >>> lattice = FiniteLattice[PrimeFactors](domain=[PrimeFactors(2), PrimeFactors(3)]) >>> list(map(int, lattice.domain)) [6, 2, 3, 1]
- __copy__() FiniteLattice[_E]
Get a copy of the lattice.
The operation is in \(O(j+m)\).
- Returns:
The copy of this lattice.
- Return type:
FiniteLattice[_E]
- __init__(domain: Iterable[_E]) None
Initialise a
FiniteLattice>
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.
- Yields:
Tuple[_P, _P]
– A couple of the relation.
- 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: AbstractFiniteReversibleCoveringRelation[_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) AbstractFiniteLattice[_E]
Get a filter of a lattice.
- Parameters:
element (_E) – The lower limit
- Raises:
ValueError – If the element does not belong to the poset.
NotImplementedError – For the moment
- 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) AbstractFiniteLattice[_E]
Get an ideal of a lattice.
- Parameters:
element (_E) – The upper limit
- Raises:
ValueError – If the element does not belong to the poset.
NotImplementedError – For the moment
- 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 = False) AbstractSet[_E]
Get the elements greater than a limit.
- Parameters:
limit (_E) – The lower limit
strict (bool) – Is the comparison strict?
- Raises:
NotImplementedError – For the moment.
- property maximum: _E
Get the maximum element of this lattice.
- Returns:
the maximum element
- Return type:
_E
- 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:
_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:
- Raises:
ValueError – If the element does not belong to the poset.
- property reduced_context: AbstractFiniteBinaryRelation[_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:
limit (_E) – The upper limit
strict (bool) – Is the comparison strict?
- Raises:
NotImplementedError – For the moment.
- class ReducedContextDiagram(lattice: FiniteLattice[_E], graph_renderer: ReducedContextDiagramRenderer[_E] | None = None, domain_renderer: NodeRenderer[_E, _E] | None = None, co_domain_renderer: NodeRenderer[_E, _E] | None = None, edge_renderer: EdgeRenderer[_E, _E] | None = None)
ReducedContextDiagram
is used for drawing sagittal diagrams.It is useful for drawing sagittal diagrams of lattice reduced context in jupyter notebooks.
- __init__(lattice: FiniteLattice[_E], graph_renderer: ReducedContextDiagramRenderer[_E] | None = None, domain_renderer: NodeRenderer[_E, _E] | None = None, co_domain_renderer: NodeRenderer[_E, _E] | None = None, edge_renderer: EdgeRenderer[_E, _E] | None = None) None
Initialise a
ReducedContextDiagram
instance.- Parameters:
lattice (
FiniteLattice[_E]
) – The lattice.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: AbstractFiniteBinaryRelation[_E, _F]
Get the relation.
- Returns:
The underlying relation.
- Return type:
- class ReducedContextDiagramRenderer
ReducedContextDiagramRenderer
renders attributes.it is used for a reduced context diagram.
Notes
- add_destination(element: _F, index: int | None = None, current: bool = False, successors: AbstractSet[_E] | None = None, predecessors: AbstractSet[_E] | None = None) None
Add a destination to the graph.
- Parameters:
element (_F) – The destination to add.
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: AbstractSet[_F] | None = None, predecessors: AbstractSet[_E] | None = None) None
Add an edge to the graph.
- Parameters:
source (_E) – The edge source
destination (_F) – The edge destination
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: int | None = None, current: bool = False, successors: AbstractSet[_F] | None = None, predecessors: AbstractSet[_F] | None = None) None
Add a source to the graph.
- Parameters:
element (_E) – The source to add.
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.