import semilattices as SL
%matplotlib inline

Sorted semilattices

A sorted semilattice is a semilattice \(\mathcal{S}\) in which each vertex \(v \in \mathcal{S}\) can be assigned one or more labels \(v.\text{labels}\) defining a total ordering on \(\mathcal{S}\) if they are unique. Not all the vertices need labels, some may be unlabeled, in which case they will be ordered according to their coordinates after all the vertices with a label.

Single sorting label

We start borrowing an example from the section on coordinate semilattice where now we allow for vertices with a label “weight” and assign it a value.

sl = SL.SortedCoordinateSemilattice(dims=2, label_keys=['weight']) # Specify the sorting labels
root = sl.new_vertex(labels={'weight':10})
c1 = sl.new_vertex(edge=1, parent=root, labels={'weight':9})
c0 = sl.new_vertex(edge=0, parent=root, labels={'weight':8})
c0c0 = sl.new_vertex(edge=0, parent=c0, labels={'weight':7})
c0c1 = sl.new_vertex(edge=1, parent=c0, labels={'weight':6})
c0c1c1 = sl.new_vertex(edge=1, parent=c0c1, labels={'weight':5})
c0c1c0 = sl.new_vertex(edge=0, parent=c0c1, labels={'weight':4})
c0c0c0 = sl.new_vertex(edge=0, parent=c0c0, labels={'weight':3})
c0c0c0c0 = sl.new_vertex(edge=0, parent=c0c0c0, labels={'weight':2})
c0c0c0c1 = sl.new_vertex(edge=1, parent=c0c0c0, labels={'weight':1})

Let us now visualize the semilattice.

sl.draw(cartesian=True, show=False, color='label', color_label='weight')

Alternatively, the labels can be set afterward using the function update_labels.

for i, v in enumerate(sl): sl.update_labels( v, weight=len(sl)-i )

We can access the vertices now in the order sorted by the “weight” using the get_sorted function.

for v in sl.vertices.get_sorted('weight'):
    print(str(v.coordinates) + ": %d" % v.labels.get('weight'))

{0: 1}: 1
{}: 2
{0: 1, 1: 2}: 3
{1: 1}: 4
{0: 2}: 5
{0: 1, 1: 1}: 6
{0: 4}: 7
{0: 3}: 8
{0: 2, 1: 1}: 9
{0: 3, 1: 1}: 10

Since the semilattice has only one label, one can use directly the sorted property.

for v in sl.vertices.sorted:
    print(str(v.coordinates) + ": %d" % v.labels.get('weight'))

{0: 1}: 1
{}: 2
{0: 1, 1: 2}: 3
{1: 1}: 4
{0: 2}: 5
{0: 1, 1: 1}: 6
{0: 4}: 7
{0: 3}: 8
{0: 2, 1: 1}: 9
{0: 3, 1: 1}: 10

One can also access the sorted subset of vertices in the frontier.

for v in sl.frontier.sorted:
    print(str(v.coordinates) + ": %d" % v.labels.get('weight'))

{0: 1, 1: 2}: 3
{1: 1}: 4
{0: 4}: 7
{0: 2, 1: 1}: 9
{0: 3, 1: 1}: 10

Labels can be removed from single vertices through the update_labels functions.

sl.update_labels(root, weight=None)
for v in sl:
    lbl = str(v.labels.get('weight'))
    print(str(v.coordinates) + ": " + lbl)

{0: 3, 1: 1}: 10
{0: 2, 1: 1}: 9
{0: 3}: 8
{0: 4}: 7
{0: 1, 1: 1}: 6
{0: 2}: 5
{1: 1}: 4
{0: 1, 1: 2}: 3
{}: None
{0: 1}: 1

Multiple sorting labels

We use again the previous coordinate semilattice here.

sl = SL.SortedCoordinateSemilattice(dims=2, label_keys=['weight', 'degree'])
root = sl.new_vertex()
c1 = sl.new_vertex(edge=1, parent=root)
c0 = sl.new_vertex(edge=0, parent=root)
c0c0 = sl.new_vertex(edge=0, parent=c0)
c0c1 = sl.new_vertex(edge=1, parent=c0)
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)

As before we assign labels to all the vertices.

for i, v in enumerate(sl): sl.update_labels( v, weight=len(sl)-i, degree=v.coordinates.lp(p=1) )

And visualize both.

sl.draw(cartesian=True, show=False, color='label', color_label='weight')
sl.draw(cartesian=True, show=False, color='label', color_label='degree')

Missing labels

Here we consider the case only a subset of the vertices are assigned a label. For example only the node in the frontier are assigned a “degree”.

sl = SL.SortedCoordinateSemilattice(dims=2, label_keys=['degree']) # Specify the sorting labels
root = sl.new_vertex()
c1 = sl.new_vertex(edge=1, parent=root, labels={'degree': 10})
c0 = sl.new_vertex(edge=0, parent=root, labels={'degree': 1})
c0c0 = sl.new_vertex(edge=0, parent=c0, labels={'degree': 1})
c0c1 = sl.new_vertex(edge=1, parent=c0, labels={'degree': 1})
c0c1c1 = sl.new_vertex(edge=1, parent=c0c1, labels={'degree': 1})
c0c1c0 = sl.new_vertex(edge=0, parent=c0c1, labels={'degree': 1})
c0c0c0 = sl.new_vertex(edge=0, parent=c0c0, labels={'degree': 1})
c0c0c0c0 = sl.new_vertex(edge=0, parent=c0c0c0, labels={'degree': 1})
c0c0c0c1 = sl.new_vertex(edge=1, parent=c0c0c0, labels={'degree': 1})

for v in sl.frontier: sl.update_labels( v, degree=v.coordinates.lp(p=1) )

The nodes with no label will be color-coded to black here.

sl.draw(cartesian=True, show=False, color='label', color_label='degree')

The labels with no assigned values raise a KeyError meaning that the corresponding key is unassigned.

for v in sl.vertices:
    try:
        print(str(v.coordinates) + ": %d" % v.labels['degree'])
    except KeyError:
        print(str(v.coordinates) + ": missing 'degree' label ")

{0: 1}: 1
{0: 3, 1: 1}: 4
{0: 1, 1: 2}: 3
{1: 1}: 1
{0: 3}: 1
{}: missing 'degree' label
{0: 2}: 1
{0: 4}: 4
{0: 2, 1: 1}: 3
{0: 1, 1: 1}: 1

Automatic creation of decreasing sorted semilattices

Here we create a decreasing coordinate semilattice with multiple labels: one expressing the \(l_p\) norm of the vertices (\(p=0.4\)) and another random.

import numpy as np
sl = SL.create_lp_semilattice(
    2, 15, p=.45, weights={0:1.0,1:1.4},
    SemilatticeConstructor=SL.SortedDecreasingCoordinateSemilattice,
    label_keys = ['weight', 'random'])
for v in sl: sl.update_labels(
        v,
        weight=v.coordinates.lp(p=.4),
        random=np.random.randn())

And let us visualize them.

sl.draw(cartesian=True, show=False, mark_frontier=False, mark_childless=True, mark_admissible_frontier=True, color='label', color_label='weight')

sl.draw(cartesian=True, show=False, color='label', color_label='random', nodes_cmap='jet')