Data associations (grid functions)IntroductionOverview over the Grid CategoryThe combinatorial grid layer

The combinatorial grid layer

Central to the notion of a grid are the combinatorial relationships among its entities of different dimension, namely, their incidence relation.

The combinatorial grid layer consists of (combinatorial) Grids (C) as comprehensive entities, grid elements (C), like Vertex, Edge, or Cell, which are its building blocks, element handles (C) (minimal representations or indices of elements), sequences iterators (C) that allow to iterate over all elements of a given type, and incidence iterators (C) allowing to iterate over all elements of some fixed dimension incident to a given element.

a grid consisting of 2 adjacent triangles (2 cells, 5 edges, 4 vertices)

A simple grid ...
the lattice of this grid
...and its lattice

For example, in the images, the grid consists of the following elements: vertices v1, ..., v4, edges e1, ...e5 and cells c1, c2. Their incidence relation is given by the lattice, where two different elements x, y are incident, if there is a path from x down to y (the path is not allowed to visit the same level more than once). Therefore, elements of the same dimension are never incident, only adjacent. For example, c1 is incident to v3, and adjacent to c2.

These concepts give rise to a lot of different concrete types which are associated with a concrete grid type. Because this association is so fundamental and important, we use the special grid-types entity to represent it. This is a class template which is specialized for concrete grid types, and thus acts as a mapping from concrete grid types to the associated types introduced below.


Basically, a grid consists of a collection of vertices, edges etc. which are termed k-Elements (other common names are k-Faces or k-cells).
The notion is captured by the following types, named according to their dimension and their co-dimension.


Dimension Codimension
Vertex 0 -
Edge 1 -
Face 2 -
Facet - 1
Cell - 0

Other common names are node (for vertex) and volume (for cell). These are not used here.

The above naming scheme allows for a dimension-independent formulation of many algorithms: e.g. fluxes are always defined on Facets (see example).

In general, some of these types can coincide: for a 2D-grid, the types Edge and Facet are often the same. Also, the type Face cannot be defined for 1D-grids.

Element handles

An element implementation must be a class, because there are some member functions required (C). A corresponding object must contain a reference to the underlying grid, which is redundant when considering sets of elements belonging to the same grid. For a minimal representation of elements, often just a number (a element handle) is required, which allows unambiguous reconstruction of an element belonging to a given grid.

Element handles can be used to represent sets of elements in an economic way, or to implement mappings between different grids (grid morphisms).

Sequence iterators

At a basic level, a grid can be seen as a container of its elements, that is, as a sequence of vertices, edges and so on. Correspondingly, a grid defines sequence iterators (C) to capture this property.

These iterators satisfy the STL Forward Iterator requirements.

A cell iterator hopping from cell to cell
A cell iterator

Examples: A loop over all vertices of a grid G would read:

       my_grid_type g;
       // ...
       int nv = 0;
       for(VertexIterator v = g.FirstVertex(); ! v.IsDone(); ++v)
       ASSERT( nv == g.NumOfVertices() );

To draw the line-graph of a grid, we would do:

       my_geometry geom(g);
       // ...
       for(EdgeIterator e = G.FirstEdge(); ! e.IsDone(); ++e)
         draw(geom.<FONT COLOR="008F00">segment</FONT>(*e));

Incidence iterators

Grids are more than just a collection of vertices, edges and so on. We want to be able to navigate through the neighbourhood of an k-element. For this purpose, we need incidence iterators. For example we might want to access all vertices incident to a cell.

A cell-on-cell iterator loops through the 3 adjacent triangles of a triangle
A cell-on-cell iterator

In order to iterate over the incident elements of a Cell, we can implement (and use) the following iterators:


EdgeOnCellIterator Cell::FirstEdge()
FacetOnCellIterator Cell::FirstFacet()
CellOnCellIterator Cell::FirstCell()

The corresponding iterators for vertices have analogous names. Strictly speaking CellOnCellIterator is not an incidence-iterator, because two neighboring cells are not incident. A typical example might be to calculate flows over cell boundaries. In pseudo-code, this reads:

     for all cells c of the grid g
        initialize the flux to 0
        for all facets fc  of the cell c
          add the flux over fc to the flux of c

Using our concepts, this translates into the following:

 a_grid_type g;
 typedef <FONT COLOR="008F00">grid_types</FONT><a_grid_type> gt;
 // ....
 grid_function<Cell,flux_type> fluxes(g);
 for(gt::CellIterator c = g.FirstCell(); ! c.IsDone(); ++c) {
   fluxes[*c]= flux_type(0.0);
   for(gt::FacetOnCellIterator f = (*c).FirstFacet(); ! f.IsDone(); ++f)
     fluxes[*c] += calculate_flow(f);

Here flux_type depends on the application and typically is a vector of low dimension.

Guntram Berti

Data associations (grid functions)IntroductionOverview over the Grid CategoryThe combinatorial grid layer