import semilattices as SL
%matplotlib inline

Coordinate semilattices

We start by constructing a semilattice, where we manually keep track of the nodes created. Note, it is not required to assign a new vertex (the return of the method call sl.new_vertex) to a variable, but this becomes useful for manual defining the graph dependence structure of the semilattice, as we do throughout this tutorial.

sl = SL.CoordinateSemilattice(dims=2)     # Creates a semilattice of dimension 2
print(sl.properties)
root = sl.new_vertex()                    # Add the root vertex to the semilattice
c1 = sl.new_vertex(edge=1, parent=root)   # Add the child along coordinate 1 to the root vertex

Properties(VertexConstructor=<class 'semilattices._vertices.CoordinateVertex'>, VertexSetConstructor=<class 'sortedcontainers.sortedset.SortedSet'>, VertexSetConstructorKwargs={}, l1_vertices_partition_flag=True, l1_frontier_partition_flag=True, l1_childless_partition_flag=True, dims=2)

Next we plot the current semilattice.

sl.draw(cartesian=True, show=False)

Then, let us add some new nodes…

c0 = sl.new_vertex(edge=0, parent=root)   # Add the child along coordinate 0 to the root vertex
c0c0 = sl.new_vertex(edge=0, parent=c0)   # Add the child along coordinate 0 to the c0 vertex
c0c1 = sl.new_vertex(edge=1, parent=c0)   # Add the child along coordinate 1 to the c0 node
sl.draw(cartesian=True, show=False)

Note that in line 3 above, we add the child of c0 along coordinate 1. This child not only has c0 as its parent, but also the vertex c1 which was inserted previously. The function new_vertex detects the fact that the parent c1 exists and connects it correctly.

Let us add some more vertices.

c0c1c1 = sl.new_vertex(edge=1, parent=c0c1)
c0c1c0 = sl.new_vertex(edge=0, parent=c0c1)
c0c0c0 = sl.new_vertex(edge=0, parent=c0c0)
c0c0c0c0 = sl.new_vertex(edge=0, parent=c0c0c0)
c0c0c0c1 = sl.new_vertex(edge=1, parent=c0c0c0)
sl.draw(cartesian=True, show=False)

Adding vertices that already exist raises exceptions.

try:
    c0c0c0 = sl.new_vertex(edge=0, parent=c0c0)
except SL.ChildAlreadyExists:
    print("Catched exception of child already existing...")
sl.draw(cartesian=True, show=False)

Catched exception of child already existing...

It is also possible to remove nodes, while preserving the connectivity of the semilattice.

sl.delete_vertex(c0c0)
sl.draw(cartesian=True, show=False)

The frontier

The frontier is the subset of vertices \(\mathcal{F} \subset \mathcal{V}\) that admit additional children. As we state in the definition of coordinate semilattice, every vertex can have at most \(d\) children. Therefore a vertex is in the frontier if it has less than \(d\) children.

The frontier can be accessed by the following field.

sl.frontier

SortedSet([<semilattices._vertices.CoordinateVertex object at 0x7f2b99faef28>, <semilattices._vertices.CoordinateVertex object at 0x7f2b99d80780>, <semilattices._vertices.CoordinateVertex object at 0x7f2b99d80748>, <semilattices._vertices.CoordinateVertex object at 0x7f2b99bda1d0>, <semilattices._vertices.CoordinateVertex object at 0x7f2b99e21940>])

We may iterate over the frontier and print out the coordinates of the vertices belonging to it.

for v in sl.frontier:
    print(v.coordinates)

{0: 1}
{0: 1, 1: 2}
{0: 2, 1: 1}
{0: 3, 1: 1}
{1: 1}

Or, we could visualize it using different markers (squares for the nodes in the frontier).

sl.draw(cartesian=True, mark_frontier=True, show=False)

Let’s delete a vertex!

sl.delete_vertex(c1)
sl.draw(cartesian=True, mark_frontier=True, show=False)

for v in sl.frontier:
    print(v.coordinates)
print("or another way:")
for v in SL.LevelsIterable(sl, iter_attribute='_l1_frontier_partition'):
    print(v.coordinates)

{}
{0: 1}
{0: 1, 1: 2}
{0: 2, 1: 1}
{0: 3, 1: 1}
or another way:
{0: 1}
{0: 1, 1: 2}
{0: 2, 1: 1}
{0: 3, 1: 1}
{}

for lvl, vertices in sl.l1_frontier_partition.items():
    print("lvl", lvl)
    for v in vertices:
        print(v.coordinates)
    print("\n")

lvl 1
{0: 1}


lvl 3
{0: 1, 1: 2}
{0: 2, 1: 1}


lvl 4
{0: 3, 1: 1}


lvl 0
{}

Childless vertices

Childless vertices are the subset of vertices \(\mathcal{F} \subset \mathcal{V}\) that have no children. This set is a subset of the frontier.

The childless vertices can be accessed by the following field.

sl.childless

SortedSet([<semilattices._vertices.CoordinateVertex object at 0x7f2b99d80780>, <semilattices._vertices.CoordinateVertex object at 0x7f2b99bda1d0>])

As with the frontier, we may iterate over the childless vertices and print out the coordinates of the vertices belonging to it.

for v in sl.childless:
    print(v.coordinates)

{0: 1, 1: 2}
{0: 3, 1: 1}

Or, as with the frontier, we could visualize it using different markers (♢ for the nodes in the childless set). Note, if one also marks the frontier, the childless vertices will default to marking with ♢, even though they are a subset of the frontier as well.

sl.draw(cartesian=True, mark_frontier=True, mark_childless=True,  show=False)

The levels structure

The sets \(\{\mathcal{L}_i\}\) of \(\mathcal{V}\) partition \(\mathcal{V}\) in into vertices that belong to level \(i\). These correspond to vertices whose coordinates sum to \(i\), or in other words whose \(\ell^1\)-norm of the coordinates is \(i\).

These sets can be accessed through the following data structure.

sl.l1_vertices_partition

<semilattices._datastructures.LevelsPartition at 0x7f2bcace2318>

We can for example access all the vertices in level \(1\) as follows.

for v in sl.l1_vertices_partition[1]:
    print(v.coordinates)

{0: 1}

Or we could visualize the semilattice with vertices colored according to their l1 norm.

sl.draw(cartesian=True, color='l1_norm', show=False)

We can also visualize the semilattice with vertices colored according to their ‘average dimension.’

sl.draw(cartesian=True, color='dims', show=False)

Iterating over a semilattice

There are a number of ways for iterating over a semilattice. The simplest way is using the semilattice itself, which does not guarantee any specific ordering.

for v in sl:
    print(v.coordinates)

{}
{0: 1}
{0: 1, 1: 1}
{0: 1, 1: 2}
{0: 2, 1: 1}
{0: 3, 1: 1}

Alternatively one may be interested in iterating breadth first.

for v in SL.BreadthFirstSemilatticeIterable(sl):
    print(v.coordinates)

{}
{0: 1}
{0: 1, 1: 1}
{0: 2, 1: 1}
{0: 1, 1: 2}
{0: 3, 1: 1}

Or depth first.

for v in SL.DepthFirstSemilatticeIterable(sl):
    print(v.coordinates)

{}
{0: 1}
{0: 1, 1: 1}
{0: 1, 1: 2}
{0: 2, 1: 1}
{0: 3, 1: 1}

One could also to iterate level-by-level.

for v in SL.LevelsIterable(sl):
    print(v.coordinates)

{}
{0: 1}
{0: 1, 1: 1}
{0: 1, 1: 2}
{0: 2, 1: 1}
{0: 3, 1: 1}

Union and intersection of semilattices

Semilattices are closed under union and intersection operations. So, two semilattices can be merged into one by taking the union or the intersection of the two. These operations could be performed in-place or not-in-place.

In order to show this feature, let us first generate another semilattice.

sl2 = SL.CoordinateSemilattice(dims=2)
root = sl2.new_vertex()
c0 = sl2.new_vertex(edge=0, parent=root)
c1 = sl2.new_vertex(edge=1, parent=root)
c0c1 = sl2.new_vertex(edge=0, parent=c1)
c1c1 = sl2.new_vertex(edge=1, parent=c1)
c1c1c1 = sl2.new_vertex(edge=1, parent=c1c1)
c1c1c1c0 = sl2.new_vertex(edge=0, parent=c1c1c1)
c0c0 = sl2.new_vertex(edge=0, parent=c0)
sl2.draw(cartesian=True, show=False)

Then let’s take the not-in-place union with the previous semilattice.

usl = sl | sl2
usl.draw(cartesian=True, show=False)

The corresponding in-place operation is performed as follows:

sl_copy = sl.copy()    # We copy sl in order to be able to re-use it later
sl_copy |= sl2
sl_copy.draw(cartesian=True, show=False)

Let us take the not-in-place intersection with the previous semilattice.

isl = sl & sl2
isl.draw(cartesian=True, show=False)

The corresponding in-place operation is:

sl_copy = sl.copy()    # We copy sl in order to be able to re-use it later
sl_copy &= sl2
sl_copy.draw(cartesian=True, show=False)

Visualization

In the previous examples we have seen several usages of the function CoordinateSemilattice.draw. There are two main plotting projections available, the cartesian, which works in 2d and 3d, and the “default” which project everything in 2 dimensions.

We construct a 3 dimensional semilattice to show their differences.

sl = SL.CoordinateSemilattice(dims=3)
root = sl.new_vertex()
c0 = sl.new_vertex(edge=0, parent=root)
c1 = sl.new_vertex(edge=1, parent=root)
c2 = sl.new_vertex(edge=2, parent=root)
c0c0 = sl.new_vertex(edge=0, parent=c0)
c0c1 = sl.new_vertex(edge=1, parent=c0)
c0c2 = sl.new_vertex(edge=2, parent=c0)
c0c0c0 = sl.new_vertex(edge=0, parent=c0c0)
c0c0c1 = sl.new_vertex(edge=1, parent=c0c0)
c1c2 = sl.new_vertex(edge=2, parent=c1)
c0c1c2 = sl.new_vertex(edge=2, parent=c0c1)
c1c1 = sl.new_vertex(edge=1, parent=c1)

In general the cartesian projection provides a better spacing of the nodes, but can be used only in 2 dimensions or 3 dimensions.

sl.draw(cartesian=True, show=False)

The “default” projection instead puts the different axis of the dimensions along different branches of the semilattice projection and, as a result of plotting a high-dimensional semilattice in 2 dimesnions, clusters the nodes towards these branches.

sl.draw(show=False)

/home/docs/checkouts/readthedocs.org/user_builds/semilattices/envs/latest/lib/python3.6/site-packages/networkx/drawing/nx_pylab.py:579: MatplotlibDeprecationWarning:
The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.
  if not cb.iterable(width):

As a result some nodes and some edges may be crossing and overlapping, which is an unavoidable side effect. On the other hand this projection is still useful to get a general overview of the semilattice in high-dimensions.