Relation

The galactic.algebras.relational module defines types for relations.

and their implementations:

It defines two factories that have the ability to create sets for set operations:

It also defines classes for drawing diagrams into jupyter notebooks:

It also defines classes for drawing Sagittal diagrams into jupyter notebooks:

And classes for displaying binary relation into jupyter notebooks:

class AbstractBinaryRelation

AbstractBinaryRelation represents binary relation.

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

abstract property universes: Tuple[Container[_E], Container[_F]]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[Container[_E], Container[_F]]

property domain: Container[_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:

Container[_E]

property co_domain: Container[_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:

Container[_F]

abstract successors(element: _E) → Container[_F]

Get the successors of an element.

Parameters:

element (_E) – The element whose successors are requested

Returns:

The successors.

Return type:

Container[_F]

Raises:

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

abstract predecessors(element: _F) → Container[_E]

Get the predecessors of an element.

Parameters:

element (_F) – The element whose predecessors are requested

Returns:

The predecessors.

Return type:

Container[_E]

Raises:

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

class AbstractEndoRelation

An AbstractEndoRelation is a 2-relation from a universe to itself.

property co_domain: Container[_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:

Container[_F]

property domain: Container[_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:

Container[_E]

abstract predecessors(element: _F) → Container[_E]

Get the predecessors of an element.

Parameters:

element (_F) – The element whose predecessors are requested

Returns:

The predecessors.

Return type:

Container[_E]

Raises:

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

abstract successors(element: _E) → Container[_F]

Get the successors of an element.

Parameters:

element (_E) – The element whose successors are requested

Returns:

The successors.

Return type:

Container[_F]

Raises:

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

abstract property universes: Tuple[Container[_E], Container[_E]]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[Container[_E], Container[_E]]

class AbstractDirectedAcyclicGraph

AbstractDirectedAcyclicGraph represents directed acyclic graph.

property co_domain: Container[_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:

Container[_F]

property domain: Container[_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:

Container[_E]

abstract predecessors(element: _F) → Container[_E]

Get the predecessors of an element.

Parameters:

element (_F) – The element whose predecessors are requested

Returns:

The predecessors.

Return type:

Container[_E]

Raises:

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

abstract property sinks: Container[_E]

Get the sinks of this DAG.

Returns:

The sinks of this DAG.

Return type:

Container[_E]

abstract property sources: Container[_E]

Get the sources of this DAG.

Returns:

The sources of this DAG.

Return type:

Container[_E]

abstract successors(element: _E) → Container[_F]

Get the successors of an element.

Parameters:

element (_E) – The element whose successors are requested

Returns:

The successors.

Return type:

Container[_F]

Raises:

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

abstract property universes: Tuple[Container[_E], Container[_E]]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[Container[_E], Container[_E]]

class AbstractFiniteBinaryRelation

AbstractFiniteBinaryRelation represents binary relation.

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

property co_domain: AbstractSet[_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[_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 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 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: Tuple[AbstractSet[_E], AbstractSet[_F]]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[AbstractSet[_E], AbstractSet[_F]]

class AbstractFiniteEndoRelation

An AbstractFiniteEndoRelation is a 2-relation from a universe to itself.

property co_domain: AbstractSet[_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[_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 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 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: Tuple[AbstractSet[_E], AbstractSet[_E]]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[AbstractSet[_E], AbstractSet[_E]]

class AbstractFiniteDirectedAcyclicGraph

AbstractFiniteDirectedAcyclicGraph represents directed acyclic graph.

property co_domain: AbstractSet[_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[_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 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: AbstractSet[_E]

Get the sinks of this DAG.

Returns:

The sinks of this DAG.

Return type:

AbstractSet[_E]

abstract property sources: AbstractSet[_E]

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 universes: Tuple[AbstractSet[_E], AbstractSet[_E]]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[AbstractSet[_E], AbstractSet[_E]]

class FiniteBinaryRelation(*args: Iterable[Tuple[_E, _F]], domain: Iterable[_E] | None = None, co_domain: Iterable[_F] | None = None)

BinaryRelation implements AbstractFiniteBinaryRelation.

Examples

>>> from galactic.algebras.relational import FiniteBinaryRelation
>>> b = FiniteBinaryRelation[int, int](domain=[1, 2, 3], co_domain=[2, 3, 4])
>>> list(b)
[]
>>> list(b.domain)
[1, 2, 3]
>>> list(b.co_domain)
[2, 3, 4]
>>> list(b.universes[0])
[1, 2, 3]
>>> b |= [(1, 4), (3, 4)]
>>> list(b)
[(1, 4), (3, 4)]
>>> list(b.successors(1))
[4]
>>> list(b.predecessors(4))
[1, 3]
>>> len(b.predecessors(4))
2
__init__(*args: Iterable[Tuple[_E, _F]], domain: Iterable[_E] | None = None, co_domain: Iterable[_F] | None = None) → None

Initialise a BinaryRelation instance.

Parameters:

  • *args (Tuple[_E, _F]]) – A single iterable of couple.

  • domain (Iterable[_E], optional) – An iterable of initial values for the domain.

  • co_domain (Iterable[_F], optional) – An iterable of initial values for the co-domain.

Raises:

TypeError – If the there are more than 1 positional argument.

add(value: Tuple[_E, _F]) → None

Add a couple to the relation.

Parameters:

value (Tuple[_E, _F]) – The couple to add.

clear() → None

Clear the relation.

property co_domain: MutableSet[_F]

Get the co-domain of this binary relation.

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

Returns:

The domain of this binary relation.

Return type:

MutableSet[_F]

discard(value: Tuple[_E, _F]) → None

Discard a tuple from the relation.

Parameters:

value (Tuple[_E, _F]) – The couple to discard.

property domain: MutableSet[_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:

MutableSet[_E]

isdisjoint(other)

Return True if two sets have a null intersection.

pop()

Return the popped value. Raise KeyError if empty.

predecessors(element: _F) → MutableSet[_E]

Get the predecessors of an element.

Parameters:

element (_F) – The element whose predecessors are requested

Returns:

The predecessors.

Return type:

MutableSet[_E]

Raises:

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

remove(value)

Remove an element. If not a member, raise a KeyError.

successors(element: _E) → MutableSet[_F]

Get the successors of an element.

Parameters:

element (_E) – The element whose successors are requested

Returns:

The successors.

Return type:

MutableSet[_F]

Raises:

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

property universes: Tuple[MutableSet[_E], MutableSet[_F]]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[MutableSet[_E], MutableSet[_F]]

class FiniteBinaryRelationFactory

FiniteBinaryRelationFactory provides a _from_iterable() method.

This method is used by builtin set classes when set operations are executed.

Notes

See https://docs.python.org/fr/3/library/collections.abc.html.

class AbstractRelation

AbstractRelation represents finitary relation.

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

abstract property universes: Tuple[Container[Any], ...]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[Container[Any], ...]

class AbstractFiniteRelation

AbstractFiniteRelation represents finitary relation.

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

isdisjoint(other)

Return True if two sets have a null intersection.

abstract property universes: Tuple[AbstractSet[Any], ...]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[AbstractSet[Any], ...]

class FiniteRelation(*args: Iterable[Tuple[object, ...]], universes: Tuple[Iterable[object], ...] | None = None)

FiniteRelation implements AbstractFiniteRelation.

A relation is a subset of the Cartesian product between domains.

Examples

>>> from galactic.algebras.relational import FiniteRelation
>>> r = FiniteRelation([(1, 2, 3), (2, 3, 4), (3, 4, 5)])
>>> list(r)
[(1, 2, 3), (2, 3, 4), (3, 4, 5)]
>>> r.discard((2, 3, 4))
>>> list(r)
[(1, 2, 3), (3, 4, 5)]
>>> list(r.universes[0])
[1, 2, 3]
>>> list(r.universes[1])
[2, 3, 4]
>>> list(r.universes[2])
[3, 4, 5]
>>> r.universes[0].clear()
>>> list(r)
[]
>>> list(r.universes[0])
[]
>>> list(r.universes[1])
[2, 3, 4]
>>> list(r.universes[2])
[3, 4, 5]
__init__(*args: Iterable[Tuple[object, ...]], universes: Tuple[Iterable[object], ...] | None = None) → None

Initialise a FiniteRelation instance.

Parameters:
Raises:

TypeError – If there are more than 1 positional argument.

add(value: Tuple[object, ...]) → None

Add a tuple to the relation.

Parameters:

value (Tuple[object, ...]) – The tuple to add.

clear() → None

Clear the relation.

discard(value: Tuple[object, ...]) → None

Discard a tuple from the relation.

Parameters:

value (Tuple[object, ...]) – The tuple to discard.

isdisjoint(other)

Return True if two sets have a null intersection.

pop()

Return the popped value. Raise KeyError if empty.

remove(value)

Remove an element. If not a member, raise a KeyError.

property universes: Tuple[AbstractSet[object], ...]

Get the universes of this relation.

Returns:

The universes of this relation.

Return type:

Tuple[AbstractSet[Any], ...]

class FiniteRelationFactory

FiniteRelationFactory provides a _from_iterable() method.

This method is used by builtin set classes when set operations are executed.

Notes

See https://docs.python.org/fr/3/library/collections.abc.html.

class FiniteSelection(relation: AbstractFiniteRelation, criteria: Mapping[int, Any])

Select some tuple from a relation using criteria.

Examples

>>> from galactic.algebras.relational import FiniteRelation, FiniteSelection
>>> r = FiniteRelation([(1, 2, 3), (2, 3, 3), (1, 4, 5)])
>>> s = FiniteSelection(r, {2: 3})
>>> list(s)
[(1, 2, 3), (2, 3, 3)]
__init__(relation: AbstractFiniteRelation, criteria: Mapping[int, Any]) → None

Select some tuple from the relation using criteria.

Parameters:
isdisjoint(other)

Return True if two sets have a null intersection.

property universes: Tuple[AbstractSet[Any], ...]

Get the universe of this relation.

Returns:

The universes.

Return type:

Tuple[AbstractSet[Any], ...]

class FiniteProjection(relation: AbstractFiniteRelation, indexes: Iterable[int])

Project a relation.

Examples

>>> from galactic.algebras.relational import FiniteRelation, FiniteProjection
>>> r = FiniteRelation([(1, 2, 3), (2, 3, 3), (1, 4, 5)])
>>> p = FiniteProjection(r, [1, 2])
>>> list(p)
[(2, 3), (3, 3), (4, 5)]
__init__(relation: AbstractFiniteRelation, indexes: Iterable[int]) → None

Project a relation.

Parameters:
isdisjoint(other)

Return True if two sets have a null intersection.

property universes: Tuple[AbstractSet[Any], ...]

Get the universe of this relation.

Returns:

The universes.

Return type:

Tuple[AbstractSet[Any], ...]

class NodeRenderer

NodeRenderer renders graphviz nodes.

Notes

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

attributes(element: _E, index: int | None = None, current: bool = False, successors: AbstractSet[_F] | None = None, predecessors: AbstractSet[_F] | None = None) → Dict[str, str]

Get the dictionary of graphviz attributes for a node.

Parameters:

  • element (_E) – The element to render.

  • index (int, optional) – The element index.

  • current (bool) – is element the current element?

  • successors (AbstractSet[_F], optional) – The successors of the element.

  • predecessors (AbstractSet[_F], optional) – The predecessors of the element.

Returns:

A dictionary of graphviz attributes.

Return type:

Dict[str, str]

class EdgeRenderer

EdgeRenderer renders edge attributes.

Notes

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

attributes(source: _E, destination: _F, successors: AbstractSet[_F] | None = None, predecessors: AbstractSet[_E] | None = None) → Dict[str, str]

Get the dictionary of graphviz attributes for an edge.

Parameters:

  • source (_E) – The edge source

  • destination (_F) – The edge destination

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

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

Returns:

A dictionary of graphviz attributes

Return type:

Dict[str, str]

class GraphRenderer

GraphRenderer renders graph attributes.

Notes

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

add_destination(element: _F, index: int | None = None, current: bool = False, successors: AbstractSet[_E] | None = None, predecessors: AbstractSet[_E] | None = None) → None

Add a destination to the graph.

Parameters:

  • element (_F) – The destination to add.

  • 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: _E, destination: _F, successors: AbstractSet[_F] | None = None, predecessors: AbstractSet[_E] | None = None) → None

Add an edge to the graph.

Parameters:

  • source (_E) – The edge source

  • destination (_F) – The edge destination

  • 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: _E, index: int | None = None, current: bool = False, successors: AbstractSet[_F] | None = None, predecessors: AbstractSet[_F] | None = None) → None

Add a source to the graph.

Parameters:

  • element (_E) – The source to add.

  • 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]

Get the graphviz attributes for the graph.

Returns:

A dictionary of graphviz attributes

Return type:

Dict[str, str]

class BinaryTable(relation: AbstractFiniteBinaryRelation[_E, _F], domain_renderer: CellRenderer[_E] | None = None, co_domain_renderer: CellRenderer[_F] | None = None)

BinaryTable can render binary relation in jupyter notebook.

__init__(relation: AbstractFiniteBinaryRelation[_E, _F], domain_renderer: CellRenderer[_E] | None = None, co_domain_renderer: CellRenderer[_F] | None = None) → None

Initialise a BinaryTable instance.

Parameters:

  • relation (:class:`AbstractFiniteBinaryRelation[_E, _F]) – <AbstractFiniteBinaryRelation>` The binary relation.

  • domain_renderer (CellRenderer[_E]) – The domain renderer.

  • co_domain_renderer (CellRenderer[_E]) – The co-domain renderer.

property co_domain_renderer: CellRenderer[_F]

Get the co-domain renderer.

Returns:

The co-domain renderer.

Return type:

CellRenderer[_E]

property domain_renderer: CellRenderer[_E]

Get the domain renderer.

Returns:

The domain renderer.

Return type:

CellRenderer[_E]

property relation: AbstractFiniteBinaryRelation[_E, _F]

Get the relation.

Returns:

The underlying relation.

Return type:

AbstractFiniteBinaryRelation[_E, _F]

class CellRenderer

CellRenderer is used to render cell elements for a binary table.

render(element: _E, index: int) → str

Render an element.

Parameters:

  • element (_E) – The element to render

  • index (int) – The element index.

Returns:

The string representation of the element into a table.

Return type:

str

class SagittalDiagramRenderer

SagittalDiagramRenderer renders attributes.

it is used for a sagittal diagram.

Notes

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

add_destination(element: _F, index: int | None = None, current: bool = False, successors: AbstractSet[_E] | None = None, predecessors: AbstractSet[_E] | None = None) → None

Add a destination to the graph.

Parameters:

  • element (_F) – The destination to add.

  • 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: _E, destination: _F, successors: AbstractSet[_F] | None = None, predecessors: AbstractSet[_E] | None = None) → None

Add an edge to the graph.

Parameters:

  • source (_E) – The edge source

  • destination (_F) – The edge destination

  • 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: _E, index: int | None = None, current: bool = False, successors: AbstractSet[_F] | None = None, predecessors: AbstractSet[_F] | None = None) → None

Add a source to the graph.

Parameters:

  • element (_E) – The source to add.

  • 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]

Get the graphviz attributes for the graph.

Returns:

A dictionary of graphviz attributes for the graph

Return type:

dict

class SagittalDiagram(relation: AbstractFiniteBinaryRelation[_E, _F], graph_renderer: SagittalDiagramRenderer[_E, _F] | None = None, domain_renderer: NodeRenderer[_E, _F] | None = None, co_domain_renderer: NodeRenderer[_F, _E] | None = None, edge_renderer: EdgeRenderer[_E, _F] | None = None)

SagittalDiagram is used for drawing Sagittal diagrams.

It is useful for visualizing binary relations in jupyter notebooks.

__init__(relation: AbstractFiniteBinaryRelation[_E, _F], graph_renderer: SagittalDiagramRenderer[_E, _F] | None = None, domain_renderer: NodeRenderer[_E, _F] | None = None, co_domain_renderer: NodeRenderer[_F, _E] | None = None, edge_renderer: EdgeRenderer[_E, _F] | None = None) → None

Initialise a SagittalDiagram instance.

Parameters:
property co_domain_renderer: NodeRenderer[_F, _E]

Get the co-domain renderer.

Returns:

The co-domain renderer.

Return type:

NodeRenderer[_F, _E]

property domain_renderer: NodeRenderer[_E, _F]

Get the domain renderer.

Returns:

The domain renderer.

Return type:

NodeRenderer[_E, _F]

property edge_renderer: EdgeRenderer[_E, _F]

Get the edge renderer.

Returns:

The edge renderer.

Return type:

EdgeRenderer[_E, _F]

property graph_renderer: GraphRenderer[_E, _F]

Get the graph renderer.

Returns:

The graph renderer.

Return type:

GraphRenderer[_E, _F]

property relation: AbstractFiniteBinaryRelation[_E, _F]

Get the relation.

Returns:

The underlying relation.

Return type:

AbstractFiniteBinaryRelation[_E, _F]

property source: str

Get the graphviz source for this partially ordered set.

Returns:

The graphviz output for this partially ordered set.

Return type:

str