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

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 dimensionindependent 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 nonmanifolds, 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 basic idea underlying our library is that the connectivity among the cells and simplices in a complex can be described as a graphbased 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 breadthfirst 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.
Another interesting feature of our Mangrove TDS Library is provided by what we call ghost topological entities. Adjacencybased 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 to one top cell bounded by .
As experimentally shown in [14], ghost topological entities highly improves the efficiency of topological queries and the expressive power of any adjacencybased representation, which becomes almost equivalent to an incidencebased 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 adjacencybased data structure, equipped with ghost topological entities, may be a fair solution for many tasks with respect to using an incidencebased data structure, considerably more expensive.
You can refer to the Ghost Topological Entities Section for more details, regarding ghost topological entities.
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:
the Incidence Graph (IG) [27] (see The IG data structure Section);
the Incidence Simplicial (IS) data structure [23] (see The IS data structure Section);
the Simplified Incidence Graph (SIG) data structure [21] (see The SIG data structure Section);
the Generalized Indexed data structure with Adjacencies (IA*) [13] (see The IA* data structure Section);
the Extended Indexed data structure with Adjacencies (EIA) [24] (see The EIA data structure Section).
We have also implemented two dimensionspecific data structures for, respectively, cell and simplicial 2 and 3complexes, necessarily embedded in the Euclidean 3D space, namely:
the TriangleSegment (TS) data structure [22] (see The TS data structure Section);
the NonManifold Indexed data structure with Adjacencies (NMIA) [18] (see The NMIA data structure Section).
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.