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

Here, we propose a brief analysis of the Extended Indexed data structure with Adjacencies (EIA), initially proposed in [24] for representing simplicial complexes of any dimension. In particular, we briefly propose its extension to a specific class of cell complexes, and its description as mangrove in our Mangrove TDS Library.
The Extended Indexed data structure with Adjacencies (EIA) is an explicit adjacencybased representation for pseudomanifolds (see the NonManifold Complexes Section) of any dimension, discretized by simplicial (but also cell) complexes, and not necessarily embedded in the Euclidean space.
Given any pseudomanifold cell complex , the EIA data structure encodes only vertices and maximal topological entities, plus a subset of coboundary relations for each vertex, and a subset of adjacency relation for each (maximal) topological entity in . In particular, for each maximal topological entity , it encodes:
For each vertex , the EIA data structure encodes partial coboundary relation , which associates with one arbitrary maximal topological entity (representative cell) for each cluster in the star of . Recall that any cluster in the star of is a maximal subcomplex of , formed by maximal topological entities, which are incident at .
As shown in [24], the key operation consists of retrieving all maximal cells of in the star of any vertex . This topological query can be expressed as the expansion of each cluster in the star of through adjacency relation (directly encoded). Its time complexity is linear in the number of maximal cells of interest, thus it is optimal.
The graphbased representation of the EIA data structure, which we call the EIAgraph, is a partial mangrove. Let any cell complex , then the EIAgraph is formed by:
We call the spanning subgraph of , formed by all nodes, corresponding to vertices and maximal topological entities, and by boundary arcs, as the EIA Boundary Graph. Similarly, we also call the spanning subgraph of , formed by all nodes, corresponding to vertices and maximal topological entities, and by coboundary arcs, as the IG Coboundary Graph. We also call the spanning subgraph of , formed by all nodes, corresponding to maximal topological entities, and by adjacency arcs, as the EIA Adjacency Graph.
Encoding the EIAgraph as mangrove requires to store also several Hasse diagrams (see the Ghost Topological Entities Section), one for each type of maximal cells cells in . Experimental results in [12],[14] show that their storage cost does not depend on the number of maximal cells in , and their storage cost is basically not relevant.
The EIA data structure is implemented in the mangrove_tds::Mangrove_EIA class, which is a subclass of the mangrove_tds::Mangrove_PartialMangrove class.
In particular, nodes of the EIAgraph are stored in two arraybased collections of topological entities (see the Internal Encoding of Mangroves Section), one for vertices and one for maximal cells.
For a node , corresponding to a maximal cell , only indices of its vertices (of dimension ) are stored, as well as indices of maximal cells (of dimension ), adjacent to .
For a node , corresponding to a vertex , only indices of representative maximal cells for clusters, incident at , are stored.
The mangrove_tds::Mangrove_EIA class contains implementations of all topological queries, and editing operators. It is a templated class itself, built on the template Derived class. This latter is exploited in the context of the Curiously Recurring Template Pattern (as inherited by the mangrove_tds::Mangrove_Mangrove class) in order to implement the static polymorphism. In this way, we can reuse some parts and provide only member functions, specialized for the EIA data structure.
template< class Derived > class Mangrove_EIA : public Mangrove_PartialMangrove< Derived > { public: /* Implementing topological queries and editing operators. */ ... };
In particular, in the mangrove_tds::Mangrove_EIA class, it is also possible to customize two aspects:
Specifically, these two aspects are fundamental for defining what maximal cells can be represented in the EIA data structure. In order to support a wide range of possibilities, the current implementation of these aspects is parametric in the mangrove_tds::Mangrove_EIA class. These aspects must be managed in the templated Derived class, which is also a trait class. In the current implementation, we propose two specific traits:
class Mangrove_EIA_Simpl : public Mangrove_EIA< Mangrove_EIA_Simpl > { public: /* Topological queries and editing operators are inherited. */ ... /* Sorting vertices in increasing order */ ... /* Retrieving topological queries from supported Hasse diagrams. */ ... }; class Mangrove_EIA_Cell : public Mangrove_EIA< Mangrove_EIA_Cell > { public: /* Topological queries and editing operators are inherited. */ ... /* Sorting vertices in increasing order */ ... /* Retrieving topological queries from supported Hasse diagrams. */ ... };