The Mangrove TDS Library  2.0
A C++ tool for the Fast Prototyping of Topological Data Structures
Our Contributions

Our contribution is given by the Mangrove Topological Data Structure (Mangrove TDS) Library, which has been designed, implemented, and described in the PhD. Thesis in Computer Science [14] of Dr. David Canino. His research has been conducted under the supervision of Professor Leila De Floriani, at the Department of Computer Science, Bioengineering, Robotics and Systems Engineering, University of Genova, Genova, Italy (DIBRIS).

Our Mangrove TDS Library offers an effective and efficient solution to the problems mentioned in the Introduction Chapter.

The original purpose of our work was to have a library implementing efficient data structures for simplicial and cell complexes, which are dimension-independent and entirely general, that is not geared only to complexes embedded in Euclidean space. In particular, we focus our attention on representations able to manipulate also non-manifolds, since the most tools in the current literature are not able to manage these shapes efficiently [14] (see also What we have in the Current Literature Section). A first description of our framework, restricted to simplicial complexes, is given in [12].

In particular, our Mangrove TDS Library offer three important contributions:

The First Contribution: Mangroves

The basic idea underlying our library is that the connectivity among the cells and simplices in a complex can be described as a graph-based representation, which we call a mangrove. Mangroves, which form a particular class of graphs, are exploited for describing the generic prototype of a topological data structure, mentioned in The Rapid Prototyping Approach and its Advantages Section.

As a consequence, the key idea of our approach consists of customizing the content of a mangrove in order to simulate a specific topological data structure. Following [19], this latter can be described in terms of what topological entities and what topological relations are directly encoded. As a consequence, any topological data structure can be described by its corresponding mangrove. This allows to reuse several theoretical results of graphs' theory, applied to the topological data structures. In particular, topological queries can be expressed as breadth-first traversals of mangroves.

As a consequence, our tool can be easily extended by adding and reusing the internal representations of our library, able to represent graphs. This implies naturally that internal representation of any complex can be dynamically replaced in order to choose the most efficient one for any specific task. In particular, it is sufficient to exploit the most suitable mangrove for the task of interest.

Note that this can be done under a unique API application, which hides the content of any mangrove, giving the possibility to write a program only once.

You can refer to the Defining Mangroves Section for more details, regarding mangroves.

The Second Contribution: Ghost Topological Entities

Another interesting feature of our Mangrove TDS Library is provided by what we call ghost topological entities. Adjacency-based data structures [19], are widely used for representing simplicial complexes, and they encode only vertices and top simplices (those that do not bound other simplices). As a consequence, it is not possible to execute topological queries on any cell. This may be a problem for our goals, illustrated in The Rapid Prototyping Approach and its Advantages Section.

Specifically, ghost topological entities are implicit representations of those cells not encoded explicitly. The key idea consists of associating each cell with at least one arbitrary top cell bounded by it. Thus, it is possible to exploit adjacency relations, encoded only for top cells, without navigating on a maximal path from a cell $\sigma$ to one top cell $\sigma'$ bounded by $\sigma$.

As experimentally shown in [14], ghost topological entities highly improves the efficiency of topological queries and the expressive power of any adjacency-based representation, which becomes almost equivalent to an incidence-based one, i.e., to a representation in which all cells are explicitly encoded [19].

However, ghost topological entities requires auxiliary data structure for being effective. In any case, as shown in [12], this overhead does not depend on the size of the complex, but only on the different types of its cells. Hence, it can be considered negligible. Therefore, an adjacency-based data structure, equipped with ghost topological entities, may be a fair solution for many tasks with respect to using an incidence-based data structure, considerably more expensive.

You can refer to the Ghost Topological Entities Section for more details, regarding ghost topological entities.

The Third Contribution: Seven Topological Data Structures

The validity and the modeling capabilities of our Mangrove TDS Library are shown by implementing SEVEN topological data structures with complementary properties by exploiting the rapid prototyping capabilities of our tool.

Specifically, we have implemented five data structures for simplicial and cell complexes of arbitrary dimension, and not necessarily embedded in the Euclidean space, namely:

We have also implemented two dimension-specific data structures for, respectively, cell and simplicial 2- and 3-complexes, necessarily embedded in the Euclidean 3D space, namely:

The first three data structures can represent both arbitrary simplicial and cell complexes of any dimension. On the contrary, the remaining topological data structures can represent simplicial complexes of any dimension and a limited class of cell complexes (but very relevant in the applications), such that cells have a constant number of boundary cells, like quadrilaterals, pentagons, hexagonals, and hexahedra.

An interested reader can refer to the Defining Mangroves Section for understanding how it is possible to design and implement a topological data structure as a mangrove within our tool.

In [14] we have also performed experimental results regarding the efficiency of topological queries for these representations. These results are also summarized in [12] and in the Experimental Results Section.

Our Mangrove TDS Library IS NOT a mere collection of these data structures, but it is a GENERIC framework, specialized for the fast prototyping of topological data structures for simplicial and cell complexes. As shown in [14], any topological data structure can be successfully designed within our library. In future versions of the Mangrove TDS Library, the number of topological data structures will be surely increased.