FHDpy: Python package for compressed data structures of Heegaard splitting (v 0.0.1)

This package was created to serve as a proof of concept for the paper Compressed Data Structures for Heegaard Splittings, authored by Henrique Ennes and Clément Maria. The code, however, is of full responsibility of the first author, so you can only blame him for anything that does not work.

Background

A Heegaard splitting is a representation of a closed 3-manifold by the gluing of two handlebodies of common boundary $\Sigma_g$ through an element of its mapping class group, $\phi \in \text{Mod}(\Sigma_g)$. Equivalently, a Heegaard splitting can be described by two sets of $g$ disjoint curves, say $\alpha$ and $\beta$, with $\beta = \phi(\alpha)$, whose intersection pattern conveys much of the topology of the underlying 3-manifold. We algorithmically explore this notion in the preprint, where we propose a representation of Heegaard diagrams through straight-line programs (SLPs) of the intersection sequences of the $\beta$-curves and the edges of cellular complexes of a surface.

The SLP data structure encodes some 3-manifolds with exponentially less space compared to the usual triangulation representation of 3-manifolds, while still allowing for efficient algorithms to manipulate and investigate their topology. This package implements some of these manipulations, which are explained in greater detail in the mentioned paper.

Philosophy

Although there exist Python packages for constructing and manipulating SLPs, we opted to implement an SLP module by hand. There are a few reasons behind this decision.

1. We wanted to stick to a particular syntax and notation. In particular, we use SLPs that are not in binary form (Chomsky normal form), allowing for mixed assignments and better communication with Twister notation.
2. This is also a proof of concept: SLPs are fun and among the easiest data structures one could hope for, while still achieving compression power comparable to the binary representation of integers.

Moreover, although all of this code would be significantly faster if implemented in different languages (and, indeed, speed is an important aspect of our argument here), we opted to have everything in Python, in the name of accessibility (and the author's better acquaintance with this programming language).

Finally, the code is extensively commented, and some (but not all) programming choices were made for the sake of pedagogy and not efficiency.

Installation

You can install the project with pip.

# Clone the repository
git clone https://github.com/HLovisiEnnes/FHDpy/

# Option 1: Install in editable mode (recommended for development)
pip install -e .

# Option 2: Install normally
pip install .

About this version

For someone who has read the original paper, it will soon become clear that, although all experiments from Section 5 solely use this package, we deviate in two major aspects from the rest of the text:

1. we do not necessarily consider triangulations of surfaces, but rather more general cellular complexes;
2. we do not use normal coordinates as inputs.

These choices make sense in the experiments described here (i.e., when the inputs are words in the mapping class group represented by some generating set), but they make some of the algorithms described in Section 4 not readily useful. In due time, however, we plan to extend this code to include those cases, although we will likely not achieve the advertised running times for all.

In order of priority, we want to implement in the next versions:

1. Stefankovic's randomized normalization algorithm;
2. automatic construction of marked triangulations of closed surfaces of arbitrary genus;
3. the Erickson–Nayyeri algorithm for tracing street complexes (this one will probably take even longer).

Unfortunately, we are not able to give exact deadlines for these implementations, but the author would gladly accept suggestions for further improvements.

Tutorial

The package is divided into three (very short) modules, one for the SLP machinery, one for the Heegaard diagrams, and one for finite group presentations. There are two tutorial notebooks for each of the first two modules, the third one is still experiemental and more functions will be implemented soon. Although the FHD module uses SLP, the converse is not true, and many SLP-only functions are implemented. The images and experiments described in the paper can be found in ExperimentsWithFHD.ipynb.