Collections¶

The galactic.algebras.poset.collections module defines essential type for representing partially ordered sets.

Complexities are given in function of the number of elements \(n\).

class galactic.algebras.poset.collections.PartiallyOrderedSet¶

Bases: typing.AbstractSet

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

abstract __iadd__(iterable)¶

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

Keyword Arguments

iterable – An iterable of elements

Returns

class:PartiallyOrderedSet[P] – <galactic.algebras.poset.collections.PartiallyOrderedSet> if this addition succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __add__(iterable)¶

Enlarge the partially ordered set with an iterable of elements.

Keyword Arguments

iterable – An iterable of elements

Returns

class:PartiallyOrderedSet[P] – <galactic.algebras.poset.collections.PartiallyOrderedSet> if this addition succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __imatmul__(other)¶

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

Parameters

other – The other partially ordered set

Returns

class:PartiallyOrderedSet[P] – <galactic.algebras.poset.collections.PartiallyOrderedSet> if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __matmul__(other)¶

Combine the partially ordered set with another partially ordered set.

Parameters

other – The other partially ordered set

Returns

class:PartiallyOrderedSet[P] – <galactic.algebras.poset.collections.PartiallyOrderedSet> if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

abstract __copy__()¶

Copy the partially ordered set.

Returns: The copied partially ordered set
Return type: PartiallyOrderedSet

abstract top() → Iterator[P]¶

Get an iterator over the top elements.

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

abstract bottom() → Iterator[P]¶

Get an iterator over the bottom elements.

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

abstract upper_limit(limit: P, strict: bool = False) → Collection[P]¶

Get the collection of elements lesser than a limit.

Parameters

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

Returns

The collection over the selected elements.

Return type

Collection[P]

abstract lower_limit(limit: P, strict: bool = False) → Collection[P]¶

Get the collection of elements greater than a limit.

Parameters

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

Returns

The collection over the selected elements.

Return type

Collection[P]

abstract following(limit: P) → Iterator[P]¶

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

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

abstract preceding(limit: P) → Iterator[P]¶

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

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

abstract successors(element: P) → Iterator[P]¶

Get an iterator over the successors of an element.

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

abstract predecessors(element: P) → Iterator[P]¶

Get an iterator over the predecessors of an element.

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

abstract descendants(element: P) → Iterator[P]¶

Get an iterator over the descendants of an element.

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

abstract filter(element: P) → Iterator[P]¶

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

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

abstract ascendants(element: P) → Iterator[P]¶

Get an iterator over the ascendants of an element.

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

abstract ideal(element: P) → Iterator[P]¶

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

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

abstract siblings(element: P) → Iterator[P]¶

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 (P) – The element whose siblings are requested
Returns: An iterator over the siblings.
Return type: Iterator[P]
Raises: ValueError: – If the element does not belong to the poset.

abstract co_parents(element: P) → Iterator[P]¶

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 (P) – The element whose co-parents are requested
Returns: An iterator over the co-parents.
Return type: Iterator[P]
Raises: ValueError: – If the element does not belong to the poset.

abstract neighbors(element: P) → Iterator[P]¶

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

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

class galactic.algebras.poset.collections.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) → bool¶

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

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

__copy__()¶

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

__add__(iterable)¶

Enlarge the partially ordered set with an iterable of elements.

Keyword Arguments

iterable – An iterable of elements

Returns

class:AbstractPartiallyOrderedSet[P] – <galactic.algebras.poset.collections.AbstractPartiallyOrderedSet> if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

__imatmul__(other)¶

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

Parameters

other – The other partially ordered set

Returns

class:AbstractPartiallyOrderedSet[P] – <galactic.algebras.poset.collections.AbstractPartiallyOrderedSet> if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

__matmul__(other)¶

Combine the partially ordered set with another partially ordered set.

Parameters

other – The other partially ordered set

Returns

class:AbstractPartiallyOrderedSet[P] – <galactic.algebras.poset.collections.AbstractPartiallyOrderedSet> if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

top() → Iterator[P]¶

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[P]

bottom() → Iterator[P]¶

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[P]

class Limit(poset: galactic.algebras.poset.collections.PartiallyOrderedSet[P], limit: P, strict: bool = False)¶

Bases: typing.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: P, strict: bool = False) → Collection[P]¶

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

Parameters

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

Returns

A collection over the selected elements.

Return type

Collection[P]

lower_limit(limit: P, strict: bool = False) → Iterator[P]¶

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

Parameters

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

Returns

A collection over the selected elements.

Return type

Collection[P]

following(limit: P) → Iterator[P]¶

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 (P) – The upper limit
Returns: An iterator over the following elements.
Return type: Iterator[P]

preceding(limit: P) → Iterator[P]¶

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 (P) – The lower limit
Returns: An iterator over the preceding elements.
Return type: Iterator[P]

successors(element: P) → Iterator[P]¶

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 (P) – The element whose successors are requested
Returns: An iterator over the successors.
Return type: Iterator[P]
Raises: ValueError: – If the element does not belong to the poset.

predecessors(element: P) → Iterator[P]¶

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 (P) – The element whose predecessors are requested
Returns: An iterator over the predecessors.
Return type: Iterator[P]
Raises: ValueError: – If the element does not belong to the poset.

descendants(element: P) → Iterator[P]¶

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

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

filter(element: P) → Iterator[P]¶

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

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

ascendants(element: P) → Iterator[P]¶

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

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

ideal(element: P) → Iterator[P]¶

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

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

siblings(element: P) → Iterator[P]¶

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 (P) – The element whose siblings are requested
Returns: An iterator over the siblings.
Return type: Iterator[P]
Raises: ValueError: – If the element does not belong to the poset.

co_parents(element: P) → Iterator[P]¶

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 (P) – The element whose co-parents are requested
Returns: An iterator over the co-parents.
Return type: Iterator[P]
Raises: ValueError: – If the element does not belong to the poset.

neighbors(element: P) → Iterator[P]¶

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 (P) – The element whose neighbors are requested
Returns: An iterator over the neighbors.
Return type: Iterator[P]
Raises: ValueError: – If the element does not belong to the poset.

class galactic.algebras.poset.collections.HasseDiagram(poset: galactic.algebras.poset.collections.PartiallyOrderedSet[P], **options)¶

Bases: typing.Generic

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

dot()¶

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.collections.CompactPartiallyOrderedSet(iterable: Iterable[P] = 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.collections import CompactPartiallyOrderedSet
>>> from galactic.examples.arithmetic.algebras 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: Iterable[P] = 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[P]) – 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[P]¶

Get an iterator over the elements.

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

__contains__(element) → 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)¶

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

Keyword Arguments

iterable – An iterable of elements

Returns

class:CompactPartiallyOrderedSet[P] – <galactic.algebras.poset.collections.CompactPartiallyOrderedSet> if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

class galactic.algebras.poset.collections.BasicPartiallyOrderedSet(iterable: Iterable[P] = 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.collections import BasicPartiallyOrderedSet
>>> from galactic.examples.arithmetic.algebras 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: Iterable[P] = None)¶

Initialise a BasicPartiallyOrderedSet instance.

Keyword Arguments: iterable (Iterable[P]) – 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[P]¶

Get an iterator over the elements.

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

__contains__(element) → 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)¶

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

Keyword Arguments

iterable – An iterable of elements

Returns

class:BasicPartiallyOrderedSet[P] – <galactic.algebras.poset.collections.BasicPartiallyOrderedSet> if this combination succeeds.
NotImplementedType – if the operation is not implemented between the two objects

top() → Iterator[P]¶

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

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

bottom() → Iterator[P]¶

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

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

successors(element: P) → Iterator[P]¶

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

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

predecessors(element: P) → Iterator[P]¶

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

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