1%%%%%%%%%%%%%%%%%%% 2% XLiFE++ is an extended library of finite elements written in C++ 3% Copyright (C) 2014 Lunéville, Eric; Kielbasiewicz, Nicolas; Lafranche, Yvon; Nguyen, Manh-Ha; Chambeyron, Colin 4% 5% This program is free software: you can redistribute it and/or modify 6% it under the terms of the GNU General Public License as published by 7% the Free Software Foundation, either version 3 of the License, or 8% (at your option) any later version. 9% This program is distributed in the hope that it will be useful, 10% but WITHOUT ANY WARRANTY; without even the implied warranty of 11% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12% GNU General Public License for more details. 13% You should have received a copy of the GNU General Public License 14% along with this program. If not, see <http://www.gnu.org/licenses/>. 15%%%%%%%%%%%%%%%%%%% 16 17\section{Cluster tree} 18 19The clustering of a set of objects consists in a partition of this set with a hierarchical structure. Each node of the cluster being a subset of the parent node subset. The partitioning of a subset is done according to some rules depending of the purpose of the cluster.\\ 20 21In the case of a mesh, we are interested in clusters of points (mesh nodes) or in clusters of elements where the partitioning rule aims to separate geometrically the points or the elements. 22\begin{figure}[H] 23 \centering 24 \includePict[width=16cm]{clusters.png} 25\end{figure} 26\xlifepp provides two classes templated by the type T of objects to be clustered : 27\begin{itemize} 28 \item {\class ClusterNode<T>} managing one node of the tree representation 29 \item {\class ClusterTree<T>} managing the tree representation from the root node 30\end{itemize} 31 32\subsection {The {\classtitle ClusterNode} class} 33 34The {\class ClusterNode<T>} class describes one node of the tree representing the cluster where {\tt T} is the type of objects to be clustered. It is assumed that {\tt T} is a geometric object and that the three following functions are available: 35\vspace{.1cm} 36\begin{lstlisting} 37dimen_t dim(const T&) const; //dimension of T object 38real_t coords(const T&, number_t i) const //i-th coordinates of T object 39BoundingBox boundingBox(const T &) //xy(z) bounding box of T object 40\end{lstlisting} 41\vspace{.1cm} 42For instance, these functions are provided for the \xlifepp classes : {\class Point}, {\class FeDof}, {\class Element} allowing to cluster mesh using either some points of mesh (vertices), some finite element dofs or some finite elements. \\ 43 44The class manages standard informations: 45\vspace{.1cm} 46\begin{lstlisting} 47vector<T>* objects_; //pointer to the list of all objects 48vector<number_t> numbers_;//object numbers related to objects_ vector 49ClusterNode* parent_; //pointer to its parent (0 for root node) 50ClusterNode* child_; //pointer to its first child (0 = no child) 51ClusterNode* next_; //pointer to its brother, (0 = no brother) 52number_t depth_; //depth of node/leaf in tree (0 for root node) 53BoundingBox boundingBox_; //bounding box from characteristic points 54BoundingBox realBoundingBox_; //bounding box from bounding boxes of objects 55\end{lstlisting} 56\vspace{.1cm} 57The list of objects belonging to the cluster node is given by the {\tt numbers\_} vector that stores the indices of objects in the vector {\tt objects\_}. The clusters we deal with are supposed to be geometrical clusters and the clustering methods are mainly based on splitting of boxes, it is the reason why the class deals explicitly with bounding boxes. In the context of finite element, some additional data (mutable) can be handled : 58\vspace{.1cm} 59\begin{lstlisting} 60vector<number_t> dofNumbers_; //list of dof numbers related to the node 61vector<Element*> elements_; //list of element numbers related to the node 62\end{lstlisting} 63\vspace{.1cm} 64The class provides only one constructor assigning fundamental data ({\tt objects\_, parent\_, child\_, next\_, depth\_}) and a {\tt clear} method that deletes recursively the subtree from the current node: 65\vspace{.1cm} 66\begin{lstlisting} 67ClusterNode(vector<T>*,ClusterNode*,number_t, ClusterNode*=0, ClusterNode*=0); 68void clear(); 69\end{lstlisting} 70\vspace{.1cm} 71\begin{remark} 72The copy constructor and assignment operator are the default ones, so the tree structure is not duplicated but only shared. Be cautious, when you use copy or assignment. 73\end{remark}\\ 74 75The class provides some functions to get some properties or data: 76\vspace{.1cm} 77\begin{lstlisting} 78number_t dimSpace() const; //geometric dimension 79number_t size() const; //number of objects 80bool isVoid() const; //true if void node 81vector<ClusterNode*> getLeaves() const; //list of leave pointers 82list<number_t> getNumbers(bool) const; //list of Numbers (recursive) 83const BoundingBox& box() const; //return the real bounding box if allocated 84real_t boxDiameter() const; //diameter ot the (real) bounding box 85\end{lstlisting} 86\vspace{.1cm} 87The main member function that builds the tree structure from a division process is: 88\vspace{.1cm} 89\begin{lstlisting} 90void divideNode(ClusteringMethod cm, number_t mininleaf, 91 number_t maxdepth=0, bool store = true); 92\end{lstlisting} 93\vspace{.1cm} 94where 95\begin{itemize} 96 \item {\class ClusteringMethod} is the enumeration of clustering methods: 97\begin{lstlisting} 98enum ClusteringMethod { _regularBisection, _boundingBoxBisection, 99 _cardinalityBisection, _uniformKdtree, _nonuniformKdtree }; 100\end{lstlisting} 101 \vspace{.1cm} 102 Except the {\tt \_uniformKdtree} and {\tt \_nonuniformKdtree} methods, each others are bisection method in the direction where the boxes is larger, so the tree is a binary one. {\tt \_regularBisection} split boxes in two boxes of the same size, {\tt \_boundingBoxBisection} split bounding boxes of objects in two boxes of the same size, {\tt \_cardinalityBisection} split boxes in two boxes such that each new boxes have the same number of objects. The trees produced by this last method are better balanced. The {\tt \_uniformKdtree} and {\tt \_nonuniformKdtree} methods split any boxes in 2, 4 or 8 sub-boxes regarding the space dimension (1, 2 or 3); the sub-boxes are of the same size in any direction. Thus it produces binary tree in 1D, quadtree in 2D and octree in 3D. With {\tt \_uniformKdtree} method, all the boxes at the same level have the same size whereas with {\tt \_nonuniformKdtree} method, all the boxes are the minimal bounding boxes defined from the objects that they embed. 103 \item {\tt maxinleaf} is the maximum of objects in a leaf node, more precisely, a node is divided when its number of objects is greater than {\tt maxinleaf} 104 \item {\tt maxdepth}, if not null, allows to stop the division process when {\tt maxdepth} is reached. This stopping criteria has priority over the previous criteria. 105 \item if {\tt store} parameter is true, data ({\tt numbers\_}, bounding boxes, ...) are stored for each node else they are only stored for each leaves. By default its value is true, but if cluster is too large, not storing some data may save memory but some algorithms working on clusters could be slower. 106\end{itemize} 107 108\begin{remark} 109 Up to now, only three clustering methods are offered, but it is quite easy to add a new one by handling a new case in {\tt divideNode} function. Bisection methods build binary tree but there is not limitation of the number of children in the {\class ClusterNode} class! 110\end{remark}\\ 111 112When some data ({\tt numbers\_}, bounding boxes, ...) are not available it is possible to build or update it: 113\vspace{.1cm} 114\begin{lstlisting} 115void setBoundingBox(); //set the bounding box 116void setRealBoundingBox(); //set the real bounding box 117void updateRealBoundingBoxes(); //update recursively real bounding boxes 118void updateNumbers(); //update numbers_ vector 119\end{lstlisting} 120\vspace{.1cm} 121When dealing with finite elements some additional data may be useful, in particular the link between dofs and elements. To avoid costly re-computation, it may be clever to store it. The following member functions do the job on demand when working with a {\tt ClusterNode<FeDof>} or a {\tt ClusterNode<Element>}: 122\vspace{.1cm} 123\begin{lstlisting} 124const vector<number_t>& dofNumbers() const; //access to dofNumbers 125const vector<Element*>& elements() const; //access to elt pointers 126vector<number_t> getDofNumbers(bool=false) const; //list of dof numbers 127vector<Element*> getElements(bool=false) const; //list of elt numbers 128void updateDofNumbers(); //update recursively dofNumbers 129void updateElements(); //update recursively elements 130number_t nbDofs() const; //number of dofs 131\end{lstlisting} 132\vspace{.1cm} 133Finally, there are some stuff to print and save to file node informations: 134\vspace{.1cm} 135\begin{lstlisting} 136void printNode(std::ostream&, bool shift=true) const; //print node 137void print(std::ostream&) const; //print tree from current node (recursive) 138void printLeaves(std::ostream&) const; //print leaves of the tree 139void saveToFile(const string_t&, bool) const; //save bounding boxes to file 140friend ostream& operator<<(std::ostream&, const ClusterNode<T>&); 141\end{lstlisting} 142\vspace{.1cm} 143 144\subsection {The {\classtitle ClusterTree} class} 145 146The {\class ClusterTree<T>} class is the front end of {\class ClusterNode<T>} class which supports the tree structure of the cluster. Because the {\class ClusterTree<T>} class interfaces most data and functionnalities of the {\class ClusterNode<T>} class, for explanation go to the previous section.\\ 147 148The {\class ClusterTree<T>} class manages the parameters and informations required or provided by the the {\class ClusterTree<T>} class. It handles the tree structure (the cluster) through the root node pointer: 149\vspace{.1cm} 150\begin{lstlisting} 151template <typename T = FeDof> class ClusterTree 152{public: 153vector<T>* objects_; //pointer to a list of objects 154ClusteringMethod method_; //clustering method 155number_t maxInBox_; //maximum number of objects in a leaf 156number_t depth; //depth of the tree 157bool storeNodeData_; //store data on each node if true 158bool clearObjects_; //if true deallocate vector objects_ when clear 159number_t nbNodes; //number of nodes (info) 160number_t nbLeaves; //number of leaves (info) 161bool withOverlap_; //true if dof numbering of nodes overlap 162bool noEmptyBox_; //do not keep empty boxes in tree 163 private: 164ClusterNode<T>* root_; //root node of cluster 165... 166\end{lstlisting} 167\vspace{.1cm} 168Note that the {\class ClusterTree} has {\class FeDof} object as template default argument. This is the standard cluster used by the {\class HMatrix} class presented in a next section. 169 170This class provides a unique constructor, building the cluster from a list of geometric object, a clustering method, the maximal depth of the tree, the maximal number of objects in leaf node and a flag telling if empty leaf nod are removed from the tree : 171\vspace{.1cm} 172\begin{lstlisting} 173ClusterTree(const vector<T>&, ClusteringMethod, number_t depth, 174 number_t maxinleaf=0, bool store=true, bool noemptybox = true); 175\end{lstlisting} 176\vspace{.1cm} 177\begin{remark} 178The copy constructor and assignment operator are the default ones, so the tree structure is not duplicated but only shared. Be cautious, when you use copy or assignment. In particular avoid destruction of {\class ClusterTree} object, except if you set the member data {\tt clearObjects\_} to {\tt false} before destroy it. 179\end{remark}\\ 180 181Almost all the member functions are interface to their equivalent in {\class ClusterNode} class: 182\vspace{.1cm} 183\begin{lstlisting} 184ClusterNode<T>* root(); 185void setOverlap(); 186void updateBoundingBoxes(); //update recursively bounding boxes 187void updateRealBoundingBoxes(); //update recursively real bounding boxes 188void updateNumbers(); //update recursively Numbers_ vector 189void updateDofNumbers(); //update recursively DofNumbers_ vector 190void updateElements(); //update recursively Elements_ vector 191void updateInfo(); //update tree info (depth, ...) 192number_t nbDofs() const; 193void print(ostream&) const; //print tree 194void printLeaves(ostream&) const; //print only leaves 195void saveToFile(const string_t&, 196 bool withRealBox= false) const; //save (real) bounding boxes to file 197ostream& operator<<(ostream& out, const ClusterTree<T>&); 198\end{lstlisting} 199\vspace{.1cm} 200\goodbreak 201For instance, to generate a cluster of a disk mesh, write : 202\vspace{.1cm} 203\begin{lstlisting} 204Disk disk(_center=Point(0.,0.),_radius=1.,_nnodes=16,_domain_name="Omega"); 205Mesh mesh(disk,_triangle,1,_gmsh); 206Domain omg=mesh.domain("Omega"); 207Space V(omg,P0,"V",false); 208ClusterTree<FeDof> clt(V.feSpace()->dofs,_regularBisection,10); 209clt.saveToFile("cluster_disk.txt"); 210\end{lstlisting} 211\vspace{.1cm} 212As the dofs of P0 approximation are virtually located at the centroids of triangles, clustering of FeDof is equivalent to the clustering of centroids. We show on the figure \ref{fig_clusterdisk} the clustering of a disk mesh (1673 nodes) with maximum of 10 nodes by box, using regular method, boundingbox, cardinality bisection methods. Only boxes of leaves are displayed; different colors correspond to different node depths. 213\begin{figure}[H] 214 \centering 215 \includePict[width=5cm]{regular_cluster.png}\hspace{.1cm} 216 \includePict[width=5cm]{bounding_cluster.png}\hspace{.1cm} 217 \includePict[width=5cm]{cardinal_cluster.png} 218 \caption{ clustering of a disk mesh using regular, boundingbox and cardinality bisection methods} 219 \label{fig_clusterdisk} 220\end{figure} 221\begin{figure}[H] 222 \centering 223 \includePict[width=5cm]{uniform_kdtree.png} \hspace{.2cm} 224 \includePict[width=5cm]{nonuniform_kdtree.png} 225 \caption{ clustering of a disk mesh using {\tt \_uniformKdtree} and {\tt \_nonuniformKdtree} methods } 226 \label{fig_clusterdisk_kdtree} 227\end{figure} 228 229\displayInfos{library=hierarchicalMatrix, header=clusterTree.hpp, implementation=clusterTree.cpp, test={test\_clusterNode.cpp}, header dep={space.h, config.h, utils.h}} 230