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

Here, we briefly summarize our experiments, already discussed in [14], regarding topological data structures, that we have designed and implemented within our Mangrove TDS Library.
In particular, we concentrate our attention on:
As shown in the What we have in the Current Literature Section, most of tools in the literature are not extensible, and do not support any rapid prototyping capabilities.
Moreover, most of them do not support efficiently nonmanifold domains, and it may be an issue in the applications. In fact, another interesting properties of a mesh database is given by the efficient representations of nonmanifolds and the recognition of nonmanifold singularities, when possible. In fact, this operation is not decidable for combinatorial complexes, with [38]. As shown in [14], some topological data structures do not support this operation at all, or do not provide any information regarding the structure of the neighborhood for any cell. In this latter case, it is necessary to reconstruct the neighborhood of any cell from scratch. For instance, we suppose to encode the following complexes with The IG data structure [27]. In both cases, the star of vertex contains edges (in bold lines), that form coboundary relation , stored in the Incidence Graph in both cases. But, in the first case, vertex is manifold, while it is nonmanifold in the second case. Thus, we cannot state anything regarding without reconstructing the connected components in the link of . This operation may be expensive, namely linear in the number of cells in the star of , as shown in [14].
On the contrary, experimental results show that The IS data structure and The IA* data structure support recognition of nonmanifold singularities in an efficient way in the average case. For instance, in the IS data structure [23], any cell is nonmanifold if partial coboundary relation contains more than one cell, corresponding the number of connected components in the link of . In the IA* data structure [13], any vertex is nonmanifold if its star is formed by more than one cluster of any dimension , corresponding to partial coboundary relation . In the same way, a face of any top cell is nonmanifold if . In both the IS and IA* data structures, the time complexity of these operations is , like in the previous examples. In the remaining cases, it is necessary to reconstruct onthefly the topology of the link in the same way of the IG data structure. However, they encode the sufficient information for retrieving information of interest efficiently, and without encoding the complete immediate star of any cell in the IG data structure. This implies that the IG data structure becomes very verbose when representing manifolds, like in the previous example, as already stated in [19],[24],[23].
The following schema, already presented in [12], summarizes properties, including the recognition of nonmanifolds, of mesh databases, that we mentioned in the What we have in the Current Literature Section.
The VCG Library [45]  The OpenMesh Library [39]  The OpenVolumeMesh Library [40]  The CGoGN Library [16]  The CGAL Library [15]  
Type of Complexes  Simplicial  Cell  Cell  Cell  Any 
Dimension of Complexes  Up to 3  Up to 2  Up to 3  Any  Any 
Internal Representation  Adjacencybased  OM [5]  OVM [34]  Combinatorial Maps [33]  Many 
Extensibility  No (limited)  No (limited)  No (limited)  No (limited)  Modules 
NonManifolds  Yes (efficient)  Yes, but not at edges  Yes, but not efficient  Only QuasiManifolds  Yes 
Following Figures show the storage costs for topological data structures, used by these tools, and for all topological data structures, that we have designed and implemented in our Mangrove TDS Library.
In particular, when representing complexes, we consider:
 
In particular, when representing complexes, we consider:

As a consequence, most of these tools are based on topological data structures, that are more verbose than the Incidence Graph [27] (see The IG data structure Section). This latter represents complexes of any dimension with a nonmanifold domain, it may be verbose, and requires a large overhead, when representing manifolds [19],[14]. In particular, it does not expose nonmanifold singularities explicitly, and does not allow for their fast recognition, as stated above.
On the contrary, our Mangrove TDS Library, thanks to its modular and extensible architecture, supports any topological data structure, including those representations, which are efficient in space and in recognizing nonmanifold singularities, and do not introduce overhead when representing manifolds, like the Incidence Simplicial (IS) data structure [23] (see The IS data structure Section), the Simplified Incidence Graph (SIG) [21] (see The SIG data structure Section), and the Generalized Indexed data structure with Adjacencies (IA*) [13] (see The IA* data structure). These latter are dimensionindependent for abstract complexes, not necessarily embedded in any Euclidean space.
In [14], we have deeply compared efficiency of topological queries (mentioned in Operations on Mangroves Section) on all topological data structures, currently implemented in our Mangrove TDS Library.
In any case, our tests show that the IA* and IS data structures offer an optimal compromise regarding expressive power, storage cost, and efficiency of topological queries for  and complexes. Specifically, the IA* data structure can be considered as the most efficient data structure among those we have analyzed.
Recall that the IA* data structure encodes only vertices and top cells for abstract complexes of any dimension. However, our tests also show that the ghost references improve expressive power of partial mangroves, like the IA* data structure, and allow performing topological queries faster (or a with a limited overhead) with respect to global mangroves, like the IS data structure. For instance, the large majority of vertexbased queries are more efficient on the IA* data structure, like, for instance, the STAR, COBOUNDARYK, and LINK queries. Again, the combinatorial boundary of any top cell can be retrieved, in terms of ghost references, without navigating all boundary relations. In fact, it is necessary to generate ghost references, related to faces of by considering only the type of (see the Ghost Topological Entities Section).
Following Figures show mean running times (in milliseconds) of the BOUNDARY, STAR, and LINK queries on the IS and the IA* data structures for all complexes, analyzed in [14].
Specifically, the BOUNDARY query, executed on any simplex, is about faster in the IA* data structure. The STAR and the LINK queries, executed on any vertex, are, respectively, about and times faster in the IA* data structure. On the contrary, retrieving the STAR query for any ghost edge is only is only faster in the IS data structure, despite the need to retrieve all top cells in the star of vertices of in the IA* data structure.
Note that the BOUNDARY, the STAR, and the LINK queries play a key role in our modeling framework. For instance, the IS MANIFOLD query, when it is not possible to state immediately, is based on the analysis of the link of any cell (thus on the LINK query), and it results in a quick implementation. The ADJACENCY query, except for maximal cells, is performed by combining the BOUNDARY and the STAR queries. According to our tests in [14], it is is slightly slower than on the IG data structure (less than ). Recall that, for any cell, the IG data structure encodes immediate boundary relation and immediate coboundary relation , thus the time complexity of adjacency relation can be considered as almost constant. In the other data structures (including the IA* data structure), it is necessary to extract these relations explicitly. In any case, our tests show that the IA* data structure is the most efficient for doing it, except the Incidence Graph, thanks to the efficiency of the above queries.
Our Mangrove TDS Library is completely dimensionindependent, and can also support topological data structures, representing highdimensional complexes. In particular, it may support representations, specialized for highdimensional shapes in the context of computational topology, like those described in [3],[4].
In our current work, we have started to study the behavior of the IG, IS, and IA* data structures when representing dimensional complexes, with . Some preliminary results have been briefly presented in [12]. In particular, we have analyzed dimensional versions of the Sierpinski shape (with ) with and maximal simplices. These shapes have been represented, respectively, with the IG, the IS, and the IA* data structures. Following Tables and Figures show experimental results regarding the storage costs of topological data structures, expressed as the number of references. Here, the storage cost of Euclidean coordinates is not considered. For the sake of clarity, the ratio between the IG and IS data structures is shown separately, since they have basically the same behavior for high dimensions.
 
Another test we have performed consists of understanding the level of saturation for these topological data structures. In other words, it would be interesting to understand the maximum dimension and the maximum size of complexes, that can be represented by our plugins on a specific PC.
In order to address this problem, we have exploited The Mangrove_sature* unit tests on the IG, the IS, and the IA* data structures. Recall that these unit tests apply stellar operators on top simplices, directed encoded in our topological data structures, until almost the physical among of RAM in the current platform is needed and completely assigned. Following Table summarizes our experimental results regarding the saturation of our topological data structures on an Intel i7 Processor with RAM, where we have limited the analysis to dimensional versions of the Sierpinski shape (with ) with and maximal simplices.
IG  IS  IA*  
All these experiments show how the IG and the IS tend to be much expensive when representing highdimensional shapes. In particular, their storage cost tend to exponentially grow with respect to the dimension of the complex. Hence, they should not be exploited in high dimensions. On the contrary, the IA* data structure is much more compact for any dimension , e.g., it is, respectively, and times more compact than the and the data structures for complexes. In any case, we can conjecture that the IA* data structure is surely suitable for applications in medium dimensions.