- 7.1.1 The 0-Cell Complex
- 7.1.2 The 1-Cell Complex
- 7.1.3 The 2-Cell Complex
- 7.1.4 Higher-Dimensional Cell Complexes
- 7.1.5 Data Access

7.1 The Generic Topology Library

The most basic mechanisms of the GTL are the utilization of cell types and complex types, as explained theoretically in Section 1.3.2. A common topological data structure specification scheme can thereby be derived, as given in Section 5.1.

The GTL transforms each of the given theoretical concepts into a
module, where the connection matrix implementation builds the base for
the GTL. The poset concept and the corresponding cell topology is
implemented by a cell property module, where several posets for
different dimensions are stored. Also, several boundary operations for
cell traversal are thereby covered. The complex module then implements
the local and global cell complex properties, whereby the global cell
complex uses procedurally generated incidence and adjacence
information and the local cell complex requires the information stored
in the connection matrix. The quantity storage module enables an
interface to various container structures. Finally, the container
layer uses the index space concept and implements an interface to the
cell and complex properties.
A topological declaration of a simplex and a cuboid object with their
respective dimensions is illustrated in the next code
snippet^{7.1}.

The first specification describes a simple vertex element, a zero-dimensional simplex cell, whereas the second line specifies a cube, a three-dimensional cell. Based on the poset mechanism of the GTL and the concept of a boundary operator (Section 5.2 and Section 5.3), different types of incidence traversal operations are already available. This means that the complete cell topology can be used. However, the cell topology does not contain any cell complex information, such as neighboring cell information.

This information is available by the topology of cell complexes, where only a few complex types are presented in the following code snippet. It should be noted here, however that the complex type is definitely not restricted to these types of cells. Arbitrary types can be used which model the corresponding concepts.

As can be seen, a variety of data structures is thereby uniformly available. Various underlying implementations can be used with a topological formal interface, e.g., the GrAL library for the third line. Basically, the GTL represents a formal topological interface for different types of data structures. Additionally, it provides implementations for the topologies introduced in Section 5.1.

These two parts also integrate a homogeneous access to compile-time
and run-time mechanisms. It is important to implement the different
evaluation times separately in order to obtain an overall high
performance.
The following table gives an overview of the different parts of the
library with their corresponding evaluation times.

compile-time | run-time | |

cell topology, simplex | yes | no |

cell topology, cuboid | yes | no |

cell topology, polytope | no | yes |

complex topology, local | no | yes |

complex topology, global | yes | no |

An example of the connection matrix, e.g., for a 3-simplex cell complex, is depicted in Figure 7.3:

It can be seen that the connection matrix uses the orientation of the -cells and is sparse and enables incidence relations (from left to bottom) and adjacence relations (from bottom to left).
The implementation of the container concept is given which combines
the complex types (base space properties) with the data types (fiber
space properties), where the `indexspace` property is used to
introduce the distance of the data from the base space. Finally, an
interface to a quantity storage is available, which is connected to
the GTL by a unique identifier for each cell.

The given example uses an index space depth of zero, which means that
the data is directly stored at the cell location.

7.1.1 The 0-Cell Complex

The best known and most widely used data structures in programming can
be described by the 0-cell complex types, e.g., the data structures of
the C++ STL, depicted in Figure 7.4. The
reason for the common topological structure of the C++ STL data
structures is the fact that the iterators cannot access any higher
dimensional internal structure. One the one hand, this is one of the
major advances of the iterator approach of the STL by separating data
structure and algorithms. The implementation complexity is thereby
significantly reduced. On the other hand, all iterators can only
access the zero-dimensional cell of a data structure. Hence it is not
possible, e.g., to iterate over the neighbors of a C++
`std::map`.

The following source snippet introduces the specification of the given
topological classification scheme (Section
5.1) with respect to simple
well-known data structures, such as arrays or singly linked lists.
The tags *global* and *local* in the following code
snippet specify the locality of the complex topology.

These examples can also be expressed using the STL iterator traits to
classify the data structures:

The following code snippet demonstrates the equivalence of the STL and the GTL data structures:

Here, the separation of the topological structure from the data
specification is made explicit, in comparison to the STL, which,
unfortunately, combines traversal and data access. Several problems
are caused by this combined specification of a data
structure^{7.2}.
The given index-space concept is used to provide full backward
compatibility for the quantity access mechanism, which means that the
corresponding traversal mechanism can directly access the obtained
iterator.

7.1.2 The 1-Cell Complex

Another important representative of a commonly used cell complex is a
one-dimensional complex, usually called a graph. Figure
7.5 shows a typical example. A cell of this
type of cell complex is called an *edge*. Incidence and
adjacence information exists between edges and vertices.

In the following, the BGL facilities are compared to the traversal mechanisms provided by the GTL. The following example presents the traversal all edges of a 1-cell complex:

The GTL offers the same functionality as is demonstrated in the
following code snippet. The `global` tag is used to demonstrate
the global structure of the graph, which means that the internal data
layout is prepared for dense graph storage. In terms of the BGL, an
`adjacency graph` data structure is used.

Related to interoperability, all algorithms developed for the BGL can be used on this structure as well, including the property map concept. The property map can be seen as a specialization of the fiber bundle approach.

7.1.3 The 2-Cell Complex

Commonly used discretization schemes use as base requirement a two-dimensional cell complex, usually called a mesh or grid. Although this cell complex can be projected onto a graph, necessary information is not available for, e.g., a finite volume or finite element method. These schemes require at least cell information, which means that a two-dimensional cell is required. A graph does not contain any cell information except the edges. In the following, the topological specification mechanism is given with respect to two important types of 2-cell complexes, a structured grid and an unstructured mesh. The storage and traversal operators of structured grids benefit greatly from the global complex topology, because all traversal operations can be rendered at compile-time. No additional cell adjacence information has to be stored compared to the unstructured mesh.

To illustrate a traversal operation offered by the GTL, the following
code snippet presents a vertex-on-cell traversal with an additional
incident edge traversal. A graphical representation of this traversal
is given in Figure 7.6, where an arbitrary cell of
the complex is used. Then a vertex-on-cell traversal is initialized,
where the marked objects depict the currently evaluated objects. In
the first stage of the iteration the vertex `v1` is used, and
the iteration is performed over the incident edge `E1,E2`. The
iteration then continues with the remaining vertices.

The given code can be used for both of the 2-cell complex types, the
`complex_structured` and `complex_unstructured`. During
the loop, an edge-on-vertex traversal is created and initialized with
the evaluated vertex.

Traversal can be used independently of the dimension or type of cell complex. Only three topological properties have to be met by the cell complex: vertices, edges, and cells. All cell complex types which support these three objects can be used for this traversal.

To highlight the interoperability of the GTL, two examples are shown using an implementation of related work of the CGAL and GrAL. The first example presents the traversal mechanisms of the CGAL compared to the GTL. A traversal of all facets related to a cell is shown.

The special geometric object `Polyhedron` in terms of the GTL
is implemented by a common container type.

The CGAL can be used as a complete implementation of the
concepts given by the GTL. An interface layer is available to use all
CGAL data types within the GTL.

The second example is related to the GrAL. The close relationship
between the GrAL and the GTL makes a complete interoperability between
these libraries possible. Several different `grid_types` can
be used in GrAL, similarly to the GTL container type. The main
difference is the orthogonality of the cell types and the complex
types in the GTL.

As can be seen, the traversal mechanisms are implemented very closely
to the `grid_types`. The `random_access` property
cannot be used by all traversal operations. This complicates the
optimization and performance steps related to application design. The
next code snippet presents the GTL implementation. It should be noted
that the GTL interface can easily be implemented using the GrAL.

The interfaces can be exchanged easily and each of these libraries can
be used with the GTL interface. Therefore the reuse of source code due
to the GTL approach is a major advantage.

7.1.4 Higher-Dimensional Cell Complexes

The 3-cell complex is similar to the 2-cell complex, if simplex or cuboid cell types are used. Therefore the corresponding figures and code snippets are omitted. Based on the given formal definition of finite cell complexes, higher dimensions can be used as well. The theoretical mechanisms introduced in Section 1.3.2 and the implementation of the concepts given in Section 5.1 enable a clean interface for extensions, e.g., a 4-simplex, a pentachoron, depicted in Figure 7.7.

The poset of the 4-cube is omitted due to the large number of facets. Renderings of a 4-simplex and a 4-cube are presented in Figures 7.8-7.9.

The following code snippet shows the implementation of an arbitrary topology with the structure of the 4-cell simplex complex. All previously presented algorithms can be used, due to the common traversal mechanisms.

The GTL implements all the given data structures from Section 5.1 as well as generic algorithms for simplex and cuboid cell topologies of arbitrary dimensions.

7.1.5 Data Access

Separated by the fiber bundle approach, the stored data corresponding
to the topological elements, such as vertices or edges, is available
orthogonally by an element identifier, e.g., element number. During
initialization, the quantity accessor `q` is bound to a
specific domain with its quantity key. To access the underlying data,
the `operator()` is evaluated with a vertex of the cell complex
as argument and returns a reference to the stored value.

The implementation of the fiber bundle approach in the GTL follows:

As can be seen, the `base_index` selects the
respective fiber, whereas the `quan_key` selects the
corresponding fiber element. In contrast to the cursor and property
map concept, the fiber bundle approach allows traversal operations
within fiber space as well:

It is also possible to extract a section, which means that a whole
data set attached to a base space can be returned:

- ...
snippet
^{7.1} - Most of the
`typedef`s are omitted to make the given source snippets as clear and focused as possible. - ...
structure
^{7.2} - Detailed information related to this issue is given in Appendix B

R. Heinzl: Concepts for Scientific Computing