Posets¶

The galactic.algebras.poset module defines types for representing posets.

AbstractPartiallyOrderedSet;
AbstractUpperBoundedSet;
AbstractLowerBoundedSet;
AbstractBoundedSet;
AbstractCoveringRelation;
AbstractReversibleCoveringRelation;

their implementations:

PartiallyOrderedSet;
ReversibleCoveringRelation

and their elements which are partially comparable:

PartiallyComparable

with their functions:

bottom()
top()
lower_limit()
upper_limit()

It also defines the HasseDiagram class for drawing Hasse diagram of partially ordered sets into jupyter notebooks.

class AbstractCoveringRelation(*args, **kwds)¶

The AbstractCoveringRelation represents the covering relation of a poset.

property co_domain¶

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¶

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() → Iterable[Tuple[_P, AbstractSet[_P], AbstractSet[_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: _F) → AbstractSet[_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¶

Get the elements with no successors.

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

abstract property sources¶

Get the elements with no predecessors.

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

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

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

abstract property universes¶

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¶

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¶

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[_P, AbstractSet[_P], AbstractSet[_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: _F) → AbstractSet[_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¶

Get the elements with no successors.

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

abstract property sources¶

Get the elements with no predecessors.

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

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

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

abstract property universes¶

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[_P, _P]]¶

Get an iterator over the elements.

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

abstract property bottom¶

Get the bottom elements.

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

property co_domain¶

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¶

Get the covering relation.

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

property domain¶

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: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_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: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_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: _F) → AbstractSet[_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¶

Get the sinks of this DAG.

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

abstract property sources¶

Get the sources of this DAG.

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

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

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

abstract property top¶

Get the top elements.

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

abstract property universes¶

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[_P, _P]]¶

Get an iterator over the elements.

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

abstract property bottom¶

Get the bottom elements.

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

property co_domain¶

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¶

Get the covering relation.

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

property domain¶

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: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_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: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_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¶

Get the maximum of the poset.

Returns: The maximum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

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

abstract property sinks¶

Get the sinks of this DAG.

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

abstract property sources¶

Get the sources of this DAG.

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

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

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

abstract property top¶

Get the top elements.

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

abstract property universes¶

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[_P, _P]]¶

Get an iterator over the elements.

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

abstract property bottom¶

Get the bottom elements.

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

property co_domain¶

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¶

Get the covering relation.

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

property domain¶

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: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_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: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_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¶

Get the minimum of the poset.

Returns: The minimum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

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

abstract property sinks¶

Get the sinks of this DAG.

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

abstract property sources¶

Get the sources of this DAG.

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

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

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

abstract property top¶

Get the top elements.

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

abstract property universes¶

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[_P, _P]]¶

Get an iterator over the elements.

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

abstract property bottom¶

Get the bottom elements.

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

property co_domain¶

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¶

Get the covering relation.

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

property domain¶

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: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_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: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_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¶

Get the maximum of the poset.

Returns: The maximum element.
Return type: _P

abstract property minimum¶

Get the minimum of the poset.

Returns: The minimum element.
Return type: _P

abstract predecessors(element: _F) → AbstractSet[_E]¶

Get the predecessors of an element.

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

abstract property sinks¶

Get the sinks of this DAG.

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

abstract property sources¶

Get the sources of this DAG.

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

abstract successors(element: _E) → AbstractSet[_F]¶

Get the successors of an element.

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

abstract property top¶

Get the top elements.

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

abstract property universes¶

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[_P]) → Iterator[_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[_P]) → Iterator[_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[_P], limit: _P, strict: bool = False) → Iterator[_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[_P], limit: _P, strict: bool = False) → Iterator[_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[_P]] = None)¶

The ReversibleCoveringRelation class.

It implements the AbstractReversibleCoveringRelation class.

__copy__() → galactic.algebras.poset.ReversibleCoveringRelation[_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[_P]] = None)¶

Initialise a ReversibleCoveringRelation instance.

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

property co_domain¶

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¶

Get the domain of this covering relation.

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

extend(iterable: Iterable[_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[_P, AbstractSet[_P], AbstractSet[_P]]]¶

Get the neighbourhood of elements.

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

predecessors(element: _P) → AbstractSet[_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¶

Get the elements with no successors.

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

property sources¶

Get the elements with no predecessors.

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

successors(element: _P) → AbstractSet[_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¶

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[_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[_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[_P]] = None)¶

Initialise a PartiallyOrderedSet instance.

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

__iter__() → Iterator[Tuple[_P, _P]]¶

Get an iterator over the elements.

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

property bottom¶

Get the bottom elements.

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

property co_domain¶

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¶

Get the covering relation of this poset.

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

property domain¶

Get the domain of this poset.

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

extend(iterable: Iterable[_P]) → None ¶

Extend this poset.

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

filter(element: _P) → galactic.algebras.poset.AbstractLowerBoundedSet[_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: _P) → galactic.algebras.poset.AbstractUpperBoundedSet[_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: _P) → AbstractSet[_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¶

Get the sink elements.

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

property sources¶

Get the source elements.

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

successors(element: _P) → AbstractSet[_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¶

Get the top elements.

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

property universes¶

Get the universes of this poset.

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

class DynamicDiagram(domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_P, _P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_P, _P]] = None)¶

The DynamicDiagram class is designed to allow dynamic graph rendering.

__init__(domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_P, _P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_P, _P]] = None)¶

Initialise a DynamicDiagram instance.

Parameters

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

property body¶

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¶

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: _P, successors: AbstractSet[_P], predecessors: AbstractSet[_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[_P], domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_P, _P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_P, _P]] = None)¶

The HasseDiagram class is used for drawing Hasse diagrams.

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

Initialise a Hasse diagram instance.

Parameters

poset (AbstractPartiallyOrderedSet[_P]) – A poset.
domain_renderer (NodeRenderer[_P, _P]) – A node renderer.
edge_renderer (EdgeRenderer[_P, _P]) – An edge renderer.

property domain_renderer¶

Get the domain renderer.

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

property edge_renderer¶

Get the edge renderer.

Returns: The edge renderer.
Return type: EdgeRenderer[_P, _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¶

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¶

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[_P], domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_P, _P]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_P, _P]] = None)¶

The IterativeDiagram class allows iterative rendering.

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

Initialise a IterativeDiagram instance.

Parameters

poset (AbstractPartiallyOrderedSet[_P]) – A poset.
domain_renderer (NodeRenderer[_P, _P]) – A node renderer.
edge_renderer (EdgeRenderer[_P, _P]) – An edge renderer.