inputs/dev/clustering.tex

%%%%%%%%%%%%%%%%%%%
% XLiFE++ is an extended library of finite elements written in C++
%     Copyright (C) 2014  Lunéville, Eric; Kielbasiewicz, Nicolas; Lafranche, Yvon; Nguyen, Manh-Ha; Chambeyron, Colin
%
%     This program is free software: you can redistribute it and/or modify
%     it under the terms of the GNU General Public License as published by
%     the Free Software Foundation, either version 3 of the License, or
%     (at your option) any later version.
%     This program is distributed in the hope that it will be useful,
%     but WITHOUT ANY WARRANTY; without even the implied warranty of
%     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%     GNU General Public License for more details.
%     You should have received a copy of the GNU General Public License
%     along with this program.  If not, see <http://www.gnu.org/licenses/>.
%%%%%%%%%%%%%%%%%%%

\section{Cluster tree}

The 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.\\

In 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.
\begin{figure}[H]
	\centering
	\includePict[width=16cm]{clusters.png}
\end{figure}
\xlifepp provides two classes templated by the type T of objects to be clustered :
\begin{itemize}
	\item {\class ClusterNode<T>} managing one node of the tree representation
	\item {\class ClusterTree<T>} managing the tree representation from the root node
\end{itemize}

\subsection {The {\classtitle ClusterNode} class}

The {\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:
\vspace{.1cm}
\begin{lstlisting}
dimen_t dim(const T&) const;               //dimension of T object
real_t coords(const T&, number_t i) const  //i-th coordinates of T object
BoundingBox boundingBox(const T &)         //xy(z) bounding box of T object
\end{lstlisting}
\vspace{.1cm}
For 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. \\

The class manages standard informations:
\vspace{.1cm}
\begin{lstlisting}
vector<T>* objects_;      //pointer to the list of all objects
vector<number_t> numbers_;//object numbers related to objects_ vector
ClusterNode* parent_;     //pointer to its parent (0 for root node)
ClusterNode* child_;      //pointer to its first child (0 = no child)
ClusterNode* next_;       //pointer to its brother, (0 = no brother)
number_t depth_;          //depth of node/leaf in tree (0 for root node)
BoundingBox boundingBox_;        //bounding box from characteristic points
BoundingBox realBoundingBox_;    //bounding box from bounding boxes of objects
\end{lstlisting}
\vspace{.1cm}
The 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 :
\vspace{.1cm}
\begin{lstlisting}
vector<number_t> dofNumbers_;  //list of dof numbers related to the node
vector<Element*> elements_;    //list of element numbers related to the node
\end{lstlisting}
\vspace{.1cm}
The 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:
\vspace{.1cm}
\begin{lstlisting}
ClusterNode(vector<T>*,ClusterNode*,number_t, ClusterNode*=0, ClusterNode*=0);
void clear();
\end{lstlisting}
\vspace{.1cm}
\begin{remark}
The 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.
\end{remark}\\

The class provides some functions to get some properties or data:
\vspace{.1cm}
\begin{lstlisting}
number_t dimSpace() const;   //geometric dimension
number_t size() const;       //number of objects
bool isVoid() const;         //true if void node
vector<ClusterNode*> getLeaves() const; //list of leave pointers
list<number_t> getNumbers(bool) const;  //list of Numbers (recursive)
const BoundingBox& box() const;     //return the real bounding box if allocated
real_t boxDiameter() const;         //diameter ot the (real) bounding box
\end{lstlisting}
\vspace{.1cm}
The main member function that builds the tree structure from a division process is:
\vspace{.1cm}
\begin{lstlisting}
void divideNode(ClusteringMethod cm, number_t mininleaf,
                number_t maxdepth=0, bool store = true);
\end{lstlisting}
\vspace{.1cm}
where
\begin{itemize}
	\item {\class ClusteringMethod} is the enumeration of clustering methods:
\begin{lstlisting}
enum ClusteringMethod { _regularBisection, _boundingBoxBisection,
                        _cardinalityBisection, _uniformKdtree, _nonuniformKdtree };
\end{lstlisting}
	\vspace{.1cm}
	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.
	\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}
	\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.
	\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.
\end{itemize}

\begin{remark}
	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!
\end{remark}\\

When some data ({\tt numbers\_}, bounding boxes, ...) are not available it is possible to build or update it:
\vspace{.1cm}
\begin{lstlisting}
void setBoundingBox();           //set the bounding box
void setRealBoundingBox();       //set the real bounding box
void updateRealBoundingBoxes();  //update recursively real bounding boxes
void updateNumbers();            //update numbers_ vector
\end{lstlisting}
\vspace{.1cm}
When 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>}:
\vspace{.1cm}
\begin{lstlisting}
const vector<number_t>& dofNumbers() const; //access to dofNumbers
const vector<Element*>& elements() const;   //access to elt pointers
vector<number_t> getDofNumbers(bool=false) const; //list of dof numbers
vector<Element*> getElements(bool=false) const;   //list of elt numbers
void updateDofNumbers();                   //update recursively dofNumbers
void updateElements();                     //update recursively elements
number_t nbDofs() const;                   //number of dofs
\end{lstlisting}
\vspace{.1cm}
Finally, there are some stuff to print and save to file node informations:
\vspace{.1cm}
\begin{lstlisting}
void printNode(std::ostream&, bool shift=true) const; //print node
void print(std::ostream&) const;         //print tree from current node (recursive)
void printLeaves(std::ostream&) const;   //print leaves of the tree
void saveToFile(const string_t&, bool) const; //save bounding boxes to file
friend ostream& operator<<(std::ostream&, const ClusterNode<T>&);
\end{lstlisting}
\vspace{.1cm}

\subsection {The {\classtitle ClusterTree} class}

The {\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.\\

The {\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:
\vspace{.1cm}
\begin{lstlisting}
template <typename T = FeDof> class ClusterTree
{public:
vector<T>* objects_;       //pointer to a list of objects
ClusteringMethod method_;  //clustering method
number_t maxInBox_;        //maximum number of objects in a leaf
number_t depth;            //depth of the tree
bool storeNodeData_;       //store data on each node if true
bool clearObjects_;        //if true deallocate vector objects_ when clear
number_t nbNodes;          //number of nodes (info)
number_t nbLeaves;         //number of leaves (info)
bool withOverlap_;         //true if dof numbering of nodes overlap
bool noEmptyBox_;          //do not keep empty boxes in tree
 private:
ClusterNode<T>* root_;     //root node of cluster
...
\end{lstlisting}
\vspace{.1cm}
Note 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.

This 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   :
\vspace{.1cm}
\begin{lstlisting}
ClusterTree(const vector<T>&, ClusteringMethod, number_t depth,
            number_t maxinleaf=0, bool store=true, bool noemptybox = true);
\end{lstlisting}
\vspace{.1cm}
\begin{remark}
The 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.
\end{remark}\\

Almost all the member functions are interface to their equivalent in {\class ClusterNode} class:
\vspace{.1cm}
\begin{lstlisting}
ClusterNode<T>* root();
void setOverlap();
void updateBoundingBoxes();            //update recursively bounding boxes
void updateRealBoundingBoxes();        //update recursively real bounding boxes
void updateNumbers();                  //update recursively Numbers_ vector
void updateDofNumbers();               //update recursively DofNumbers_ vector
void updateElements();                 //update recursively Elements_ vector
void updateInfo();                     //update tree info (depth, ...)
number_t nbDofs() const;
void print(ostream&) const;            //print tree
void printLeaves(ostream&) const;      //print only leaves
void saveToFile(const string_t&,
      bool withRealBox= false) const; //save (real) bounding boxes to file
ostream& operator<<(ostream& out, const ClusterTree<T>&);
\end{lstlisting}
\vspace{.1cm}
\goodbreak
For instance, to generate a cluster of a disk mesh, write :
\vspace{.1cm}
\begin{lstlisting}
Disk disk(_center=Point(0.,0.),_radius=1.,_nnodes=16,_domain_name="Omega");
Mesh mesh(disk,_triangle,1,_gmsh);
Domain omg=mesh.domain("Omega");
Space V(omg,P0,"V",false);
ClusterTree<FeDof> clt(V.feSpace()->dofs,_regularBisection,10);
clt.saveToFile("cluster_disk.txt");
\end{lstlisting}
\vspace{.1cm}
As 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.
\begin{figure}[H]
	\centering
	\includePict[width=5cm]{regular_cluster.png}\hspace{.1cm}
	\includePict[width=5cm]{bounding_cluster.png}\hspace{.1cm}
	\includePict[width=5cm]{cardinal_cluster.png}
	\caption{ clustering of a disk mesh using regular, boundingbox and cardinality bisection methods}
	\label{fig_clusterdisk}
\end{figure}
\begin{figure}[H]
	\centering
	\includePict[width=5cm]{uniform_kdtree.png} \hspace{.2cm}
	\includePict[width=5cm]{nonuniform_kdtree.png}
	\caption{ clustering of a disk mesh using {\tt \_uniformKdtree} and {\tt \_nonuniformKdtree} methods }
	\label{fig_clusterdisk_kdtree}
\end{figure}

\displayInfos{library=hierarchicalMatrix, header=clusterTree.hpp, implementation=clusterTree.cpp, test={test\_clusterNode.cpp}, header dep={space.h, config.h, utils.h}}