Posets

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of values.
Returns:: True if the poset is disjoint from the other.
Return type:: bool

abstract issubset(other)

Test whether every element in the poset is in other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of values.
Returns:: True if the poset is a subset of the other.
Return type:: bool

abstract issuperset(other)

Test whether every element in the other is in the poset.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of values.
Returns:: True if the poset is a superset of the other.
Return type:: bool

abstract upper_limit(limit, strict=False)

Get the values less than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

A collection of values.

Return type:

Collection[_P]

abstract lower_limit(limit, strict=False)

Get the values greater than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

A collection of values.

Return type:

Collection[_P]

abstract property order: AbstractFinitePartialOrder[_P]

Get the partial order of this poset.

Return type:: The partial order.

abstract property cover: AbstractFiniteCoveringRelation[_P]

Get the covering relation of this poset.

Return type:: The covering relation.

abstract property top: Collection[_P]

Get the top elements.

Return type:: The top elements.

abstract property maximum: _P | None

Get the maximum element if any.

Return type:: The maximum element.

abstract property bottom: Collection[_P]

Get the bottom elements.

Return type:: The bottom elements.

abstract property minimum: _P | None

Get the minimum element if any.

Return type:: The minimum element.

abstract filter(element)

Get a filter of a poset.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The lower limit
Returns:: A view on the lower bounded poset.
Return type:: AbstractFinitePartiallyOrderedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the lower bound is no longer part of the original poset.

abstract ideal(element)

Get an ideal of the poset.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The upper limit
Returns:: A view on the upper bounded set.
Return type:: AbstractFinitePartiallyOrderedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the upper bound is no longer part of the original poset.

abstract property version: int

Get the poset version.

Return type:: The poset version.

Notes

This can be used to detect a change in the poset.

class FrozenFinitePartiallyOrderedSet(*others, elements=None)

Bases: FinitePartiallyOrderedSetMixin[_P]

It implements posets.

The initializer can take 0 or 1 argument that should be iterable.

An instance stores its values in two dictionaries for the immediate successors (\(\succ\)) and the immediate predecessors (\(\prec\)).

Its memory complexity is in \(O(n)\).

Operation complexities:

__contains__(): \(O(1)\)
__len__(): \(O(1)\)
__iter__(): \(O(1)\)
top(): \(O(1)\)
bottom(): \(O(1)\)
successors(): \(O(1)\)
predecessors(): \(O(1)\)

Parameters:

*others (AbstractFinitePartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – A sequence of poset
elements (Iterable[TypeVar(_P, bound= PartiallyComparable)] | None, default: None) – An iterable of values

Example

>>> from galactic.algebras.poset import MutableFinitePartiallyOrderedSet
>>> from galactic.algebras.examples.arithmetic import PrimeFactors
>>> poset = MutableFinitePartiallyOrderedSet[PrimeFactors](
...     elements=[
...         PrimeFactors(2*3*5*7),
...         PrimeFactors(3*5*7*11),
...         PrimeFactors(3*5*7),
...         PrimeFactors(3*5),
...         PrimeFactors(5),
...         PrimeFactors(7),
...     ]
... )
>>>

It’s possible to iterate over the poset elements. The elements are iterated level by level starting from the top ones.

Example

>>> sorted(list(map(int, poset)))
[5, 7, 15, 105, 210, 1155]

It’s possible to know the poset length.

Example

>>> len(poset)
6

It’s possible to know if an element is in the poset.

Example

>>> PrimeFactors(210) in poset
True
>>> PrimeFactors(211) in poset
False

It’s possible to iterate over the top and bottom elements.

Example

>>> sorted(list(map(int, poset.top)))
[210, 1155]
>>> sorted(list(map(int, poset.bottom)))
[5, 7]

It’s possible to iterate over the descendants and the ascendants of an element.

Example

>>> sorted(list(map(int, poset.filter(PrimeFactors(105)))))
[105, 210, 1155]
>>> sorted(list(map(int, poset.ideal(PrimeFactors(105)))))
[5, 7, 15, 105]

It’s possible to iterate over the (immediate) successors and the (immediate) predecessors of an element.

Example

>>> sorted(list(map(int, poset.cover.successors(PrimeFactors(105)))))
[210, 1155]
>>> sorted(list(map(int, poset.order.successors(PrimeFactors(105)))))
[105, 210, 1155]
>>> sorted(list(map(int, poset.cover.predecessors(PrimeFactors(105)))))
[7, 15]
>>> sorted(list(map(int, poset.order.predecessors(PrimeFactors(105)))))
[5, 7, 15, 105]

It’s possible to enlarge a partially ordered set.

Example

>>> poset.update([PrimeFactors(13)])
>>> sorted(list(map(int, poset)))
[5, 7, 13, 15, 105, 210, 1155]

property version: int

Get the version number.

Return type:: The version number.

Notes

This can be used to detect a change in the poset.

copy()

Get a copy of the partially ordered set.

Return type:: Self
Returns:: The copy of this poset.

union(*others)

Compute the union of the poset and the others.

Parameters:: *others (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – A sequence of iterable.
Returns:: The union of the poset and the others.
Return type:: Self

intersection(*others)

Compute the intersection between the poset and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The intersection between the poset and the others
Return type:: Self

difference(*others)

Compute the difference between the poset and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The difference between the poset and the others
Return type:: Self

symmetric_difference(other)

Compute the symmetric difference between the poset and the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of elements.
Returns:: The symmetric difference between the poset and the other.
Return type:: Self

property order: AbstractFinitePartialOrder[_P]

Get the partial order of this poset.

Return type:: The partial order.

property cover: AbstractFiniteCoveringRelation[_P]

Get the covering relation of this poset.

Return type:: The covering relation.

property top: Collection[_P]

Get the top elements.

Return type:: The top elements.

property tail: _P | None

Get the tail element if any.

Return type:: The tail element.
Raises:: KeyError – If the semi-lattice is empty.

property bottom: Collection[_P]

Get the bottom elements.

Return type:: The bottom elements.

property head: _P | None

Get the head element if any.

Return type:: The head element.
Raises:: KeyError – If the semi-lattice is empty.

filter(element)

Get a filter of a poset.

This is a view of this poset restricted the lower limit.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The lower limit
Returns:: A view on the lower bounded poset.
Return type:: AbstractFinitePartiallyOrderedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the lower bound is no longer part of the original poset.

ideal(element)

Get an ideal of the poset.

This is a view of this poset restricted the upper limit.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The upper limit
Returns:: A view on the upper bounded set.
Return type:: AbstractFinitePartiallyOrderedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the upper bound is no longer part of the original poset.

isdisjoint(other)

Test if the relation is disjoint from the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the relation is in other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other relation is in the relation.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a superset of the other.
Return type:: bool

lower_limit(limit, strict=False)

Get the values greater than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

A collection of values.

Return type:

Collection[_P]

property maximum: _P | None

Get the maximum element if any.

Return type:: The maximum element.

property minimum: _P | None

Get the minimum element if any.

Return type:: The minimum element.

upper_limit(limit, strict=False)

Get the values less than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

An collection of values.

Return type:

Collection[_P]

class MutableFinitePartiallyOrderedSet(*others, elements=None)

Bases: FrozenFinitePartiallyOrderedSet[_P]

It represents mutable finite poset.

add(value)

Add a value to the poset.

Parameters:: value (TypeVar(_P, bound= PartiallyComparable)) – The value to add.
Return type:: None

remove(value)

Remove a value from the poset.

Parameters:: value (TypeVar(_P, bound= PartiallyComparable)) – The value to remove.
Return type:: None

discard(value)

Discard a value from the poset.

Parameters:: value (TypeVar(_P, bound= PartiallyComparable)) – The value to discard.
Return type:: None

pop()

Remove and return the first value of the set.

Return type:: TypeVar(_P, bound= PartiallyComparable)
Returns:: The value removed.

popitem(last=False)

Remove and return the first value of the set.

Parameters:: last (bool, default: False) – Does the remove take place at the end or the beginning?
Returns:: The value removed.
Return type:: _P

clear()

Clear the poset.

Return type:: None

property bottom: Collection[_P]

Get the bottom elements.

Return type:: The bottom elements.

copy()

Get a copy of the partially ordered set.

Return type:: Self
Returns:: The copy of this poset.

property cover: AbstractFiniteCoveringRelation[_P]

Get the covering relation of this poset.

Return type:: The covering relation.

difference(*others)

Compute the difference between the poset and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The difference between the poset and the others
Return type:: Self

filter(element)

Get a filter of a poset.

This is a view of this poset restricted the lower limit.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The lower limit
Returns:: A view on the lower bounded poset.
Return type:: AbstractFinitePartiallyOrderedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the lower bound is no longer part of the original poset.

property head: _P | None

Get the head element if any.

Return type:: The head element.
Raises:: KeyError – If the semi-lattice is empty.

ideal(element)

Get an ideal of the poset.

This is a view of this poset restricted the upper limit.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The upper limit
Returns:: A view on the upper bounded set.
Return type:: AbstractFinitePartiallyOrderedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the upper bound is no longer part of the original poset.

intersection(*others)

Compute the intersection between the poset and the others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Returns:: The intersection between the poset and the others
Return type:: Self

isdisjoint(other)

Test if the relation is disjoint from the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the relation is in other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other relation is in the relation.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a superset of the other.
Return type:: bool

lower_limit(limit, strict=False)

Get the values greater than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

A collection of values.

Return type:

Collection[_P]

property maximum: _P | None

Get the maximum element if any.

Return type:: The maximum element.

property minimum: _P | None

Get the minimum element if any.

Return type:: The minimum element.

property order: AbstractFinitePartialOrder[_P]

Get the partial order of this poset.

Return type:: The partial order.

symmetric_difference(other)

Compute the symmetric difference between the poset and the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of elements.
Returns:: The symmetric difference between the poset and the other.
Return type:: Self

property tail: _P | None

Get the tail element if any.

Return type:: The tail element.
Raises:: KeyError – If the semi-lattice is empty.

property top: Collection[_P]

Get the top elements.

Return type:: The top elements.

union(*others)

Compute the union of the poset and the others.

Parameters:: *others (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – A sequence of iterable.
Returns:: The union of the poset and the others.
Return type:: Self

upper_limit(limit, strict=False)

Get the values less than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

An collection of values.

Return type:

Collection[_P]

property version: int

Get the version number.

Return type:: The version number.

Notes

This can be used to detect a change in the poset.

extend(iterable)

Extend a poset with the iterable.

Parameters:: iterable (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of values
Return type:: None

update(*others)

Update a poset with the union of itself and others.

Parameters:: *others (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – A sequence of iterable.
Return type:: None

intersection_update(*others)

Update a poset with the intersection of itself and others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Return type:: None

difference_update(*others)

Update a poset with the difference of itself and others.

Parameters:: *others (Iterable[Any]) – A sequence of iterable.
Return type:: None

symmetric_difference_update(other)

Update a poset with the symmetric difference of itself and the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of elements.
Return type:: None

class FinitePartiallyOrderedSetView(poset, lower=None, upper=None)

Bases: FinitePartiallyOrderedSetMixin[_P]

It represents view on partially ordered sets.

Parameters:

poset (AbstractFinitePartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – A poset.
lower (Optional[TypeVar(_P, bound= PartiallyComparable)], default: None) – The lower limit.
upper (Optional[TypeVar(_P, bound= PartiallyComparable)], default: None) – The upper limit.

Notes

Unpredictable behavior can occur if the lower or the upper bound is no longer part of the original poset.

isdisjoint(other)

Test if the relation is disjoint from the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the relation is in other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other relation is in the relation.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a superset of the other.
Return type:: bool

lower_limit(limit, strict=False)

Get the values greater than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

A collection of values.

Return type:

Collection[_P]

property maximum: _P | None

Get the maximum element if any.

Return type:: The maximum element.

property minimum: _P | None

Get the minimum element if any.

Return type:: The minimum element.

upper_limit(limit, strict=False)

Get the values less than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

An collection of values.

Return type:

Collection[_P]

property version: int

Get the poset version.

Return type:: The poset version.

Notes

This can be used to detect a change in the poset.

property order: AbstractFinitePartialOrder[_P]

Get the partial order of this bounded set.

Return type:: The partial order.

property cover: AbstractFiniteCoveringRelation[_P]

Get the covering relation of this bounded set.

Return type:: The covering relation.

property top: Collection[_P]

Get the top elements.

Return type:: The top elements.

property bottom: Collection[_P]

Get the bottom elements.

Return type:: The bottom elements.

filter(element)

Get a filter of a bounded set.

This is a view of this poset restricted by the lower limit.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The lower limit
Returns:: A view on the lower bounded poset.
Return type:: FinitePartiallyOrderedSetView[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the lower bound is no longer part of the original poset.

ideal(element)

Get an ideal of the bounded set.

This is a view of this poset restricted by the upper limit.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The upper limit
Returns:: A view on the upper bounded set.
Return type:: FinitePartiallyOrderedSetView[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the upper bound is no longer part of the original poset.

class FinitePartiallyOrderedSetMixin

Bases: Generic[_P]

It represents finite poset mixin.

isdisjoint(other)

Test if the relation is disjoint from the other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the relation is in other.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other relation is in the relation.

Parameters:: other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of couples.
Returns:: True if the relation is a superset of the other.
Return type:: bool

property maximum: _P | None

Get the maximum element if any.

Return type:: The maximum element.

property minimum: _P | None

Get the minimum element if any.

Return type:: The minimum element.

upper_limit(limit, strict=False)

Get the values less than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

An collection of values.

Return type:

Collection[_P]

lower_limit(limit, strict=False)

Get the values greater than the limit.

Parameters:

limit (TypeVar(_P, bound= PartiallyComparable)) – The limit.
strict (bool, default: False) – Is the comparison strict?

Returns:

A collection of values.

Return type:

Collection[_P]

class PartiallyComparable(*args, **kwargs)

Bases: Protocol

Partially comparable elements.

A partially ordered type sets for each pair of elements \(a\), \(b\) either:

\(a \leq b\)
\(b \leq a\)
a and b are incomparable (\(a \| b\))

The relation \(\leq\) must be:

reflexive (\(a \leq a\))
transitive (\(a \leq b\) and \(b \leq c\) implies \(a \leq c\))
anti-symmetric (\(a \leq b\) and \(b \leq a\) implies \(a = b\))

A class implementing the PartiallyComparable protocol must be declared by inheriting from PartiallyComparable and must implement the methods:

__lt__()
__gt__()
__le__()
__ge__()

Notes

The builtin classes

are considered as subclasses of PartiallyComparable.

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(5) <= PrimeFactors(10)  # 5 is a divisor of 10
True
>>> PrimeFactors(5) <= PrimeFactors(11)  # 5 is not a divisor of 11
False
>>> PrimeFactors(5) >= PrimeFactors(11)  # 5 is not a multiple of 11
False

abstract __lt__(other)

Test if this element is lesser than the other.

Parameters:: other (Self) – the other element
Returns:: True if this element is lesser than the other.
Return type:: bool

abstract __gt__(other)

Test if this element is greater than the other.

Parameters:: other (Self) – the other element
Returns:: True if this element is greater than the other.
Return type:: bool

abstract __le__(other)

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

Parameters:: other (Self) – the other element
Returns:: True if this element is lesser than or equal to the other.
Return type:: bool

abstract __ge__(other)

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

Parameters:: other (Self) – the other element
Returns:: True if this element is greater than or equal to the other.
Return type:: bool

bottom(iterable)

Compute an iterator over the bottom elements of the iterable.

This operation computes in \(O(n^2)\) where \(n\) is the number of elements in the iterable.

Parameters:: iterable (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of partially ordered elements.
Returns:: An iterator over the bottom elements.
Return type:: Iterator[_P]

Example

>>> from galactic.algebras.poset import top
>>> values = [{1, 2, 3}, {1, 2, 3, 4}, {2, 3, 4, 5}]
>>> list(bottom(list(map(frozenset, values))))
[frozenset({1, 2, 3}), frozenset({2, 3, 4, 5})]

top(iterable)

Compute an iterator over the top elements of the iterable.

This operation computes in \(O(n^2)\) where \(n\) is the number of elements in the iterable.

Parameters:: iterable (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of partially ordered elements.
Returns:: An iterator over the top elements.
Return type:: Iterator[_P]

Example

>>> from galactic.algebras.poset import top
>>> values = [{1, 2, 3}, {1, 2, 3, 4}, {2, 3, 4, 5}]
>>> list(top(list(map(frozenset, values))))
[frozenset({1, 2, 3, 4}), frozenset({2, 3, 4, 5})]

lower_limit(iterable, limit, strict=False)

Compute an iterator over the elements greater than the limit.

This operation computes in \(O(n)\) where \(n\) is the number of elements in the iterable.

Parameters:

iterable (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of partially ordered elements.
limit (TypeVar(_P, bound= PartiallyComparable)) – The lower limit
strict (bool, default: False) – Is the comparison strict?

Yields:

_P – A selected element

Return type:

Iterator[TypeVar(_P, bound= PartiallyComparable)]

Example

>>> from galactic.algebras.poset import lower_limit
>>> values = [{1, 2}, {1, 2, 3}, {2, 3}]
>>> list(lower_limit(list(map(frozenset, values)), frozenset({2, 3})))
[frozenset({1, 2, 3}), frozenset({2, 3})]

# noqa: DAR301

upper_limit(iterable, limit, strict=False)

Compute an iterator over the elements lesser than the limit.

This operation computes in \(O(n)\) where \(n\) is the number of elements in the iterable.

Parameters:

iterable (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of partially ordered elements.
limit (TypeVar(_P, bound= PartiallyComparable)) – The upper limit
strict (bool, default: False) – Is the comparison strict?

Yields:

_P – A selected element.

Return type:

Iterator[TypeVar(_P, bound= PartiallyComparable)]

Example

>>> from galactic.algebras.poset import upper_limit
>>> values = [{1, 2}, {1, 2, 3}, {2, 3}]
>>> list(upper_limit(list(map(frozenset, values)), frozenset({2, 3})))
[frozenset({2, 3})]

# noqa: DAR301

class AbstractFinitePartialOrder(*args, **kwargs)

Bases: AbstractFiniteDirectedAcyclicRelation[_P], Protocol[_P]

It represents finite partial orders.

abstract property co_domain: Collection[_F]

Get the co-domain of this binary relation.

It returns the second universe.

Return type:: The co-domain of this binary relation.

abstract property domain: Collection[_E]

Get the domain of this binary relation.

It returns the first universe.

Return type:: The domain of this binary relation.

abstract predecessors(element)

Get the predecessors of an element.

Parameters:: element (TypeVar(_F)) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: Collection[_E]
Raises:: NotImplementedError –

abstract property sinks: Collection[_E]

Get the sinks of this DAG.

Return type:: The sinks of this DAG.

abstract property sources: Collection[_E]

Get the sources of this DAG.

Return type:: The sources of this DAG.

abstract successors(element)

Get the successors of an element.

Parameters:: element (TypeVar(_E)) – The element whose successors are requested
Returns:: The successors.
Return type:: Collection[_F]
Raises:: NotImplementedError –

abstract property universes: tuple[Collection[_E], Collection[_F]]

Get the universes of this relation.

Return type:: The universes of this relation.

class FinitePartialOrder(poset)

Bases: FiniteRelationMixin, Generic[_P]

It represents a partial order.

Parameters:: poset (AbstractFinitePartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – A poset.

property universes: tuple[Collection[_P], Collection[_P]]

Get the universes.

Return type:: The universes.

property domain: Collection[_P]

Get the domain.

Return type:: The domain.

property co_domain: Collection[_P]

Get the co-domain of this partial order.

Return type:: The co-domain of this partial order.

Notes

The domain and the co-domain of a partial order are identical.

property sinks: Collection[_P]

Get the sink elements.

Return type:: The sink elements.

property sources: Collection[_P]

Get the source elements.

Return type:: The source elements.

isdisjoint(other)

Test if the relation is disjoint from the other.

Parameters:: other (Iterable[tuple[Any, ...]]) – An iterable of ntuple.
Returns:: True if the relation is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the relation is in other.

Parameters:: other (Iterable[tuple[Any, ...]]) – An iterable of ntuple.
Returns:: True if the relation is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other relation is in the relation.

Parameters:: other (Iterable[tuple[Any, ...]]) – An iterable of ntuple.
Returns:: True if the relation is a superset of the other.
Return type:: bool

successors(element)

Get the successors of an element.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The element whose successors are requested.
Returns:: The successors.
Return type:: Collection[_P]
Raises:: ValueError – If the element does not belong to the poset.

predecessors(element)

Get the predecessors of an element.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The element whose predecessors are requested.
Returns:: The predecessors.
Return type:: Collection[_P]
Raises:: ValueError – If the element does not belong to the poset.

class AbstractFiniteCoveringRelation(*args, **kwargs)

Bases: AbstractFiniteDirectedAcyclicRelation[_P], Protocol[_P]

It represents a covering relation.

abstract neighbourhoods(reverse=False)

Get an iterator over the neighbourhoods of an element.

Parameters:: reverse (bool, default: False) – Is this a bottom-up generation ?
Returns:: An iterable giving a triple (element, successors, predecessors) for each element in the covering relation represented by a neighbourhood.
Return type:: Iterator[Neighbourhood[_P]]
Raises:: NotImplementedError –

abstract property co_domain: Collection[_F]

Get the co-domain of this binary relation.

It returns the second universe.

Return type:: The co-domain of this binary relation.

abstract property domain: Collection[_E]

Get the domain of this binary relation.

It returns the first universe.

Return type:: The domain of this binary relation.

abstract predecessors(element)

Get the predecessors of an element.

Parameters:: element (TypeVar(_F)) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: Collection[_E]
Raises:: NotImplementedError –

abstract property sinks: Collection[_E]

Get the sinks of this DAG.

Return type:: The sinks of this DAG.

abstract property sources: Collection[_E]

Get the sources of this DAG.

Return type:: The sources of this DAG.

abstract successors(element)

Get the successors of an element.

Parameters:: element (TypeVar(_E)) – The element whose successors are requested
Returns:: The successors.
Return type:: Collection[_F]
Raises:: NotImplementedError –

abstract property universes: tuple[Collection[_E], Collection[_F]]

Get the universes of this relation.

Return type:: The universes of this relation.

class FiniteCoveringRelationMixin(poset)

Bases: FiniteRelationMixin, Generic[_P]

It represents finite covering relation.

Parameters:: poset (AbstractFinitePartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – A poset.

property universes: tuple[Collection[_P], Collection[_P]]

Get the universes of this covering relation.

Return type:: The universes of this covering relation.

property domain: Collection[_P]

Get the domain of this covering relation.

Return type:: The domain of this covering relation.

Notes

The domain and the co-domain of a covering relation are identical.

property co_domain: Collection[_P]

Get the co-domain of this covering relation.

Return type:: The co-domain of this covering relation.

Notes

The domain and the co-domain of a covering relation are identical.

abstract successors(element)

Get the successors of an element.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The element whose successors are requested
Returns:: The successors.
Return type:: Collection[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the element is no longer part of the original poset.

isdisjoint(other)

Test if the relation is disjoint from the other.

Parameters:: other (Iterable[tuple[Any, ...]]) – An iterable of ntuple.
Returns:: True if the relation is disjoint from the other.
Return type:: bool

issubset(other)

Test whether every element in the relation is in other.

Parameters:: other (Iterable[tuple[Any, ...]]) – An iterable of ntuple.
Returns:: True if the relation is a subset of the other.
Return type:: bool

issuperset(other)

Test whether every element in the other relation is in the relation.

Parameters:: other (Iterable[tuple[Any, ...]]) – An iterable of ntuple.
Returns:: True if the relation is a superset of the other.
Return type:: bool

abstract predecessors(element)

Get the predecessors of an element.

Parameters:: element (TypeVar(_P, bound= PartiallyComparable)) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: Collection[_P]
Raises:: ValueError – If the element does not belong to the poset.

Notes

Unpredictable behavior can occur if the element is no longer part of the original poset.

property sinks: Collection[_P]

Get the elements with no successors.

Returns:: The elements with no successors.
Return type:: Collection[_P]

property sources: Collection[_P]

Get the elements with no predecessors.

Returns:: The elements with no predecessors.
Return type:: Collection[_P]

abstract neighbourhoods(reverse=False)

Get an iterator over the neighbourhoods of an element.

Parameters:: reverse (bool, default: False) – Is this a bottom-up generation ?
Returns:: An iterator giving a triple (element, successors, predecessors) for each element in the covering relation represented by a neighbourhood.
Return type:: Iterator[Neighbourhood[_P]]
Raises:: NotImplementedError –

class Bottom(poset, lower, upper)

Bases: Generic[_P]

It represents the bottom elements in a bounded set.

Parameters:

poset (AbstractFinitePartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – The inner poset.
lower (Optional[TypeVar(_P, bound= PartiallyComparable)]) – The lower bound.
upper (Optional[TypeVar(_P, bound= PartiallyComparable)]) – The upper bound.

class Top(poset, lower, upper)

Bases: Generic[_P]

It represents the top elements in a bounded set.

Parameters:

poset (AbstractFinitePartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – The inner poset.
lower (Optional[TypeVar(_P, bound= PartiallyComparable)]) – The lower bound.
upper (Optional[TypeVar(_P, bound= PartiallyComparable)]) – The upper bound.