Representation of a cluster tree. More...

Data Structures
struct	_cluster
	Representation of cluster trees. More...

Typedefs
typedef struct _cluster	cluster
	Representation of a cluster tree.

typedef cluster *	pcluster
	Pointer to cluster object.

typedef const cluster *	pccluster
	Pointer to constant cluster object.

Enumerations
enum	clustermode { H2_ADAPTIVE, H2_REGULAR, H2_SIMSUB, H2_PCA }
	Set the clustering strategy. More...

Functions
pcluster	new_cluster (uint size, uint *idx, uint sons, uint dim)
	Create a new cluster object. More...

void	del_cluster (pcluster t)
	Delete a cluster object. More...

void	update_cluster (pcluster t)
	Complete the initialisation of a cluster object. More...

pcluster	build_adaptive_cluster (pclustergeometry cf, uint size, uint *idx, uint clf)
	Build a cluster tree from a clustergeometry object using adaptive clustering. More...

pcluster	build_regular_cluster (pclustergeometry cf, uint size, uint *idx, uint clf, uint direction)
	Build a cluster tree from a clustergeometry object using regular clustering. More...

pcluster	build_simsub_cluster (pclustergeometry cf, uint size, uint *idx, uint clf)
	Build a cluster tree from a clustergeometry object using simultaneous subdivision clustering. More...

pcluster	build_pca_cluster (pclustergeometry cf, uint size, uint *idx, uint clf)
	Build a cluster tree from a clustergeometry object based on the principal component analysis. More...

pcluster	build_cluster (pclustergeometry cf, uint size, uint *idx, uint clf, clustermode mode)
	Build a cluster tree from a clustergeometry object using cluster strategy clustermode. More...

uint	getdepth_cluster (pccluster t)
	Compute the depth of a cluster object. More...

uint	getmindepth_cluster (pccluster t)
	Compute the minimal level of a cluster object. More...

void	extend_cluster (pcluster t, uint depth)
	Extends a given cluster until getmindepth_cluster(t) == depth. More...

void	cut_cluster (pcluster t, uint depth)
	Cut a cluster object until a new depth is reached. More...

void	balance_cluster (pcluster t, uint depth)
	Balance a cluster tree to a given depth. More...

void	coarsen_cluster (pcluster t, uint minsize)
	Coarsen a cluster tree to a minimal size. More...

void	setsons_cluster (pcluster t, uint sons)
	Set the number of sons of a cluster tree. More...

real	getdiam_2_cluster (pccluster t)
	Compute the euclidian diameter of the bounding box of a cluster. More...

real	getdist_2_cluster (pccluster t, pccluster s)
	Compute the euclidian distance of two clusters. More...

real	getdiam_max_cluster (pccluster t)
	Compute the diameter of the bounding of a cluster in the maximum norm. More...

real	getdist_max_cluster (pccluster t, pccluster s)
	Compute the distance of two clusters in the maximum norm. More...

void	iterate_cluster (pccluster t, uint tname, void(pre)(pccluster t, uint tname, void data), void(post)(pccluster t, uint tname, void data), void *data)
	Hierarchical iterator for a cluster tree. More...

void	iterate_parallel_cluster (pccluster t, uint tname, uint pardepth, void(pre)(pccluster t, uint tname, void data), void(post)(pccluster t, uint tname, void data), void *data)
	Parallel hierarchical iterator for a cluster tree. More...

pcluster *	enumerate_cluster (pcluster t)
	Enumerate all clusters in a cluster tree. More...

void	write_cdf_cluster (pccluster t, const char *name)
	Write cluster to NetCDF file. More...

void	write_cdfpart_cluster (pccluster t, int nc_file, const char *prefix)
	Write cluster to part of a NetCDF file. More...

pcluster	read_cdf_cluster (const char *name)
	Read cluster from NetCDF file. More...

pcluster	read_cdfpart_cluster (int nc_file, const char *prefix)
	Read cluster from part of a NetCDF file. More...

Detailed Description

Representation of a cluster tree.

The cluster class is used to represent cluster trees including coordinates of the corresponding bounding box and pointers to its sons.

Enumeration Type Documentation

enum clustermode

Set the clustering strategy.

Characterises the cluster strategy stored in clustermode.

Remarks: Used to forward a cluster strategy to build_cluster.

Enumerator
H2_ADAPTIVE	Geometrically adaptive clustering.
H2_REGULAR	Geometrically regular clustering.
H2_SIMSUB	Simultaneous subdivision clustering.
H2_PCA	Geometrically clustering based principal component analysis (PCA).

Function Documentation

void balance_cluster	(	pcluster	t,
		uint	depth
	)

Balance a cluster tree to a given depth.

Balances a cluster tree $ t $ in such a way that getdepth_cluster $(t) == $ getmindepth_cluster $(t) == depth $ .

Parameters

t	Cluster object to be balanced.
depth	New depth of the cluster tree.

pcluster build_adaptive_cluster	(	pclustergeometry	cf,
		uint	size,
		uint *	idx,
		uint	clf
	)

Build a cluster tree from a clustergeometry object using adaptive clustering.

Builds an adaptive cluster tree (clustermode = H2_ADAPTIVE) basing on the geometrical informations of the clustergeometry object. The boundig box is splitted adaptively into two parts corresponding to two sons in the direction with the largest spatial extension and the index set is splitted accordingl, if its size is greater than the leaf size, else the cluster is a leaf cluster. During this clustering the bounding boxes are updated.

Parameters

cf	clustergeometry object with geometrical information.
size	Number of indices.
idx	Index set.
clf	Maximal leaf size.

Returns: Returns an adaptive cluster tree object.

pcluster build_cluster	(	pclustergeometry	cf,
		uint	size,
		uint *	idx,
		uint	clf,
		clustermode	mode
	)

Build a cluster tree from a clustergeometry object using cluster strategy clustermode.

Builds a cluster tree basing on the geometrical information of the clustergeometry object. The parameter clustermode sets the used cluster strategy and the appropriate function defined above is called.

Parameters

cf	clustergeometry object with geometrical information.
size	Number of indices.
idx	Index set.
clf	Maximal leaf size.
mode	Cluster strategy

Returns: Returns the newly created cluster tree.

pcluster build_pca_cluster	(	pclustergeometry	cf,
		uint	size,
		uint *	idx,
		uint	clf
	)

Build a cluster tree from a clustergeometry object based on the principal component analysis.

Compute the principal directions of a cluster and split it along the largest extent.

Parameters

cf	clustergeometry object with geometrical information.
size	Number of indices.
idx	Index set.
clf	Maximal leaf size.

Returns: Returns a cluster tree object basing on pca.

pcluster build_regular_cluster	(	pclustergeometry	cf,
		uint	size,
		uint *	idx,
		uint	clf,
		uint	direction
	)

Build a cluster tree from a clustergeometry object using regular clustering.

Builds a regular cluster tree (clustermode = H2_REGULAR) basing on the geometrical informations of the clustergeometry object. The splitting starts with the forwarded direction and the following directions are chosen via cycling through all possible directions. The bounding box is splitted regularly in two parts corresponding to two sons and the index set is subdivided accordingly, if its size is greater than the leaf size, else the cluster is a leaf cluster. During this clustering the bounding boxes are updated.

Parameters

cf	clustergeometry object with geometrical information.
size	Number of indices.
idx	Index set.
clf	Maximal leaf size.
direction	Direction for the next splitting step.

Returns: Returns a regular cluster tree object.

pcluster build_simsub_cluster	(	pclustergeometry	cf,
		uint	size,
		uint *	idx,
		uint	clf
	)

Build a cluster tree from a clustergeometry object using simultaneous subdivision clustering.

The bounding box of a cluster is regularly subdivided along each coordinate direction, then empty sub-boxes are removed.

Parameters

cf	clustergeometry object with geometrical information.
size	Number of indices.
idx	Index set.
clf	Maximal leaf size.

Returns: Returns a cluster tree object basing on simultaneous subdivision clustering

void coarsen_cluster	(	pcluster	t,
		uint	minsize
	)

Coarsen a cluster tree to a minimal size.

Coarsens a cluster object $ t $ in such a way that $t->size \geq \text{minsize}$ for all clusters $ t $ .

Parameters

t	Cluster object.
minsize	minimal size for all cluster trees.

void cut_cluster	(	pcluster	t,
		uint	depth
	)

Cut a cluster object until a new depth is reached.

Cut a cluster tree until a given depth is reached. Parts of the cluster tree, which exceed the new depth, are deleted.

Parameters

t	Cluster object to be cut.
depth	Depth of the cluster tree after the cut.

void del_cluster ( pcluster t )

Delete a cluster object.

Releases the storage corresponding to the cluster object. If the cluster has sons, their storage is released too.

Parameters

t	Cluster object to be deleted.

pcluster* enumerate_cluster ( pcluster t )

Enumerate all clusters in a cluster tree.

The clusters are enumerated recursively, top-down and left-to-right, i.e., the root gets the index 0, the first son gets the indices 1 to t->son[0]->desc, the second son gets the indices t->son[0]->desc+1 to t->son[0]->desc+t->son[1]->desc, and so on.

The resulting array has t->desc entries.

Parameters

t	Root cluster.

Returns: Array of pointers to all t->desc clusters, enumerated top-down and left-to-right.

void extend_cluster	(	pcluster	t,
		uint	depth
	)

Extends a given cluster $t$ until getmindepth_cluster(t) == depth.

Parameters

t	Input cluster tree which minimal depth will be extended to `depth`
depth	Minimal depth of the cluster tree to be reached.

uint getdepth_cluster ( pccluster t )

Compute the depth of a cluster object.

Compute the maximal depth of a cluster tree.

Parameters

t	Cluster object.

Returns: Depth of the cluster tree.

real getdiam_2_cluster ( pccluster t )

Compute the euclidian diameter of the bounding box of a cluster.

Computes the euclidian diameter of the bounding box $ B_t $ of a cluster object $ t $ : $\text{diam}_2 (B_t) := \text{max} \left\{ \left\| x-y\right\|_2 : x,y \in B_t\right\}$ .

Parameters

t	Of this cluster the euclidian diameter is computed.

Returns: Returns the euclidian diameter of the bounding box.

real getdiam_max_cluster ( pccluster t )

Compute the diameter of the bounding of a cluster in the maximum norm.

Compute the diameter of the bounding box $ B_t $ of a cluster object $ t $ in the maximum norm: $\text{diam}_{\infty} (B_t) := \left\{ \left\| x-y \right\|_{\infty} : x, y \in B_t \right\}$ .

Parameters

t	Of this cluster the diameter is computed.

Returns: Returns the diameter of the bounding box in the maximum norm.

real getdist_2_cluster	(	pccluster	t,
		pccluster	s
	)

Compute the euclidian distance of two clusters.

Computes the euclidian distance of two bounding boxes $ B_t $ and $ B_s $ of two clusters $ t $ and $ s $ : $\text{dist}_2(B_t, B_s) := \min \left\{ \left\| x-y \right\|_2 : x \in B_t, y \in B_s \right\}.$

Parameters

t	Row cluster.
s	Col cluster.

Returns: Returns the euclidian distance of two clusters.

real getdist_max_cluster	(	pccluster	t,
		pccluster	s
	)

Compute the distance of two clusters in the maximum norm.

Computes the distance of the bounding boxes of two cluster objects $ t $ and $ s $ in the maximum norm: $\text{dist}_{\infty} (B_t, B_s) := \min \left\{ \left\| x-y \right\| _{\infty} : x \in B_t, y \in B_s \right\}$ .

Parameters

t	Row cluster.
s	Col cluster.

Returns: Returns the distant of two clusters in the maximum norm.

uint getmindepth_cluster ( pccluster t )

Compute the minimal level of a cluster object.

Compute the minimal level of the leaf clusters in a cluster tree.

Parameters

t	Cluster object.

Returns: Minimal level of the leaf clusters of the cluster tree.

void iterate_cluster	(	pccluster	t,
		uint	tname,
		void()(pccluster t, uint tname, void data)	pre,
		void()(pccluster t, uint tname, void data)	post,
		void *	data
	)

Hierarchical iterator for a cluster tree.

Iterate over the cluster basis and all its descendants. The pre function is called for each element before its descendants are processed, the post function is called afterwards The cluster tree is iterated in a depth first scheme:

tname will take values between tname and tname+t->sons-1, where tname is interpreted as the index of the root, while the indices of the first son start at tname+1, the indices of the second start at tname+1+1t->son[0]->desc, and so on.

Remarks: If the cluster tree is included in an enumerated object like an enumerated clusterbasis, the parameter tname can be used to adresss to this ordered object.

Parameters

t	Root of the cluster tree.
tname	Identificator of the (partial) cluster tree, initially 0.
pre	Callback function applied before iterating through childs.
post	Callback function applied after iterating through childs.
data	Auxiliary data for the callback functions `pre` and `post` .

void iterate_parallel_cluster	(	pccluster	t,
		uint	tname,
		uint	pardepth,
		void()(pccluster t, uint tname, void data)	pre,
		void()(pccluster t, uint tname, void data)	post,
		void *	data
	)

Parallel hierarchical iterator for a cluster tree.

Iterate over the cluster basis and all its descendants. The pre function is called for each element before its descendants are processed, the post function is called afterwards The cluster tree is iterated in a depth first scheme:

tname will take values between tname and tname+t->sons-1, where tname is interpreted as the index of the root, while the indices of the first son start at tname+1, the indices of the second start at tname+1+1t->son[0]->desc, and so on.

Remarks: If the cluster tree is included in an enumerated object like an enumerated clusterbasis, the parameter tname can be used to adresss to this ordered object.

Parameters

t	Root of the cluster tree.
tname	Identificator of the (partial) cluster tree, initially 0.
pardepth	Parallelization depth.
pre	Callback function applied for iterating through childs.
post	Callback function applied for iterating through childs.
data	Auxiliary data for the callback funtions `pre` and `post` .

pcluster new_cluster	(	uint	size,
		uint *	idx,
		uint	sons,
		uint	dim
	)

Create a new cluster object.

Allocates storage for the object and sets the pointers to the sons to NULL.

Remarks: Should always be matched by a call to del_cluster.

Parameters

size	Number of indices.
idx	Index set.
sons	Number of sons.
dim	Spatial dimension of bounding box.

Returns: New cluster object.

pcluster read_cdf_cluster ( const char * name )

Read cluster from NetCDF file.

Parameters

name	File name.

Returns: cluster read from file.

pcluster read_cdfpart_cluster	(	int	nc_file,
		const char *	prefix
	)

Read cluster from part of a NetCDF file.

Parameters

nc_file	File handle.
prefix	Prefix for variable names.

Returns: cluster read from file.

void setsons_cluster	(	pcluster	t,
		uint	sons
	)

Set the number of sons of a cluster tree.

Sets the number of sons of a given cluster object to a given number. All sons are initialised with NULL.

Parameters

t	cluster object.
sons	Number of sons of the cluster object after calling this function.

void update_cluster ( pcluster t )

Complete the initialisation of a cluster object.

Complete the initialisation of the cluster object after all sons have been initialised. The Number of the descendants of the cluster is counted.

Parameters

t	Cluster object to be completed.

void write_cdf_cluster	(	pccluster	t,
		const char *	name
	)

Write cluster to NetCDF file.

Parameters

t	Cluster.
name	File name.

void write_cdfpart_cluster	(	pccluster	t,
		int	nc_file,
		const char *	prefix
	)

Write cluster to part of a NetCDF file.

Parameters

t	Cluster.
nc_file	File handle.
prefix	Prefix for variable names.

Data Structures

Typedefs

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

Function Documentation