Poset¶

The galactic.algebras.poset module defines essential type for representing partially ordered sets and their elements:

PartiallyOrderedSet;
PartiallyOrdered.

class galactic.algebras.poset.PartiallyOrdered¶

Bases: collections.abc.Hashable

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

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

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

__lt__()
__le__()
__gt__()
__ge__()
__eq__()
__hash__()

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)
True
>>> Integer(5) <= Integer(11)
False
>>>

abstract __lt__(other: Any) → bool ¶

Test if this element is lesser than the other.

Parameters

other – the other element

Returns

bool – True if this element is lesser than the other.
NotImplementedType – 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

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

abstract __eq__(other: Any) → bool ¶

Test if this element is equal to the other.

Parameters

other – the other element

Returns

bool – True if this element is equal to the other.
NotImplementedType – if the operation is not implemented between the two objects

abstract __le__(other: Any) → bool ¶

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

Parameters

other – the other element

Returns

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

__ge__(other: Any) → bool ¶

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

Parameters

other – the other element

Returns

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

class galactic.algebras.poset.LowerBounded¶

Bases: galactic.algebras.poset.elements.PartiallyOrdered

The LowerBounded <galactic.algebras.poset.LowerBounded type defines a minimum value for instances.

abstract classmethod minimum() → galactic.algebras.poset.elements.LowerBounded¶

Returns the minimum element of this type

Returns: the minimum element
Return type: LowerBounded <galactic.algebras.poset.LowerBounded

class galactic.algebras.poset.UpperBounded¶

Bases: galactic.algebras.poset.elements.PartiallyOrdered

The UpperBounded <galactic.algebras.poset.UpperBounded type defines a maximum value for instances.

abstract classmethod maximum() → galactic.algebras.poset.elements.UpperBounded¶

Returns the maximum element of this type.

Returns: the maximum element
Return type: UpperBounded <galactic.algebras.poset.UpperBounded

galactic.algebras.poset.bottom(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

The bottom() function computes an iterator over the bottom elements of the iterable collection. This operation computes in \(O(n^2)\) where \(n\) is the number of elements in the iterable.

Keyword Arguments: iterable (Iterable[PartiallyOrdered]) – An iterable of partially ordered elements.
Returns: An iterator over the bottom elements.
Return type: Iterator[PartiallyOrdered]

Example

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

galactic.algebras.poset.top(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

The top() function computes an iterator over the top elements of the iterable collection. This operation computes in \(O(n^2)\) where \(n\) is the number of elements in the iterable.

Keyword Arguments: iterable (Iterable[PartiallyOrdered]) – An iterable of partially ordered elements.
Returns: An iterator over the top elements.
Return type: Iterator[PartiallyOrdered]

Example

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

galactic.algebras.poset.lower_limit(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None, limit: Optional[galactic.algebras.poset.elements.PartiallyOrdered] = None, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

The lower_limit() function computes 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.

Keyword Arguments

iterable (Iterable[PartiallyOrdered]) – 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[PartiallyOrdered]

Example

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

galactic.algebras.poset.upper_limit(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None, limit: Optional[galactic.algebras.poset.elements.PartiallyOrdered] = None, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

The upper_limit() function computes 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.

Keyword Arguments

iterable (Iterable[PartiallyOrdered]) – 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[PartiallyOrdered]

Example

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

class galactic.algebras.poset.PartiallyOrderedSet¶

Bases: collections.abc.Set

A partially ordered set is a set of PartiallyOrdered <galactic.algebras.poset.PartiallyOrdered elements. It must also implements the Set interface.

abstract __iadd__(iterable: Iterable[galactic.algebras.poset.elements.PartiallyOrdered]) → galactic.algebras.poset.collections.PartiallyOrderedSet¶

In-place enlarge the partially ordered set with an iterable of elements.

Keyword Arguments

iterable (Iterable[PartiallyOrdered]) – An iterable of elements

Returns

PartiallyOrderedSet – if this addition succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __add__(iterable: Iterable[galactic.algebras.poset.elements.PartiallyOrdered]) → galactic.algebras.poset.collections.PartiallyOrderedSet¶

Enlarge the partially ordered set with an iterable of elements.

:keyword iterable Iterable[PartiallyOrdered]: An iterable of elements

Returns

PartiallyOrderedSet – if this addition succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __imatmul__(other: Iterable[galactic.algebras.poset.elements.PartiallyOrdered]) → galactic.algebras.poset.collections.PartiallyOrderedSet¶

In-place combine the partially ordered set with another partially ordered set.

Parameters

other – The other partially ordered set

Returns

PartiallyOrderedSet – if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __matmul__(other: Iterable[galactic.algebras.poset.elements.PartiallyOrdered]) → galactic.algebras.poset.collections.PartiallyOrderedSet¶

Combine the partially ordered set with another partially ordered set.

Parameters

other – The other partially ordered set

Returns

PartiallyOrderedSet – if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __copy__() → galactic.algebras.poset.collections.PartiallyOrderedSet¶

Copy the partially ordered set.

Returns: The copied partially ordered set
Return type: PartiallyOrderedSet

abstract top() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the top elements.

Returns: An iterator over the top elements.
Return type: Iterator[PartiallyOrdered]

abstract bottom() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the bottom elements.

Returns: An iterator over the bottom elements.
Return type: Iterator[PartiallyOrdered]

abstract upper_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator of elements lesser than a limit.

Parameters

limit (PartiallyOrdered) – The upper limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[PartiallyOrdered]

abstract lower_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator of elements greater than a limit.

Parameters

limit (PartiallyOrdered) – The lower limit
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected elements.

Return type

Iterator[PartiallyOrdered]

abstract following(limit: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the bottom elements greater than a limit.

Parameters: limit (PartiallyOrdered) – The upper limit
Returns: An iterator over the selected elements.
Return type: Iterator[PartiallyOrdered]

abstract preceding(limit: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the top elements lower than a limit.

Parameters: limit (PartiallyOrdered) – The lower limit
Returns: An iterator over the selected elements.
Return type: Iterator[PartiallyOrdered]

abstract successors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the successors of an element.

Parameters: element (PartiallyOrdered) – The element whose successors are requested
Returns: An iterator over the successors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

abstract predecessors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the predecessors of an element.

Parameters: element (PartiallyOrdered) – The element whose predecessors are requested
Returns: An iterator over the predecessors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

abstract descendants(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the descendants of an element.

Parameters: element (PartiallyOrdered) – The element whose descendants are requested
Returns: An iterator over the descendants.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

abstract filter(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the filter of an element. See https://en.wikipedia.org/wiki/Filter_(mathematics).

Parameters: element (PartiallyOrdered) – The element whose filter is requested
Returns: An iterator over the filter elements.
Return type: Iterator[PartiallyOrdered]

abstract ascendants(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the ascendants of an element.

Parameters: element (PartiallyOrdered) – The element whose ascendants are requested
Returns: An iterator over the ascendants.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

abstract ideal(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the ideal of an element. See https://en.wikipedia.org/wiki/Ideal_(order_theory).

Parameters: element (PartiallyOrdered) – The element whose ideal is requested
Returns: An iterator over the ideal elements.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

abstract siblings(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the siblings of an element. A sibling is an element which has a common predecessor with the element and which is not a descendant of the element.

Parameters: element (PartiallyOrdered) – The element whose siblings are requested
Returns: An iterator over the siblings.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

abstract co_parents(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the co-parents of an element. A co-parent is an element which has a common successor with the element and which is not a ascendant of the element.

Parameters: element (PartiallyOrdered) – The element whose co-parents are requested
Returns: An iterator over the co-parents.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

abstract neighbors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the neighbors of an element (siblings or co-parents).

Parameters: element (PartiallyOrdered) – The element whose neighbors are requested
Returns: An iterator over the neighbors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

class galactic.algebras.poset.AbstractPartiallyOrderedSet¶

Bases: galactic.algebras.poset.collections.PartiallyOrderedSet, abc.ABC

The AbstractPartiallyOrderedSet implements a mixin for subclasses.

__len__() → int ¶

Get the number of elements. This basic operation count the number of elements. Its complexity is in \(O(n)\). Sub-classes may have overloaded this operation.

Returns: the number of elements
Return type: int

__contains__(element: Any) → bool ¶

Get the membership of an element. Its complexity is in \(O(n)\). Sub-classes may have overloaded this operation.

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

__copy__() → galactic.algebras.poset.collections.AbstractPartiallyOrderedSet¶

Get a copy of the partially ordered set. Its complexity is in \(O(n)\). Sub-classes may have overloaded this operation.

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

__add__(iterable: Iterable[Any]) → galactic.algebras.poset.collections.AbstractPartiallyOrderedSet¶

Enlarge the partially ordered set with an iterable of elements.

Keyword Arguments

iterable – An iterable of elements

Returns

AbstractPartiallyOrderedSet – if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

__imatmul__(other: Any) → Any¶

In-place combine the partially ordered set with another partially ordered set.

Parameters

other – The other partially ordered set

Returns

AbstractPartiallyOrderedSet – if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

__matmul__(other: Any) → Any¶

Combine the partially ordered set with another partially ordered set.

Parameters

other – The other partially ordered set

Returns

AbstractPartiallyOrderedSet – if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

top() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the top elements. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.

Returns: An iterator over the top elements.
Return type: Iterator[PartiallyOrdered]

bottom() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the bottom elements. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.

Returns: An iterator over the bottom elements.
Return type: Iterator[PartiallyOrdered]

class Limit(poset: galactic.algebras.poset.collections.PartiallyOrderedSet, limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False)¶

Bases: collections.abc.Collection, abc.ABC

The Limit is a collection class for representing elements of a partially ordered set lesser or greater than a limit.

upper_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get the collection of the elements lesser than a limit. The iteration is in \(O(n)\).

Parameters

limit (PartiallyOrdered) – The upper limit
strict (bool) – Is the comparison strict?

Returns

A collection over the selected elements.

Return type

Iterator[PartiallyOrdered]

lower_limit(limit: galactic.algebras.poset.elements.PartiallyOrdered, strict: bool = False) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get the collection of the elements greater than a limit. The iteration is in \(O(n)\).

Parameters

limit (PartiallyOrdered) – The lower limit
strict (bool) – Is the comparison strict?

Returns

A collection over the selected elements.

Return type

Iterator[PartiallyOrdered]

following(limit: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the following of a limit. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.

Parameters: limit (PartiallyOrdered) – The upper limit
Returns: An iterator over the following elements.
Return type: Iterator[PartiallyOrdered]

preceding(limit: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the preceding of an element. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.

Parameters: limit (PartiallyOrdered) – The lower limit
Returns: An iterator over the preceding elements.
Return type: Iterator[PartiallyOrdered]

successors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the successors of an element. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose successors are requested
Returns: An iterator over the successors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

predecessors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the predecessors of an element. The iteration is in \(O(n^2)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose predecessors are requested
Returns: An iterator over the predecessors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

descendants(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the descendants of an element. The iteration is in \(O(n)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose descendants are requested
Returns: An iterator over the descendants.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

filter(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the ideal of an element. The iteration is in \(O(n)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose ideal is requested
Returns: An iterator over the ideal elements.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

ascendants(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the ascendants of an element. The iteration is in \(O(n)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose ascendants are requested
Returns: An iterator over the ascendants.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

ideal(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the filter of an element. The iteration is in \(O(n)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose filter is requested
Returns: An iterator over the filter elements.
Return type: Iterator[PartiallyOrdered]

siblings(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the siblings of an element. A sibling is an element which has a common predecessor with the element and which is not a descendant of the element.

The iteration is in \(O(n^4)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose siblings are requested
Returns: An iterator over the siblings.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

co_parents(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the co-parents of an element. A co-parent is an element which has a common successor with the element and which is not a ascendant of the element. The iteration is in \(O(n^4)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose co-parents are requested
Returns: An iterator over the co-parents.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

neighbors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the neighbors of element (siblings or co-parents). The iteration is in \(O(n^4)\). Sub-classes may have overloaded this operation.

Parameters: element (PartiallyOrdered) – The element whose neighbors are requested
Returns: An iterator over the neighbors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

class galactic.algebras.poset.BasicPartiallyOrderedSet(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None)¶

Bases: galactic.algebras.poset.collections.AbstractPartiallyOrderedSet

The BasicPartiallyOrderedSet implements a set of PartiallyOrdered elements.

A BasicPartiallyOrderedSet instance stores its values in two dictionaries for the successors and the predecessors.

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

Example

>>> from galactic.algebras.poset import BasicPartiallyOrderedSet
>>> from galactic.examples.arithmetic import Integer
>>> poset = BasicPartiallyOrderedSet([
...     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.

Example

>>> sorted([int(element) for element in poset])
[5, 7, 15, 105, 210, 1155]

It’s possible to know the poset length.

Example

>>> len(poset)
6

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

Example

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

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

Example

>>> sorted([int(element) for element in poset.top()])
[210, 1155]
>>> sorted([int(element) for element in poset.bottom()])
[5, 7]

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

Example

>>> sorted([int(element) for element in poset.descendants(Integer(105))])
[210, 1155]
>>> sorted([int(element) for element in poset.filter(Integer(105))])
[105, 210, 1155]
>>> sorted([int(element) for element in poset.ascendants(Integer(105))])
[5, 7, 15]
>>> sorted([int(element) for element in poset.ideal(Integer(105))])
[5, 7, 15, 105]

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

Example

>>> sorted([int(element) for element in poset.successors(Integer(105))])
[210, 1155]
>>> sorted([int(element) for element in poset.predecessors(Integer(105))])
[7, 15]

It’s possible to iterate over the siblings, the co-parents and the neighbors of an element.

Example

>>> sorted([int(element) for element in poset.siblings(Integer(7))])
[]
>>> sorted([int(element) for element in poset.co_parents(Integer(7))])
[15]
>>> sorted([int(element) for element in poset.neighbors(Integer(7))])
[15]

It’s possible to enlarge a partially ordered set.

Example

>>> poset = poset + [Integer(13)]
>>> sorted([int(element) for element in poset])
[5, 7, 13, 15, 105, 210, 1155]

It’s possible to combine two partially ordered sets.

Example

>>> poset = poset @ BasicPartiallyOrderedSet([Integer(17)])
>>> sorted([int(element) for element in poset])
[5, 7, 13, 15, 17, 105, 210, 1155]

__init__(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None)¶

Initialise a BasicPartiallyOrderedSet instance.

Keyword Arguments: iterable (Iterable[PartiallyOrdered]) – An iterable of elements

__len__() → int ¶

Get the number of elements. This operation is in \(O(1)\).

Returns: the number of elements
Return type: int

__iter__() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the elements.

Returns: an iterator over the elements
Return type: Iterator[PartiallyOrdered]

__contains__(element: Any) → bool ¶

Get the membership of an element. This operation is in \(O(1)\).

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

__iadd__(iterable: Iterable[Any]) → galactic.algebras.poset.collections.BasicPartiallyOrderedSet¶

In-place enlarge the partially ordered set with an iterable of elements.

Keyword Arguments

iterable – An iterable of elements

Returns

BasicPartiallyOrderedSet – if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

top() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the top elements. The iteration is in \(O(n)\).

Returns: An iterator over the top elements.
Return type: Iterator[PartiallyOrdered]

bottom() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the bottom elements. The iteration is in \(O(n)\).

Returns: An iterator over the bottom elements.
Return type: Iterator[PartiallyOrdered]

successors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the successors of an element. The iteration is in \(O(n^2)\).

Parameters: element (PartiallyOrdered) – The element whose successors are requested
Returns: An iterator over the successors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

predecessors(element: galactic.algebras.poset.elements.PartiallyOrdered) → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the predecessors of an element. The iteration is in \(O(n^2)\).

Parameters: element (PartiallyOrdered) – The element whose predecessors are requested
Returns: An iterator over the predecessors.
Return type: Iterator[PartiallyOrdered]
Raises: ValueError: – If the element does not belong to the poset.

class galactic.algebras.poset.CompactPartiallyOrderedSet(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None)¶

Bases: galactic.algebras.poset.collections.AbstractPartiallyOrderedSet

The CompactPartiallyOrderedSet implements a set of PartiallyOrdered elements.

A CompactPartiallyOrderedSet instance stores its values in one set, keeping order of the elements passed during initialization.

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

Example

>>> from galactic.algebras.poset import CompactPartiallyOrderedSet
>>> from galactic.examples.arithmetic import Integer
>>> poset = CompactPartiallyOrderedSet([
...     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.

Example

>>> sorted([int(element) for element in poset])
[5, 7, 15, 105, 210, 1155]

It’s possible to know the poset length.

Example

>>> len(poset)
6

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

Example

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

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

Example

>>> sorted([int(element) for element in poset.top()])
[210, 1155]
>>> sorted([int(element) for element in poset.bottom()])
[5, 7]

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

Example

>>> sorted([int(element) for element in poset.descendants(Integer(105))])
[210, 1155]
>>> sorted([int(element) for element in poset.filter(Integer(105))])
[105, 210, 1155]
>>> sorted([int(element) for element in poset.ascendants(Integer(105))])
[5, 7, 15]
>>> sorted([int(element) for element in poset.ideal(Integer(105))])
[5, 7, 15, 105]

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

Example

>>> sorted([int(element) for element in poset.successors(Integer(105))])
[210, 1155]
>>> sorted([int(element) for element in poset.predecessors(Integer(105))])
[7, 15]

It’s possible to iterate over the siblings, the co-parents and the neighbors of an element.

Example

>>> sorted([int(element) for element in poset.siblings(Integer(7))])
[]
>>> sorted([int(element) for element in poset.co_parents(Integer(7))])
[15]
>>> sorted([int(element) for element in poset.neighbors(Integer(7))])
[15]

It’s possible to enlarge a partially ordered set.

Example

>>> poset = poset + [Integer(13)]
>>> sorted([int(element) for element in poset])
[5, 7, 13, 15, 105, 210, 1155]

It’s possible to combine two partially ordered sets.

Example

>>> poset = poset @ CompactPartiallyOrderedSet([Integer(17)])
>>> sorted([int(element) for element in poset])
[5, 7, 13, 15, 17, 105, 210, 1155]

__init__(iterable: Optional[Iterable[galactic.algebras.poset.elements.PartiallyOrdered]] = None)¶

Initialise a CompactPartiallyOrderedSet instance. The space used to store the poset is in \(O(n)\) where \(O(n)\) is the number of elements in the iterable collection.

Keyword Arguments: iterable (Iterable[PartiallyOrdered]) – An iterable of elements

__len__() → int ¶

Get the number of elements. This operation is in \(O(1)\).

Returns: the number of elements
Return type: int

__iter__() → Iterator[galactic.algebras.poset.elements.PartiallyOrdered]¶

Get an iterator over the elements.

Returns: an iterator over the elements
Return type: Iterator[PartiallyOrdered]

__contains__(element: Any) → bool ¶

Get the membership of an element. This operation is in \(O(1)\).

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

__iadd__(iterable: Iterable[Any]) → galactic.algebras.poset.collections.CompactPartiallyOrderedSet¶

In-place enlarge the partially ordered set with an iterable of elements.

Keyword Arguments

iterable – An iterable of elements

Returns

CompactPartiallyOrderedSet – if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

class galactic.algebras.poset.HasseDiagram(poset: galactic.algebras.poset.collections.PartiallyOrderedSet, renderer: galactic.algebras.poset.collections.GraphvizRenderer = <galactic.algebras.poset.collections.GraphvizRenderer object>)¶

Bases: object

The HasseDiagram is used for drawing Hass diagrams of partially ordered sets.

property source¶

Get the dot source for this partially ordered set.

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

class galactic.algebras.poset.GraphvizRenderer¶

Bases: object

The GraphvizRenderer class renders graphviz node and edge attributes for PartiallyOrdered instances.

initialize() → None ¶: Initialize the renderer.

node_attributes(node: galactic.algebras.poset.elements.PartiallyOrdered, _poset: galactic.algebras.poset.collections.PartiallyOrderedSet) → Dict[str, str]¶

Returns a dictionnary of graphviz attributes for a node.

Parameters

node (PartiallyOrdered) – The node to render
count (int) – The node order
successors (List[PartiallyOrdered]) – The successors of the node
predecessors (List[PartiallyOrdered]) – The predecessors of the node

Returns

A dictionnary of graphviz attributes

Return type

Dict[str, str]

edge_attributes(source: galactic.algebras.poset.elements.PartiallyOrdered, destination: galactic.algebras.poset.elements.PartiallyOrdered, poset: galactic.algebras.poset.collections.PartiallyOrderedSet) → Dict[str, str]¶

Returns a dictionnary of graphviz attributes for an node.

Parameters

source (PartiallyOrdered) – The edge source
destination (PartiallyOrdered) – The edge destination

Returns

A dictionnary of graphviz attributes

Return type

Dict[str, str]