As a consequence of the outcome of algorithm requirements analysis, we can identify a set of functional primitives, forming a micro-kernel for grid data structures. This micro-kernel serves two fundamental purposes: First, it separates basic (atomic) functionality from derived (composite) functionality, thus answering the question ``What belongs into a grid data structure?'' And second, in the context of generic programming, it serves as a broker layer between concrete data representations and generic components like algorithms and other data structures.
The identification of a small yet sufficient set of basic primitives is an iterative process, depending on an analysis of both typical algorithm requirements and data structure capabilities, as mentioned in the preceding section.
With respect to the universe of possible operations on grids the micro-kernel is (almost) minimal: No part of it can be expressed appropriately by other parts in the general case. With respect to the basic functionality offered by concrete grid data structures it is maximal: A given representation component in general implements only a part of it. For example, a simple triangulation data structure which only stores the vertex indices for each cell cannot provide iteration over neighbor cells. On the other hand, we are able to provide a generic implementation of neighbor iteration, using the part of the micro-kernel supported by the triangulation component. However, this will not be as efficient as a specialized implementation by extending the triangulation component.
|
All iterator concepts are refinements of the STL Forward Iterator. Sequence iterators allow for global loops over all elements of a grid, incidence iterators provide access to elements incident to a given element.
|
We chose to make read and write operations syntactically different (operators () and [], resp.) in order to give better control over them. For example, a partial grid function normally needs to allocate new storage when write access to a previously untouched element occurs; an effect that is clearly undesired when one just wants to read, possibly getting the default value.1A typical use of partial grid functions is the marking of elements during some algorithm (e. g. depth-first traversal), with marking initialized to false in time. This allows for efficient implementations of local algorithms in sublinear time (with respect to the size of the whole grid).
If a grid function is simply passed to an algorithm, clearly the interfaces of Grid Function (or Mutable Grid Function, if it is an output variable) are sufficient. Many algorithms, however, use temporary grid functions internally. Therefore, it is crucial that (a) there is a uniform way to create (and destroy) grid functions, besides accessing and altering their values, and (b), that the totality of needed grid functions does not influence the definition of the underlying grid data structures. The latter would introduce an undue coupling from algorithms to grid data structures.
Therefore, we chose to provide the following class templates in the micro-kernel, where E is the element type (that is, argument type), and T is the value type:
template<class E, class T> class grid_function; template<class E, class T> class partial_grid_function;
The class template grid_function is a model of Total Grid Function, and partial_grid_function is a model of Partial Grid Function. Whereas the value type T can be dealt with in a fully generic way, the dependency on the E parameter is more interesting, and is discussed below.
The creation of grid functions is straightforward:
MyGrid G; // create a grid ... // associate ints ('colors') to vertices grid_function <MyVertex,int> color (G); // mark edges, default: false partial_grid_function<MyEdge ,bool> marked(G, false); // put 2-vectors on cells, init. with (0,0). grid_function <MyCell ,vec2> state (G,vec2(0,0));Here MyVertex and MyEdge are typedefs to models of Vertex and Edge, corresponding to the type MyGrid.
Grid algorithms can be formulated quite naturally using this micro-kernel. For example, counting for each vertex the number of incident cells translates into the following code:2
// init. ncells[v] to 0 grid_function<Vertex,int> ncells(G,0); // for all cells c of G for(CellIterator c(G); c; ++c) // for all vertices of c for(VertexOnCellIterator vc(*c); vc; ++vc) ncells[*vc]++; for(VertexIterator v(G); v; ++v) cout << "ncell: " << ncells(*v) << '\n';
This code also shows the use of a total grid function. With a good optimizing compiler, the efficiency achieved for this generic piece of code is quite close to that of a low-level version, see below.
Modifying operations on data structures are harder to cope with.
We chose to base mutating algorithms on coarse-grained mutating operations,
namely grid copy, grid enlargement and grid cutting (removal of parts).
These operations have proven useful in conjunction
with generic implementations of distributed grids
and adaptive refinement strategies,
yet more work is needed to fully master mutating operations.
In particular, the question of how to handle dependent data,
such as grid functions, when adding or deleting parts of a grid
is not entirely settled.
A majority of important algorithms, however,
are non-mutating
(ignoring the unproblematic write-access to grid functions).