next up previous
Next: Generic Components Up: Generic Components for Grid Previous: Analysis of grids and


A Micro-kernel for Grid Data Structures

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.



Table 1: Concepts for combinatorial functionality
Elements handles Sequence Iterators Incidence Iterators
Vertex Vertex Handle Vertex Iterator VertexOnVertex Iterator
      EdgeOnVertex Iterator
      CellOnVertex Iterator
       
Edge Edge Handle Edge Iterator CellOnEdge Iterator
      . . .
Facet Facet Handle Facet Iterator VertexOnFacet Iterator
      . . .
Cell Cell Handle Cell Iterator VertexOnCell Iterator
      . . .


Following the terminology of the SGI STL (18), we use the term concept for a set of requirements. A concrete entity (e. g. a class) satisfying a concept's requirements is called model of the concept. The concepts for the combinatorial requirements are listed in table 1. Element concepts, like Vertex, correspond directly to their mathematical counterparts mentioned above. Among others, they give access to incident elements and are used to access data stored in grid functions (see below). Handle concepts provide for a sort of minimal representation of grid elements. They are unique only in conjunction with a fixed grid. Their main use is the economic implementation of grid functions, grid subranges and the like.

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.



Table 2: Concepts for grid function functionality. Refinement relationship is shown by indentation: Total and Partial G. F. are both refinements of Container G. F.
Concept Feature Member
Grid Function (G. F.) element (arg) type typedef element_type (E)
  value type typedef value_type (T)
  grid type typedef grid_type
  read access T const& operator()(E const&)
    (mapping E $ \mapsto$ T)
Mutable G. F. + write access T & operator[](E const&)
    (see below for () vs. [])
Container G. F. + creation grid_function()
    grid_function(grid_type const&)
     
Total G. F. + storage on all elements grid_function(grid_type const&,

T const&)

     
Partial G. F. + storage on some elem. grid_function(grid_type const&,

T const&)

  + default value set_default(T const&)


Grid functions allow access and storage of arbitrary data on grid elements. They correspond to the mathematical notion of functions from the discrete set of grid elements (of a fixed dimension) to value of some type $ T$. Concepts for grid functions are shown in table 2. All grid function concepts are refinements of STL Adaptable Unary Function, with element and value type corresponding to argument and result type, resp.

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 $ O(1)$ 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).


next up previous
Next: Generic Components Up: Generic Components for Grid Previous: Analysis of grids and
Guntram Berti 2000-09-29