galactic.algebras.poset.core

Contents

galactic.algebras.poset.core#

Defines core classes and functions for partially ordered sets (posets).

Protocols

Classes for posets

Functions and classes on partially comparable elements

Classes representing the underlying order relation

Mixins

class PartiallyComparable(*args, **kwargs)#

Bases: Hashable, Protocol

Represents elements that are partially comparable.

In a partially ordered type, for each pair of elements \(a\), \(b\), one of the following holds:

  • \(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 implement the following methods:

Notes

The builtin classes

are considered as subclasses of PartiallyComparable.

Example

Consider subset of integers ordered by the relation \(a \leq b\) if \(a\) is a subset of \(b\):

>>> frozenset([5]) <= frozenset([2, 5])
True
>>> frozenset([5]) <= frozenset([11])
False
>>> frozenset([11]) <= frozenset([5])
False
__lt__(other)#

Check if self is less than other.

Parameters:

other (object) – The other element to compare with

Returns:

True if self is less than other

Return type:

bool

Notes

In a partial order, this means self <= other and self != other. It returns False if the elements are incomparable (which is the default of the PartialllyComparable class).

__gt__(other)#

Check if self is greater than other.

Parameters:

other (object) – The other element to compare with

Returns:

True if self is greater than other

Return type:

bool

Notes

In a partial order, this means self >= other and self != other. It returns False if the elements are incomparable (which is the default of the PartialllyComparable class).

__le__(other)#

Check if self is less than or equal to other.

Parameters:

other (object) – The other element to compare with

Returns:

True if self is less than or equal to other.

Return type:

bool

__ge__(other)#

Check if self is greater than or equal to other.

Parameters:

other (object) – The other element to compare with

Returns:

True if self is greater than or equal to other.

Return type:

bool

class PartiallyOrderedSet(*args, **kwargs)#

Bases: Collection[_P], Protocol

Represents a partially ordered set (poset).

A poset is a set of elements equipped with a partial order relation that defines how the elements are related to each other.

Notes

The poset supports various operations such as checking for disjointness, subset and superset relations, and retrieving upper and lower limits of elements. It also provides methods to access the top and bottom elements, as well as the maximum and minimum elements if they exist. The poset can be filtered to create a view bounded by a lower or upper element, and it maintains a version number to track changes in the poset.

abstract property version: int#

Get the version of the poset.

Returns:

The version number

Return type:

int

Notes

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

__eq__(other)#

Check if the poset is equal to another poset.

Parameters:

other (object) – Another poset to compare with

Returns:

True if the posets are equal

Return type:

bool

__bool__()#

Check if the poset is non-empty.

Returns:

True if the poset is non-empty, False otherwise

Return type:

bool

__lt__(other)#

Check if the poset is less than another poset.

Parameters:

other (object) – Another poset to compare with

Returns:

True if the poset is less than the other poset

Return type:

bool

Notes

If other is not an instance of Collection, this method returns NotImplemented.

__gt__(other)#

Check if the poset is greater than another poset.

Parameters:

other (object) – Another poset to compare with

Returns:

True if the poset is greater than the other poset

Return type:

bool

Notes

If other is not an instance of Collection, this method returns NotImplemented.

__le__(other)#

Check if the poset is less than or equal to another poset.

Parameters:

other (object) – Another poset to compare with

Returns:

True if the poset is less than or equal to the other poset

Return type:

bool

Notes

If other is not an instance of Collection, this method returns NotImplemented.

__ge__(other)#

Check if the poset is greater than or equal to another poset.

Parameters:

other (object) – Another poset to compare with

Returns:

True if the poset is greater than or equal to the other poset

Return type:

bool

Notes

If other is not an instance of Collection, this method returns NotImplemented.

isdisjoint(other)#

Check if the poset is disjoint from another iterable.

Parameters:

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

Returns:

True if the poset and the other iterable have no elements in common

Return type:

bool

issubset(other)#

Check whether every element in the poset is in the other iterable.

Parameters:

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

Returns:

True if the poset is a subset of the other iterable

Return type:

bool

issuperset(other)#

Check whether every element in the other iterable is in the poset.

Parameters:

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

Returns:

True if the poset is a superset of the other iterable

Return type:

bool

abstract property top: Collection[_P]#

Get the top elements of the poset.

Returns:

The top elements

Return type:

Collection[_P]

property maximum: _P | None#

Get the maximum element of the poset, if it exists.

Returns:

The maximum element, or None if there is not a unique maximum

Return type:

_P | None

abstract property bottom: Collection[_P]#

Get the bottom elements of the poset.

Returns:

The bottom elements

Return type:

Collection[_P]

property minimum: _P | None#

Get the minimum element of the poset, if it exists.

Returns:

The minimum element, or None if there is not a unique minimum

Return type:

_P | None

abstractmethod filter(elem)#

Return the filter of the poset with the given lower bound.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The lower bound element

Returns:

A view of the poset bounded below by the element

Return type:

PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset.

Notes

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

abstractmethod ideal(elem)#

Return the ideal of the poset with the given upper bound.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The upper bound element

Returns:

A view of the poset bounded above by the element

Return type:

PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset.

Notes

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

upper_limit(*limits, strict=False)#

Return the elements less than the given limits.

Parameters:

  • *limits (TypeVar(_P, bound= PartiallyComparable)) – The limit elements

  • strict (bool, default: False) – If True, only strictly less elements are returned

Returns:

A collection of elements less than the limits

Return type:

Collection[TypeVar(_P, bound= PartiallyComparable)]

lower_limit(*limits, strict=False)#

Return the elements greater than the given limits.

Parameters:

  • *limits (TypeVar(_P, bound= PartiallyComparable)) – The limit elements.

  • strict (bool, default: False) – If True, only strictly greater elements are returned

Returns:

A collection of elements greater than the limits

Return type:

Collection[TypeVar(_P, bound= PartiallyComparable)]

abstract property order: Ordering[_P]#

Get the partial order of the poset.

Returns:

The partial order

Return type:

Ordering[_P]

abstract property cover: Ordering[_P]#

Get the covering relation of the poset.

Returns:

The covering relation

Return type:

Ordering[_P]

class Ordering(*args, **kwargs)#

Bases: EndoRelation[_P], Protocol

Represents either a partial order or a covering relation.

It is an endo-relation that satisfies the properties of antisymmetry, and:

  • transitivity and reflexivity for partial orders

  • non-transitivity and irreflexivity for covering relations

It can be represented as a directed acyclic graph (DAG).

A directed acyclic graph is a finite directed graph that has no cycles, meaning there is no way to start at a vertex and return to it by following directed edges. In a DAG, the edges represent relationships between vertices, and the absence of cycles ensures that there is a partial ordering among the vertices. DAGs are commonly used to represent dependencies, such as task scheduling, version control systems, and data processing pipelines, where the direction of the edges indicates the flow of information or control from one vertex to another.

See https://en.wikipedia.org/wiki/Order_theory

abstract property sinks: Collection[_P]#

Get the sinks of this ordering.

Returns:

The sinks of this ordering

Return type:

Collection[_E]

abstract property sources: Collection[_P]#

Get the sources of this ordering.

Returns:

The sources of this ordering

Return type:

Collection[_E]

class FrozenPartiallyOrderedSet(*elements)#

Bases: PartiallyOrderedSet[_P]

Implements partially ordered sets (posets).

The initializer accepts zero or more arguments, each being an iterable.

Instances store their elements in two dictionaries: one for immediate successors (\(\succ\)) and one for immediate predecessors (\(\prec\)).

Memory complexity is \(O(n)\).

Operation complexities:

Parameters:

*elements (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – The elements of the poset

Example

>>> from galactic.algebras.poset.core import MutablePartiallyOrderedSet
>>> from pprint import pprint
>>> poset = MutablePartiallyOrderedSet[frozenset[int]](
...     [
...         frozenset([2, 3, 5, 7]),
...         frozenset([3, 5, 7, 11]),
...         frozenset([3, 5, 7]),
...         frozenset([3, 5]),
...         frozenset([5]),
...         frozenset([7]),
...     ]
... )
>>> poset
<galactic.algebras.poset.core.MutablePartiallyOrderedSet object at 0x...>

You can iterate over the poset elements. The iteration proceeds level by level, starting from the top elements.

Example

>>> pprint(list(poset))
[frozenset({3, 5, 7}),
 frozenset({3, 5}),
 frozenset({5}),
 frozenset({7}),
 frozenset({2, 3, 5, 7}),
 frozenset({11, 3, 5, 7})]

You can get the length of the poset.

Example

>>> len(poset)
6

You can check if an element is in the poset.

Example

>>> frozenset([2, 3, 5, 7]) in poset
True
>>> frozenset([2, 3, 5, 13]) in poset
False

You can iterate over the top and bottom elements.

Example

>>> pprint(list(poset.top))
[frozenset({11, 3, 5, 7}), frozenset({2, 3, 5, 7})]
>>> pprint(list(poset.bottom))
[frozenset({5}), frozenset({7})]

You can iterate over the descendants and ascendants of an element.

Example

>>> pprint(list(poset.filter(frozenset([3, 5, 7]))))
[frozenset({3, 5, 7}), frozenset({2, 3, 5, 7}), frozenset({11, 3, 5, 7})]
>>> pprint(list(poset.ideal(frozenset([3, 5, 7]))))
[frozenset({3, 5, 7}), frozenset({3, 5}), frozenset({5}), frozenset({7})]

You can iterate over the (immediate) successors and (immediate) predecessors of an element.

Example

>>> pprint(list(poset.cover.successors(frozenset([3, 5, 7]))))
[frozenset({2, 3, 5, 7}), frozenset({11, 3, 5, 7})]
>>> pprint(list(poset.order.successors(frozenset([3, 5, 7]))))
[frozenset({3, 5, 7}), frozenset({2, 3, 5, 7}), frozenset({11, 3, 5, 7})]
>>> pprint(list(poset.cover.predecessors(frozenset([3, 5, 7]))))
[frozenset({3, 5}), frozenset({7})]
>>> pprint(list(poset.order.predecessors(frozenset([3, 5, 7]))))
[frozenset({3, 5, 7}), frozenset({3, 5}), frozenset({5}), frozenset({7})]

You can enlarge a partially ordered set.

Example

>>> poset.update([frozenset([13])])
>>> pprint(list(poset))
[frozenset({3, 5, 7}),
 frozenset({3, 5}),
 frozenset({5}),
 frozenset({7}),
 frozenset({2, 3, 5, 7}),
 frozenset({11, 3, 5, 7}),
 frozenset({13})]
property version: int#

Get the version number of the poset.

Returns:

The version number

Return type:

int

Notes

This can be used to detect changes in the poset.

__hash__()#

Get the hash value of the poset.

Returns:

The hash value

Return type:

int

Notes

The hash value is cached after the first computation.

__copy__()#

Create a shallow copy of the poset.

Returns:

A shallow copy of this poset

Return type:

Self

copy()#

Return a copy of the poset.

Returns:

A copy of this poset

Return type:

Self

__contains__(elem)#

Check if an element is in the poset.

Parameters:

elem (object) – The element to check

Returns:

True if the element is in the poset, False otherwise

Return type:

bool

__iter__()#

Iterate over the elements in the poset.

Returns:

An iterator over the elements in the poset

Return type:

Iterator[TypeVar(_P, bound= PartiallyComparable)]

__len__()#

Get the number of elements in the poset.

Returns:

The number of elements in the poset

Return type:

int

__or__(other)#

Compute the union of the poset and another collection.

Parameters:

other (object) – Another collection to unite with

Returns:

The union of the poset and the other collection

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

__and__(other)#

Compute the intersection of the poset and another collection.

Parameters:

other (object) – Another collection to intersect with

Returns:

The intersection of the poset and the other collection

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

__sub__(other)#

Compute the difference between the poset and another collection.

Parameters:

other (object) – Another collection to subtract

Returns:

The difference between the poset and the other collection

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

__xor__(other)#

Compute the symmetric difference between the poset and another collection.

Parameters:

other (object) – Another collection to compute the symmetric difference with

Returns:

The symmetric difference between the poset and the other collection

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

union(*others)#

Compute the union of the poset and the given iterables.

Parameters:

*others (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – A sequence of iterables

Returns:

The union of the poset and the others

Return type:

Self

intersection(*others)#

Compute the intersection of the poset and the given iterables.

Parameters:

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

Returns:

The intersection of the poset and the others

Return type:

Self

difference(*others)#

Compute the difference between the poset and the given iterables.

Parameters:

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

Returns:

The difference between the poset and the others

Return type:

Self

symmetric_difference(other)#

Compute the symmetric difference between the poset and the given iterable.

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

Get the partial order of this poset.

Returns:

The partial order

Return type:

Ordering[_P]

property cover: Ordering[_P]#

Get the covering relation of this poset.

Returns:

The covering relation

Return type:

Ordering[_P]

property top: Collection[_P]#

Get the top elements of the poset.

Returns:

The top elements

Return type:

Collection[_P]

property tail: _P | None#

Returns the tail element, if any.

Returns:

The tail element

Return type:

_P | None

Raises:

KeyError – If the poset is empty

property bottom: Collection[_P]#

Get the bottom elements of the poset.

Returns:

The bottom elements

Return type:

Collection[_P]

property head: _P | None#

Get the head element, if any.

Returns:

The head element

Return type:

_P | None

Raises:

KeyError – If the poset is empty

filter(elem)#

Return a filter of the poset with the given lower bound.

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

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The lower bound

Returns:

A view of the poset bounded below by the element

Return type:

PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset

Notes

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

ideal(elem)#

Return an ideal of the poset with the given upper bound.

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

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The upper bound

Returns:

A view of the poset bounded above by the element

Return type:

PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset

Notes

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

class MutablePartiallyOrderedSet(*elements)#

Bases: FrozenPartiallyOrderedSet[_P]

Implements mutable posets.

add(elem)#

Add an element to the poset.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The element to add

Return type:

None

remove(elem)#

Remove an element from the poset.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The element to remove

Return type:

None

discard(elem)#

Discard an element from the poset.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The element to discard

Return type:

None

pop()#

Remove and return the first element of the poset.

Returns:

The removed element

Return type:

TypeVar(_P, bound= PartiallyComparable)

popitem(last=False)#

Remove and return the first element of the poset.

Parameters:

last (bool, default: False) – If True, removes from the end; otherwise, from the beginning

Returns:

The removed element

Return type:

TypeVar(_P, bound= PartiallyComparable)

clear()#

Remove all elements from the poset.

Return type:

None

__ior__(other)#

Perform in-place union with another collection.

Parameters:

other (object) – Another collection to unite with

Returns:

The updated poset

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

__iand__(other)#

Perform in-place intersection with another collection.

Parameters:

other (object) – Another collection to intersect with

Returns:

The updated poset

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

__isub__(other)#

Perform in-place difference with another collection.

Parameters:

other (object) – Another collection to subtract

Returns:

The updated poset

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

__ixor__(other)#

Perform in-place symmetric difference with another collection.

Parameters:

other (object) – Another collection to compute the symmetric difference with

Returns:

The updated poset

Return type:

Self

Notes

If other is not an instance of Iterable, this method returns NotImplemented.

extend(iterable)#

Extend the poset with elements from the iterable.

Parameters:

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

Return type:

None

update(*others)#

Update the poset with the union of itself and the given iterables.

Parameters:

*others (Iterable[TypeVar(_P, bound= PartiallyComparable)]) – A sequence of iterables

Return type:

None

intersection_update(*others)#

Update the poset with the intersection of itself and the given iterables.

Parameters:

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

Return type:

None

difference_update(*others)#

Update the poset with the difference of itself and the given iterables.

Parameters:

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

Return type:

None

symmetric_difference_update(other)#

Update the poset with the symmetric difference of itself and the given iterable.

Parameters:

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

Return type:

None

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

Bases: PartiallyOrderedSet[_P]

Represents a view on a partially ordered set (poset).

This view is bounded by a lower and an upper limit, which can be None to indicate no bound in that direction. The view provides access to the underlying poset’s elements, covering relation, and partial order, while filtering the elements based on the specified bounds.

Parameters:

Notes

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

property version: int#

Get the version of the underlying poset.

Returns:

The version number

Return type:

int

Notes

This can be used to detect changes in the poset.

__bool__()#

Check if the bounded set is non-empty.

Returns:

True if the bounded set is non-empty, False otherwise

Return type:

bool

__contains__(elem)#

Check if an element belongs to the bounded set.

Parameters:

elem (object) – The element to check

Returns:

True if the element belongs to the bounded set, False otherwise

Return type:

bool

__iter__()#

Iterate over the elements in the bounded set.

Returns:

An iterator over the elements in the bounded set

Return type:

Iterator[TypeVar(_P, bound= PartiallyComparable)]

__len__()#

Get the number of elements in the bounded set.

Returns:

The number of elements in the bounded set

Return type:

int

property order: Ordering[_P]#

Get the partial order of this bounded set.

Returns:

The partial order

Return type:

Ordering[_P]

property cover: Ordering[_P]#

Get the covering relation of this bounded set.

Returns:

The covering relation

Return type:

Ordering[_P]

property top: Collection[_P]#

Get the top elements of the bounded set.

Returns:

The top elements

Return type:

Collection[_P]

property bottom: Collection[_P]#

Returns the bottom elements of the bounded set.

Returns:

The bottom elements

Return type:

Collection[_P]

filter(elem)#

Return a filter view of the bounded set with the given lower bound.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The lower bound

Returns:

A view of the poset bounded below by the element

Return type:

PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset

Notes

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

ideal(elem)#

Return an ideal view of the bounded set with the given upper bound.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The upper bound

Returns:

A view of the poset bounded above by the element

Return type:

PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset

Notes

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

bottom(iterable)#

Compute an iterator over the bottom elements of the iterable.

This operation runs 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[TypeVar(_P, bound= PartiallyComparable)]

Example

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

Compute an iterator over the top elements of the iterable.

This operation runs 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[TypeVar(_P, bound= PartiallyComparable)]

Example

>>> from galactic.algebras.poset.core import top
>>> values = [
...     frozenset([1, 2, 3]),
...     frozenset([1, 2, 3, 4]),
...     frozenset([2, 3, 4, 5]),
... ]
>>> list(top(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 runs in \(O(n)\) where \(n\) is the number of elements in the iterable.

Parameters:
Yields:

_P – A selected element

Example

>>> from galactic.algebras.poset.core import lower_limit
>>> values = [
...     frozenset([1, 2]),
...     frozenset([1, 2, 3]),
...     frozenset([2, 3]),
... ]
>>> list(lower_limit(values, frozenset([2, 3])))
[frozenset({1, 2, 3}), frozenset({2, 3})]
upper_limit(iterable, *limits, strict=False)#

Compute an iterator over the elements less than the given limits.

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

Parameters:
Yields:

_P – A selected element

Example

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

Bases: BinaryRelation[_P, _P]

Represents a partial order.

A partial order is a binary relation that is reflexive, antisymmetric, and transitive. It can be represented by a set of ordered pairs, where each pair indicates that one element is less than or equal to another. In a poset, some elements are comparable and others are not. If a <= b and b <= c, then by transitivity a <= c; otherwise elements may be incomparable.

Parameters:

poset (PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – The underlying poset

Notes

The domain and co-domain of a partial order are identical, so they are represented as a single universe.

__bool__()#

Check if the partial order is non-empty.

Returns:

True if the partial order is non-empty, False otherwise

Return type:

bool

__contains__(pair)#

Check if a pair belongs to the partial order.

Parameters:

pair (object) – The pair to check

Returns:

True if the pair belongs to the partial order, False otherwise

Return type:

bool

__iter__()#

Iterate over the pairs in the partial order.

Returns:

An iterator over the pairs in the partial order

Return type:

Iterator[tuple[TypeVar(_P, bound= PartiallyComparable), TypeVar(_P, bound= PartiallyComparable)]]

__len__()#

Get the length of the partial order.

Returns:

The length of the partial order

Return type:

int

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

Get the universes of the partial order.

Returns:

The universes

Return type:

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

property domain: Collection[_P]#

Get the domain of the partial order.

Returns:

The domain

Return type:

Collection[_P]

property co_domain: Collection[_P]#

Get the co-domain of the partial order.

Returns:

The co-domain

Return type:

Collection[_P]

Notes

The domain and codomain of a partial order are identical.

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]

successors(elem)#

Return the successors of an element.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The element whose successors are requested

Returns:

The successors of the element

Return type:

Collection[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset

predecessors(elem)#

Return the predecessors of an element.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The element whose predecessors are requested

Returns:

The predecessors of the element

Return type:

Collection[TypeVar(_P, bound= PartiallyComparable)]

Raises:

ValueError – If the element does not belong to the poset

class CoveringRelationMixin(poset)#

Bases: BinaryRelation[_P, _P], ABC

Mixin for covering relations.

Parameters:

poset (PartiallyOrderedSet[TypeVar(_P, bound= PartiallyComparable)]) – The underlying poset

__bool__()#

Check if the covering relation is non-empty.

Returns:

True if the covering relation is non-empty, False otherwise

Return type:

bool

__contains__(pair)#

Check if a pair belongs to the covering relation.

Parameters:

pair (object) – The pair to check

Returns:

True if the pair belongs to the covering relation, False otherwise

Return type:

bool

__iter__()#

Iterate over the pairs in the covering relation.

Returns:

An iterator over the pairs in the covering relation

Return type:

Iterator[tuple[TypeVar(_P, bound= PartiallyComparable), TypeVar(_P, bound= PartiallyComparable)]]

__len__()#

Get the length of the covering relation.

Returns:

The length of the covering relation

Return type:

int

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

Get the universes of the covering relation.

Returns:

The universes of the covering relation

Return type:

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

property domain: Collection[_P]#

Get the domain of the covering relation.

Returns:

The domain of the covering relation

Return type:

Collection[_P]

Notes

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

property co_domain: Collection[_P]#

Get the co-domain of the covering relation.

Returns:

The co-domain of the covering relation

Return type:

Collection[_P]

Notes

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

abstractmethod successors(elem)#

Return the successors of an element.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The element whose successors are requested

Returns:

The successors of the element

Return type:

Collection[TypeVar(_P, bound= PartiallyComparable)]

abstractmethod predecessors(elem)#

Return the predecessors of an element.

Parameters:

elem (TypeVar(_P, bound= PartiallyComparable)) – The element whose predecessors are requested

Returns:

The predecessors of the element

Return type:

Collection[TypeVar(_P, bound= PartiallyComparable)]

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]

class Bottom(poset, *, lower, upper)#

Bases: Collection[_P]

Represents a view on the bottom elements in a bounded poset.

Parameters:
__bool__()#

Check if the collection is non-empty.

Returns:

True if the collection is non-empty, False otherwise

Return type:

bool

__contains__(elem)#

Check if an element belongs to the collection.

Parameters:

elem (object) – The element to check

Returns:

True if the element belongs to the collection, False otherwise

Return type:

bool

__iter__()#

Iterate over the elements in the collection.

Returns:

An iterator over the elements in the collection

Return type:

Iterator[TypeVar(_P, bound= PartiallyComparable)]

__len__()#

Get the number of elements in the collection.

Returns:

The number of elements in the collection

Return type:

int

class Top(poset, *, lower, upper)#

Bases: Collection[_P]

Represents a view on the top elements in a bounded poset.

Parameters:
__bool__()#

Check if the collection is non-empty.

Returns:

True if the collection is non-empty, False otherwise

Return type:

bool

__contains__(elem)#

Check if an element belongs to the collection.

Parameters:

elem (object) – The element to check

Returns:

True if the element belongs to the collection, False otherwise

Return type:

bool

__iter__()#

Iterate over the elements in the collection.

Returns:

An iterator over the elements in the collection

Return type:

Iterator[TypeVar(_P, bound= PartiallyComparable)]

__len__()#

Get the number of elements in the collection.

Returns:

The number of elements in the collection

Return type:

int

Contents