Relation

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

• AbstractFinitaryRelation;

• AbstractBinaryRelation;

• AbstractEndoRelation;

• AbstractDirectedAcyclicGraph.

and their implementations:

• FinitaryRelation;

• BinaryRelation;

• Selection;

• Projection.

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

• FinitaryRelationFactory;

• BinaryRelationFactory.

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

• SagittalDiagram;

• NodeRenderer;

• EdgeRenderer.

And classes for displaying binary relation into jupyter notebooks:

• BinaryTable;

• CellRenderer.

class AbstractFinitaryRelation(*args, **kwds)

The AbstractFinitaryRelation class represents finitary relation.

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

isdisjoint(other)

Return True if two sets have a null intersection.

abstract property universes

Get the universes of this relation.

Returns

The universes of this relation.

Return type

Tuple[AbstractSet[Any], ...]

class FinitaryRelation(*args: Iterable[Tuple[Hashable, …]], universes: Optional[Tuple[Iterable[Hashable], …]] = None)

The FinitaryRelation class implements AbstractFinitaryRelation.

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

Examples

>>> from galactic.algebras.relational import FinitaryRelation
>>> r = FinitaryRelation([(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[Hashable, …]], universes: Optional[Tuple[Iterable[Hashable], …]] = None) → None

Initialise a FinitaryRelation instance.

Parameters

• args (Iterable[Tuple[Hashable, ...]]) – A single iterable of tuple.

• universes (Tuple[Iterable[Hashable], ...]) – Some initial values for the universes.

add(element: Tuple[Hashable, …]) → None

Add a tuple to the relation.

Parameters

element (Tuple[Hashable, ...]) – The tuple to add.

clear() → None

Clear the relation.

discard(element: Tuple[Hashable, …]) → None

Discard a tuple from the relation.

Parameters

element (Tuple[Hashable, ...]) – 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

Get the universes of this relation.

Returns

The universes of this relation.

Return type

Tuple[AbstractSet[Any], ...]

class FinitaryRelationFactory

The FinitaryRelationFactory 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 AbstractBinaryRelation(*args, **kwds)

The AbstractBinaryRelation class represents binary relation.

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

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

Get the universes of this relation.

Returns

The universes of this relation.

Return type

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

class AbstractEndoRelation(*args, **kwds)

An AbstractEndoRelation is a binary relation from an universe to itself.

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

Get the universes of this relation.

Returns

The universes of this relation.

Return type

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

class AbstractDirectedAcyclicGraph(*args, **kwds)

The AbstractDirectedAcyclicGraph represents directed acyclic graph.

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 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 universes

Get the universes of this relation.

Returns

The universes of this relation.

Return type

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

class BinaryRelation(*args: Iterable[Tuple[_G, _H]], domain: Optional[Iterable[_G]] = None, co_domain: Optional[Iterable[_H]] = None)

The BinaryRelation class implements AbstractBinaryRelation.

Examples

>>> from galactic.algebras.relational import BinaryRelation
>>> b = BinaryRelation[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[_G, _H]], domain: Optional[Iterable[_G]] = None, co_domain: Optional[Iterable[_H]] = None) → None

Initialise a BinaryRelation instance.

Parameters

• args (Iterable[Tuple[_G, _H]]) – A single iterable of couple.

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

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

add(element: Tuple[_G, _H]) → None

Add a couple to the relation.

Parameters

element (Tuple[_G, _H]) – The couple to add.

clear() → None

Clear the relation.

property co_domain

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

discard(element: Tuple[_G, _H]) → None

Discard a tuple from the relation.

Parameters

element (Tuple[_G, _H]) – The couple to discard.

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

MutableSet[_G]

isdisjoint(other)

Return True if two sets have a null intersection.

pop()

Return the popped value. Raise KeyError if empty.

predecessors(element: _H) → MutableSet[_G]

Get the predecessors of an element.

Parameters

element (_H) – The element whose predecessors are requested

Returns

The predecessors.

Return type

MutableSet[_G]

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: _G) → MutableSet[_H]

Get the successors of an element.

Parameters

element (_G) – The element whose successors are requested

Returns

The successors.

Return type

MutableSet[_H]

Raises

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

property universes

Get the universes of this relation.

Returns

The universes of this relation.

Return type

Tuple[MutableSet[_G], MutableSet[_H]]

class BinaryRelationFactory(*args, **kwds)

The BinaryRelationFactory 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 Selection(relation: galactic.algebras.relational.AbstractFinitaryRelation, criteria: Mapping[int, Any])

Select some tuple from a relation using criteria.

Examples

>>> from galactic.algebras.relational import FinitaryRelation, Selection
>>> r = FinitaryRelation([(1, 2, 3), (2, 3, 3), (1, 4, 5)])
>>> s = Selection(r, {2: 3})
>>> list(s)
[(1, 2, 3), (2, 3, 3)]

__init__(relation: galactic.algebras.relational.AbstractFinitaryRelation, criteria: Mapping[int, Any]) → None

Select some tuple from the relation using criteria.

Parameters

criteria (Mapping[int, Any]) – A set of criterion

isdisjoint(other)

Return True if two sets have a null intersection.

property universes

Get the universe of this finitary relation.

Returns

The universes.

Return type

Tuple[AbstractSet[Any], ...]

class Projection(relation: galactic.algebras.relational.AbstractFinitaryRelation, indexes: Iterable[int])

Project a relation.

Examples

>>> from galactic.algebras.relational import FinitaryRelation, Projection
>>> r = FinitaryRelation([(1, 2, 3), (2, 3, 3), (1, 4, 5)])
>>> p = Projection(r, [1, 2])
>>> list(p)
[(2, 3), (3, 3), (4, 5)]

__init__(relation: galactic.algebras.relational.AbstractFinitaryRelation, indexes: Iterable[int]) → None

Project a relation.

Parameters

indexes (Iterable[int]) – An iterable of indexes.

isdisjoint(other)

Return True if two sets have a null intersection.

property universes

Get the universe of this finitary relation.

Returns

The universes.

Return type

Tuple[AbstractSet[Any], ...]

class SagittalDiagram(relation: galactic.algebras.relational.AbstractBinaryRelation[_E, _F], domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_E, _F]] = None, co_domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_F, _E]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_E, _F]] = None)

The SagittalDiagram class is used for drawing Sagittal diagrams.

It is useful for visualizing binary relations in jupyter notebooks.

__init__(relation: galactic.algebras.relational.AbstractBinaryRelation[_E, _F], domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_E, _F]] = None, co_domain_renderer: Optional[galactic.algebras.relational.NodeRenderer[_F, _E]] = None, edge_renderer: Optional[galactic.algebras.relational.EdgeRenderer[_E, _F]] = None) → None

Initialise a SagittalDiagram instance.

Parameters

• relation (AbstractBinaryRelation[_E, _F]) – The binary relation.

• domain_renderer (NodeRenderer[_E, _F]) – The domain renderer.

• co_domain_renderer (NodeRenderer[_F, _E]) – The co-domain renderer.

• edge_renderer (EdgeRenderer[_E, _F]) – The co-domain renderer.

attributes() → Dict[str, str]

Return a dictionary of graphviz attributes for the graph.

property co_domain_renderer

Get the co-domain renderer.

Returns

The co-domain renderer.

Return type

NodeRenderer[_F, _E]

property domain_renderer

Get the domain renderer.

Returns

The domain renderer.

Return type

NodeRenderer[_E, _F]

property edge_renderer

Get the edge renderer.

Returns

The edge renderer.

Return type

EdgeRenderer[_E, _F]

property relation

Get the relation.

Returns

The underlying relation.

Return type

AbstractBinaryRelation[_E, _F]

property source

Get the graphviz source for this partially ordered set.

Returns

The graphviz output for this partially ordered set.

Return type

str

class NodeRenderer(*args, **kwds)

The NodeRenderer class renders graphviz nodes.

Notes

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

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

Return a dictionary of graphviz attributes for a node.

Parameters

• element (_E) – The element to render.

• index (Optional[int]) – The element index.

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

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

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

Returns

A dictionary of graphviz attributes.

Return type

Dict[str, str]

class EdgeRenderer(*args, **kwds)

The EdgeRenderer class renders edge attributes.

Notes

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

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

Return a dictionary of graphviz attributes for an edge.

Keyword Arguments

• source (_E) – The edge source

• destination (_F) – The edge destination

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

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

Returns

A dictionary of graphviz attributes

Return type

Dict[str, str]

class BinaryTable(relation: galactic.algebras.relational.AbstractBinaryRelation[_E, _F], domain_renderer: Optional[galactic.algebras.relational.CellRenderer[_E]] = None, co_domain_renderer: Optional[galactic.algebras.relational.CellRenderer[_F]] = None)

The BinaryTable class can render binary relation in jupyter notebook.

__init__(relation: galactic.algebras.relational.AbstractBinaryRelation[_E, _F], domain_renderer: Optional[galactic.algebras.relational.CellRenderer[_E]] = None, co_domain_renderer: Optional[galactic.algebras.relational.CellRenderer[_F]] = None) → None

Initialise a BinaryTable instance.

Parameters

• relation (AbstractBinaryRelation[_E, _F]) – The binary relation.

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

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

property co_domain_renderer

Get the co-domain renderer.

Returns

The co-domain renderer.

Return type

CellRenderer[_E]

property domain_renderer

Get the domain renderer.

Returns

The domain renderer.

Return type

CellRenderer[_E]

property relation

Get the relation.

Returns

The underlying relation.

Return type

AbstractBinaryRelation[_E, _F]

class CellRenderer(*args, **kwds)

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

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

Render an element.

Keyword Arguments

• element (_E) – The element to render

• index (int) – The element index.

Returns

The string representation of the element into a table.

Return type

str