Glossary of Grid Category Terms |

**adjacent**- 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. **category**- 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.
**component**- 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.
**concept**-
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.
**CW-complex**-
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*R*.) The boundary of each^{k}*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. **dimension-homogeneous**-
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*). **element**-
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**- 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.
**incident**- 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*. **homogeneous dimension**-
A grid is of
*homogeneous dimension*if all its principal elements have the same dimension. **lattice**-
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. **manifold-with-boundary**-
A combinatorial grid of dimension
*d*is a manifold-with-boundary grid, if it has a*geometric realization*which is a manifold with boundary. **model**- 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 };

**poset**-
A (strict) poset
*S*is a**p**artially**o**rdered 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*. **principal element**-
A grid element is
*principal*if it is not incident to another element of higher dimension. **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 { public: 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.

Glossary of Grid Category Terms |