Prev Up
Go backward to Components
Go up to Top

Glossary of Grid Category Terms

Two cells are adjacent if they are incident to a common facet. Two vertices are adjacent if they are incident to a common edge. For other types of elements, we do not define adjacency.


associative copy
An associative copy between two grids is a copy operation which preserves (outputs) a mapping between the elements of the first and those of the second grid, such that this mapping is (part of) a grid morphism.


boundary facet
See interior facet.


bound to a grid
We say that a grid entity e of type E is bound to a grid g if g is an object of type E::grid_type and &g == &(e.TheGrid()). Here E might be a model of Grid Element, Grid Function or the like.


is used to denote a group of related components which implement concepts from the same problem domain, such as grid-related components (grid category), which has sub-categories combinatorial grids, grid functions (or data association), and grid geometries.


A component is any piece of code which can be used elsewhere, for example a class template, a single class, a set of related classes, or a function implementing an algorithm.


Following to the STL parlance a concept is a set of type requirements. Generic algorithms require their arguments to be models of certain concepts. The STL documentation explains further:
Concepts are not a part of the C++ language; there is no way to declare a concept in a program, or to declare that a particular type is a model of a concept.


A finite CW-complex C of dimension d is a set of topological open k-cells with 0 <= k <= d. (An open k-cell is a set homeomorphic to the open k-ball in Rk.) The boundary of each k-cell in C must be formed by the union of cells of lower dimension which are also contained in C.

This is a very general definition, which must often be refined for practical purposes. However, the case of cells with holes (sometimes used in geometric modeling) is not covered by the definition.


A grid element is called principal if it is not incident to a higher dimensional element. A grid is dimension-homogeneous, if each principal element is of the highest dimension (namely, the dimension of the grid, d).

This property excludes for example isolated vertices, or `free' edges (if the dimension is at least 2).


We use the term element to denote any k-cell of a grid: A vertex is a 0-element, an edge a 1-element, and a cell a d-element (if the grid is d-dimensional). See also Element subsection


generic programming
Generic programming has been called "programming with concepts". It aims at implementing algorithms as general as possible, without sacrificing efficiency by doing overgeneralization or introducing undue amounts of runtime overhead. More information can be found here.


geometric realization
A geometric realization of a combinatorial (or abstract) complex (which is given by a graded poset or a lattice) is a CW-complex which has the same (or isomorphic) incidence poset.


Grid is used as synonym for a finite dimension-homogeneous CW-complex.


grid morphism
A grid morphism is a mapping between the posets of two grids which respects the partial order. It is an isomorphism if it is bijective.


Two elements are incident if one is contained in the boundary of the other. Thus, elements of the same dimension cannot be incident, only adjacent.


interior facet
A facet f is called interior with respect to a cell set C (which is assumed to be a sub-range of a manifold-with-boundary grid), if there two different cells in C which are incident to f. If there is exactly one cell in C incident to f, then f is a boundary facet of C. If there is no such cell, f is not a facet of C.


A lattice is a graded, bounded poset with the additional property that given two element a and b, there is a unique minimal upper bound a \/ b (the join) greater then a and b, and a unique maximal lower bound a /\ b (the meet). For example, two edges both incident to the same 2D cell have as join that cell, and as meet either a common vertex (which must be unique) or the empty set.


A combinatorial grid of dimension d is a manifold-with-boundary grid, if it has a geometric realization which is a manifold with boundary.


A concrete type is a model of a concept, if it fullfils the requirements of the concept.


partial specialization
refers to binding a part of the parameters of some generic component (class template) to some more specialized type. For example, consider the fully generic template frame for total grid functions:
  template<class E, class T>
  class grid_function<E,T> {};
In generic algorithms, this serves as a placeholder for the actual implementations of grid_function for concrete element types E. For example, total grid functions for the Complex2D grid type are implemented by using vectors for the element types Complex2D::Vertex and Complex2D::Cell, and by using hash tables for the element type Complex2D::Edge:
  template<class T>
  grid_function<Complex2D::Vertex, T> 
    : public grid_function_vector<Complex2D::Vertex, T> {
    // repeat constructors

  template<class T>
  grid_function<Complex2D::Cell, T> 
    : public grid_function_vector<Complex2D::Cell, T> {
    // repeat constructors

  template<class T>
  grid_function<Complex2D::Edge, T> 
    : public grid_function_hash<Complex2D::Edge, T> {
    // repeat constructors


A (strict) poset S is a partially ordered finite set, that is, a set with a partial order < which is antisymmetric and transitive. The poset of a grid consists of the grid's elements, partially ordered by inclusion.

A poset is bounded if there are unique minimal and maximal elements ^0 and ^1. A chain is a totally ordered subset of a poset. A bounded poset is called graded if every maximal chain has the same length (its number of elements minus 1). For a <= b, the interval [a,b] is the set of all elements in between:

[a,b] = { c in S | a <= c <= b }
If S is graded, the rank of a in S is the length of a maximal chain in [^0,a].

The poset of a grid G can be made into a bounded one by adjoining the improper elements ^0 = Ø and ^1 = |G|, with dimensions -1 and d+1.


publishing a type
means a standard way of associating types with classes. One way to do it is to use nested typedefs within the class, like in the following example from the STL:
   template<class T>
   class vector {
     typedef T  value_type;
     typedef T* iterator;
Here the class template vector publishes value_type and iterator, which can be used in another component:
    template<class Container>
    void f(Container const& C, Container::value_type const& t) 
      Container::iterator i = C.begin();
      // ...
Another way to look at it is to say that vector<T> defines a mapping from type vector<T> to a set of associated type like vector<T>::iterator.

A different and somewhat more flexible way of achieving this is using so called traits classes, which makes use of several different such mappings for a given type possible. For this purpose, responsibility for the type definitions is delegated to a separate class, the traits class.

   template<class C>
   struct container_traits {}; // default: empty

   // specialize for vectors
   template<class T>
   struct container_traits< vector<T> > {
     typedef T  value_type;
     typedef T* iterator;
     // ...
If the algorithm f above continues to be parameterized by C alone, not much changes, only the occurences of C::iterator has to replaced by container_traits<C>::iterator. On the other hand, one might imagine a counted iterator, which counts the number of increments. It would not be easy to introduce this without traits. However, we can use an additional traits parameter to the algorithm f:
    template<class Container, class Traits>
    void f(Container const& C, Container::value_type const& t, Traits const&) 
      Traits::iterator i = C.begin();
      // ...
Now it is possible to introduce counted iterators, without any change to the algorithm implementation:
  template<class C>
  struct counted_traits 
    typedef C::value_type value_type; // use same value type
    typedef counted_iterator<C::iterator> iterator;
    // ... 

  // use f, count increments
  MyContainer myc;
  typedef counted_traits<MyContainer> my_traits;
  f(my_c, t, my_traits());
In the grid component framework, the template grid_types<> plays exactly the rôle of container_traits<> above.

A similar effect could be achieved by deriving from the container class, or defining a wrapper class with a delegation mechanism, which would contain the changed typedefs. However, this would not work for built-in types, and also not for aggregations (containers of containers), because there is no way of changing the type of contained items.

Guntram Berti

Prev Up