Getting Started
The Rel class implements a low-level mutable data structure to store a finite relation between finite sets:
\[R \subseteq X_1 \times ... \times X_n\]
It presumes that the component sets \(X_1,...,X_n\) are finite zero-based contiguous integer ranges, in the form \(X_j = \lbrace 0,...,s_j-1\rbrace\). The tuple \((s_1,...,s_n)\) of component set sizes is referred to as the shape of the relation \(R\), while the tuples \((x_1,...x_n) \in R\) are referred to as its entries.
Relations are implemented using 64-bit roaring bitmaps to store the underlying set of entries.
Install
You can install the latest release from PyPI as follows:
$ pip install roaringrel
Usage
All functionality of the library is accessible from the Rel class:
>>> from roaringrel import Rel
You can create a relation by specifying a shape for it, as a tuple of positive integers:
>>> Rel((2, 3, 4))
<Rel of shape (2, 3, 4) with 0 entries>
The code above creates a ternary relation \(R\), initially empty:
You can also specify initial entries for the relation at creation:
>>> Rel((2, 3, 4), [(0, 0, 0), (1, 1, 1), (1, 2, 3)])
<Rel of shape (2, 3, 4) with 3 entries>
The code above creates a ternary relation \(R\), initially with the given three entries:
Relations are sized iterable containers of entries:
>>> r = Rel((2, 3, 4), [(0, 0, 0), (1, 1, 1), (1, 2, 3)])
>>> len(r)
3
>>> list(r)
[(0, 0, 0), (1, 1, 1), (1, 2, 3)]
>>> (0, 0, 0) in r
True
Relations support basic binary operators as sets of entries, restricted to operations having the same shape:
>>> a = Rel((2, 3, 4), [(0, 0, 0), (1, 2, 3)])
>>> b = Rel((2, 3, 4), [(0, 0, 0), (1, 1, 1)])
>>> a&b # intersection
<Rel of shape (2, 3, 4) with 1 entries>
>>> list(a&b)
[(0, 0, 0)]
>>> a|b # union
<Rel of shape (2, 3, 4) with 3 entries>
>>> list(a|b)
[(0, 0, 0), (1, 1, 1), (1, 2, 3)]
>>> a^b # symmetric difference
<Rel of shape (2, 3, 4) with 2 entries>
>>> list(a^b)
[(1, 1, 1), (1, 2, 3)]
>>> a-b # difference
<Rel of shape (2, 3, 4) with 1 entries>
>>> list(a-b)
[(1, 2, 3)]
Relations support comparison as sets of entries, with subset comparison restricted to relations having the same shape:
>>> a == b # equality comparison
False
>>> a&b <= b # subset comparison
True
>>> a&b < b # strict subset comparison
True
Relations are mutable, with support for addition, removal and flipping of individual elements:
>>> a = Rel((2, 3, 4), [(0, 0, 0), (1, 2, 3)])
>>> a.add((1, 1, 1)) # add entry
>>> list(a)
[(0, 0, 0), (1, 1, 1), (1, 2, 3)]
>>> a.remove((1, 2, 3)) # remove entry
>>> list(a)
[(0, 0, 0), (1, 1, 1)]
>>> a.flip((0, 0, 0)) # flip on existing entry: remove
>>> list(a)
[(1, 1, 1)]
>>> a.flip((0, 0, 0)) # flip on missing entry: add
>>> list(a)
[(0, 0, 0), (1, 1, 1)]
>>> a.remove((1, 2, 3)) # remove entry which is not in the relation
Traceback (most recent call last):
...
KeyError: (1, 2, 3)
The update operations enable addition, removal and flipping (symmetric difference) of multiple entries at once:
>>> a = Rel((2, 3, 4), [(0, 0, 0), (1, 2, 3)])
>>> a.update([(1, 1, 1), (1, 2, 2)]) # add multiple entries
>>> list(a)
[(0, 0, 0), (1, 1, 1), (1, 2, 2), (1, 2, 3)]
>>> a.difference_update([(0, 0, 0), (0, 1, 1)]) # remove multiple entries
>>> list(a)
[(1, 1, 1), (1, 2, 2), (1, 2, 3)]
>>> a.symmetric_difference_update([(1, 2, 3), (0, 1, 1)]) # flip multiple entries
>>> list(a)
[(0, 1, 1), (1, 1, 1), (1, 2, 2)]
Relations support inplace versions of the binary operation, mutating the lhs relation:
>>> a = Rel((2, 3, 4), [(0, 0, 0), (1, 2, 3)])
>>> b = Rel((2, 3, 4), [(0, 0, 0), (1, 1, 1)])
>>> a ^= b
>>> list(a)
[(1, 1, 1), (1, 2, 3)]
>>> a &= b
>>> list(a)
[(1, 1, 1)]
>>> a |= b
>>> list(a)
[(0, 0, 0), (1, 1, 1)]
>>> a -= b
>>> list(a)
[]
The copy method can be used to obtain an independently mutable copy of a relation:
>>> r = Rel((2, 3, 4), [(0, 0, 0), (1, 1, 1), (1, 2, 3)])
>>> s = r.copy()
>>> r == s
True
>>> list(r)
[(0, 0, 0), (1, 1, 1), (1, 2, 3)]
>>> list(s)
[(0, 0, 0), (1, 1, 1), (1, 2, 3)]
>>> r.remove((0, 0, 0))
>>> r == s
False
>>> list(r)
[(1, 1, 1), (1, 2, 3)]
>>> list(s)
[(0, 0, 0), (1, 1, 1), (1, 2, 3)]
Relations can be pickled, and unpickle into independently mutable relations:
>>> import pickle
>>> r = Rel((2, 3, 4), [(0, 0, 0), (1, 1, 1), (1, 2, 3)])
>>> s = pickle.loads(pickle.dumps(r))
>>> r == s
True
>>> s.remove((0, 0, 0))
>>> r == s
False
Entry normalisation
RoaringRel is a low-level library, intended for use in performance-critical code, so the methods which take entries never validate them. Entries are normalised instead: each element is reduced modulo the size of its own component set, so that negative elements index from the end of the component set, as is usual in Python, and out-of-range elements wrap around.
>>> r = Rel((2, 3, 4))
>>> r.add((0, -1, -1)) # negative elements index from the end
>>> list(r)
[(0, 2, 3)]
>>> r.add((0, 5, 0)) # out-of-range elements wrap around
>>> list(r)
[(0, 2, 0), (0, 2, 3)]
An entry shorter than the shape has its missing trailing elements taken to be zero, while an entry longer than the shape has its surplus elements ignored:
>>> r = Rel((2, 3, 4))
>>> r.add((1,)) # same as (1, 0, 0)
>>> list(r)
[(1, 0, 0)]
>>> r.add((0, 1, 2, 9, 9)) # same as (0, 1, 2)
>>> list(r)
[(0, 1, 2), (1, 0, 0)]
Because every element is reduced into the range of its own component set, normalisation is a total operation: no entry whatsoever can take a relation outside of its own shape, so an out-of-range entry cannot corrupt the relation. What it does instead is silently address a different, valid entry.
Where that tradeoff is not acceptable, the validate_entry method checks an entry against the shape of the relation:
>>> r = Rel((2, 3, 4))
>>> r.validate_entry((0, 1, 2)) # valid entry: no error
>>> r.validate_entry((0, 5, 0)) # invalid entry: error
Traceback (most recent call last):
...
ValueError: Expected element at index 1 to be in range(3), found 5 instead.
This method is never called internally, so validation is entirely opt-in: code which understands the tradeoff above pays nothing for it.