The geometric layerIntroductionThe combinatorial grid layerData associations (grid functions)

Data associations (grid functions)

In any serious application, we need to deal with values attached to k-elements: for example, state variables living on vertices in a typical FEM-program, costs on edges in network-flow algorithms or state variables on cells in a cell-centered Finite-Volume-code. There are two different aspects of this necessity:

On the one hand, such mappings are often passed to algorithms. Then, algorithms should make only minimal assumptions on the nature of the mapping, in particular, they should not commit to a particular representation of such data associations.

On the other hand, algorithms themselves often need to attach values to element temporarily. In this case, they have to be able to create such data associations themselves, and perhaps to decide on some performance-critical features of the implementations.

The underlying mathematical model of the first usage scenario is that of a function f from the set of k-Elements of a Grid

<TABLE class="image"> <TR> <TD class="image"> Grid function on cells

grid function on cells
</TD> <TD class="image"> Grid function on edges
Grid function on edges
</TD> </TR> </TABLE>

The grid function concept (C), is a natural interface which is close to the mathematical model. This interface can be implemented by many different representations, including calculation on-the-fly, and corresponds to the first requirement (data abstraction).

Beyond this, the second scenario (temporary values / local grid functions) requires a container component, which extends this interface with methods for creation of grid functions. The corresponding concept is container grid function (C).

There is a interesting and important choice left open now: Either, we can reserve memory for the value of each element in the grid, and considering each value not explicitly set on an element an error. Or, we could determine a default value, and consider each element whose valeu is not explicitely set having this default value. The first option leads to the total grid function concept (C) , storing a value for every element.

The second option gives rise to partial grid functions (C) which stores values only on a part of the grid elements, assigning a default value to the others.

Depending on the choice, there are slightly different semantics of the constructors, as well as same new operations in the case of partial grid functions.

Owing to the great importance of both total and partial grid function containers for the implementation of many algorithms, these entities should be available under a uniform syntax, if they are defined for a concrete grid type. More precisely, the following class templates are then available: (E is constrained to be an element type (C) associated to this grid type, T can be chosen arbitrary.)

template<class E, class T> 
class grid_function; // total grid function 
template<class E, class T>
class partial_grid_function; // partial grid function

There are examples of grids types without such associated grid functions. These are typically used for special restricted purposes only, like grid adapters for input from a file, which offer a clean way to encapsulate specific file formats from the rest of the world. An example is IstreamComplex2DFmt.

Example: We can use a partial grid function to mark cells for refinement:

partial_grid_function<Cell,bool> refine(G,false);
....
for(CellIterator c = G.FirstCell(); ! c.IsDone(); ++c)
 if(error(*c) > tolerance())
   refine[*c] = true;

Guntram Berti


The geometric layerIntroductionThe combinatorial grid layerData associations (grid functions)