 |
deal.II version GIT relicensing-2289-g1e5549a87a 2024-12-21 21:30:00+00:00
|
|
deal.II version GIT relicensing-2289-g1e5549a87a 2024-12-21 21:30:00+00:00
|
Modules | |
| Accessor classes of the mesh iterators | |
Namespaces | |
| namespace | IteratorFilters |
| namespace | IteratorState |
deal.II has several classes which are understood conceptually as meshes. Apart from the obvious Triangulation, there is, for example, the 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 and DoFHandler, as well as the function that generate such objects:
| Class | cell_iterator type | function call |
|---|---|---|
| Triangulation | typename Triangulation::cell_iterator | Triangulation::begin() |
| DoFHandler | typename DoFHandler::cell_iterator | 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 | Triangulation::begin_active() |
| DoFHandler | typename DoFHandler::active_cell_iterator | 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.
| using parallel::distributed::Triangulation< dim, spacedim >::cell_iterator = typename ::Triangulation<dim, spacedim>::cell_iterator |
An alias that is used to identify cell iterators. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias identifies cells in a triangulation. You can find the exact type it refers to in the base class's own alias, 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.
| using parallel::distributed::Triangulation< dim, spacedim >::active_cell_iterator = typename ::Triangulation<dim, spacedim>::active_cell_iterator |
An alias that is used to identify active cell iterators. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias identifies active cells in a triangulation. You can find the exact type it refers to in the base class's own alias, 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.
| using DoFHandler< dim, spacedim >::cell_accessor = typename ActiveSelector::CellAccessor |
An alias that is used to identify cell iterators in DoFHandler objects. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias works, in essence, like the corresponding Triangulation::cell_accessor alias. However, it also makes available the member functions of DoFCellAccessor, in addition to the ones already available through the CellAccessor class.
Definition at line 336 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::face_accessor = typename ActiveSelector::FaceAccessor |
An alias that is used to identify iterators that point to faces. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias works, in essence, like the corresponding Triangulation::face_accessor alias. However, it also makes available the member functions of DoFAccessor, in addition to the ones already available through the TriaAccessor class.
Definition at line 350 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::line_iterator = typename ActiveSelector::line_iterator |
An alias that defines an iterator over the (one-dimensional) lines of a mesh. In one-dimensional meshes, these are the cells of the mesh, whereas in two-dimensional meshes the lines are the faces of cells.
Definition at line 359 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::active_line_iterator = typename ActiveSelector::active_line_iterator |
An alias that allows iterating over the active lines, i.e., that subset of lines that have no children. In one-dimensional meshes, these are the cells of the mesh, whereas in two-dimensional meshes the lines are the faces of cells.
In two- or three-dimensional meshes, lines without children (i.e., the active lines) are part of at least one active cell. Each such line may additionally be a child of a line of a coarser cell adjacent to a cell that is active. (This coarser neighbor would then also be active.)
Definition at line 374 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::quad_iterator = typename ActiveSelector::quad_iterator |
An alias that defines an iterator over the (two-dimensional) quads of a mesh. In two-dimensional meshes, these are the cells of the mesh, whereas in three-dimensional meshes the quads are the faces of cells.
Definition at line 383 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::active_quad_iterator = typename ActiveSelector::active_quad_iterator |
An alias that allows iterating over the active quads, i.e., that subset of quads that have no children. In two-dimensional meshes, these are the cells of the mesh, whereas in three-dimensional meshes the quads are the faces of cells.
In three-dimensional meshes, quads without children (i.e., the active quads) are faces of at least one active cell. Each such quad may additionally be a child of a quad face of a coarser cell adjacent to a cell that is active. (This coarser neighbor would then also be active.)
Definition at line 398 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::hex_iterator = typename ActiveSelector::hex_iterator |
An alias that defines an iterator over the (three-dimensional) hexes of a mesh. This iterator only makes sense in three-dimensional meshes, where hexes are the cells of the mesh.
Definition at line 407 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::active_hex_iterator = typename ActiveSelector::active_hex_iterator |
An alias that allows iterating over the active hexes of a mesh. This iterator only makes sense in three-dimensional meshes, where hexes are the cells of the mesh. Consequently, in these three-dimensional meshes, this iterator is equivalent to the active_cell_iterator alias.
Definition at line 418 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::active_cell_iterator = typename ActiveSelector::active_cell_iterator |
An alias that is used to identify active cell iterators. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias identifies active cells in a DoFHandler object. While the actual data type of the alias 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 440 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::cell_iterator = typename ActiveSelector::cell_iterator |
An alias that is used to identify cell iterators. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias 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 alias from the level_cell_iterator alias.
While the actual data type of the alias 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 468 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::face_iterator = typename ActiveSelector::face_iterator |
An alias that is used to identify iterators that point to faces. The concept of iterators is discussed at length in the iterators documentation topic.
While the actual data type of the alias 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 486 of file dof_handler.h.
| using DoFHandler< dim, spacedim >::active_face_iterator = typename ActiveSelector::active_face_iterator |
An alias 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 alias is identical to the face_iterator alias. In particular, dereferencing either yields the same kind of object.
Definition at line 499 of file dof_handler.h.
| using Triangulation< dim, spacedim >::cell_iterator = TriaIterator<CellAccessor<dim, spacedim> > |
An alias that is used to identify cell iterators. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias 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.
| using Triangulation< dim, spacedim >::active_cell_iterator = TriaActiveIterator<CellAccessor<dim, spacedim> > |
An alias that is used to identify active cell iterators. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias 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.
| using Triangulation< dim, spacedim >::face_iterator = TriaIterator<TriaAccessor<dim - 1, dim, spacedim> > |
An alias that is used to identify iterators that point to faces. The concept of iterators is discussed at length in the iterators documentation topic.
The current alias 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.
| using Triangulation< dim, spacedim >::active_face_iterator = TriaActiveIterator<TriaAccessor<dim - 1, dim, spacedim> > |
An alias 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 alias is identical to the face_iterator alias. In particular, dereferencing either yields the same kind of object.
| using Triangulation< dim, spacedim >::vertex_iterator = TriaIterator<::TriaAccessor<0, dim, spacedim> > |
An alias that defines an iterator type to iterate over vertices of a mesh. The concept of iterators is discussed at length in the iterators documentation topic.
| using Triangulation< dim, spacedim >::active_vertex_iterator = TriaActiveIterator<::TriaAccessor<0, dim, spacedim> > |
An alias that defines an iterator type to iterate over vertices of a mesh. The concept of iterators is discussed at length in the iterators documentation topic.
This alias is in fact identical to the vertex_iterator alias above since all vertices in a mesh are active (i.e., are a vertex of an active cell).
| using Triangulation< dim, spacedim >::line_iterator = typename IteratorSelector::line_iterator |
| using Triangulation< dim, spacedim >::active_line_iterator = typename IteratorSelector::active_line_iterator |
An alias that allows iterating over the active lines, i.e., that subset of lines that have no children. In one-dimensional meshes, these are the cells of the mesh, whereas in two-dimensional meshes the lines are the faces of cells.
In two- or three-dimensional meshes, lines without children (i.e., the active lines) are part of at least one active cell. Each such line may additionally be a child of a line of a coarser cell adjacent to a cell that is active. (This coarser neighbor would then also be active.)
| using Triangulation< dim, spacedim >::quad_iterator = typename IteratorSelector::quad_iterator |
| using Triangulation< dim, spacedim >::active_quad_iterator = typename IteratorSelector::active_quad_iterator |
An alias that allows iterating over the active quads, i.e., that subset of quads that have no children. In two-dimensional meshes, these are the cells of the mesh, whereas in three-dimensional meshes the quads are the faces of cells.
In three-dimensional meshes, quads without children (i.e., the active quads) are faces of at least one active cell. Each such quad may additionally be a child of a quad face of a coarser cell adjacent to a cell that is active. (This coarser neighbor would then also be active.)
| using Triangulation< dim, spacedim >::hex_iterator = typename IteratorSelector::hex_iterator |
| using Triangulation< dim, spacedim >::active_hex_iterator = typename IteratorSelector::active_hex_iterator |
An alias that allows iterating over the active hexes of a mesh. This iterator only makes sense in three-dimensional meshes, where hexes are the cells of the mesh. Consequently, in these three-dimensional meshes, this iterator is equivalent to the active_cell_iterator alias.
1.9.8