SemilatticesΒΆ
This package is devoted to the construction and modification of semilattices. Mathematically, a lower-(upper-) semilattice is a partially ordered set for which any nonempty finite subset has an infimum(supremum). The greatest lower bound (least upper bound) of a lower-(upper-) semilattice is called is meet (join).
In the language of graphs, a semilattice is a special type of rooted connected graph. In particular it can be viewed as a tree whose leaves can have multiple parents.
The package implements the interface to many types of semilattices, which enforce different connectivity properties and provide access to different data structures.
The most basic type of practically useful semilattice is the
CoordinateSemilattice,
which can be defined as follows: the tuple
\(\mathcal{S}=(\mathcal{V}, \mathcal{E})\) is a coordinate semilattice of
dimension \(d\) if
- \(\mathcal{S}\) is connected
- there exist a unique vertex \(r\in\mathcal{V}\), denoted root, such that \(r.\text{parents} = \varnothing\)
- each vertex \(v\in\mathcal{V}\) has at most \(d\) children
- each vertex \(v\in\mathcal{V}\) which is \(v.\text{level}\) edges away from the root has at most \(\min(d, v.\text{level})\) parents (the connectivity properties implies that any vertex but the root must have at least one parent and up to d parents).
The children of a vertex of level \(v.\text{level}\) will belong to the level \(v.\text{level}+1\) while its parents will belong to the level \(v.\text{level}-1\).
The following figure shows a \(d=3\) dimensional semilattice, where each vertex is labeled using its coordinates \(v.\text{coordinates}\), namely the number of edges in each coordinate direction which connect \(v\) to the root. The root can be seen at the bottom to have an empty coordinates set. Its children have coordinate \(1\) in the direction in which they are related to the root, and so on. The vertices in the same level are displayed along the same row. Vertices have a level property \(v.\text{level}:=\sum v.\text{coordinates}\).
The Tutorial will walk the user through the construction and handling
of CoordinateSemilattice and
semilattice classes that extend it.