API - semilattices

Classes

Class	Description
ComplementSparseKeysSet	This is used to handle the sparse_keys (admissible children) of the root.
CoordinateDict	Sorted dictionary of coordinates. It defaults to zero for missing elements.
DefaultDict	This is a dictionary which defaults to a prescribed value if a key is missing.
LevelsPartition	Dictionary for keeping track of subsets of a coordinate semilattice at each level.
MixedElement	An element whose comparability can change.
MixedSortedContainer	This is a container where some elements are sorted if assigned a label(s), otherwise are just stored.
SpaceWeightDict	This is a dictionary that default to 1 for missing elements.
StaticElement	An element whose comparability cannot change.
ArgumentsException
ChildAlreadyExists
CorruptedSemilatticeException
DecreasingSemilatticeException
EdgeException
EmptySemilatticeException
FrontierException
GraphException
InitializationException
InvalidChild
InvalidDimension
InvalidParent
InvalidVertex
InvalidVertexConstructor
IteratorException
LabelsException
SemilatticeException
SparseKeysException
ViolatesDecreasingProperty
VertexException
SemilatticeIterable	Base class defining an iterable for the semilattice.
BreadthFirstSemilatticeIterable	Breadth first iterable for the semilattice.
DepthFirstSemilatticeIterable	Depth first iterable for the semilattice.
CoupledSemilatticeIterable	Base class defining an iterable for two semilattices at the same time.
CoupledIntersectionSemilatticeIterable	Iterable over the intersection of two semilattices.
BreadthFirstCoupledIntersectionSemilatticeIterable	Breadth first iterable over the intersection of two semilattices.
DepthFirstCoupledIntersectionSemilatticeIterable	Depth first iterable over the intersection of two semilattices.
CoupledUnionSemilatticeIterable	Iterable over the union of two semilattices.
BreadthFirstCoupledUnionSemilatticeIterable	Iterable over the union of two semilattices.
DepthFirstCoupledUnionSemilatticeIterable	Iterable over the union of two semilattices.
LevelsIterable	Iterable over the semilattice vertices by level.
ParentsPowersetIterable	Iterable over the vertices that are the ancestors defined by the powerset of the parent directions of v.
SLO	Base object for every object in the module.
SemilatticeVertex	A vertex that can have multiple parents.
SparseVertex	A vertex that admit children only in a prescribed set of directions.
CoordinateVertex	A semilattice vertex that have the concept of directional distance from the root.
LabeledVertex	Labeled Vertices are provided an optional label(s).
LabeledSparseVertex	A vertex that is LabeledVertex and SparseVertex.
SparseCoordinateVertex	A vertex that is CoordinateVertex and SparseVertex.
LabeledCoordinateVertex	A vertex that is LabeledVertex and CoordinateVertex.
SparseLabeledCoordinateVertex	A vertex that is LabeledVertex, CoordinateVertex and SparseVertex.
Semilattice	An (order-) semilattice is a rooted connected directed acyclic graph resembling the structure of a tree, i.e. it has a depth/levels. However, unlike a tree, each vertex can have multiple parents.
CoordinateSemilattice	A semilattice with pre-defined dimension.
DecreasingCoordinateSemilattice	A DecreasingCoordinateSemilattice is a semilattice \((\mathcal{S}\,\le)\) that is closed under meets,
SortedCoordinateSemilattice	A SortedCoordinateSemilattice is a semilattice with Labeled vertices.
SortedDecreasingCoordinateSemilattice

Functions

Function	Description
adjacency_mat_eq	Checks equality between two adjacency matrices
adjacency_mat	Creates an adjacency matrix defining the directed edges (in or out) between vertices and other_vertices
setLogLevel	Set the log level for all existing and new objects related to the semilattices module
deprecate
cprofile
any_kwarg_required
default_kwargs
exactly_one_kwarg_optional
exactly_one_kwarg_required
invalid_type
optional_kwargs_types
require_kwargs
required_kwargs
valid_type
argsort
create_lp_semilattice	Create the semilattice of all vertices in the \(\ell^p\) spherical sector of a given norm
permute	Creates a new semilattice with permuted dimensions

Documentation

semilattices.adjacency_mat_eq(mat, other_mat)

Checks equality between two adjacency matrices

semilattices.adjacency_mat(vertices, other_vertices, mat_type=<class 'scipy.sparse.coo.coo_matrix'>)

Creates an adjacency matrix defining the directed edges (in or out) between vertices and other_vertices

class semilattices.ComplementSparseKeysSet(*args, **kwargs)

This is used to handle the sparse_keys (admissible children) of the root.

Instead of storing the sparse keys of the root, one stores the children of the root which happens implicitely when one tries to remove the child from this data structure. All set operations should be operations that are complements with respect to the set of integers [0, self.max_dim - 1].

__init__(*args, **kwargs)

Keyword Arguments:  max_dim (int) – maximum dimension of the associated semilattice.

add(key)

Adding to the ComplementSparseKeysSet is simply removing from the set, if the key existed in the first place.

clear()

Clearing the ComplementSparseKeysSet is is equivalent to removing all elements from _keys

copy()

Returns a deep copy

discard(key)

Removing from the ComplementSparseKeysSet is simply adding to the set

max_dim

Maximum dimension for the complement sparse key set data structure.

remove(key)

Removes a key.

Removing from the ComplementSparseKeysSet corresponds to adding to the set

class semilattices.CoordinateDict(obj=None, *args, **kwargs)

Sorted dictionary of coordinates. It defaults to zero for missing elements.

We interpret a key as a dimension and a values as the coordinate in the key dimension. A coordinate can be used to identify the position of a vertex in a CoordinateSemilattice. In particular in this case, each element key, value indicates that a vertex is value steps away in the key direction from the root vertex.

copy()

Creates a copy of the object.

By default, creates a copy that is an instance of ImmutableCoordinateDict. If immutable == False, then it creates an instance of CoordinateDict. This is used when creating a neighboring vertex.

dims_sorted

Sorted list of dimensions #should be a tuple, but not worth the comptational cost of creating the tuple?

Type:list

l0

\(l_{0}\) quasi-norm of the coordinates.

Type:float

l1

\(l_1\) norm of the coordinates.

Type:float

linf

\(l_{\infty}\) norm of the coordinates.

Type:float

lp(p, w=None)

Returns the \(l_p\) norm (\(p\geq 1\)) or quasi-norm (\(0\leq p < 1\)) of the coordinates.

For unweighted spaces this is

\[\Vert {\bf c} \Vert_p = \left( \sum_{i=1}^d {\bf c}_i^p \right)^{1/p} \;.\]

For weighted spaces this is

\[\Vert {\bf c} \Vert_p = \left( \sum_{i=1}^d {\bf w}_i {\bf c}_i^p \right)^{1/p} \;.\]

Parameters:

• p (float) – the order of the norm/quasi-norm
• w (list) – weights for each dimension

nnz

Number of non-zero coordinates.

See also

l0()

permute(p)

Permutes the keys of the coordinates

Given the naturally ordered coordinates {0:c[0], 1:c[1], ... ) and the permutation p, the resulting coordinates will be (0:c[p[0]], 1:c[p[1]], ...).

Parameters:p (iterable) – permutation of the coordinates

sorted

(dim_i, coordinate_val_i)

Type:list Type:Sorted (by dimension) list of coordinate tuples

stamp

Returns tuple (hashable) of sorted

update_coordinates(new_coordinates)

Given new coordinates, update all the underlying values.

class semilattices.DefaultDict(*args, **kwargs)

This is a dictionary which defaults to a prescribed value if a key is missing.

copy() → a shallow copy of D

class semilattices.LevelsPartition(iterable=(), level_attr='l1', level_container_constructor=<class 'set'>, level_container_constructor_kwargs={})

Dictionary for keeping track of subsets of a coordinate semilattice at each level.

The i’th key corresponds to a SortedSet of all of the vertices of the semilattice in level i. It has the interface of a dict as well as of a set.

__init__(iterable=(), level_attr='l1', level_container_constructor=<class 'set'>, level_container_constructor_kwargs={})

Parameters:

• optional_iterator (iterator) – iterator with initializiation elements
• level_attr (str) – attribute of vertices to use to define the level. Default is the \(l_1\) norm l1.
• level_container_constructor (class) – the constructor for the levels containers. Shold have the add, remove and clear functions.
• level_container_constructor_kwargs (dict) – arguments to be passed to the level container constructor.

__getitem__(key)

Returns the key level

__setitem__(key, value)

Sets the key level

__delitem__(key)

Deletes the key level

__len__()

Returns the number of levels

add(vertex)

Add a vertex to the partition.

It takes the level_attr of the vertex and places the vertex in the correct element of the partition

clear()

Removes all the elements

discard(vertex)

Remove a vertex from the partition if present

It takes the level_attr of the vertex and remove the vertex from the partition

get_level(vertex)

Get the container holding elements at the same level of vertex

Note: Vertex does not have to belong to such level. The properties of vertex are used to get the container that would contain it.

items()

Returns an iterable over the tuples (level, vertices set)

keys()

Returns an iterable over the level numbers

remove(vertex)

Remove a vertex from the partition.

It takes the level_attr of the vertex and remove the vertex from the partition

Raises:KeyError – if vertex is missing

update(vertex_iterator)

Update the partition by adding all vertices in an iterator.

It takes an iterator vertex_iterator of vertices and adds each vertex to the partition. No checks are performed to check if the vertex_iterator is valid, therefore exceptions can occur

values()

Returns an iterable over the vertices set

class semilattices.MixedElement(comparable_flag=False)

An element whose comparability can change.

Objects of the same class can be comparable or not at different times. Unlike for StaticElement, here the comparability of the object can be changed.

class semilattices.MixedSortedContainer(*iterator, **kwargs)

This is a container where some elements are sorted if assigned a label(s), otherwise are just stored.

All elements are stored in a set (access is O(1)). The elements that are assigned a value to the key key are added also to a sorted list(s).

__init__(*iterator, **kwargs)

Parameters:

iterator (iterator) – an iterator with elements initializing the data structure

Keyword Arguments:  

• label_keys (iterable) – an iterable of label (string) attributes for sorting
• default_label_key (string) – default label

add(vertex)

Insert a vertex in the data structure.

clear()

Clear the datastructure.

discard(vertex)

Remove a vertex from the data structure. Does not Raise exception if missing.

get_sorted(label_key=None)

Returns the iterator over the sorted (by default label) labeled vertices.

Warning

It will iterate ONLY over the vertices that have been assigned a label. A warning will be raised if some of the vertices have not been labeled.

remove(vertex)

Remove a vertex from the data structure. Raises exception if missing.

Raises:KeyError – if the vertex does not belong to the data structure.

sorted

Returns the iterator over the sorted (by default label) labeled vertices.

Warning

It will iterate ONLY over the vertices that have been assigned a label. A warning will be raised if some of the vertices have not been labeled.

update_labels(vertex, **kwargs)

Updates the label(s) of the vertex.

Internally the MixedElement function _update_labels is called in order to make the vertex comparable.

class semilattices.SpaceWeightDict(*args, **kwargs)

This is a dictionary that default to 1 for missing elements.

class semilattices.StaticElement(comparable_flag=False)

An element whose comparability cannot change.

Within semilattice we use this for objects of the same class that either are comparable between each other or are not. Unlike for MixedElement, here comparability is a fixed property.

__init__(comparable_flag=False)

Parameters:comparable_flag (bool) – whether the object is comparable or not.

is_comparable

Whether the object can be compared.

exception semilattices.ArgumentsException

exception semilattices.ChildAlreadyExists

exception semilattices.CorruptedSemilatticeException

exception semilattices.DecreasingSemilatticeException

exception semilattices.EdgeException

exception semilattices.EmptySemilatticeException

exception semilattices.FrontierException

exception semilattices.GraphException

exception semilattices.InitializationException

exception semilattices.InvalidChild

exception semilattices.InvalidDimension

exception semilattices.InvalidParent

exception semilattices.InvalidVertex

exception semilattices.InvalidVertexConstructor

exception semilattices.IteratorException

exception semilattices.LabelsException

exception semilattices.SemilatticeException

exception semilattices.SparseKeysException

exception semilattices.ViolatesDecreasingProperty

exception semilattices.VertexException

class semilattices.SemilatticeIterable(graph, QueueConstructor, start_vertex=None, iter_attribute='children')

Base class defining an iterable for the semilattice.

Parameters:

• graph (Semilattice) – semilattice to iterate through
• QueueConstructor – queue constructor to be used within the iterator. This will define whether iteration is breadth or depth first. See BreadthFirstSemilatticeIterable and DepthFirstSemilatticeIterable for more details.
• start_vertex (SemilatticeVertex) – vertex from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

start_vertex

Starting vertex

Type:SemilatticeVertex

class semilattices.BreadthFirstSemilatticeIterable(graph, start_vertex=None, iter_attribute='children')

Breadth first iterable for the semilattice.

Parameters:

• graph (Semilattice) – semilattice to iterate through
• start_vertex (SemilatticeVertex) – vertex from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.DepthFirstSemilatticeIterable(graph, start_vertex=None, iter_attribute='children')

Depth first iterable for the semilattice.

Parameters:

• graph (Semilattice) – semilattice to iterate through
• start_vertex (SemilatticeVertex) – vertex from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.CoupledSemilatticeIterable(graph1, graph2, QueueConstructor, start_vertex1=None, start_vertex2=None, iter_attribute='children')

Base class defining an iterable for two semilattices at the same time.

The intended behavior is similar to the Python function zip(), but defining breadth/depth first iterators over the union/intersection of two semilattices.

Parameters:

• graph1 (Semilattice) – first semilattice to iterate through
• graph2 (Semilattice) – second semilattice to iterate through
• QueueConstructor – queue constructor to be used within the iterator. This will define whether iteration is breadth or depth first. See BreadthFirstSemilatticeIterable and DepthFirstSemilatticeIterable for more details.
• start_vertex1 (SemilatticeVertex) – vertex in the first semilattice from which to start the iteration.
• start_vertex2 (SemilatticeVertex) – vertex in the second semilattice from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.CoupledIntersectionSemilatticeIterable(graph1, graph2, QueueConstructor, start_vertex1=None, start_vertex2=None, iter_attribute='children')

Iterable over the intersection of two semilattices.

The intended behavior is similar to the Python function zip(), but defining breadth/depth first iterators over the intersection of two semilattices.

Parameters:

• graph1 (Semilattice) – first semilattice to iterate through
• graph2 (Semilattice) – second semilattice to iterate through
• QueueConstructor – queue constructor to be used within the iterator. This will define whether iteration is breadth or depth first. See BreadthFirstSemilatticeIterable and DepthFirstSemilatticeIterable for more details.
• start_vertex1 (SemilatticeVertex) – vertex in the first semilattice from which to start the iteration.
• start_vertex2 (SemilatticeVertex) – vertex in the second semilattice from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.BreadthFirstCoupledIntersectionSemilatticeIterable(graph1, graph2, start_vertex1=None, start_vertex2=None, iter_attribute='children')

Breadth first iterable over the intersection of two semilattices.

The intended behavior is similar to the Python function zip(), but defining breadth first iterators over the intersection of two semilattices.

Parameters:

• graph1 (Semilattice) – first semilattice to iterate through
• graph2 (Semilattice) – second semilattice to iterate through
• start_vertex1 (SemilatticeVertex) – vertex in the first semilattice from which to start the iteration.
• start_vertex2 (SemilatticeVertex) – vertex in the second semilattice from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.DepthFirstCoupledIntersectionSemilatticeIterable(graph1, graph2, start_vertex1=None, start_vertex2=None, iter_attribute='children')

Depth first iterable over the intersection of two semilattices.

The intended behavior is similar to the Python function zip(), but defining depth first iterators over the intersection of two semilattices.

Parameters:

• graph1 (Semilattice) – first semilattice to iterate through
• graph2 (Semilattice) – second semilattice to iterate through
• start_vertex1 (SemilatticeVertex) – vertex in the first semilattice from which to start the iteration.
• start_vertex2 (SemilatticeVertex) – vertex in the second semilattice from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.CoupledUnionSemilatticeIterable(graph1, graph2, QueueConstructor, start_vertex1=None, start_vertex2=None, iter_attribute='children')

Iterable over the union of two semilattices.

The intended behavior is similar to the Python function zip(), but defining breadth/depth first iterators over the union of two semilattices.

Parameters:

• graph1 (Semilattice) – first semilattice to iterate through
• graph2 (Semilattice) – second semilattice to iterate through
• QueueConstructor – queue constructor to be used within the iterator. This will define whether iteration is breadth or depth first. See BreadthFirstSemilatticeIterable and DepthFirstSemilatticeIterable for more details.
• start_vertex1 (SemilatticeVertex) – vertex in the first semilattice from which to start the iteration.
• start_vertex2 (SemilatticeVertex) – vertex in the second semilattice from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.BreadthFirstCoupledUnionSemilatticeIterable(graph1, graph2, start_vertex1=None, start_vertex2=None, iter_attribute='children')

Iterable over the union of two semilattices.

The intended behavior is similar to the Python function zip(), but defining breadth first iterators over the union of two semilattices.

Parameters:

• graph1 (Semilattice) – first semilattice to iterate through
• graph2 (Semilattice) – second semilattice to iterate through
• start_vertex1 (SemilatticeVertex) – vertex in the first semilattice from which to start the iteration.
• start_vertex2 (SemilatticeVertex) – vertex in the second semilattice from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.DepthFirstCoupledUnionSemilatticeIterable(graph1, graph2, start_vertex1=None, start_vertex2=None, iter_attribute='children')

Iterable over the union of two semilattices.

The intended behavior is similar to the Python function zip(), but defining depth first iterators over the union of two semilattices.

Parameters:

• graph1 (Semilattice) – first semilattice to iterate through
• graph2 (Semilattice) – second semilattice to iterate through
• start_vertex1 (SemilatticeVertex) – vertex in the first semilattice from which to start the iteration.
• start_vertex2 (SemilatticeVertex) – vertex in the second semilattice from which to start the iteration.
• iter_attribute (str) – attribute of SemilatticeVertex to iterate through. Default is children. Alternative can be parents, to iterate upward towards the root.

class semilattices.LevelsIterable(sl, start_level=0, iter_attribute='_l1_vertices_partition')

Iterable over the semilattice vertices by level.

Parameters:

• sl (Semilattice) – semilattice to iterate through.
• start_level (int) – level from which to start.

class semilattices.ParentsPowersetIterable(v)

Iterable over the vertices that are the ancestors defined by the powerset of the parent directions of v. This set of vertices forms a lattice, or ‘hypercube’ of vertices. A sign, indicating that a vertex visited is either an even or odd number of levels away from the original vertex v is also returned. :param v: vertex for which to iterate through parents powerset :type v: CoordinateVertex

semilattices.setLogLevel(level)

Set the log level for all existing and new objects related to the semilattices module

Parameters:level (int) – logging level

class semilattices.SLO

Base object for every object in the module.

This object provides functions for storage and logging.

store(fname, force=False)

Store the object with the selected file name fname

Parameters:

• fname (str) – file name
• force (bool) – whether to force overwriting

class semilattices.SemilatticeVertex(obj=None, *args, **kwargs)

A vertex that can have multiple parents.

A SemilatticeVertex is an element of a semilattice. There is no limit to the number of vertices that it can contain. Children and parents are stored in SortedDict.

classmethod cast(vertex_instance, **kwargs)

Casts other vertex instance to type cls

cast_to(cls, **kwargs)

Casts self to type cls

children

The children vertices in the semilattice

Type:SortedDict

in_deg

Number of inward pointing edges, i.e. number of parents

Type:int

out_deg

Number of outward pointing edges, i.e. number of children

Type:int

parents

The parent vertices in the semilattice

Type:SortedDict

class semilattices.SparseVertex(obj=None, *args, **kwargs)

A vertex that admit children only in a prescribed set of directions.

partial_siblings_count

A counter recording the number of present siblings in each direction.

For direction d, partial_siblings_count[d] is the number of siblings already available, which would be the parents of a child of self in the d direction.

Type:Counter

sparse_keys

Set of directions in which it’s allowed to add children.

Type:set

class semilattices.CoordinateVertex(obj=None, *args, **kwargs)

A semilattice vertex that have the concept of directional distance from the root.

CoordinateVertex can be canonically ordered, because the coordinates are natural number valued and the keys for parents/children are also natural numbers.

Keyword Arguments:  coordinates (CoordinateDict) – semilattice coordinate where each (key,value) element indicates that the vertex is value distant from the root in the direction key.

coordinates

immutable dictionary of coordinates

Type:CoordinateDict

class semilattices.LabeledVertex(obj=None, *args, **kwargs)

Labeled Vertices are provided an optional label(s).

Two vertices are comparable if both of them are provided a label (i.e. scalar or anything ‘<’ comparable)

To make sorted data structures robust to the user changing the label(s), the data structure containing the element should be used to update the label of the vertices.

Keyword Arguments:  

• labels (dict) – labels for the vertex (used for sorting)
• data (dict) – data attached to the vertex (not used for sorting)

data

Dictionary of metadata attached to the vertex. Data metadata are not used as ‘labels’, which define orderings for vertices.

default_label

Default Label dictionary for the vertex, used for < = comparison

labels

Dictionary of labels for the vertex

class semilattices.LabeledSparseVertex(obj=None, *args, **kwargs)

A vertex that is LabeledVertex and SparseVertex.

class semilattices.SparseCoordinateVertex(obj=None, *args, **kwargs)

A vertex that is CoordinateVertex and SparseVertex.

class semilattices.LabeledCoordinateVertex(obj=None, *args, **kwargs)

A vertex that is LabeledVertex and CoordinateVertex.

In order to be “comparable”, a Labeled Vertex must be assigned a LabeledVertex.label (i.e. scalar or anything ‘<’ comparable). Comparison between two LabeledCoordinateVertex is done first according to the LabeledVertex.label, then according to the CoordinateVertex.coordinates. Vertices with missing LabeledVertex.label are always considered to be smaller than vertices with labels. If both the vertices are not “comparable”, i.e. are not assigned labels, then compare only by CoordinateVertex.coordinates.

To make sorted data structures robust to the user changing the LabeledVertex.label, the data structure containing the element should be used to update the label of the vertices.

Keyword Arguments:  

• label – label for the vertex. Default is None
• coordinate (CoordinateDict) – semilattice coordinate

class semilattices.SparseLabeledCoordinateVertex(obj=None, *args, **kwargs)

A vertex that is LabeledVertex, CoordinateVertex and SparseVertex.

class semilattices.Semilattice(*args, **kwargs)

An (order-) semilattice is a rooted connected directed acyclic graph resembling the structure of a tree, i.e. it has a depth/levels. However, unlike a tree, each vertex can have multiple parents.

We denote the in-vertex neighbors of a vertex in the graph as parents and the out-vertex neighbors of a vertex in the graph children. ancestors and descentants follow the same terminology.

__init__(*args, **kwargs)

Optional Args:

semilattice (Semilattice): a semilattice to cast from

Keyword Arguments:  

• VertexConstructor (class) – a subclass of SemilatticeVertex (default: SemilatticeVertex)
• VertexSetConstructor (class) – a container class defining the data structure containing vertices (default: set)

__len__()

Number of vertices

__contains__(vertex)

Checks whether a vertex is in the semilattice Complexity: O(1)

__eq__(other)

Checks whether two semilattices have the same structure and VertexConstructor

__le__(other)

Checks whether self contains other

__ge__(other, NotImplemented=NotImplemented)

Return a >= b. Computed by @total_ordering from (not a <= b) or (a == b).

__iter__()

The default iterator iterates over the datastructure defined to contain the vertices

__ior__(other)

Returns the in-place union of two graphs.

For the elements in the intersection of self and other it always copies vertices from self.

Parameters:

• self (Semilattice) – first graph
• other (Semilattice) – second graph

Returns:

(Semilattice) – the union of self and other

__or__(other)

Returns the non-in-place union of two graphs.

For the elements in the intersection of self and other it always copies vertices from self.

Parameters:

• self (Semilattice) – first graph
• other (Semilattice) – second graph

Returns:

(Semilattice) – the union of self and other

__iand__(other)

Returns the in-place intersection of two graphs.

Elements are always retained from self.

Parameters:

• self (Semilattice) – first graph
• other (Semilattice) – second graph

Returns:

(Semilattice) – the intersection of self and other

__and__(other)

Returns the non-in-place intersection of two graphs.

Elements are always retained from self.

Parameters:

• self (Semilattice) – first graph
• other (Semilattice) – second graph

Returns:

(Semilattice) – the intersection of self and other

class Properties(VertexConstructor, VertexSetConstructor, VertexSetConstructorKwargs)

VertexConstructor

Alias for field number 0

VertexSetConstructor

Alias for field number 1

VertexSetConstructorKwargs

Alias for field number 2

VertexConstructor

Class constructor of the vertices in the semilattice.

Type:class

VertexSetConstructor

Class constructor for sets of vertices in the semilattice.

Type:class

VertexSetConstructorKwargs

Arguments to pass into a Vertex Set Constructor. This is particularly used when, for example, labels are set for vertex sets that are sorted

Type:class

append(v, other)

Appends a semilattice to the vertex v of self

Parameters:

• v (Vertex) – vertex to which append the semilattice
• other (Semilattice) – semilattice to be appended

cardinality()

Number of vertices

children_adjacency_mat

Adjacency matrix built traversing children

Returns:

Adjacency matrix (type self.adjacency_mat_type) built by

traversing the parents

clone()

Create a new empty semilattice with the same properties as self

copy()

A deep copy of the semilattice.

delete_vertex(deletion_target)

Deletes a vertex from the semilattice.

Parameters:deletion_target (SemilatticeVertex) – vertex to be deleted Returns:

(set) – set containing all the vertices removed from the

semilattice in the process of remoing deletion_target

intersection(other)

In-place intersection of two graphs.

Elements are always retained from self.

Parameters:

• self (Semilattice) – first graphs
• other (Semilattice) – second graphs

is_comparable_to(other)

Whether the semilattice is comparable to other.

Two semilattices are comparable if their VertexConstructor are the same.

issubsemilattice(other)

Checks whether self contains other

issupersemilattice(other)

Checks whether other contains self

iterator(start_vertex=None, iter_attribute='children', iter_type=<class 'semilattices._iterables.BreadthFirstSemilatticeIterable'>)

Returns an iterator for the semilattice.

See SemilatticeIterable for more details.

multiply(other)

Inplace product of the two semilattices

A product of two semilattices results in an increased semilattice where from each vertex of self starts a full other semilattice. The cost of this operation is \(\mathcal{O}(n_1 n_2)\) in the worst case.

Parameters:

• self (Semilattice) – first semilattice
• other (Semilattice) – second semilattice

new_vertex(**kwargs)

Adds a new child to parent along the direction edge

Keyword Arguments:  

• edge (int) – edge for child
• parent (Vertex) – vertex to which to add a child

Optional Keword Args:

new_vertex (Vertex): the new vertex, constructed on the outside **kwargs: keyword arguments for the construction of the new vertex,

to be passed to the vertex constructor

Returns:

(SemilatticeVertex) – the added vertex

Raises:

• InvalidVertex – if the vertex is not an instance of Vertex
• ChildAlreadyExists – if vertex already has a edge child.

order()

Same as cardinality

parents_adjacency_mat

Adjacency matrix built traversing parents

Returns:

Adjacency matrix (type self.adjacency_mat_type) built by

traversing the parents

properties

Properties of the semilattice that define construction of a new empty semilattice. This quantity it essentially ‘immutable’. The user should not try to modify self._properties (undefined behavior for this code)

random_vertex()

Return a random vertex from the semilattice.

Returns:(SemilatticeVertex) – random vertex

root

The root vertex

Type:SemilatticeVertex

union(other, start_vertex_self=None, start_vertex_other=None)

In-place union of two graphs.

For the elements in the intersection of self and other it always copies vertices from self.

Parameters:

• self (Semilattice) – first graph
• other (Semilattice) – second graph
• start_vertex_self (Vertex) – vertex of self from which to start the union
• start_vertex_other (Vertex) – vertex of other from which to start the union

vertices

The set of vertices in the semilattice

Type:set

class semilattices.CoordinateSemilattice(*args, **kwargs)

A semilattice with pre-defined dimension.

A (meet order-) semilattice is a partially-ordered set of vertices \((\mathcal{S}, \le)\), where the binary relation \(\le\) defines a meet between \(x\) and \(y\) \(\in \mathcal{S}\) in the following way: \(\forall x,y \in \mathcal{S}, x \le y \equiv x \wedge y = x\). A semilattice has the property that the infimum/meet/greatest lower bound \(z = (x \wedge y) \in \mathcal{S}\). The root vertex is the infimum \(z\) of all vertices in the semilattice.

__init__(*args, **kwargs)

Optional Args:

semilattice (Semilattice): a semilattice to cast from

Keyword Arguments:  

• dims (int) – semilattice dimension (maximum number of children per vertex)
• VertexConstructor (class) – a subclass of CoordinateVertex (default: CoordinateVertex)
• VertexSetConstructor (class) – a container class defining the data structure containing vertices (default: SortedSet)
• l1_vertices_partition (bool) – whether to keep track of the \(\ell^1\) partition of vertices (default: True)
• l1_frontier_partition (bool) – whether to keep track of the \(\ell^1\) partition of the frontier (default: True)

class Properties(VertexConstructor, VertexSetConstructor, VertexSetConstructorKwargs, l1_vertices_partition_flag, l1_frontier_partition_flag, l1_childless_partition_flag, dims)

VertexConstructor

Alias for field number 0

VertexSetConstructor

Alias for field number 1

VertexSetConstructorKwargs

Alias for field number 2

dims

Alias for field number 6

l1_childless_partition_flag

Alias for field number 5

l1_frontier_partition_flag

Alias for field number 4

l1_vertices_partition_flag

Alias for field number 3

childless

Childless set of vertices in the semilattice.

The childless vertices are the set of vertices which don’t have any children. It is a subset of the frontier.

draw(ax=None, **kwargs)

Draw the semilattice.

Parameters:

ax – matplotlib axes

Keyword Arguments:  

• cartesian (bool) – if set to True
• color (str) – if set to dims color the semilattice by dimension
• cmap – matplotlib colormap
• mark_frontier (bool) – if set to True mark the frontier nodes

frontier

Set of vertices in the frontier of the semilattice.

The frontier is defined to be the set of vertices which don’t have all the children.

is_comparable_to(other)

Checks if self is comparable to other

Parameters:other (Vertex) – vertex to check if self is comparable to

max_coordinate(dim)

Returns the maximum coordinate in dimension dim

max_coordinates

Returns the coordinates of the greatest coordinates in each effective dimension of the semilattice

max_l1_norm

Returns the maximum l1 norm of any coordinate in the semilattice

modify_dims(**kwargs)

Modify the dimension dims of the semilattice.

**kwargs:

add_dims (uint): (positive #) dimensions to add to dims (optional) percent_increase (uint): (positive #) percent to expand dims. Floor rounding takes place. (optional)

num_potential_children_of(parent)

Number of dimensions where parent can have children

Parameters:parent (CoordinateSemilatticeVertex) – parent vertex Returns:(int) – number of dimensions where parent can have children

potential_children_edges_of(parent)

List of dimensions where parent can have children

Parameters:parent (CoordinateSemilatticeVertex) – parent vertex Returns:(list) – list of dimensions where parent can have children

random_potential_children_edge_of(parent)

Return dimension where parent can have a child, selected randomly.

Parameters:parent (CoordinateSemilatticeVertex) – parent vertex Returns:(int) – dimension

random_potential_parent()

Returns a random vertex from the frontier (i.e. that may have a child)

class semilattices.DecreasingCoordinateSemilattice(*args, **kwargs)

A DecreasingCoordinateSemilattice is a semilattice \((\mathcal{S}\,\le)\) that is closed under meets, that is it is decreasing: \(x \le y \implies x \in \mathcal{S}\). A decreasing semilattice is often called ‘downward-closed, or ‘admissible’ when the semilattice is interpreted as a multiindex set parameterizing quadrature or interpolation problems

Parameters:

• dims (int) – semilattice dimension (maximum number of children per vertex)
• VertexConstructor (class) – type of vertices in the semilattice. It must extend SparseCoordinateVertex

class Properties(VertexConstructor, VertexSetConstructor, VertexSetConstructorKwargs, l1_vertices_partition_flag, l1_frontier_partition_flag, l1_childless_partition_flag, dims, l1_admissible_frontier_partition_flag)

VertexConstructor

Alias for field number 0

VertexSetConstructor

Alias for field number 1

VertexSetConstructorKwargs

Alias for field number 2

dims

Alias for field number 6

l1_admissible_frontier_partition_flag

Alias for field number 7

l1_childless_partition_flag

Alias for field number 5

l1_frontier_partition_flag

Alias for field number 4

l1_vertices_partition_flag

Alias for field number 3

admissible_frontier

The set of fontier vertices with admissible an admissible child(ren). Sorted by lexicographic ordering of the vertices.

draw(ax=None, **kwargs)

Draw the semilattice.

For additional keyword arguments see CoordinateSemialattice.draw().

Parameters:ax – matplotlib axes Keyword Arguments:  mark_admissible_frontier (bool) – if set to true marks the admissible frontier nodes

l1_admissible_frontier_partition

A partition of the admissible frontier by l1 norm

num_potential_children_of(parent)

Return number of all possible edges for new children of a parent

potential_children_edges(parent)

Return all possible edges for new children of a parent

random_potential_children_edge_of(parent)

Return a random possible edge for a new child for a parent When one need a random potential children_edge, the user should use this function,

random_potential_parent()

Draw a random vertex that can potentially be a new parent

random_vertex(admissible_frontier=False, frontier=False)

Parameters:

• admissible_frontier (bool) – whether or not to draw random vertex from the admissible frontier (default is False)
• frontier (bool) – whether or not to draw random vertex from the frontier (default is False)

Draw a random vertex from the semilattice, its frontier, or its admissible frontier

class semilattices.SortedCoordinateSemilattice(*args, **kwargs)

A SortedCoordinateSemilattice is a semilattice with Labeled vertices.

The elements of the SortedCoordinateSemilattice are sorted by the labels in a heap. One can add and remove labeled vertices in the lattice, and the ordering is maintained by the heap. SortedCoordinateSemilattice relies on the LabeledVertex and MixedSortedContainer data structures.

class Properties(VertexConstructor, VertexSetConstructor, VertexSetConstructorKwargs, l1_vertices_partition_flag, l1_frontier_partition_flag, l1_childless_partition_flag, dims, label_keys, default_label_key, data_keys)

VertexConstructor

Alias for field number 0

VertexSetConstructor

Alias for field number 1

VertexSetConstructorKwargs

Alias for field number 2

data_keys

Alias for field number 9

default_label_key

Alias for field number 8

dims

Alias for field number 6

l1_childless_partition_flag

Alias for field number 5

l1_frontier_partition_flag

Alias for field number 4

l1_vertices_partition_flag

Alias for field number 3

label_keys

Alias for field number 7

draw(ax=None, **kwargs)

Draw the semilattice.

For additional keyword arguments see CoordinateSemialattice.draw().

Parameters:ax – matplotlib axes Keyword Arguments:  color (bool) – if set to labels colors with respect to the label of the vertex

sorted

Returns the sorted labeled vertices based on the default label

Warning

It will iterate ONLY over the vertices that have been assigned a label. A warning will be raised if some of the vertices have not been labeled.

sorted_frontier

Returns the sorted frontier based on the default label

Warning

It will iterate ONLY over the vertices that have been assigned a label. A warning will be raised if some of the vertices have not been labeled.

update_data(vertex, **kwargs)

Update metadata of a vertex

Parameters:vertex (LabeledVertex) – vertex to label Keyword Arguments:  keyword arg should be metadata of the vertex (each) –

update_labels(vertex, **kwargs)

Update label(s) of a vertex

Parameters:vertex (LabeledVertex) – vertex to label Keyword Arguments:  keyword arg should be a label of the vertex (each) –

class semilattices.SortedDecreasingCoordinateSemilattice(*args, **kwargs)

class Properties(VertexSetConstructorKwargs, l1_childless_partition_flag, default_label_key, l1_frontier_partition_flag, VertexSetConstructor, l1_vertices_partition_flag, label_keys, l1_admissible_frontier_partition_flag, dims, data_keys, VertexConstructor)

VertexConstructor

Alias for field number 10

VertexSetConstructor

Alias for field number 4

VertexSetConstructorKwargs

Alias for field number 0

data_keys

Alias for field number 9

default_label_key

Alias for field number 2

dims

Alias for field number 8

l1_admissible_frontier_partition_flag

Alias for field number 7

l1_childless_partition_flag

Alias for field number 1

l1_frontier_partition_flag

Alias for field number 3

l1_vertices_partition_flag

Alias for field number 5

label_keys

Alias for field number 6

delete_vertex(deletion_target)

Args:

deletion_target (SparseLabeledCoordinateVertex): vertex to delete

Delete the specifed vertex, along with all dependencies of the vertex

semilattices.create_lp_semilattice(dims, norm, p=1, weights=None, SemilatticeConstructor=<class 'semilattices._decreasingcoordinatesemilatticebase.DecreasingCoordinateSemilattice'>, **kwargs)

Create the semilattice of all vertices in the \(\ell^p\) spherical sector of a given norm

For a particular norm value, \(0\leq p\leq \infty\), and optional anisotropic weighting for the \(p\) norm, this function creates a semilattice of all vertices enclosed in the \(\ell^p\) spherical sector of the given norm size, with optional anisotropic dimension dependence. The vertices form a decreasing coordinate semilattice.

Parameters:

• dim (int) – The dimension of the semilattice
• norm (float) – norm of the \(\ell^p\) spherical sector enclosing all vertices of the output semilattice
• p (int) – The \(p\) in \(\ell^p\)
• weights (SpaceWeightDict) – A weighting on the \(\ell^p\) norm \(\|x \|_{\ell^p_W} = (\sum_{i=1}^{dim} w_i | x_i |^p)^{1/p}\). Each dictionary key is the dimension \(i\), while while each corresponding value is \(w_i\). Weights must be >1. Missing values are considered 1.
• SemilatticeConstructor (DecreasingCoordinateSemilattice) – derived subclass of DecreasingCoordinateSemilattice defining the type of semilattice to return
• **kwargs – additional keyword arguments to be passed to the SemilatticeConstructor specified. See the specific semilattices for the list of keyword arguments that may be provided.

Returns:

(DecreasingCoordinateSemilattice) – The constructed semilattice

semilattices.permute(sl, p)

Creates a new semilattice with permuted dimensions

We assume the semilattice sl to have dimensions (0, 1, 2). Given the permutation (2, 0, 1) this function will output a semilattice sl1 with the following propery: being v a vertex of sl and v1 the corresponding vertex of sl1, then v1.children[0] == v.children[2], v1.children[1] == v.children[0], v1.children[2] == v.children[1], where the vertices are deepcopy of one-another.

Parameters:

• sl (CoordinateSemilattice) – input semilattice.
• p (Iterable) – permuted dimensions.