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

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:

  • their expressive power and their storage cost, specifically with respect to other representations in the literature, mentioned in the What we have in the Current Literature Section.
  • the efficiency of topological queries;
  • the representation of high-dimensional complexes.

Comparisons with Other Tools

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 non-manifold 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 non-manifolds and the recognition of non-manifold singularities, when possible. In fact, this operation is not decidable for combinatorial $d$-complexes, with $d\ge 6$ [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 $2$-complexes with The IG data structure [27]. In both cases, the star of vertex $v$ contains $5$ edges (in bold lines), that form co-boundary relation $\mathcal R_{0,1}(v)$, stored in the Incidence Graph in both cases. But, in the first case, vertex $v$ is manifold, while it is non-manifold in the second case. Thus, we cannot state anything regarding $v$ without reconstructing the connected components in the link of $v$. This operation may be expensive, namely linear in the number of cells in the star of $v$, as shown in [14].

Edges incident at a manifold and at a non-manifold vertex in any 2-complex.

On the contrary, experimental results show that The IS data structure and The IA* data structure support recognition of non-manifold singularities in an efficient way in the average case. For instance, in the IS data structure [23], any $p$-cell $\gamma$ is non-manifold if partial co-boundary relation $\mathcal R_{p,p+1}^*(\gamma)$ contains more than one $(p + 1)$-cell, corresponding the number of connected components in the link of $\gamma$. In the IA* data structure [13], any vertex $v$ is non-manifold if its star is formed by more than one cluster of any dimension $p$, corresponding to partial co-boundary relation $\mathcal R_{0,p}^*(v)$. In the same way, a $(p-1)$-face $\tau$ of any top $p$-cell is non-manifold if $\mathcal R_{p-,p}^*(\tau)\not=\emptyset$. In both the IS and IA* data structures, the time complexity of these operations is $\mathcal O(1)$, like in the previous examples. In the remaining cases, it is necessary to reconstruct on-the-fly 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 non-manifolds, 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 ComplexesSimplicialCellCellCellAny
Dimension of ComplexesUp to 3Up to 2Up to 3AnyAny
Internal RepresentationAdjacency-basedOM [5]OVM [34]Combinatorial Maps [33]Many
ExtensibilityNo (limited)No (limited)No (limited)No (limited)Modules
Non-ManifoldsYes (efficient)Yes, but not at edgesYes, but not efficientOnly Quasi-ManifoldsYes

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 $2$-complexes, we consider:
In particular, when representing $3$-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 non-manifold domain, it may be verbose, and requires a large overhead, when representing manifolds [19],[14]. In particular, it does not expose non-manifold 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 non-manifold 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 dimension-independent for abstract complexes, not necessarily embedded in any Euclidean space.

Note that also the Triangle Segment (TS) [22] (see The TS data structure Section), and the Non-Manifold Indexed data structure with Adjacencies (NMIA) [18] (see The NMIA data structure Section), have the same properties as the above data structures, but they are, respectively, restricted to $2$- and $3$-complexes, necessarily embedded in the 3D Euclidean space.

Efficiency of Topological Queries

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.

The main result of this analysis consists of understanding that there is not one topological data structure with an optimum behavior for all operations.

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 $2$- and $3$-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 vertex-based 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 $\gamma'$ 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 $\gamma'$ by considering only the type of $\gamma'$ (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 $3$-complexes, analyzed in [14].


Specifically, the BOUNDARY query, executed on any $3$-simplex, is about $30\%$ faster in the IA* data structure. The STAR and the LINK queries, executed on any vertex, are, respectively, about $30\%$ and $2.5$ times faster in the IA* data structure. On the contrary, retrieving the STAR query for any ghost edge $e$ is only is only $10\%$ faster in the IS data structure, despite the need to retrieve all top cells in the star of vertices of $e$ 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 $5\%$). Recall that, for any $p$-cell, the IG data structure encodes immediate boundary relation $\mathcal R_{p,p-1}$ and immediate co-boundary relation $\mathcal R_{p,p+1}$, thus the time complexity of adjacency relation $\mathcal R_{p,p}$ 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.

These results (regarding the IA* data structure) are very interesting, since the IA* data structure is more compact than any incidence-based topological data structure, and its storage cost remains basically unchanged, even if several auxiliary graphs for ghost references are needed.

Representing High-dimensional Complexes

Our Mangrove TDS Library is completely dimension-independent, and can also support topological data structures, representing high-dimensional complexes. In particular, it may support representations, specialized for high-dimensional shapes in the context of computational topology, like those described in [3],[4].

Designing these representations as mangroves, and writing the related plugins in our tool, are open problems to be addressed as future work.

In our current work, we have started to study the behavior of the IG, IS, and IA* data structures when representing $d$-dimensional complexes, with $d>3$. Some preliminary results have been briefly presented in [12]. In particular, we have analyzed $d$-dimensional versions of the Sierpinski shape (with $2\le d\le 8$) with $s_0$ and $s_d$ maximal $d$-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.

2D version of the Sierpinski shape
$d$  $s_0$  $s_d$ IG IS IA*

$2$  $2.8\times10^6$  $5.6\times10^6$  $44.8\times10^6$  $38\times10^6$  $22.4\times10^6$
$3$  $1.4\times10^6$  $4.2\times10^6$  $92.1\times10^6$  $68.6\times10^6$  $19.6\times10^6$
$4$  $0.7\times10^6$  $2.7\times10^6$  $149\times10^6$  $104.3\times10^6$  $14.9\times10^6$
$5$  $0.28\times10^6$  $1.4\times10^6$  $188\times10^6$  $123.6\times10^6$  $8.96\times10^6$
$6$  $0.12\times10^6$  $0.72\times10^6$  $222.6\times10^6$  $143.1\times10^6$  $5.3\times10^6$
$7$  $75\times10^3$  $0.52\times10^6$  $365.5\times10^6$  $228\times10^6$  $4.3\times10^6$
$8$  $34\times10^3$  $0.27\times10^6$  $425\times10^6$  $260\times10^6$  $2.5\times10^6$
Storage costs of the IG,IS, and IA* data structures.
Ratio among the storage costs of the IG, IS, and IA* data structures.
Ratio among the storage costs of the IG and IS data structures.
The Sierpinski shape is fractal, and thus it is scale-invariant. As a consequence, the ratio among the storage costs of our topological data structures does not depend on the $d$-complex scale, and it remains constant, for any $d$.

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 $64Gb$ RAM, where we have limited the analysis to $d$-dimensional versions of the Sierpinski shape (with $2\le d\le 8$) with $s_0$ and $s_d$ maximal $d$-simplices.


  $d$  $s_0$  $s_d$  $s_0$  $s_d$  $s_0$  $s_d$

  $2$  $67\times 10^6$  $134\times 10^6$  $67\times 10^6$  $134\times 10^6$  $67.1\times 10^6$  $134.2\times 10^6$
  $3$  $22.4\times 10^6$  $67\times 10^6$  $22.4\times 10^6$  $67\times 10^6$  $44.7\times 10^6$  $134\times 10^6$
  $4$  $13.4\times 10^6$  $53.7\times 10^6$  $13.4\times 10^6$  $53.7\times 10^6$  $32\times 10^6$  $128.5\times 10^6$
  $5$  $6.6\times 10^6$  $32.9\times 10^6$  $6.7\times 10^6$  $33.4\times 10^6$  $13.4\times 10^6$  $67.1\times 10^6$
  $6$  $3.1\times 10^6$  $18.9\times 10^6$  $3.2\times 10^6$  $19.2\times 10^6$  $11.2\times 10^6$  $67.1\times 10^6$
  $7$  $1.19\times 10^6$  $8.39\times 10^6$  $1.21\times 10^6$  $8.4\times 10^6$  $9.6\times 10^6$  $67.1\times 10^6$
  $8$  $0.76\times 10^6$  $6\times 10^6$  $0.78\times 10^6$  $6.3\times 10^6$  $8.4\times 10^6$  $67.1\times 10^6$

All these experiments show how the IG and the IS tend to be much expensive when representing high-dimensional shapes. In particular, their storage cost tend to exponentially grow with respect to the dimension $d$ 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 $d$, e.g., it is, respectively, $103$ and $170$ times more compact than the $IG$ and the $IS$ data structures for $8$-complexes. In any case, we can conjecture that the IA* data structure is surely suitable for applications in medium dimensions.

Understanding the behavior of the IA* data structure with high-dimensional shapes is currently an open issue, to be resolved as future work. In particular, it may be necessary to study the behavior and the storage cost of adjacencies, restricted to top cells, that may become very expensive to be encoded.
The Mangrove_sature* unit tests surely increase the resolution of the complex, and thus the storage cost of the corresponding mangrove. In any case, they also increase the number of adjacencies of maximal simplices. Thus, they can be also exploited for studying the influence of adjacency relation in high dimensions. In particular, our experimental results show that the storage cost of the IA* data structure is influenced mostly by adjacency relations. Another open problem, to be address as future work, consists of studying the storage cost of our topological data structures, when representing complexes with a limited number of adjacencies.