Posets

abstract neighbours() → Iterable[Tuple[galactic.algebras.poset._abstract._P, AbstractSet[galactic.algebras.poset._abstract._P], AbstractSet[galactic.algebras.poset._abstract._P]]]

Get an iterable over the neighbours of elements.

Each iteration yields a triple element, successors(element), predecessors(element).

Returns:
Return type:: Iterable[Tuple[_P, AbstractSet[_P], AbstractSet[_P]]]

abstract predecessors(element: galactic.algebras.relational._binary._F) → AbstractSet[galactic.algebras.relational._binary._E]

Get the predecessors of an element.

Parameters:: element (_F) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_E]
Raises:: ValueError – If the element does not belong to the relation.

abstract property sinks: AbstractSet[galactic.algebras.poset._abstract._P]

Get the elements with no successors.

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

abstract property sources: AbstractSet[galactic.algebras.poset._abstract._P]

Get the elements with no predecessors.

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

abstract successors(element: galactic.algebras.relational._binary._E) → AbstractSet[galactic.algebras.relational._binary._F]

Get the successors of an element.

Parameters:: element (_E) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_F]
Raises:: ValueError – If the element does not belong to the relation.

abstract property universes: Tuple[AbstractSet[galactic.algebras.relational._binary._E], AbstractSet[galactic.algebras.relational._binary._F]]

Get the universes of this relation.

Returns:: The universes of this relation.
Return type:: Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractReversibleCoveringRelation(*args, **kwds)

The AbstractReversibleCoveringRelation class.

It represents a reversible version of the covering relation of a poset.

property co_domain: AbstractSet[galactic.algebras.relational._binary._F]

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns:: The co-domain of this binary relation.
Return type:: AbstractSet[_F]

property domain: AbstractSet[galactic.algebras.relational._binary._E]

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns:: The domain of this binary relation.
Return type:: AbstractSet[_E]

isdisjoint(other): Return True if two sets have a null intersection.

abstract neighbours() → Reversible[Tuple[galactic.algebras.poset._abstract._P, AbstractSet[galactic.algebras.poset._abstract._P], AbstractSet[galactic.algebras.poset._abstract._P]]]

Get a reversible iterable over the neighbours of elements.

Each iteration yields a triple element, successors(element), predecessors(element).

Returns:
Return type:: Reversible[Tuple[_P, AbstractSet[_P], AbstractSet[_P]]]

abstract predecessors(element: galactic.algebras.relational._binary._F) → AbstractSet[galactic.algebras.relational._binary._E]

Get the predecessors of an element.

Parameters:: element (_F) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_E]
Raises:: ValueError – If the element does not belong to the relation.

abstract property sinks: AbstractSet[galactic.algebras.poset._abstract._P]

Get the elements with no successors.

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

abstract property sources: AbstractSet[galactic.algebras.poset._abstract._P]

Get the elements with no predecessors.

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

abstract successors(element: galactic.algebras.relational._binary._E) → AbstractSet[galactic.algebras.relational._binary._F]

Get the successors of an element.

Parameters:: element (_E) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_F]
Raises:: ValueError – If the element does not belong to the relation.

abstract property universes: Tuple[AbstractSet[galactic.algebras.relational._binary._E], AbstractSet[galactic.algebras.relational._binary._F]]

Get the universes of this relation.

Returns:: The universes of this relation.
Return type:: Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractPartiallyOrderedSet(*args, **kwds)

The :class`AbstractPartiallyOrderedSet` abstract class.

A partially ordered set is an endo-relation over a set of PartiallyComparable elements.

__contains__(item: Any) → bool

Get the membership of an element.

Parameters:: item – The element whose membership is requested.
Returns:: True if the item belongs to the partially ordered set.
Return type:: bool

__iter__() → Iterator[Tuple[galactic.algebras.poset._abstract._P, galactic.algebras.poset._abstract._P]]

Get an iterator over the elements.

Returns:: An iterator over the elements
Return type:: Iterator[Tuple[_P, _P]]

abstract property bottom: AbstractSet[galactic.algebras.poset._abstract._P]

Get the bottom elements.

Returns:: The bottom elements.
Return type:: AbstractSet[_P]

property co_domain: AbstractSet[galactic.algebras.relational._binary._F]

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns:: The co-domain of this binary relation.
Return type:: AbstractSet[_F]

abstract property cover: galactic.algebras.poset.AbstractCoveringRelation[galactic.algebras.poset._abstract._P]

Get the covering relation.

Returns:: The covering relation.
Return type:: AbstractCoveringRelation[_P]

property domain: AbstractSet[galactic.algebras.relational._binary._E]

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns:: The domain of this binary relation.
Return type:: AbstractSet[_E]

abstract filter(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractLowerBoundedSet[galactic.algebras.poset._abstract._P]

Get a filter of a poset.

Parameters:: element (_P) – The lower limit
Returns:: The lower bounded poset.
Return type:: AbstractLowerBoundedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

abstract ideal(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractUpperBoundedSet[galactic.algebras.poset._abstract._P]

Get an ideal of the poset.

Parameters:: element (_P) – The upper limit
Returns:: The upper bounded set.
Return type:: AbstractUpperBoundedSet[_P]

isdisjoint(other): Return True if two sets have a null intersection.

abstract predecessors(element: galactic.algebras.relational._binary._F) → AbstractSet[galactic.algebras.relational._binary._E]

Get the predecessors of an element.

Parameters:: element (_F) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_E]
Raises:: ValueError – If the element does not belong to the relation.

abstract property sinks: AbstractSet[galactic.algebras.relational._binary._E]

Get the sinks of this DAG.

Returns:: The sinks of this DAG.
Return type:: AbstractSet[_E]

abstract property sources: AbstractSet[galactic.algebras.relational._binary._E]

Get the sources of this DAG.

Returns:: The sources of this DAG.
Return type:: AbstractSet[_E]

abstract successors(element: galactic.algebras.relational._binary._E) → AbstractSet[galactic.algebras.relational._binary._F]

Get the successors of an element.

Parameters:: element (_E) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_F]
Raises:: ValueError – If the element does not belong to the relation.

abstract property top: AbstractSet[galactic.algebras.poset._abstract._P]

Get the top elements.

Returns:: The top elements.
Return type:: AbstractSet[_P]

abstract property universes: Tuple[AbstractSet[galactic.algebras.relational._binary._E], AbstractSet[galactic.algebras.relational._binary._F]]

Get the universes of this relation.

Returns:: The universes of this relation.
Return type:: Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractUpperBoundedSet(*args, **kwds)

The AbstractUpperBoundedSet represents upper bounded posets.

__contains__(item: Any) → bool

Get the membership of an element.

Parameters:: item – The element whose membership is requested.
Returns:: True if the item belongs to the partially ordered set.
Return type:: bool

__iter__() → Iterator[Tuple[galactic.algebras.poset._abstract._P, galactic.algebras.poset._abstract._P]]

Get an iterator over the elements.

Returns:: An iterator over the elements
Return type:: Iterator[Tuple[_P, _P]]

abstract property bottom: AbstractSet[galactic.algebras.poset._abstract._P]

Get the bottom elements.

Returns:: The bottom elements.
Return type:: AbstractSet[_P]

property co_domain: AbstractSet[galactic.algebras.relational._binary._F]

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns:: The co-domain of this binary relation.
Return type:: AbstractSet[_F]

abstract property cover: galactic.algebras.poset.AbstractCoveringRelation[galactic.algebras.poset._abstract._P]

Get the covering relation.

Returns:: The covering relation.
Return type:: AbstractCoveringRelation[_P]

property domain: AbstractSet[galactic.algebras.relational._binary._E]

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns:: The domain of this binary relation.
Return type:: AbstractSet[_E]

abstract filter(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractLowerBoundedSet[galactic.algebras.poset._abstract._P]

Get a filter of a poset.

Parameters:: element (_P) – The lower limit
Returns:: The lower bounded poset.
Return type:: AbstractLowerBoundedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

abstract ideal(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractUpperBoundedSet[galactic.algebras.poset._abstract._P]

Get an ideal of the poset.

Parameters:: element (_P) – The upper limit
Returns:: The upper bounded set.
Return type:: AbstractUpperBoundedSet[_P]

isdisjoint(other): Return True if two sets have a null intersection.

abstract property maximum: galactic.algebras.poset._abstract._P

Get the maximum of the poset.

Returns:: The maximum element.
Return type:: _P

abstract predecessors(element: galactic.algebras.relational._binary._F) → AbstractSet[galactic.algebras.relational._binary._E]

Get the predecessors of an element.

Parameters:: element (_F) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_E]
Raises:: ValueError – If the element does not belong to the relation.

abstract property sinks: AbstractSet[galactic.algebras.relational._binary._E]

Get the sinks of this DAG.

Returns:: The sinks of this DAG.
Return type:: AbstractSet[_E]

abstract property sources: AbstractSet[galactic.algebras.relational._binary._E]

Get the sources of this DAG.

Returns:: The sources of this DAG.
Return type:: AbstractSet[_E]

abstract successors(element: galactic.algebras.relational._binary._E) → AbstractSet[galactic.algebras.relational._binary._F]

Get the successors of an element.

Parameters:: element (_E) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_F]
Raises:: ValueError – If the element does not belong to the relation.

abstract property top: AbstractSet[galactic.algebras.poset._abstract._P]

Get the top elements.

Returns:: The top elements.
Return type:: AbstractSet[_P]

abstract property universes: Tuple[AbstractSet[galactic.algebras.relational._binary._E], AbstractSet[galactic.algebras.relational._binary._F]]

Get the universes of this relation.

Returns:: The universes of this relation.
Return type:: Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractLowerBoundedSet(*args, **kwds)

The AbstractLowerBoundedSet represents lower bounded posets.

__contains__(item: Any) → bool

Get the membership of an element.

Parameters:: item – The element whose membership is requested.
Returns:: True if the item belongs to the partially ordered set.
Return type:: bool

__iter__() → Iterator[Tuple[galactic.algebras.poset._abstract._P, galactic.algebras.poset._abstract._P]]

Get an iterator over the elements.

Returns:: An iterator over the elements
Return type:: Iterator[Tuple[_P, _P]]

abstract property bottom: AbstractSet[galactic.algebras.poset._abstract._P]

Get the bottom elements.

Returns:: The bottom elements.
Return type:: AbstractSet[_P]

property co_domain: AbstractSet[galactic.algebras.relational._binary._F]

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns:: The co-domain of this binary relation.
Return type:: AbstractSet[_F]

abstract property cover: galactic.algebras.poset.AbstractCoveringRelation[galactic.algebras.poset._abstract._P]

Get the covering relation.

Returns:: The covering relation.
Return type:: AbstractCoveringRelation[_P]

property domain: AbstractSet[galactic.algebras.relational._binary._E]

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns:: The domain of this binary relation.
Return type:: AbstractSet[_E]

abstract filter(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractLowerBoundedSet[galactic.algebras.poset._abstract._P]

Get a filter of a poset.

Parameters:: element (_P) – The lower limit
Returns:: The lower bounded poset.
Return type:: AbstractLowerBoundedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

abstract ideal(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractUpperBoundedSet[galactic.algebras.poset._abstract._P]

Get an ideal of the poset.

Parameters:: element (_P) – The upper limit
Returns:: The upper bounded set.
Return type:: AbstractUpperBoundedSet[_P]

isdisjoint(other): Return True if two sets have a null intersection.

abstract property minimum: galactic.algebras.poset._abstract._P

Get the minimum of the poset.

Returns:: The minimum element.
Return type:: _P

abstract predecessors(element: galactic.algebras.relational._binary._F) → AbstractSet[galactic.algebras.relational._binary._E]

Get the predecessors of an element.

Parameters:: element (_F) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_E]
Raises:: ValueError – If the element does not belong to the relation.

abstract property sinks: AbstractSet[galactic.algebras.relational._binary._E]

Get the sinks of this DAG.

Returns:: The sinks of this DAG.
Return type:: AbstractSet[_E]

abstract property sources: AbstractSet[galactic.algebras.relational._binary._E]

Get the sources of this DAG.

Returns:: The sources of this DAG.
Return type:: AbstractSet[_E]

abstract successors(element: galactic.algebras.relational._binary._E) → AbstractSet[galactic.algebras.relational._binary._F]

Get the successors of an element.

Parameters:: element (_E) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_F]
Raises:: ValueError – If the element does not belong to the relation.

abstract property top: AbstractSet[galactic.algebras.poset._abstract._P]

Get the top elements.

Returns:: The top elements.
Return type:: AbstractSet[_P]

abstract property universes: Tuple[AbstractSet[galactic.algebras.relational._binary._E], AbstractSet[galactic.algebras.relational._binary._F]]

Get the universes of this relation.

Returns:: The universes of this relation.
Return type:: Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractBoundedSet(*args, **kwds)

The AbstractBoundedSet represents bounded posets.

__contains__(item: Any) → bool

Get the membership of an element.

Parameters:: item – The element whose membership is requested.
Returns:: True if the item belongs to the partially ordered set.
Return type:: bool

__iter__() → Iterator[Tuple[galactic.algebras.poset._abstract._P, galactic.algebras.poset._abstract._P]]

Get an iterator over the elements.

Returns:: An iterator over the elements
Return type:: Iterator[Tuple[_P, _P]]

abstract property bottom: AbstractSet[galactic.algebras.poset._abstract._P]

Get the bottom elements.

Returns:: The bottom elements.
Return type:: AbstractSet[_P]

property co_domain: AbstractSet[galactic.algebras.relational._binary._F]

Get the co-domain of this binary relation.

This is a proxy to self.universes[1].

Returns:: The co-domain of this binary relation.
Return type:: AbstractSet[_F]

abstract property cover: galactic.algebras.poset.AbstractCoveringRelation[galactic.algebras.poset._abstract._P]

Get the covering relation.

Returns:: The covering relation.
Return type:: AbstractCoveringRelation[_P]

property domain: AbstractSet[galactic.algebras.relational._binary._E]

Get the domain of this binary relation.

This is a proxy to self.universes[0].

Returns:: The domain of this binary relation.
Return type:: AbstractSet[_E]

abstract filter(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractLowerBoundedSet[galactic.algebras.poset._abstract._P]

Get a filter of a poset.

Parameters:: element (_P) – The lower limit
Returns:: The lower bounded poset.
Return type:: AbstractLowerBoundedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

abstract ideal(element: galactic.algebras.poset._abstract._P) → galactic.algebras.poset.AbstractUpperBoundedSet[galactic.algebras.poset._abstract._P]

Get an ideal of the poset.

Parameters:: element (_P) – The upper limit
Returns:: The upper bounded set.
Return type:: AbstractUpperBoundedSet[_P]

isdisjoint(other): Return True if two sets have a null intersection.

abstract property maximum: galactic.algebras.poset._abstract._P

Get the maximum of the poset.

Returns:: The maximum element.
Return type:: _P

abstract property minimum: galactic.algebras.poset._abstract._P

Get the minimum of the poset.

Returns:: The minimum element.
Return type:: _P

abstract predecessors(element: galactic.algebras.relational._binary._F) → AbstractSet[galactic.algebras.relational._binary._E]

Get the predecessors of an element.

Parameters:: element (_F) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_E]
Raises:: ValueError – If the element does not belong to the relation.

abstract property sinks: AbstractSet[galactic.algebras.relational._binary._E]

Get the sinks of this DAG.

Returns:: The sinks of this DAG.
Return type:: AbstractSet[_E]

abstract property sources: AbstractSet[galactic.algebras.relational._binary._E]

Get the sources of this DAG.

Returns:: The sources of this DAG.
Return type:: AbstractSet[_E]

abstract successors(element: galactic.algebras.relational._binary._E) → AbstractSet[galactic.algebras.relational._binary._F]

Get the successors of an element.

Parameters:: element (_E) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_F]
Raises:: ValueError – If the element does not belong to the relation.

abstract property top: AbstractSet[galactic.algebras.poset._abstract._P]

Get the top elements.

Returns:: The top elements.
Return type:: AbstractSet[_P]

abstract property universes: Tuple[AbstractSet[galactic.algebras.relational._binary._E], AbstractSet[galactic.algebras.relational._binary._F]]

Get the universes of this relation.

Returns:: The universes of this relation.
Return type:: Tuple[AbstractSet[_E], AbstractSet[_F]]

class PartiallyComparable(*args, **kwds)

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 abstract class must be declared by inheriting from PartiallyComparable and must implement the methods:

__lt__()
__gt__()
__eq__()
__hash__()

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 Integer class:

>>> from galactic.examples.arithmetic import Integer
>>> Integer(5) <= Integer(10)  # 5 is a divisor of 10
True
>>> Integer(5) <= Integer(11)  # 5 is not a divisor of 11
False
>>> Integer(5) >= Integer(11)  # 5 is not a multiple of 11
False
>>>

abstract __eq__(other: Any) → bool

Test if this element is equal to the other.

Parameters:: other – the other element
Returns:: True if this element is equal to the other.
Return type:: bool

__ge__(other: Any) → bool

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

Parameters:

other – the other element

Returns:

True – if this element is greater than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __gt__(other: Any) → bool

Test if this element is greater than the other.

Parameters:

other – the other element

Returns:

True – if this element is greater than the other.
NotImplemented – if the operation is not implemented between the two objects

__le__(other: Any) → bool

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

Parameters:

other – the other element

Returns:

True – if this element is lesser than or equal to the other.
NotImplemented – if the operation is not implemented between the two objects

abstract __lt__(other: Any) → bool

Test if this element is lesser than the other.

Parameters:

other – the other element

Returns:

True – if this element is lesser than the other.
NotImplemented – if the operation is not implemented between the two objects

bottom(iterable: Iterable[galactic.algebras.poset._element._P]) → Iterator[galactic.algebras.poset._element._P]

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[_P]) – 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: Iterable[galactic.algebras.poset._element._P]) → Iterator[galactic.algebras.poset._element._P]

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[_P]) – 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: Iterable[galactic.algebras.poset._element._P], limit: galactic.algebras.poset._element._P, strict: bool = False) → Iterator[galactic.algebras.poset._element._P]

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[_P]) – An iterable of partially ordered elements.
limit – The lower limit
strict (bool) – Is the comparison strict?

Returns:

An iterator over the selected elements.

Return type:

Iterator[_P]

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})]

upper_limit(iterable: Iterable[galactic.algebras.poset._element._P], limit: galactic.algebras.poset._element._P, strict: bool = False) → Iterator[galactic.algebras.poset._element._P]

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[_P]) – An iterable of partially ordered elements.
limit – The upper limit
strict (bool) – Is the comparison strict?

Returns:

An iterator over the selected elements.

Return type:

Iterator[_P]

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})]

class ReversibleCoveringRelation(domain: Optional[Iterable[galactic.algebras.poset._cover._P]] = None)

The ReversibleCoveringRelation class.

It implements the AbstractReversibleCoveringRelation class.

__copy__() → galactic.algebras.poset.ReversibleCoveringRelation[galactic.algebras.poset._cover._P]

Get a copy of the covering relation.

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

Returns:: The copy of this covering relation.
Return type:: ReversibleCoveringRelation[_P]

__init__(domain: Optional[Iterable[galactic.algebras.poset._cover._P]] = None)

Initialise a ReversibleCoveringRelation instance.

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

property co_domain: MutableSet[galactic.algebras.poset._cover._P]

Get the co-domain of this covering relation.

Returns:: The co-domain of this covering relation.
Return type:: MutableSet[_P]

Notes

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

property domain: MutableSet[galactic.algebras.poset._cover._P]

Get the domain of this covering relation.

Returns:: The domain of this covering relation.
Return type:: MutableSet[_P]

extend(iterable: Iterable[galactic.algebras.poset._cover._P]) → None

Extend this covering relation.

Parameters:: iterable (Iterable[_P]) – An iterable of values.

isdisjoint(other): Return True if two sets have a null intersection.

neighbours() → Reversible[Tuple[galactic.algebras.poset._cover._P, AbstractSet[galactic.algebras.poset._cover._P], AbstractSet[galactic.algebras.poset._cover._P]]]

Get the neighbourhood of elements.

Returns:
Return type:: Reversible[Tuple[_P, AbstractSet[_P], AbstractSet[_P]]]

predecessors(element: galactic.algebras.poset._cover._P) → AbstractSet[galactic.algebras.poset._cover._P]

Get the predecessors of an element.

Parameters:: element (_P) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_P]
Raises:: ValueError – If the element does not belong to the covering relation.

property sinks: AbstractSet[galactic.algebras.poset._cover._P]

Get the elements with no successors.

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

property sources: AbstractSet[galactic.algebras.poset._cover._P]

Get the elements with no predecessors.

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

successors(element: galactic.algebras.poset._cover._P) → AbstractSet[galactic.algebras.poset._cover._P]

Get the successors of an element.

Parameters:: element (_P) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_P]
Raises:: ValueError – If the element does not belong to the covering relation.

property universes: Tuple[MutableSet[galactic.algebras.poset._cover._P], MutableSet[galactic.algebras.poset._cover._P]]

Get the universes of this covering relation.

Returns:: The universes of this covering relation.
Return type:: Tuple[MutableSet[_P], MutableSet[_P]]

class PartiallyOrderedSet(domain: Optional[Iterable[galactic.algebras.poset._posets._P]] = None)

The PartiallyOrderedSet implements posets.

A PartiallyOrderedSet 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)\)

Example

>>> from galactic.algebras.poset import PartiallyOrderedSet
>>> from galactic.examples.arithmetic import Integer
>>> poset = PartiallyOrderedSet[Integer](
...     domain=[
...         Integer(2*3*5*7),
...         Integer(3*5*7*11),
...         Integer(3*5*7),
...         Integer(3*5),
...         Integer(5),
...         Integer(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.domain)))
[5, 7, 15, 105, 210, 1155]

It’s possible to know the poset length.

Example

>>> len(poset.domain)
6

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

Example

>>> Integer(210) in poset.domain
True
>>> Integer(211) in poset.domain
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(Integer(105)).domain)))
[105, 210, 1155]
>>> sorted(list(map(int, poset.ideal(Integer(105)).domain)))
[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(Integer(105)))))
[210, 1155]
>>> sorted(list(map(int, poset.successors(Integer(105)))))
[105, 210, 1155]
>>> sorted(list(map(int, poset.cover.predecessors(Integer(105)))))
[7, 15]
>>> sorted(list(map(int, poset.predecessors(Integer(105)))))
[5, 7, 15, 105]

It’s possible to enlarge a partially ordered set.

Example

>>> poset.extend([Integer(13)])
>>> sorted(list(map(int, poset.domain)))
[5, 7, 13, 15, 105, 210, 1155]

__contains__(item: Any) → bool

Get the membership of an element.

Parameters:: item – The element whose membership is requested.
Returns:: True if the item belongs to the partially ordered set.
Return type:: bool

__copy__() → galactic.algebras.poset.PartiallyOrderedSet[galactic.algebras.poset._posets._P]

Get a copy of the partially ordered set.

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

Returns:: The copy of this poset.
Return type:: PartiallyOrderedSet[_P]

__init__(domain: Optional[Iterable[galactic.algebras.poset._posets._P]] = None)

Initialise a PartiallyOrderedSet instance.

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

Keyword Arguments:: domain (Iterable[_P], optional) – An iterable of values.

__iter__() → Iterator[Tuple[galactic.algebras.poset._abstract._P, galactic.algebras.poset._abstract._P]]

Get an iterator over the elements.

Returns:: An iterator over the elements
Return type:: Iterator[Tuple[_P, _P]]

property bottom: AbstractSet[galactic.algebras.poset._posets._P]

Get the bottom elements.

Returns:: The bottom elements.
Return type:: AbstractSet[_P]

property co_domain: MutableSet[galactic.algebras.poset._posets._P]

Get the co-domain of this poset.

Returns:: The co-domain of this poset.
Return type:: MutableSet[_P]

Notes

The domain and the co-domain of a poset are identical.

property cover: galactic.algebras.poset.ReversibleCoveringRelation[galactic.algebras.poset._posets._P]

Get the covering relation of this poset.

Returns:: The covering relation.
Return type:: ReversibleCoveringRelation[_P]

property domain: MutableSet[galactic.algebras.poset._posets._P]

Get the domain of this poset.

Returns:: The domain of this poset.
Return type:: MutableSet[_P]

extend(iterable: Iterable[galactic.algebras.poset._posets._P]) → None

Extend this poset.

Parameters:: iterable (Iterable[_P]) – An iterable of values.

filter(element: galactic.algebras.poset._posets._P) → galactic.algebras.poset.AbstractLowerBoundedSet[galactic.algebras.poset._posets._P]

Get a filter of a poset.

Parameters:: element (_P) – The lower limit
Returns:: The lower bounded poset.
Return type:: AbstractLowerBoundedSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

ideal(element: galactic.algebras.poset._posets._P) → galactic.algebras.poset.AbstractUpperBoundedSet[galactic.algebras.poset._posets._P]

Get an ideal of the poset.

Parameters:: element (_P) – The upper limit
Returns:: The upper bounded set.
Return type:: AbstractUpperBoundedSet[_P]

isdisjoint(other): Return True if two sets have a null intersection.

predecessors(element: galactic.algebras.poset._posets._P) → AbstractSet[galactic.algebras.poset._posets._P]

Get the predecessors of an element.

Parameters:: element (_P) – The element whose predecessors are requested
Returns:: The predecessors.
Return type:: AbstractSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

property sinks: AbstractSet[galactic.algebras.poset._posets._P]

Get the sink elements.

Returns:: The sink elements.
Return type:: AbstractSet[_P]

property sources: AbstractSet[galactic.algebras.poset._posets._P]

Get the source elements.

Returns:: The source elements.
Return type:: AbstractSet[_P]

successors(element: galactic.algebras.poset._posets._P) → AbstractSet[galactic.algebras.poset._posets._P]

Get the successors of an element.

Parameters:: element (_P) – The element whose successors are requested
Returns:: The successors.
Return type:: AbstractSet[_P]
Raises:: ValueError – If the element does not belong to the poset.

property top: AbstractSet[galactic.algebras.poset._posets._P]

Get the top elements.

Returns:: The top elements.
Return type:: AbstractSet[_P]

property universes: Tuple[MutableSet[galactic.algebras.poset._posets._P], MutableSet[galactic.algebras.poset._posets._P]]

Get the universes of this poset.

Returns:: The universes of this poset.
Return type:: Tuple[MutableSet[_P], MutableSet[_P]]

class HasseDiagramRenderer(*args, **kwds)

The HasseDiagramRenderer class renders graph attributes.

Notes

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

add_destination(element: galactic.algebras.relational._renderer._F, index: Optional[int] = None, current: bool = False, successors: Optional[AbstractSet[galactic.algebras.relational._renderer._E]] = None, predecessors: Optional[AbstractSet[galactic.algebras.relational._renderer._E]] = None) → None

Add a destination to the graph.

Parameters:

element (_F) – The destination to add.

Keyword Arguments:

index (int, optional) – The destination index.
current (bool) – is element the current element?
successors (AbstractSet[_E], optional) – The successors of the destination.
predecessors (AbstractSet[_E], optional) – The predecessors of the destination.

add_edge(source: galactic.algebras.relational._renderer._E, destination: galactic.algebras.relational._renderer._F, successors: Optional[AbstractSet[galactic.algebras.relational._renderer._F]] = None, predecessors: Optional[AbstractSet[galactic.algebras.relational._renderer._E]] = None) → None

Add an edge to the graph.

Parameters:

source (_E) – The edge source
destination (_F) – The edge destination

Keyword Arguments:

successors (AbstractSet[_F], optional) – The successors of source (including current destination).
predecessors (AbstractSet[_E], optional) – The predecessors of destination (including current source).

add_source(element: galactic.algebras.relational._renderer._E, index: Optional[int] = None, current: bool = False, successors: Optional[AbstractSet[galactic.algebras.relational._renderer._F]] = None, predecessors: Optional[AbstractSet[galactic.algebras.relational._renderer._F]] = None) → None

Add a source to the graph.

Parameters:

element (_E) – The source to add.

Keyword Arguments:

index (int, optional) – The source index.
current (bool) – is element the current element?
successors (AbstractSet[_F], optional) – The successors of the source.
predecessors (AbstractSet[_F], optional) – The predecessors of the source.

attributes() → Dict[str, str]

Return a dictionary of graphviz attributes for a Hasse diagram.

Returns:: A dictionary of graphviz attributes
Return type:: Dict[str, str]

class DynamicDiagram(graph_renderer: Optional[galactic.algebras.poset.HasseDiagramRenderer[galactic.algebras.poset._renderer._P]] = None, domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None)

The DynamicDiagram class is designed to allow dynamic graph rendering.

__init__(graph_renderer: Optional[galactic.algebras.poset.HasseDiagramRenderer[galactic.algebras.poset._renderer._P]] = None, domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None)

Initialise a DynamicDiagram instance.

Keyword Arguments:

graph_renderer (HasseDiagramRendererRenderer[_P]) – A Hasse diagram renderer.
domain_renderer (NodeRenderer[_P, _P]) – A node renderer.
edge_renderer (EdgeRenderer[_P, _P]) – An edge renderer.

property body: Sequence[str]

Get the current graphviz body.

Returns:: The current body.
Return type:: Sequence[str]

finish() → None: Finish the iteration.

pipe(output: str = 'svg') → bytes

Pipe the diagram.

Parameters:: output (str) – The format used
Returns:: The image of the diagram.
Return type:: bytes

render(filename: str) → None

Render the diagram in a file.

Parameters:: filename (str) – A file path.

property source: str

Get the graphviz source for this diagram.

Returns:: The graphviz output for this diagram.
Return type:: str

start() → None: Start a new iteration.

step(element: galactic.algebras.poset._renderer._P, successors: AbstractSet[galactic.algebras.poset._renderer._P], predecessors: AbstractSet[galactic.algebras.poset._renderer._P]) → None

Insert a new element in the diagram.

Parameters:

element (_P) – The new element
successors (AbstractSet[_P]) – The immediate successors of the element.
predecessors (AbstractSet[_P]) – The immediate predecessors of the element.

class HasseDiagram(poset: galactic.algebras.poset.AbstractPartiallyOrderedSet[galactic.algebras.poset._renderer._P], graph_renderer: Optional[galactic.algebras.poset.HasseDiagramRenderer[galactic.algebras.poset._renderer._P]] = None, domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None)

The HasseDiagram class is used for drawing Hasse diagrams.

__init__(poset: galactic.algebras.poset.AbstractPartiallyOrderedSet[galactic.algebras.poset._renderer._P], graph_renderer: Optional[galactic.algebras.poset.HasseDiagramRenderer[galactic.algebras.poset._renderer._P]] = None, domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None) → None

Initialise a Hasse diagram instance.

Parameters:

poset (AbstractPartiallyOrderedSet[_P]) – A poset.

Keyword Arguments:

graph_renderer (HasseDiagramRenderer[_P], optional) – A Hasse diagram renderer.
domain_renderer (NodeRenderer[_P, _P], optional) – A node renderer.
edge_renderer (EdgeRenderer[_P, _P], optional) – An edge renderer.

property domain_renderer: galactic.algebras.relational.NodeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]

Get the domain renderer.

Returns:: The domain renderer.
Return type:: NodeRenderer[_E, _E]

property edge_renderer: galactic.algebras.relational.EdgeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]

Get the edge renderer.

Returns:: The edge renderer.
Return type:: EdgeRenderer[_P, _P]

property graph_renderer: galactic.algebras.poset.HasseDiagramRenderer[galactic.algebras.poset._renderer._P]

Get the Hasse diagram renderer.

Returns:: The Hasse diagram renderer.
Return type:: HasseDiagramRenderer[_P]

pipe(output: str = 'svg') → bytes

Pipe the diagram.

Parameters:: output (str) – The format used
Returns:: The image of the diagram.
Return type:: bytes

property poset: galactic.algebras.poset.AbstractPartiallyOrderedSet[galactic.algebras.poset._renderer._P]

Get the poset.

Returns:: The underlying poset.
Return type:: AbstractPartiallyOrderedSet[_P]

render(filename: str) → None

Render the diagram in a file.

Parameters:: filename (str) – A file path.

property source: str

Get the graphviz source for this partially ordered set.

Returns:: The graphviz output for this partially ordered set.
Return type:: str

class IterativeDiagram(poset: galactic.algebras.poset.AbstractPartiallyOrderedSet[galactic.algebras.poset._renderer._P], graph_renderer: Optional[galactic.algebras.poset.HasseDiagramRenderer[galactic.algebras.poset._renderer._P]] = None, domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None)

The IterativeDiagram class allows iterative rendering.

__init__(poset: galactic.algebras.poset.AbstractPartiallyOrderedSet[galactic.algebras.poset._renderer._P], graph_renderer: Optional[galactic.algebras.poset.HasseDiagramRenderer[galactic.algebras.poset._renderer._P]] = None, domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[galactic.algebras.poset._renderer._P, galactic.algebras.poset._renderer._P]] = None)

Initialise a IterativeDiagram instance.

Parameters:

poset (AbstractPartiallyOrderedSet[_P]) – A poset.

Keyword Arguments:

graph_renderer (HasseDiagramRenderer[_P]) – A Hasse diagram renderer renderer.
domain_renderer (NodeRenderer[_P, _P]) – A node renderer.
edge_renderer (EdgeRenderer[_P, _P]) – An edge renderer.