🔌 Posets

Contents

🔌 Posets#

Classes and functions#

The galactic.algebras.poset module.

Abstract classes for posets

Concrete classes for posets

Elements which are partially comparable:

Function on elements which are partially comparable

Classes for representing underlying order relation

Mixins for the top and bottom collections

class Neighbourhood(element, successors, predecessors)#

Bases: Generic[_P]

It represents the neighbourhood in a covering relation.

It associates an element with its direct successors and predecessors. It is a dataclass containing three fields:

  • the element whose neighbourhood is considered;

  • the immediate successors of the element;

  • the immediate predecessors of the element.

class AbstractFinitePartiallyOrderedSet(*args, **kwargs)#

Bases: Collection[_P], Protocol[_P]

It represents finite partially ordered set (poset).

abstract property bottom: Collection[_P]#

Get the bottom elements.

Returns:

The bottom elements.

Return type:

Collection[_P]

abstract property cover: AbstractFiniteCoveringRelation[_P]#

Get the covering relation of this poset.

Returns:

The covering relation.

Return type:

AbstractFiniteCoveringRelation[_P]

abstractmethod 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.

abstractmethod 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.

abstractmethod isdisjoint(other)#

Test if the poset is disjoint from the other.

Parameters:

other (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of values.

Returns:

True if the poset is disjoint from the other.

Return type:

bool

abstractmethod 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

abstractmethod 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

abstractmethod lower_limit(*limits, strict=False)#

Get the values greater than the limits.

Parameters:
Returns:

A collection of values.

Return type:

Collection[_P]

abstract property maximum: _P | None#

Get the maximum element if any.

Returns:

The maximum element.

Return type:

_P | None

abstract property minimum: _P | None#

Get the minimum element if any.

Returns:

The minimum element.

Return type:

_P | None

abstract property order: AbstractFinitePartialOrder[_P]#

Get the partial order of this poset.

Returns:

The partial order.

Return type:

AbstractFinitePartialOrder[_P]

abstract property top: Collection[_P]#

Get the top elements.

Returns:

The top elements.

Return type:

Collection[_P]

abstractmethod upper_limit(*limits, strict=False)#

Get the values less than the limits.

Parameters:
Returns:

A collection of values.

Return type:

Collection[_P]

abstract property version: int#

Get the poset version.

Returns:

The poset version.

Return type:

int

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:

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),
...     ]
... )
>>> poset
<galactic.algebras.poset.MutableFinitePartiallyOrderedSet object at 0x...>

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 bottom: Collection[_P]#

Get the bottom elements.

Returns:

The bottom elements.

Return type:

Collection[_P]

copy()#

Get a copy of the partially ordered set.

Returns:

The copy of this poset.

Return type:

Self

property cover: AbstractFiniteCoveringRelation[_P]#

Get the covering relation of this poset.

Returns:

The covering relation.

Return type:

AbstractFiniteCoveringRelation[_P]

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.

Returns:

The head element.

Return type:

_P | None

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(*limits, strict=False)#

Get the values greater than the limits.

Parameters:
Returns:

A collection of values.

Return type:

Collection[_P]

property maximum: _P | None#

Get the maximum element if any.

Returns:

The maximum element.

Return type:

_P | None

property minimum: _P | None#

Get the minimum element if any.

Returns:

The minimum element.

Return type:

_P | None

property order: AbstractFinitePartialOrder[_P]#

Get the partial order of this poset.

Returns:

The partial order.

Return type:

AbstractFinitePartialOrder[_P]

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.

Returns:

The tail element.

Return type:

_P | None

Raises:

KeyError – If the semi-lattice is empty.

property top: Collection[_P]#

Get the top elements.

Returns:

The top elements.

Return type:

Collection[_P]

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(*limits, strict=False)#

Get the values less than the limits.

Parameters:
Returns:

An collection of values.

Return type:

Collection[_P]

property version: int#

Get the version number.

Returns:

The version number.

Return type:

int

Notes

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

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

property bottom: Collection[_P]#

Get the bottom elements.

Returns:

The bottom elements.

Return type:

Collection[_P]

clear()#

Clear the poset.

Return type:

None

copy()#

Get a copy of the partially ordered set.

Returns:

The copy of this poset.

Return type:

Self

property cover: AbstractFiniteCoveringRelation[_P]#

Get the covering relation of this poset.

Returns:

The covering relation.

Return type:

AbstractFiniteCoveringRelation[_P]

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

difference_update(*others)#

Update a poset with the difference of itself and others.

Parameters:

*others (Iterable[Any]) – A sequence of iterable.

Return type:

None

discard(value)#

Discard a value from the poset.

Parameters:

value (TypeVar(_P, bound= PartiallyComparable)) – The value to discard.

Return type:

None

extend(iterable)#

Extend a poset with the iterable.

Parameters:

iterable (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – An iterable of values

Return type:

None

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.

Returns:

The head element.

Return type:

_P | None

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

intersection_update(*others)#

Update a poset with the intersection of itself and others.

Parameters:

*others (Iterable[Any]) – A sequence of iterable.

Return type:

None

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(*limits, strict=False)#

Get the values greater than the limits.

Parameters:
Returns:

A collection of values.

Return type:

Collection[_P]

property maximum: _P | None#

Get the maximum element if any.

Returns:

The maximum element.

Return type:

_P | None

property minimum: _P | None#

Get the minimum element if any.

Returns:

The minimum element.

Return type:

_P | None

property order: AbstractFinitePartialOrder[_P]#

Get the partial order of this poset.

Returns:

The partial order.

Return type:

AbstractFinitePartialOrder[_P]

pop()#

Remove and return the first value of the set.

Returns:

The value removed.

Return type:

_P

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

remove(value)#

Remove a value from the poset.

Parameters:

value (TypeVar(_P, bound= PartiallyComparable)) – The value to remove.

Return type:

None

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

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

property tail: _P | None#

Get the tail element if any.

Returns:

The tail element.

Return type:

_P | None

Raises:

KeyError – If the semi-lattice is empty.

property top: Collection[_P]#

Get the top elements.

Returns:

The top elements.

Return type:

Collection[_P]

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

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

upper_limit(*limits, strict=False)#

Get the values less than the limits.

Parameters:
Returns:

An collection of values.

Return type:

Collection[_P]

property version: int#

Get the version number.

Returns:

The version number.

Return type:

int

Notes

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

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

Bases: FinitePartiallyOrderedSetMixin[_P]

It represents view on partially ordered sets.

Parameters:

Notes

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

property bottom: Collection[_P]#

Get the bottom elements.

Returns:

The bottom elements.

Return type:

Collection[_P]

property cover: AbstractFiniteCoveringRelation[_P]#

Get the covering relation of this bounded set.

Returns:

The covering relation.

Return type:

AbstractFiniteCoveringRelation[_P]

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.

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(*limits, strict=False)#

Get the values greater than the limits.

Parameters:
Returns:

A collection of values.

Return type:

Collection[_P]

property maximum: _P | None#

Get the maximum element if any.

Returns:

The maximum element.

Return type:

_P | None

property minimum: _P | None#

Get the minimum element if any.

Returns:

The minimum element.

Return type:

_P | None

property order: AbstractFinitePartialOrder[_P]#

Get the partial order of this bounded set.

Returns:

The partial order.

Return type:

AbstractFinitePartialOrder[_P]

property top: Collection[_P]#

Get the top elements.

Returns:

The top elements.

Return type:

Collection[_P]

upper_limit(*limits, strict=False)#

Get the values less than the limits.

Parameters:
Returns:

An collection of values.

Return type:

Collection[_P]

property version: int#

Get the poset version.

Returns:

The poset version.

Return type:

int

Notes

This can be used to detect a change in the 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

lower_limit(*limits, strict=False)#

Get the values greater than the limits.

Parameters:
Returns:

A collection of values.

Return type:

Collection[_P]

property maximum: _P | None#

Get the maximum element if any.

Returns:

The maximum element.

Return type:

_P | None

property minimum: _P | None#

Get the minimum element if any.

Returns:

The minimum element.

Return type:

_P | None

upper_limit(*limits, strict=False)#

Get the values less than the limits.

Parameters:
Returns:

An 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:

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
abstractmethod __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

abstractmethod __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

abstractmethod __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

abstractmethod __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

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, *limits, strict=False)#

Compute an iterator over the elements greater than the limits.

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

Parameters:
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, *limits, strict=False)#

Compute an iterator over the elements lesser than the limits.

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

Parameters:
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: AbstractFiniteAntisymmetricRelation[_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.

abstractmethod 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.

Returns:

The sinks of this DAG.

Return type:

Collection[_E]

abstract property sources: Collection[_E]#

Get the sources of this DAG.

Returns:

The sources of this DAG.

Return type:

Collection[_E]

abstractmethod 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 co_domain: Collection[_P]#

Get the co-domain of this partial order.

Returns:

The co-domain of this partial order.

Return type:

Collection[_P]

Notes

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

property domain: Collection[_P]#

Get the domain.

Returns:

The domain.

Return type:

Collection[_P]

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

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.

property sinks: Collection[_P]#

Get the sink elements.

Returns:

The sink elements.

Return type:

Collection[_P]

property sources: Collection[_P]#

Get the source elements.

Returns:

The source elements.

Return type:

Collection[_P]

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.

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

Get the universes.

Returns:

The universes.

Return type:

tuple[Collection[_P], Collection[_P]]

class AbstractFiniteCoveringRelation(*args, **kwargs)#

Bases: AbstractFiniteAntisymmetricRelation[_P], Protocol[_P]

It represents a covering relation.

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.

abstractmethod 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 –

abstractmethod 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.

Returns:

The sinks of this DAG.

Return type:

Collection[_E]

abstract property sources: Collection[_E]#

Get the sources of this DAG.

Returns:

The sources of this DAG.

Return type:

Collection[_E]

abstractmethod 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 co_domain: Collection[_P]#

Get the co-domain of this covering relation.

Returns:

The co-domain of this covering relation.

Return type:

Collection[_P]

Notes

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

property domain: Collection[_P]#

Get the domain of this covering relation.

Returns:

The domain of this covering relation.

Return type:

Collection[_P]

Notes

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

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

abstractmethod 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 –

abstractmethod 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]

abstractmethod 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.

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

Get the universes of this covering relation.

Returns:

The universes of this covering relation.

Return type:

tuple[Collection[_P], Collection[_P]]

class Bottom(poset, lower, upper)#

Bases: Generic[_P]

It represents the bottom elements in a bounded set.

Parameters:
class Top(poset, lower, upper)#

Bases: Generic[_P]

It represents the top elements in a bounded set.

Parameters:

Renderers#

The galactic.algebras.poset.renderer module.

It defines classes for rendering diagrams:

class HasseDiagram(poset, graph_renderer=None, domain_renderer=None, edge_renderer=None, reverse=False)#

Bases: Generic[_P]

It is used for drawing Hasse diagrams.

Parameters:
property domain_renderer: NodeRenderer[_P, _P]#

Get the domain renderer.

Return type:

The domain renderer.

property edge_renderer: EdgeRenderer[_P, _P]#

Get the edge renderer.

Return type:

The edge renderer.

property graph_renderer: HasseDiagramRenderer[_P]#

Get the Hasse diagram renderer.

Return type:

The Hasse diagram renderer.

pipe(output='svg')#

Pipe the diagram.

Parameters:

output (str, default: 'svg') – The format used

Returns:

The image of the diagram.

Return type:

bytes

property poset: AbstractFinitePartiallyOrderedSet[_P]#

Get the poset.

Return type:

The underlying poset.

render(filename)#

Render the diagram in a file.

Parameters:

filename (str) – A file path.

Return type:

None

property source: str#

Get the graphviz source for this partially ordered set.

Return type:

The graphviz output for this partially ordered set.

class DynamicDiagram(graph_renderer=None, domain_renderer=None, edge_renderer=None)#

Bases: Generic[_P]

It is designed to allow dynamic graph rendering.

Parameters:
property body: Sequence[str]#

Get the current graphviz body.

Return type:

The current body.

finish()#

Finish the iteration.

Return type:

None

pipe(output='svg')#

Pipe the diagram.

Parameters:

output (str, default: 'svg') – The format used

Returns:

The image of the diagram.

Return type:

bytes

render(filename)#

Render the diagram in a file.

Parameters:

filename (str) – A file path.

Return type:

None

property source: str#

Get the graphviz source for this diagram.

Return type:

The graphviz output for this diagram.

start()#

Start a new iteration.

Return type:

None

step(element, successors, predecessors)#

Insert a new element in the diagram.

Parameters:
Return type:

None

class IterativeDiagram(poset, graph_renderer=None, domain_renderer=None, edge_renderer=None)#

Bases: Iterable[DynamicDiagram[_P]]

It allows iterative rendering.

Parameters:
class HasseDiagramRenderer#

Bases: GraphRenderer[_P, _P]

It renders graph attributes.

Notes

See http://www.graphviz.org/doc/info/attrs.html.

add_destination(element, index=None, current=False, successors=None, predecessors=None)#

Add a destination to the graph.

Parameters:

  • element (TypeVar(_F)) – The destination to add.

  • index (int | None, default: None) – The destination index.

  • current (bool, default: False) – Is it the current element?

  • successors (Collection[TypeVar(_E)] | None, default: None) – The successors of the destination.

  • predecessors (Collection[TypeVar(_E)] | None, default: None) – The predecessors of the destination.

Return type:

None

add_edge(source, destination, successors=None, predecessors=None)#

Add an edge to the graph.

Parameters:

  • source (TypeVar(_E)) – The edge source

  • destination (TypeVar(_F)) – The edge destination

  • successors (Collection[TypeVar(_F)] | None, default: None) – The successors of source (including current destination).

  • predecessors (Collection[TypeVar(_E)] | None, default: None) – The predecessors of destination (including current source).

Return type:

None

add_source(element, index=None, current=False, successors=None, predecessors=None)#

Add a source to the graph.

Parameters:

  • element (TypeVar(_E)) – The source to add.

  • index (int | None, default: None) – The source index.

  • current (bool, default: False) – Is it the current element?

  • successors (Collection[TypeVar(_F)] | None, default: None) – The successors of the source.

  • predecessors (Collection[TypeVar(_F)] | None, default: None) – The predecessors of the source.

Return type:

None

attributes()#

Return a dictionary of graphviz attributes for a Hasse diagram.

Return type:

dict[str, str]

Returns:

A dictionary of graphviz attributes

Contents