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

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.

Formal Definition

The Simplified Incidence Graph (SIG) is an explicit incidence-based representation for any domain, including non-manifolds (see the Non-Manifold Complexes Section) of any dimension, discretized by simplicial and cell complexes of any dimension, not necessarily embedded in the Euclidean space.

Given any cell $d-$-complex $\Gamma$, the SIG data structure encodes all cells, and, for each cell in $\Gamma$, its immediate faces and a subset of its cofaces. In particular, for each $p$-cell $\gamma$, it encodes:

  • immediate boundary relation $\mathcal R_{p,p-1}(\gamma)$, which associates $\gamma$ with its immediate $(p-1)$-faces (if $p>0$);
  • partial immediate co-boundary relation $\mathcal R^*_{p,q}(\gamma)$, with $q=p+1,\ldots,d$, which associates $\gamma$ with one arbitrary top $q$-cell (known as representative cell), for each cluster of top $q$-cells in the star of $\gamma$.

Recall that any $q$-cluster in the star of $\gamma$ is any maximal, $(q-1)$-connected subcomplex of $\Gamma$, formed only by top $q$-cells in the star of $\gamma$. Following Figure shows two clusters of $3$-cells in the star of a vertex $v$. The representative $3$-cells are depicted in grey.

pseudomanifold.png
Example of two 3-clusters in the star of vertex v. Their representative 3-cells are depicted in grey.

The SIG-graph

The graph-based representation of the SIG data structure, which we call the SIG-graph, is a global mangrove. Let $\Gamma$ any cell $d$-complex $\Gamma$, then the SIG-graph $\mathcal G^{SIG}_\Gamma$ is formed by:

  • nodes corresponding to any cell in $\Gamma$. A node $n_\gamma$ corresponds to any cell $\gamma$ in $\Gamma$, directly encoded in the SIG data structure.
  • Boundary arcs $(n_\gamma,n_{\gamma'})$, corresponding to boundary relation $\mathcal R_{p,p-1}$, such that $\gamma\sim_{pp-1}\gamma'$.
  • Co-boundary arcs $(n_\gamma,n_{\gamma'})$, corresponding to any partial co-boundary relation $\mathcal R^*_{p,q}$, for any $q>p$, such that $\gamma\sim^*_{pq}\gamma'$.

We call the spanning subgraph of $\mathcal G^{SIG}_\Gamma$, formed by all nodes and boundary arcs, as SIG Boundary Graph. Similarly, we also call the spanning subgraph of $\mathcal G^{SIG}_\Gamma$, formed by all nodes and co-boundary arcs, as SIG Co-boundary Graph.

IS_link2.png
Example of simplicial 3-complex
 
IS-boundary.png
SIG Boundary Graph
 
SIG_coboundary.png
SIG Co-boundary Graph. For the sake of simplicity, arcs are not depicted as oriented.
 

Most topological queries, like retrieving boundary or the star of any cell $\gamma$, can be expressed as breadth-first traversals of nodes in the SIG-graph, which are reachable from the corrensponding node $n_\gamma$. 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 non-manifold cells, which are joints among clusters of different dimensions (see red arcs in the SIG Co-boundary Graph in the above Figure). Here, for the sake of simplicity, co-boundary arcs are depicted as non-oriented.

Attention
Note that the SIG Boundary Graph is the same as the IG Boundary (see The IG-graph) and the IS Boundary Graph (see The IS-graph). On the contrary, each arc of the SIG Co-boundary Graph can be seen as a compressed version of any maximal path in The IG-graph from any node $n_\gamma$ to a node corresponding to a top cell in the star of $\gamma$. As a consequence, the SIG data structure can be considered as a compact version of The IG data structure, as shown in [14].

Some Implementation Remarks

The SIG data structure is implemented in the mangrove_tds::Mangrove_SIG class, which is a subclass of the mangrove_tds::Mangrove_GlobalMangrove class.

Attention
Generally speaking, for each node $n_\gamma$, only the unique identifiers of endpoints of arcs, outgoing from $n_\gamma$, are stored, and their dimension is implicit.

In particular, nodes of the SIG-graph, representing any cell $d$-complex $\Gamma$, are stored in $d+1$ array-based collections of topological entities (see the Internal Encoding of Mangroves Section), one for each collection of cells in $\Gamma$.

For a node $n_\gamma$, corresponding to any $p$-cell $\gamma$, only indices of immediates faces of $\gamma$ (of dimension $p-1$) and of the top $q$-cells in $\mathcal R_{p,q}^*(\gamma)$ (with $p>q$) are stored.

Attention
Note that none arc, related to adjacency and/or auxiliary boundary relations, is encoded, thus only the effective content of the SIG data structure is encoded.
In any case, note that this information is almost transparent for the user, which may exploit capabilities of the mangrove_tds::Mangrove_Mangrove class.

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 application-dependent, 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:

  • one trait, specific for simplicial complexes, where immediate subfaces of any simplex are recursively generated as imposed by the simplicial homology. This trait is provided by the mangrove_tds::Mangrove_SIG_Simpl class.
  • one trait, specific for cell complexes, where immediate subfaces of any cell are mostly and recursively sorted according to the STEP format, very common in exchanging data in CAD applications. This trait is provided by the mangrove_tds::Mangrove_SIG_Cell class.
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 */
    ...
};
Attention
You can write your own traits with these properties.
In any case, note that these operations are almost transparent for the user, which MUST NOT exploit directly the mangrove_tds::Mangrove_SIG class, but ONLY traits. For instance, one between the mangrove_tds::Mangrove_SIG_Cell or the mangrove_tds::Mangrove_SIG_Simpl classes, but also one custom trait can be exploited.
All Unit Tests Programs demonstrate the correctness and the validity of this modular approach, which has been also exploited for other topological data structures.