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 Simplified Incidence Graph (SIG), initially proposed in [21] for representing simplicial complexes of any dimension, not necessarily embedded in the Euclidean space. In particular, we propose its extension to cell complexes, and its description as mangrove in our Mangrove TDS Library.
The Simplified Incidence Graph (SIG) is an explicit incidencebased representation for any domain, including nonmanifolds (see the NonManifold Complexes Section) of any dimension, discretized by simplicial and cell complexes of any dimension, not necessarily embedded in the Euclidean space.
Given any cell complex , the SIG data structure encodes all cells, and, for each cell in , its immediate faces and a subset of its cofaces. In particular, for each cell , it encodes:
Recall that any cluster in the star of is any maximal, connected subcomplex of , formed only by top cells in the star of . Following Figure shows two clusters of cells in the star of a vertex . The representative cells are depicted in grey.
The graphbased representation of the SIG data structure, which we call the SIGgraph, is a global mangrove. Let any cell complex , then the SIGgraph is formed by:
We call the spanning subgraph of , formed by all nodes and boundary arcs, as SIG Boundary Graph. Similarly, we also call the spanning subgraph of , formed by all nodes and coboundary arcs, as SIG Coboundary Graph.
Most topological queries, like retrieving boundary or the star of any cell , can be expressed as breadthfirst traversals of nodes in the SIGgraph, which are reachable from the corrensponding node . In particular, the key operation consists of expanding and reconstructing the content of each cluster of top cells in the star of any cell.
In particular, it is very efficient to recognize nonmanifold cells, which are joints among clusters of different dimensions (see red arcs in the SIG Coboundary Graph in the above Figure). Here, for the sake of simplicity, coboundary arcs are depicted as nonoriented.
The SIG data structure is implemented in the mangrove_tds::Mangrove_SIG class, which is a subclass of the mangrove_tds::Mangrove_GlobalMangrove class.
In particular, nodes of the SIGgraph, representing any cell complex , are stored in arraybased collections of topological entities (see the Internal Encoding of Mangroves Section), one for each collection of cells in .
For a node , corresponding to any cell , only indices of immediates faces of (of dimension ) and of the top cells in (with ) are stored.
The mangrove_tds::Mangrove_SIG 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 SIG data structure.
template< class Derived > class Mangrove_SIG : public Mangrove_GlobalMangrove< Derived > { public: /* Implementing topological queries and editing operators. */ ... };
In particular, in the mangrove_tds::Mangrove_SIG class, it is also possible to customize the order of immediate subfaces (and thus of arcs) to be stored in boundary relations of any node. This aspect may be applicationdependent, and it is fundamental for defining what top cells can be represented in the SIG data structure. In order to support a wide range of possibilities, the current implementation of this aspect is parametric in the mangrove_tds::Mangrove_SIG class. This aspect 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_SIG_Simpl : public Mangrove_SIG< Mangrove_SIG_Simpl > { public: /* Topological queries and editing operators are inherited. */ ... /* Sorting immediate faces */ ... }; class Mangrove_SIG_Cell : public Mangrove_SIG< Mangrove_SIG_Cell > { public: /* Topological queries and editing operators are inherited. */ ... /* Sorting immediate faces */ ... };