tree.h
Go to the documentation of this file.
1// LIC// ====================================================================
2// LIC// This file forms part of oomph-lib, the object-oriented,
3// LIC// multi-physics finite-element library, available
4// LIC// at http://www.oomph-lib.org.
5// LIC//
6// LIC// Copyright (C) 2006-2022 Matthias Heil and Andrew Hazel
7// LIC//
8// LIC// This library is free software; you can redistribute it and/or
9// LIC// modify it under the terms of the GNU Lesser General Public
10// LIC// License as published by the Free Software Foundation; either
11// LIC// version 2.1 of the License, or (at your option) any later version.
12// LIC//
13// LIC// This library is distributed in the hope that it will be useful,
14// LIC// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// LIC// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16// LIC// Lesser General Public License for more details.
17// LIC//
18// LIC// You should have received a copy of the GNU Lesser General Public
19// LIC// License along with this library; if not, write to the Free Software
20// LIC// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21// LIC// 02110-1301 USA.
22// LIC//
23// LIC// The authors may be contacted at oomph-lib@maths.man.ac.uk.
24// LIC//
25// LIC//====================================================================
26// Header file for generic tree structures
27#ifndef OOMPH_TREE_HEADER
28#define OOMPH_TREE_HEADER
29
30// Config header generated by autoconfig
31#ifdef HAVE_CONFIG_H
32#include <oomph-lib-config.h>
33#endif
34
35#ifdef OOMPH_HAS_MPI
36#include "mpi.h"
37#endif
38
39// OOMPH-LIB headers
40#include "Vector.h"
41#include "map_matrix.h"
42
43namespace oomph
44{
45 // Forward class definition for class representing the root of a Tree
46 class TreeRoot;
47
48 class RefineableElement;
49
50 class Mesh;
51
52 //========================================================================
53 /// A generalised tree base class that abstracts the common functionality
54 /// between the quad- and octrees used in mesh adaptation in two and
55 /// three dimensions, respectively.
56 ///
57 /// The tree can also be part of a forest. If that is the case, the root
58 /// of the tree will have pointers to the roots of neighbouring trees.
59 ///
60 /// The objects contained in the tree must be RefineableElements.
61 ///
62 /// The tree can be traversed and actions performed
63 /// at all its "nodes" or only at the leaf "nodes" ("nodes" without sons).
64 ///
65 /// Finally, the leaf "nodes" can be split depending on
66 /// a criteria defined by the object.
67 ///
68 /// Note that Trees are only generated by splitting existing
69 /// Trees. Therefore, the constructors are protected. The
70 /// only Tree that "Joe User" can create is
71 /// the (derived) class TreeRoot.
72 //=================================================================
73 class Tree
74 {
75 public:
76 /// Destructor. Note: Deleting a tree also deletes the
77 /// objects associated with its non-leave nodes.
78 virtual ~Tree();
79
80 /// Broken copy constructor
81 Tree(const Tree& dummy) = delete;
82
83 /// Broken assignment operator
84 void operator=(const Tree&) = delete;
85
86 /// Return the pointer to the object (RefineableElement)
87 /// represented by the tree
89 {
90 return Object_pt;
91 }
92
93 /// Flush the object represented by the tree
95 {
96 Object_pt = 0;
97 }
98
99 /// Return pointer to the son for a given index. Note that
100 /// to aid code readability specific enums have been defined for
101 /// specific trees. However, these are simply aliases for ints and
102 /// the general interface can be implemented once, here.
103 Tree* son_pt(const int& son_index) const
104 {
105 // If there are no sons, return NULL (0)
106 if (Son_pt.size() == 0)
107 {
108 return 0;
109 }
110 // Otherwise, return the pointer to the appropriate son
111 else
112 {
113 return Son_pt[son_index];
114 }
115 }
116
117
118 /// Set vector of pointers to sons, indexed by the
119 /// appropriate enum that identies son types.
120 /// (To aid code readability specific enums have been defined for
121 /// specific trees. However, these are simply aliases for ints and
122 /// the general interface can be implemented once, here).
124 {
125 Son_pt = son_pt;
126 }
127
128 /// Return number of sons (zero if it's a leaf node)
129 unsigned nsons() const
130 {
131 return Son_pt.size();
132 }
133
134 /// Flush the sons
136 {
137 Son_pt.clear();
138 }
139
140 /// Return pointer to root of the tree
142 {
143 return Root_pt;
144 }
145
146 /// Return pointer to root of the tree (const version)
148 {
149 return Root_pt;
150 }
151
152 /// If required, split the leaf and create its sons --
153 /// criterion: bool object_pt()-> to_be_refined() = true
154 template<class ELEMENT>
155 void split_if_required();
156
157 /// If required, p-refine the leaf --
158 /// criterion: bool object_pt()-> to_be_p_refined() = true
159 /// or bool object_pt()-> to_be_p_unrefined() = true
160 template<class ELEMENT>
161 void p_refine_if_required(Mesh*& mesh_pt);
162
163 /// If required, merge the four sons for unrefinement --
164 /// criterion: bool object_pt()-> sons_to_be_unrefined() = true
165 void merge_sons_if_required(Mesh*& mesh_pt);
166
167 /// Call the RefineableElement's deactivate_element() function.
168 void deactivate_object();
169
170 /// A function that constructs a specific type of tree. This
171 /// MUST be overloaded for each specific tree type. The use of such a
172 /// function allows the generic implementation of split_if_required().
174 Tree* const& father_pt,
175 const int& son_type) = 0;
176
177 /// Function pointer to argument-free void Tree member function
178 typedef void (Tree::*VoidMemberFctPt)();
179
180 /// Function pointer to a void Tree member function that takes a
181 /// pointer to a mesh as its argument
182 typedef void (Tree::*VoidMeshPtArgumentMemberFctPt)(Mesh*& mesh_pt);
183
184
185 /// Traverse the tree and execute void Tree member function
186 /// member_function() at all its "nodes"
187 void traverse_all(Tree::VoidMemberFctPt member_function);
188
189 /// Traverse the tree and excute void Tree member function
190 /// that takes a pointer to a mesh as an argument
192 Mesh*& mesh_pt);
193
194 /// Traverse the tree and execute void Tree member function
195 /// member_function() at all its "nodes" aparat from the leaves
197
198 /// Traverse the tree and execute void Tree member function
199 /// member_function() only at its leaves
200 void traverse_leaves(Tree::VoidMemberFctPt member_function);
201
202 /// Traverse the tree and execute void Tree member function
203 /// that takes a pointer to a mesh as an argument only at its leaves
205 Mesh*& mesh_pt);
206
207 /// Traverse tree and stick pointers to leaf "nodes" (only) into Vector
209
210 /// Traverse and stick pointers to all "nodes" into Vector
212
213 /// Return son type
214 int son_type() const
215 {
216 return Son_type;
217 }
218
219 /// Return true if the tree is a leaf node
220 bool is_leaf()
221 {
222 // If there are no sons, it's a leaf, return true
223 if (Son_pt.size() == 0)
224 {
225 return true;
226 }
227 // Otherwise return false
228 else
229 {
230 return false;
231 }
232 }
233
234 /// Return pointer to father: NULL if it's a root node
236 {
237 return Father_pt;
238 }
239
240 /// Set the father
242 {
244 }
245
246 /// Return the level of the Tree (root=0)
247 unsigned level() const
248 {
249 return Level;
250 }
251
252 /// Max. allowed discrepancy in neighbour finding routine
253 /// (distance between points when identified from two neighbouring
254 /// elements)
256 {
258 }
259
260 public:
261 /// Default value for an unassigned neighbour
262 static const int OMEGA;
263
264 protected:
265 /// Default constructor (empty and broken)
267 {
268 // Throw an error
269 throw OomphLibError("Don't call an empty constructor for a Tree object",
270 OOMPH_CURRENT_FUNCTION,
271 OOMPH_EXCEPTION_LOCATION);
272 }
273
274 /// Default constructor for empty (root) tree:
275 /// no father, no sons; just pass a pointer to its object
276 /// Protected because Trees can only be created internally,
277 /// during the split operation. Only TreeRoots can be
278 /// created externally.
280
281 /// Constructor for tree that has a father: Pass it the pointer
282 /// to its object, the pointer to its father and tell it what type
283 /// of son it is.
284 /// Protected because Trees can only be created internally,
285 /// during the split operation. Only TreeRoots can be
286 /// created externally.
288 Tree* const& father_pt,
289 const int& son_type);
290
291 /// Pointer to the root of the tree
293
294 protected:
295 /// Pointer to the Father of the Tree
297
298 /// Vector of pointers to the sons of the Tree
300
301 /// Level of the Tree (level 0 = root)
302 int Level;
303
304 /// Son type (e.g. SW/SE/NW/NE in a quadtree)
306
307 /// Pointer to the object represented by the tree
309
310 /// Max. allowed discrepancy in neighbour finding routine
311 /// (distance between points when identified from two neighbouring
312 /// elements)
314 };
315
316
317 //===================================================================
318 /// TreeRoot is a Tree that forms the root of a (recursive)
319 /// tree. The "root node" is special as it holds additional
320 /// information about its neighbours and their relative
321 /// rotation (inside a TreeForest).
322 //==================================================================
323 class TreeRoot : public virtual Tree
324 {
325 protected:
326 /// Map of pointers to the neighbouring TreeRoots:
327 /// Neighbour_pt[direction] returns the pointer to the
328 /// TreeRoot's neighbour in the (enumerated) direction.
329 /// Returns NULL if there's no neighbour in this direction.
330 std::map<int, TreeRoot*> Neighbour_pt;
331
332
333 /// Map of booleans used for periodic boundaries:
334 /// Neighbour_periodic_direction[directon] returns true if the
335 /// neighbour in that direction is actually a periodic neighbour
336 /// --- shared data values, but independent position.
337 /// The default return of the map is false.
338 std::map<int, bool> Neighbour_periodic;
339
340 public:
341 /// Constructor for the (empty) root tree
343 {
344 // TreeRoot is the Root
345 Root_pt = this;
346 }
347
348
349 /// Broken copy constructor
350 TreeRoot(const TreeRoot& dummy) = delete;
351
352 /// Broken assignment operator
353 void operator=(const TreeRoot&) = delete;
354
355 /// Return the pointer to the neighbouring TreeRoots in specified
356 /// direction. Returns NULL if there's no neighbour in this direction.
357 TreeRoot*& neighbour_pt(const int& direction)
358 {
359 return Neighbour_pt[direction];
360 }
361
362 /// Return whether the neighbour in the particular direction
363 /// is periodic.
364 bool is_neighbour_periodic(const int& direction)
365 {
366 return Neighbour_periodic[direction];
367 }
368
369 /// Set the neighbour in particular direction to be periodic
370 void set_neighbour_periodic(const int& direction)
371 {
372 Neighbour_periodic[direction] = true;
373 }
374
375 /// Set the neighbour in particular direction to be nonperiodic
376 void set_neighbour_nonperiodic(const int& direction)
377 {
378 Neighbour_periodic[direction] = false;
379 }
380
381 /// Return the number of neighbours
382 unsigned nneighbour()
383 {
384 // Loop over the neighbours and test whether they are non-null
385 unsigned count = 0;
386 for (std::map<int, TreeRoot*>::iterator it = Neighbour_pt.begin();
387 it != Neighbour_pt.end();
388 it++)
389 {
390 if (Neighbour_pt[it->first] != 0)
391 {
392 count++;
393 }
394 }
395 // Return number counted
396 return count;
397 }
398 };
399
400
401 //================================================================
402 /// A TreeForest consists of a collection of TreeRoots.
403 /// Each member tree can have neighbours in various enumerated
404 /// directions (e.g. S/W/N/E for a QuadTreeForest)
405 /// and the orientation of their compasses can differ, allowing
406 /// for complex, unstructured meshes.
407 //=================================================================
409 {
410 public:
411 /// Constructor for Tree forest: Pass Vector of
412 /// (pointers to) constituents trees.
413 TreeForest(Vector<TreeRoot*>& trees_pt);
414
415 /// Default constructor (empty and broken)
417 {
418 // Throw an error
419 throw OomphLibError(
420 "Don't call an empty constructor for a TreeForest object",
421 OOMPH_CURRENT_FUNCTION,
422 OOMPH_EXCEPTION_LOCATION);
423 }
424
425 /// Broken copy constructor
426 TreeForest(const TreeForest& dummy) = delete;
427
428 /// Broken assignment operator
429 void operator=(const TreeForest&) = delete;
430
431 /// Destructor: Delete the constituent trees (and thus
432 /// the objects associated with its non-leaf nodes!)
433 virtual ~TreeForest();
434
435 /// Traverse forst and stick pointers to leaf "nodes" into Vector
436 void stick_leaves_into_vector(Vector<Tree*>& forest_nodes);
437
438 /// Traverse forest and stick pointers to all "nodes" into Vector
439 void stick_all_tree_nodes_into_vector(Vector<Tree*>& all_forest_nodes);
440
441 /// Document/check the neighbours of all the nodes in the forest.
442 /// This must be overloaded for different types of forest.
443 virtual void check_all_neighbours(DocInfo& doc_info) = 0;
444
445 /// Open output files that will store any hanging nodes in the
446 /// forest. Return a vector of the output streams. This is included in
447 /// the tree structure, so that we can use generic routines for
448 /// mesh adaptation in two and three dimensions. The need for pointers
449 /// to the output streams is because one cannot copy a stream!
451 DocInfo& doc_info, Vector<std::ofstream*>& output_stream) = 0;
452
453 /// Close output files that will store any hanging nodes in the
454 /// forest and delete any associated storage.
455 /// This can be performed genercially in this base class.
456 void close_hanging_node_files(DocInfo& doc_info,
457 Vector<std::ofstream*>& output_stream);
458
459 /// Number of trees in forest
460 unsigned ntree()
461 {
462 return Trees_pt.size();
463 }
464
465 /// Return pointer to i-th tree in forest
466 TreeRoot* tree_pt(const unsigned& i) const
467 {
468 return Trees_pt[i];
469 }
470
471 /// Flush trees from forest
473 {
474 // Clear Trees_pt vector
475 Trees_pt.clear();
476 }
477
478 protected:
479 /// Vector containing the pointers to the trees
481 };
482
483} // namespace oomph
484
485#endif
cstr elem_len * i
Definition: cfortran.h:603
Information for documentation of results: Directory and file number to enable output in the form RESL...
A general mesh class.
Definition: mesh.h:67
An OomphLibError object which should be thrown when an run-time error is encountered....
RefineableElements are FiniteElements that may be subdivided into children to provide a better local ...
A TreeForest consists of a collection of TreeRoots. Each member tree can have neighbours in various e...
Definition: tree.h:409
void operator=(const TreeForest &)=delete
Broken assignment operator.
virtual void check_all_neighbours(DocInfo &doc_info)=0
Document/check the neighbours of all the nodes in the forest. This must be overloaded for different t...
TreeForest(const TreeForest &dummy)=delete
Broken copy constructor.
void flush_trees()
Flush trees from forest.
Definition: tree.h:472
void stick_all_tree_nodes_into_vector(Vector< Tree * > &all_forest_nodes)
Traverse forest and stick pointers to all "nodes" into Vector.
Definition: tree.cc:405
virtual void open_hanging_node_files(DocInfo &doc_info, Vector< std::ofstream * > &output_stream)=0
Open output files that will store any hanging nodes in the forest. Return a vector of the output stre...
unsigned ntree()
Number of trees in forest.
Definition: tree.h:460
void stick_leaves_into_vector(Vector< Tree * > &forest_nodes)
Traverse forst and stick pointers to leaf "nodes" into Vector.
Definition: tree.cc:379
Vector< TreeRoot * > Trees_pt
Vector containing the pointers to the trees.
Definition: tree.h:480
TreeRoot * tree_pt(const unsigned &i) const
Return pointer to i-th tree in forest.
Definition: tree.h:466
virtual ~TreeForest()
Destructor: Delete the constituent trees (and thus the objects associated with its non-leaf nodes!...
Definition: tree.cc:364
TreeForest()
Default constructor (empty and broken)
Definition: tree.h:416
void close_hanging_node_files(DocInfo &doc_info, Vector< std::ofstream * > &output_stream)
Close output files that will store any hanging nodes in the forest and delete any associated storage....
Definition: tree.cc:432
TreeRoot is a Tree that forms the root of a (recursive) tree. The "root node" is special as it holds ...
Definition: tree.h:324
std::map< int, bool > Neighbour_periodic
Map of booleans used for periodic boundaries: Neighbour_periodic_direction[directon] returns true if ...
Definition: tree.h:338
void operator=(const TreeRoot &)=delete
Broken assignment operator.
bool is_neighbour_periodic(const int &direction)
Return whether the neighbour in the particular direction is periodic.
Definition: tree.h:364
TreeRoot(const TreeRoot &dummy)=delete
Broken copy constructor.
unsigned nneighbour()
Return the number of neighbours.
Definition: tree.h:382
std::map< int, TreeRoot * > Neighbour_pt
Map of pointers to the neighbouring TreeRoots: Neighbour_pt[direction] returns the pointer to the Tre...
Definition: tree.h:330
TreeRoot(RefineableElement *const &object_pt)
Constructor for the (empty) root tree.
Definition: tree.h:342
void set_neighbour_nonperiodic(const int &direction)
Set the neighbour in particular direction to be nonperiodic.
Definition: tree.h:376
void set_neighbour_periodic(const int &direction)
Set the neighbour in particular direction to be periodic.
Definition: tree.h:370
TreeRoot *& neighbour_pt(const int &direction)
Return the pointer to the neighbouring TreeRoots in specified direction. Returns NULL if there's no n...
Definition: tree.h:357
A generalised tree base class that abstracts the common functionality between the quad- and octrees u...
Definition: tree.h:74
Tree * Father_pt
Pointer to the Father of the Tree.
Definition: tree.h:296
void traverse_leaves(Tree::VoidMemberFctPt member_function)
Traverse the tree and execute void Tree member function member_function() only at its leaves.
Definition: tree.cc:207
void stick_all_tree_nodes_into_vector(Vector< Tree * > &)
Traverse and stick pointers to all "nodes" into Vector.
Definition: tree.cc:277
unsigned nsons() const
Return number of sons (zero if it's a leaf node)
Definition: tree.h:129
TreeRoot *& root_pt()
Return pointer to root of the tree.
Definition: tree.h:141
void flush_sons()
Flush the sons.
Definition: tree.h:135
void traverse_all(Tree::VoidMemberFctPt member_function)
Traverse the tree and execute void Tree member function member_function() at all its "nodes".
Definition: tree.cc:145
void(Tree::* VoidMeshPtArgumentMemberFctPt)(Mesh *&mesh_pt)
Function pointer to a void Tree member function that takes a pointer to a mesh as its argument.
Definition: tree.h:182
Tree(const Tree &dummy)=delete
Broken copy constructor.
TreeRoot * Root_pt
Pointer to the root of the tree.
Definition: tree.h:292
RefineableElement * Object_pt
Pointer to the object represented by the tree.
Definition: tree.h:308
void p_refine_if_required(Mesh *&mesh_pt)
If required, p-refine the leaf – criterion: bool object_pt()-> to_be_p_refined() = true or bool objec...
void(Tree::* VoidMemberFctPt)()
Function pointer to argument-free void Tree member function.
Definition: tree.h:178
void operator=(const Tree &)=delete
Broken assignment operator.
bool is_leaf()
Return true if the tree is a leaf node.
Definition: tree.h:220
int son_type() const
Return son type.
Definition: tree.h:214
RefineableElement * object_pt() const
Return the pointer to the object (RefineableElement) represented by the tree.
Definition: tree.h:88
int Son_type
Son type (e.g. SW/SE/NW/NE in a quadtree)
Definition: tree.h:305
static double & max_neighbour_finding_tolerance()
Max. allowed discrepancy in neighbour finding routine (distance between points when identified from t...
Definition: tree.h:255
void flush_object()
Flush the object represented by the tree.
Definition: tree.h:94
void split_if_required()
If required, split the leaf and create its sons – criterion: bool object_pt()-> to_be_refined() = tru...
Tree * son_pt(const int &son_index) const
Return pointer to the son for a given index. Note that to aid code readability specific enums have be...
Definition: tree.h:103
int Level
Level of the Tree (level 0 = root)
Definition: tree.h:302
static const int OMEGA
Default value for an unassigned neighbour.
Definition: tree.h:262
Tree * father_pt() const
Return pointer to father: NULL if it's a root node.
Definition: tree.h:235
TreeRoot * root_pt() const
Return pointer to root of the tree (const version)
Definition: tree.h:147
unsigned level() const
Return the level of the Tree (root=0)
Definition: tree.h:247
void set_son_pt(const Vector< Tree * > &son_pt)
Set vector of pointers to sons, indexed by the appropriate enum that identies son types....
Definition: tree.h:123
void set_father_pt(Tree *const &father_pt)
Set the father.
Definition: tree.h:241
Vector< Tree * > Son_pt
Vector of pointers to the sons of the Tree.
Definition: tree.h:299
virtual Tree * construct_son(RefineableElement *const &object_pt, Tree *const &father_pt, const int &son_type)=0
A function that constructs a specific type of tree. This MUST be overloaded for each specific tree ty...
void stick_leaves_into_vector(Vector< Tree * > &)
Traverse tree and stick pointers to leaf "nodes" (only) into Vector.
Definition: tree.cc:255
virtual ~Tree()
Destructor. Note: Deleting a tree also deletes the objects associated with its non-leave nodes.
Definition: tree.cc:122
Tree()
Default constructor (empty and broken)
Definition: tree.h:266
void deactivate_object()
Call the RefineableElement's deactivate_element() function.
Definition: tree.cc:341
void traverse_all_but_leaves(Tree::VoidMemberFctPt member_function)
Traverse the tree and execute void Tree member function member_function() at all its "nodes" aparat f...
Definition: tree.cc:184
static double Max_neighbour_finding_tolerance
Max. allowed discrepancy in neighbour finding routine (distance between points when identified from t...
Definition: tree.h:313
void merge_sons_if_required(Mesh *&mesh_pt)
If required, merge the four sons for unrefinement – criterion: bool object_pt()-> sons_to_be_unrefine...
Definition: tree.cc:302
A slight extension to the standard template vector class so that we can include "graceful" array rang...
Definition: Vector.h:58
//////////////////////////////////////////////////////////////////// ////////////////////////////////...