 |
Reference documentation for deal.II version 9.0.0
|
|
Reference documentation for deal.II version 9.0.0
|
Modules | |
| Accessor classes of the mesh iterators | |
Namespaces | |
| IteratorFilters | |
| IteratorState | |
deal.II has several classes which are understood conceptually as meshes. Apart from the obvious Triangulation, these are, for example, DoFHandler and hp::DoFHandler. All of those define a set of iterators, allowing the user to traverse the whole mesh, i.e. the set of cells, faces, edges, etc that comprise the mesh, or portions of it. These iterators are all in a sense derived from the TriaIterator class.
Basically, the template signature of TriaIterator is
Conceptually, this type represents something like a pointer to an object represented by the Accessor class. Usually, you will not use the actual class names spelled out directly, but employ one of the typedefs provided by the mesh classes, such as typename Triangulation::cell_iterator. Before going into this, let us first discuss the concept of iterators, before delving into what the accessors do.
As usual in C++, iterators, just as pointers, are incremented to the next element using operator ++, and decremented to the previous element using operator –. One can also jump n elements ahead using the addition operator, it=it+n, and correspondingly to move a number of elements back. In addition, and keeping with the tradition of the standard template library, meshes provide member functions begin() and end() that provide the first element of a collection and a one-past-the-end iterator, respectively. Since there are a number of different iterators available, there is actually a whole family of such functions, such as begin_active(), begin_face(), etc.
In terms of the concepts for iterators defined in the C++ standard, the deal.II mesh iterators are bi-directional iterators: they can be incremented and decremented, but an operation like it=it+n takes a compute time proportional to n, since it is implemented as a sequence of n individual unit increments. Note that this is in contrast to the next more specialized iterator concept, random access iterators, for which access to an arbitrary object requires only constant time, rather than linear.
As mentioned above, iterators in deal.II can be considered as iterating over all the objects that constitute a mesh. (These objects are lines, quads, and hexes, and are represented by the type of Accessor class given as template argument to the iterator.) This suggests to view a triangulation as a collection of cells and other objects that are held together by a certain data structure that links all these objects, in the same was as a linked list is the data structure that connects objects in a linear fashion.
Triangulations in deal.II can indeed be considered in this way. In particular, they use the computational notion of a forest of regular trees to store their data. This can be understood as follows: Consider the cells of the coarse mesh as roots; then, if one of these coarse mesh cells is refined, it will have 2dim children, which in turn can, but do not have to have 2dim children of their own, and so on. This means, that each cell of the coarse mesh can be considered the root of a binary tree (in 1d), a quadtree (in 2d), or an octree (in 3d). The collection of these trees emanating from the cells of the coarse mesh then constitutes the forest that completely describes the triangulation, including all of its active and inactive cells. In particular, the active cells are those terminal nodes in the tree that have no descendants, i.e. cells which are not further refined. Correspondingly, inactive cells correspond to nodes in the tree with descendants, i.e. cells that are further refined.
A triangulation contains forests for lines (each of which may have 2 children), quads (each with possibly four children), and hexes (each with no or 8 children). Depending on the dimension, these objects are also termed cells or faces.
Iterators loop over the elements of such forests. While the usual iterators loop over all nodes of a forest, active iterators iterate over the elements in the same order, but skip all non-active entries and therefore only visit terminal nodes (i.e. active cells, faces, etc). There are many ways to traverse the elements of a forest, for example breadth first or depth first. Depending on the type of data structure used to store the forest, some ways are more efficient than others. At present, the way iterators traverse forests in deal.II is breadth first. I.e., iterators first visit all the elements (cells, faces, etc) of the coarse mesh before moving on to all the elements of the immediate level, i.e. the immediate children of the coarse mesh objects; after this come the grandchildren of the coarse mesh, and so on. However, it must be noted that programs should not rely on this particular order of traversing a tree: this is considered an implementation detail that can change between versions, even if we consider this an unlikely option at the present time.
Iterators have two properties: what they point to (i.e. the type of the Accessor template argument), and the exact definition of the set they iterate over. In general, iterators are always declared as
Here, Kind determines what property an accessor needs to have to be reached by this iterator (or omitted, for that matter). For example,
iterates over all objects of kind Accessor that make up the mesh (for example all cells, whether they are further refined and have children, or not), whereas
skips all objects that have children, i.e. objects that are not active. Active iterators therefore operate on a subset of the objects that normal iterators act on, namely those that possess the property that they are active. Note that this is independent of the kind of object we are operating on: all valid accessor classes have to provide the iterator classes a method to find out whether they are active or not.
(For completeness, let us mention that there is a third kind of iterators: "raw iterators" also traverse objects that are unused in the triangulation, but allocated anyway for efficiency reasons. User code should never use raw iterators, they are only for internal purposes of the library.)
Whether an object is active can be considered a "predicate": a property that is either true or false. Filtered iterators can be used to restrict the scope of existing iterators even more. For instance, you could imagine to iterate over the subset of those active cells having their user flag set or belonging to a certain subdomain (both properties are either true or false for a given object).
This is achieved by using an object of type FilteredIterator <BaseIterator>, where BaseIterator usually is one of the standard iterators discussed above.
The FilteredIterator gets an additional Predicate in its constructor and will skip all objects where this Predicate evaluates to false. A collection of predicates already implemented can be found in the namespace IteratorFilters.
All iterators of the same kind and iterating over the same kind of geometrical objects traverse the mesh in the same order. Take this code example:
Here, all iterators will always point to the same mesh cell, even though DoFHandler and Triangulation are very different classes, and even if the DoFHandlers are handling different finite elements: they all access cells in the same order, the difference is only in the Accessor. As mentioned above, the order in which iterators traverse the forest of objects is actually well-defined, but application programs should not assume any such order, but rather consider this an implementation detail of the library.
Corresponding to above example, the order in which iterators traverse active objects is the same for all iterators in the following snippet, the difference to the previous example being that here we only consider active cells:
Iterators are like pointers: they can be incremented and decremented, but they are really rather dumb. Their magic only lies in the fact that they point to some useful object, in this case the Accessor. For pointers, they point to an actual object that stores some data. On the other hand, the deal.II iterators, when dereferenced, do not return a reference to an actual object, but return an object that knows how to get at the data that represents cells. In general, this object doesn't store itself where the vertices of a cell are or what its neighbors are. However, it knows how to tease this sort of information from out of the arrays and tables and lists that the Triangulation class sets up to describe a mesh.
Accessing data that characterizes a cell is always done through the Accessor, i.e. the expression i->xxx() grants access to all attributes of this Accessor. Examples of properties you can query from an iterator are
Since dereferencing iterators yields accessor objects, these calls are to member functions Accessor::vertex(), Accessor::child() etc. These in turn figure out the relevant data from the various data structures that store this data. How this is actually done and what data structures are used is not really of concern to authors of applications in deal.II. In particular, by hiding the actual data structures we are able to store data in an efficient way, not necessarily in a way that makes it easily accessible or understandable to application writers.
Depending on what sort of data you want to access, there are different kinds of accessor classes:
Except to look up member documentation, you will not usually have to deal with the actual class names listed above. Rather, one uses the typedefs provided by the mesh classes Triangulation, DoFHandler and hp::DoFHandler, as well as the function that generate such objects:
| Class | cell_iterator type | function call |
|---|---|---|
| Triangulation | typename Triangulation::cell_iterator | |
| DoFHandler | typename DoFHandler::cell_iterator | |
| hp::DoFHandler | typename hp::DoFHandler::cell_iterator | hp::DoFHandler::begin() |
The Triangulation class supports iterating across cell faces with typename Triangulation::face_iterator, which is the type returned by Triangulation::begin_face().
Active iterators have the following properties:
| Class | cell_iterator type | function call |
|---|---|---|
| Triangulation | typename Triangulation::active_cell_iterator | |
| DoFHandler | typename DoFHandler::active_cell_iterator | |
| hp::DoFHandler | typename hp::DoFHandler::active_cell_iterator | hp::DoFHandler::begin_active() |
The Triangulation class also supports iterating across active cell faces with typename Triangulation::active_face_iterator, which is the type returned by Triangulation::begin_active_face().
In addition to these types and calls that act on cells and faces (logical concepts that depend on the dimension: a cell is a quadrilateral in 2d, but a hexahedron in 3d), there are corresponding types and calls like begin_active_quad() or end_quad() that act on the dimension independent geometric objects line, quad, and hex. These calls, just as the ones above, exist in active and non-active forms.
The actual definition of all the typedefs local to the mesh classes are stated in the
Iterators, being like pointers, act as if they pointed to an actual object, but in reality all they do is to return an accessor when dereferenced. The accessor object contains the state, i.e. it knows which object it represents, by storing for example which Triangulation it belongs to, and the level and index within this level of a cell. It is therefore able to access the data that corresponds to the cell (or face, or edge) it represents
There is a representation of past-the-end-pointers, denoted by special values of the member variables present_level and present_index in the TriaAccessor class: If present_level > =0 and present_index > =0, then the object is valid; if present_level==-1 and present_index==-1, then the iterator points past the end; in all other cases, the iterator is considered invalid. You can check this by calling the TriaAccessorBase::state() function.
Past-the-end iterators may also be used to compare an iterator with the before-the-start value, when running backwards. There is no distinction between the iterators pointing past the two ends of a vector.
Cells are stored based on a hierarchical structure of levels, therefore the above mentioned structure is useful. Faces however are not organized in levels, and accessors for objects of lower dimensionality do not have a present_level member variable.
| typedef ::Triangulation<dim,spacedim>::cell_iterator parallel::distributed::Triangulation< dim, spacedim >::cell_iterator |
A typedef that is used to identify cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies cells in a triangulation. You can find the exact type it refers to in the base class's own typedef, but it should be TriaIterator<CellAccessor<dim,spacedim> >. The TriaIterator class works like a pointer that when you dereference it yields an object of type CellAccessor. CellAccessor is a class that identifies properties that are specific to cells in a triangulation, but it is derived (and consequently inherits) from TriaAccessor that describes what you can ask of more general objects (lines, faces, as well as cells) in a triangulation.
| typedef ::Triangulation<dim,spacedim>::active_cell_iterator parallel::distributed::Triangulation< dim, spacedim >::active_cell_iterator |
A typedef that is used to identify active cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies active cells in a triangulation. You can find the exact type it refers to in the base class's own typedef, but it should be TriaActiveIterator<CellAccessor<dim,spacedim> >. The TriaActiveIterator class works like a pointer to active objects that when you dereference it yields an object of type CellAccessor. CellAccessor is a class that identifies properties that are specific to cells in a triangulation, but it is derived (and consequently inherits) from TriaAccessor that describes what you can ask of more general objects (lines, faces, as well as cells) in a triangulation.
| typedef ActiveSelector::active_cell_iterator DoFHandler< dim, spacedim >::active_cell_iterator |
A typedef that is used to identify active cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies active cells in a DoFHandler object. While the actual data type of the typedef is hidden behind a few layers of (unfortunately necessary) indirections, it is in essence TriaActiveIterator<DoFCellAccessor>. The TriaActiveIterator class works like a pointer to active objects that when you dereference it yields an object of type DoFCellAccessor. DoFCellAccessor is a class that identifies properties that are specific to cells in a DoFHandler, but it is derived (and consequently inherits) from both DoFAccessor, TriaCellAccessor and TriaAccessor that describe what you can ask of more general objects (lines, faces, as well as cells) in a triangulation and DoFHandler objects.
Definition at line 229 of file dof_handler.h.
| typedef ActiveSelector::cell_iterator DoFHandler< dim, spacedim >::cell_iterator |
A typedef that is used to identify cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies cells in a DoFHandler object. Some of these cells may in fact be active (see active cell iterators) in which case they can in fact be asked for the degrees of freedom that live on them. On the other hand, if the cell is not active, any such query will result in an error. Note that this is what distinguishes this typedef from the level_cell_iterator typedef.
While the actual data type of the typedef is hidden behind a few layers of (unfortunately necessary) indirections, it is in essence TriaIterator<DoFCellAccessor>. The TriaIterator class works like a pointer to objects that when you dereference it yields an object of type DoFCellAccessor. DoFCellAccessor is a class that identifies properties that are specific to cells in a DoFHandler, but it is derived (and consequently inherits) from both DoFAccessor, TriaCellAccessor and TriaAccessor that describe what you can ask of more general objects (lines, faces, as well as cells) in a triangulation and DoFHandler objects.
Definition at line 257 of file dof_handler.h.
| typedef ActiveSelector::face_iterator DoFHandler< dim, spacedim >::face_iterator |
A typedef that is used to identify iterators that point to faces. The concept of iterators is discussed at length in the iterators documentation module.
While the actual data type of the typedef is hidden behind a few layers of (unfortunately necessary) indirections, it is in essence TriaIterator<DoFAccessor>. The TriaIterator class works like a pointer to objects that when you dereference it yields an object of type DoFAccessor. DoFAccessor, in turn, is a class that can be used to query DoF indices on faces, but it is also derived from TriaAccessor and consequently can be used to query geometric properties such as vertices of faces, their area, etc.
Definition at line 275 of file dof_handler.h.
| typedef ActiveSelector::active_face_iterator DoFHandler< dim, spacedim >::active_face_iterator |
A typedef that is used to identify iterators that point to active faces, i.e., to faces that have no children. Active faces must be faces of at least one active cell.
Other than the "active" qualification, this typedef is identical to the face_iterator typedef. In particular, dereferencing either yields the same kind of object.
Definition at line 288 of file dof_handler.h.
| typedef TriaIterator<CellAccessor<dim,spacedim> > Triangulation< dim, spacedim >::cell_iterator |
A typedef that is used to identify cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies cells in a triangulation. The TriaIterator class works like a pointer that when you dereference it yields an object of type CellAccessor. CellAccessor is a class that identifies properties that are specific to cells in a triangulation, but it is derived (and consequently inherits) from TriaAccessor that describes what you can ask of more general objects (lines, faces, as well as cells) in a triangulation.
| typedef TriaActiveIterator<CellAccessor<dim,spacedim> > Triangulation< dim, spacedim >::active_cell_iterator |
A typedef that is used to identify active cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies active cells in a triangulation. The TriaActiveIterator class works like a pointer to active objects that when you dereference it yields an object of type CellAccessor. CellAccessor is a class that identifies properties that are specific to cells in a triangulation, but it is derived (and consequently inherits) from TriaAccessor that describes what you can ask of more general objects (lines, faces, as well as cells) in a triangulation.
| typedef TriaIterator<TriaAccessor<dim-1, dim, spacedim> > Triangulation< dim, spacedim >::face_iterator |
A typedef that is used to identify iterators that point to faces. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies faces in a triangulation. The TriaIterator class works like a pointer to objects that when you dereference it yields an object of type TriaAccessor, i.e., class that can be used to query geometric properties of faces such as their vertices, their area, etc.
| typedef TriaActiveIterator<TriaAccessor<dim-1, dim, spacedim> > Triangulation< dim, spacedim >::active_face_iterator |
A typedef that is used to identify iterators that point to active faces, i.e., to faces that have no children. Active faces must be faces of at least one active cell.
Other than the "active" qualification, this typedef is identical to the face_iterator typedef. In particular, dereferencing either yields the same kind of object.
| typedef TriaIterator<::TriaAccessor<0, dim, spacedim> > Triangulation< dim, spacedim >::vertex_iterator |
A typedef that defines an iterator type to iterate over vertices of a mesh. The concept of iterators is discussed at length in the iterators documentation module.
| typedef TriaActiveIterator<::TriaAccessor<0, dim, spacedim> > Triangulation< dim, spacedim >::active_vertex_iterator |
A typedef that defines an iterator type to iterate over vertices of a mesh. The concept of iterators is discussed at length in the iterators documentation module.
This typedef is in fact identical to the vertex_iterator typedef above since all vertices in a mesh are active (i.e., are a vertex of an active cell).
| typedef ActiveSelector::active_cell_iterator hp::DoFHandler< dim, spacedim >::active_cell_iterator |
A typedef that is used to identify active cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies active cells in a DoFHandler object. While the actual data type of the typedef is hidden behind a few layers of (unfortunately necessary) indirections, it is in essence TriaActiveIterator<DoFCellAccessor>. The TriaActiveIterator class works like a pointer to active objects that when you dereference it yields an object of type DoFCellAccessor. DoFCellAccessor is a class that identifies properties that are specific to cells in a DoFHandler, but it is derived (and consequently inherits) from both DoFAccessor, TriaCellAccessor and TriaAccessor that describe what you can ask of more general objects (lines, faces, as well as cells) in a triangulation and DoFHandler objects.
Definition at line 186 of file dof_handler.h.
| typedef ActiveSelector::cell_iterator hp::DoFHandler< dim, spacedim >::cell_iterator |
A typedef that is used to identify cell iterators. The concept of iterators is discussed at length in the iterators documentation module.
The current typedef identifies cells in a DoFHandler object. Some of these cells may in fact be active (see active cell iterators) in which case they can in fact be asked for the degrees of freedom that live on them. On the other hand, if the cell is not active, any such query will result in an error. Note that this is what distinguishes this typedef from the level_cell_iterator typedef.
While the actual data type of the typedef is hidden behind a few layers of (unfortunately necessary) indirections, it is in essence TriaIterator<DoFCellAccessor>. The TriaIterator class works like a pointer to objects that when you dereference it yields an object of type DoFCellAccessor. DoFCellAccessor is a class that identifies properties that are specific to cells in a DoFHandler, but it is derived (and consequently inherits) from both DoFAccessor, TriaCellAccessor and TriaAccessor that describe what you can ask of more general objects (lines, faces, as well as cells) in a triangulation and DoFHandler objects.
Definition at line 198 of file dof_handler.h.
| typedef ActiveSelector::face_iterator hp::DoFHandler< dim, spacedim >::face_iterator |
A typedef that is used to identify iterators that point to faces. The concept of iterators is discussed at length in the iterators documentation module.
While the actual data type of the typedef is hidden behind a few layers of (unfortunately necessary) indirections, it is in essence TriaIterator<DoFAccessor>. The TriaIterator class works like a pointer to objects that when you dereference it yields an object of type DoFAccessor. DoFAccessor, in turn, is a class that can be used to query DoF indices on faces, but it is also derived from TriaAccessor and consequently can be used to query geometric properties such as vertices of faces, their area, etc.
Definition at line 207 of file dof_handler.h.
| typedef ActiveSelector::active_face_iterator hp::DoFHandler< dim, spacedim >::active_face_iterator |
A typedef that is used to identify iterators that point to active faces, i.e., to faces that have no children. Active faces must be faces of at least one active cell.
Other than the "active" qualification, this typedef is identical to the face_iterator typedef. In particular, dereferencing either yields the same kind of object.
Definition at line 213 of file dof_handler.h.
1.8.14