import numpy as np
import semilattices as SL
%matplotlib inline

Decreasing semilattices

A decreasing (lower, down) semilattice is a coordinate semilattice which fulfill the following decreasing property:

• every vertex \(v\in\mathcal{V}\) has a complete parenthood, i.e. the semilattice contains all the possible parents of \(v\).

The number of possible parents for a vertex \(v\) is equivalent to the number \(n\) of its non-zero coordinates (i.e. \(n=\#\{c\in v.\text{coordinates} | c \neq 0\}\)). Some communities denote decreasing semilattices as downward closed semilattices.

The construction of decreasing semilattices is equivalent to the construction of coordinate semilattices, apart from the fact that one is not allowed to insert vertices violating the decreasing property. A decreasing semilattice exploits this property to efficiently provide the user with the possible children that can be added to the set semilattice while maintaining the decreasing property.

sl = SL.DecreasingCoordinateSemilattice(dims=2)
root = sl.new_vertex()
c0 = sl.new_vertex(edge=0, parent=root)
c1 = sl.new_vertex(edge=1, parent=root)
c0c0 = sl.new_vertex(edge=0, parent=c0)
c0c1 = sl.new_vertex(edge=1, parent=c0)
c1c1 = sl.new_vertex(edge=1, parent=c1)
c0c1c1 = sl.new_vertex(edge=1, parent=c0c1)
sl.draw(cartesian=True, show=False)

The admissible frontier

A fudamental concept in decreasing semilattices is the admissible frontier, which is the set of vertices \(\mathcal{A}\subset\mathcal{F}\subset\mathcal{V}\) such that \(v\in\mathcal{A}\) have less than \(d\) children and could insert at least one child which does not violate the decreasing property.

In other words, the admissible frontier \(\mathcal{A}\) contains vertices to which child(ren) may be added without violating the decreasing property (or child(ren) which are admissible).

In some communities, the \(\mathcal{A}\) is referred to as the active set, and \(\mathcal{F} \setminus \mathcal{A}\) is referred to as the old set.

The admissible frontier can be accessed through the following data structure.

sl.admissible_frontier

SortedSet([<semilattices._vertices.SparseCoordinateVertex object at 0x7f2b43c3f6a0>, <semilattices._vertices.SparseCoordinateVertex object at 0x7f2b43c3f710>, <semilattices._vertices.SparseCoordinateVertex object at 0x7f2b43c3ffd0>])

We can also visualize the nodes in the admissible frontier through arrows. Vertices in the admissible frontier are marked with arrows indicating the directions in which children can be added

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

Let’s delete a vertex:

sl.delete_vertex(c1c1)

{<semilattices._vertices.SparseCoordinateVertex at 0x7f2b43c3fa90>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b43c3ffd0>}

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

Let’s look at the childless vertices (♢)

for v in sl.childless:
    print(v.coordinates)
print("or another way:")
for v in SL.LevelsIterable(sl,iter_attribute="_l1_childless_partition"):
    print(v.coordinates)

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

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

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

The visualization also shows the directions toward which children may be added to vertices in the admissible frontier. This information may be accessed through the sparse_keys propery of vertices.

v = next(iter(sl.admissible_frontier))
print(v.coordinates)
print(v.sparse_keys)

{0: 1, 1: 1}
{0}

The admissible frontier can be accessed also through its \(\ell^1\) partition.

sl.l1_admissible_frontier_partition

<semilattices._datastructures.LevelsPartition at 0x7f2b43c38168>

This partition can be iterated over using the LevelsIterable class.

for v in SL.LevelsIterable(sl, iter_attribute='l1_admissible_frontier_partition'):
    print(v.coordinates)

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

To illustrate further how vertices become admissible as the semilattice evolves, let us now try to insert a vertex violating the decreasing property.

try:
    c0c1c1 = sl.new_vertex(edge=1, parent=c0c1)
except SL.ViolatesDecreasingProperty:
    print("The new vertex violates the decreasing property.")

The new vertex violates the decreasing property.

Adding the vertex c1c1 = {1:2} causes vertex {0: 1, 1:2} to be come admissible.

c1c1 = sl.new_vertex(edge=1, parent=c1)
sl.draw(cartesian=True, mark_childless=True, mark_admissible_frontier=True, show=False)

Now, inserting the same vertex no longer violates the decreasing property

try:
    c0c1c1 = sl.new_vertex(edge=1, parent=c0c1)
    sl.draw(cartesian=True, mark_childless=True, mark_admissible_frontier=True, show=False)
except SL.ViolatesDecreasingProperty:
    print("The new vertex violates the decreasing property.")

A convenience function allows the user to add all children that would maintain the decreasing property of the semilattice. Below we show a sequence of adding all admissible children of vertices in the current admissible frontier

for v in list(sl.admissible_frontier):
    sl.add_all_admissible_children_of(v)
    sl.draw(cartesian=True, mark_admissible_frontier=True, show=False)

Creation of \(\ell^p\)-balls

For \(p \in [0,\infty]\), an \(\ell^p\) ball semilattice with radius \(r \geq 0\) is a coordinate semilattice such that:

• the coordinates \({\bf c} = v.\text{coordinates}\) of every vertex \(v\) in the semilattice satisfy \(\Vert{\bf c}\Vert_p \leq r\),

where \(\Vert {\bf c} \Vert_p := \left( \sum_{i=0}^{d-1} {\bf c}_i^p \right)^{1/p}\) for \(p<\infty\), \(\Vert {\bf c} \Vert_\infty := \max_i {\bf c_i}\), and \(\Vert {\bf c} \Vert_0 := \sum_i^{d-1} {\bf c}_i\) if \(\#\{{\bf c}_i \ne 0\} = 1\), else \(\infty\) (our own definition)

Semilattices fulfilling this condition, fulfill automatically also the decreasing property.

We can create these decreasing semilattices using the following function.

sl = SL.create_lp_semilattice(dims=2, norm=10, p=0.6)
sl.draw(cartesian=True, mark_frontier=False, mark_childless=True, mark_admissible_frontier=True, show=False)

To illustrate deletion of vertices, we will draw a random vertex and delete it:

delete_vertex = sl.random_vertex()
print("Deleting this vertex:", delete_vertex.coordinates)

Deleting this vertex: {0: 1}

sl.delete_vertex(delete_vertex)

{<semilattices._vertices.SparseCoordinateVertex at 0x7f2b40541cc0>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40553208>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40553588>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616278>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616f98>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40baf358>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b406169e8>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40541c50>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40541710>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b405530f0>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616d30>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616d68>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40553160>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b406168d0>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616b70>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40bafe80>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616860>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616400>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40baf160>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b454e00b8>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40bafba8>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40616fd0>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40baf2b0>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40baf860>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b40bafc88>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b4057d470>,
 <semilattices._vertices.SparseCoordinateVertex at 0x7f2b4057d0b8>}

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

Notice that deleting a vertex will also result in deleting all vertices in the semilattice that violate the decreasing property as a result of the deletion.

Below we see a contrast between semilattice that are sparse and ones which are not. We create \(\ell^0\)-ball and a \(\ell^{\infty}\) ball semilattices:

sl = SL.create_lp_semilattice(dims=2, norm=10, p=0)
sl.draw(cartesian=True, mark_childless=True, mark_admissible_frontier=True, show=False)

sl = SL.create_lp_semilattice(dims=2, norm=10, p=np.inf)
sl.draw(cartesian=True, mark_childless=True, mark_admissible_frontier=True, show=False)

For convenience, a method sl.random_vertex gives one the ability to access random elements of the semilattice. We use this to delete a random vertex.

delete_vertex = sl.random_vertex()
print("Deleting this vertex:", delete_vertex.coordinates)
sl.delete_vertex(delete_vertex)
sl.draw(cartesian=True, mark_frontier=True, mark_childless=True, mark_admissible_frontier=True, show=False)

Deleting this vertex: {0: 7, 1: 4}

Different coordinates can also be assigned different weights, leading to the decreasing semilattices within weighted :math:`ell^p_{bf w}`-balls of a certain radius, where the weghted norm (quasinorm) is defined by \(\Vert{\bf c}\Vert_{p,{\bf w}} := \left( \sum_{i=0}^{d-1} {\bf w}_i {\bf c}_i^p \right)^{1/p}\) for \(p<\infty\) and \(\Vert{\bf c}\Vert_{\infty,{\bf w}} := {\bf w}_{\hat{i}} {\bf c}_\hat{i}\) otherwise (\(\hat{i}:=\arg\max_i{\bf c}_i\)).

sl = SL.create_lp_semilattice(dims=2, norm=45, p=0.5, weights={0: 1., 1:2.0})
sl.draw(cartesian=True, mark_frontier=False, mark_childless=False, mark_admissible_frontier=True, show=False, marker_size=10.0)

delete_vertex = sl.random_vertex()
print("Deleting this vertex:", delete_vertex.coordinates)
sl.delete_vertex(delete_vertex)
sl.draw(cartesian=True, mark_frontier=True, mark_childless=True, mark_admissible_frontier=True, show=False, marker_size=20.0)

Deleting this vertex: {1: 11}

This way we can quickly generate large isotropic or anisotropic decreasing semilattices.

dims = 50
sl = SL.create_lp_semilattice(
    dims=dims, norm=10, p=0.8,
    weights=dict([ (d, np.sqrt(d+1)) for d in range(dims) ]) )
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):