OpenWalnut  1.5.0dev
Public Member Functions | Private Member Functions | Private Attributes | List of all members
WHtreePartition Class Reference

this class operates over the class WHtree to extract partitions and analyze partition quality it may change some non-essential members of the tree class such as saved selected partitions but the tree structure is never modified. More...

#include <WHtreePartition.h>

+ Collaboration diagram for WHtreePartition:

Public Member Functions

 WHtreePartition (WHtree *const tree)
 Constructor. More...
 
 ~WHtreePartition ()
 Destructor. More...
 
void scanOptimalPartitions (const size_t levelDepth, std::vector< float > *partitionValuesPointer, std::vector< std::vector< size_t > > *patitionVectorPointer, const bool verbose=false)
 Obtain the partition quality values for the optimized (inter vs weighted intra cluster distance) partitions at each granulairty of the tree. More...
 
void scanHozPartitions (std::vector< float > *partitionValuesPointer, std::vector< std::vector< size_t > > *patitionVectorPointer, const bool verbose=false)
 Obtain the partition quality values for the classic partitions at each granulairty of the tree. More...
 
size_t filterMaxPartitions (const unsigned int filterRadius, std::vector< float > *partValPoint, std::vector< std::vector< size_t > > *partVectorPoint)
 Filter a set of partitions across granularity levels in orther to keep only local maxima within a certain granularity "radius". More...
 
void writePartitionSet (std::string partFileName, const std::vector< float > &partitionValues, const std::vector< std::vector< size_t > > &patitionVector)
 write a set of partitions and their quality values to a text file More...
 
void level2granularity (std::vector< nodeID_t > *partition) const
 obtain the partition corresponding to the second lowest level of granularity of a tree (using full boolean-integer node ID) that is, those those clusters correspondign to nodes having only one branching in between them and single leaves More...
 
void level2granularity (std::vector< size_t > *partition) const
 obtain the partition corresponding to the second lowest level of granularity of a tree (using only non-leaf node ID) that is, those those clusters correspondign to nodes having only one branching in between them and single leaves More...
 
float partitionClassic (float compValue, std::vector< nodeID_t > *const partition, const HT_PARTMODE mode, const HT_CONDITION condition, const bool excludeLeaves, const size_t root) const
 Gets a classic partition for the tree (those where clusters are further subdivided until a condition is met, based on number of clusters, level or biggest cluster size) More...
 
float partitionOptimized (float compValue, std::vector< nodeID_t > *const partition, const HT_PARTMODE2 mode, const HT_CONDITION condition, const bool excludeLeaves, const size_t root, const size_t levelDepth) const
 Gets an optimized partition for the tree (those where a partition characteristic must be cosnidered for several partitions and levels at a time to decide which subset of the tree to continue navigating, until a condition is met) More...
 
float partitionSharp (const float compValue, std::vector< nodeID_t > *const partition, const bool excludeLeaves, const size_t root, const bool normalized) const
 Finds clusters with sharp boundaries (long branches) the tree. More...
 
float partitionSmooth (const float compValue, std::vector< nodeID_t > *const partition, const bool excludeLeaves, const size_t root) const
 Finds regions without sharp inner boundaries the tree. More...
 

Private Member Functions

std::pair< float, float > evalPartClustSizeDiff (const std::vector< size_t > &partition) const
 Evaluate partition cluster size difference (using only non-leaf node ID) More...
 
std::pair< float, float > evalPartClustSizeDiff (const std::vector< nodeID_t > &partition) const
 Evaluate partition cluster size difference (using full boolean-integer node ID) More...
 
float evalPartOptimal (const std::vector< size_t > &partition) const
 Evaluate partition quality: spread-separation index (using only non-leaf node ID) More...
 
float evalPartOptimal (const std::vector< nodeID_t > &partition) const
 Evaluate partition quality: spread-separation index (using full boolean-integer node ID) More...
 
float evalSSindex (const std::vector< size_t > &partition) const
 Evaluate spread-separation index for selected partition (using only non-leaf node ID) More...
 
float evalSSindex (const std::vector< nodeID_t > &partition) const
 Evaluate spread-separation index for selected partition (using full boolean-integer node ID) More...
 
float evalPartIntraDist (const std::vector< size_t > &partition) const
 Evaluate intra cluster distance factor for selected partition (using only non-leaf node ID) More...
 
float evalPartIntraDist (const std::vector< nodeID_t > &partition) const
 Evaluate intra cluster distance factor for selected partition (using full boolean-integer node ID) More...
 
float evalPartIntraDistWeighted (const std::vector< size_t > &partition) const
 Evaluate weighted intra cluster distance factor for selected partition (using only non-leaf node ID) More...
 
float evalPartIntraDistWeighted (const std::vector< nodeID_t > &partition) const
 Evaluate weighted intra cluster distance factor for selected partition (using full boolean-integer node ID) More...
 
float evalPartBranchDist (const std::vector< size_t > &partition) const
 Evaluate approximated inter cluster distance factor for selected partition (using only non-leaf node ID) More...
 
float evalPartBranchDist (const std::vector< nodeID_t > &partition) const
 Evaluate approximated inter cluster distance factor for selected partition (using full boolean-integer node ID) More...
 
float evalPartBranchDistWeighted (const std::vector< size_t > &partition) const
 Evaluate approximated weighted inter cluster distance factor for selected partition (using only non-leaf node ID) More...
 
float evalPartBranchDistWeighted (const std::vector< nodeID_t > &partition) const
 Evaluate approximated weighted inter cluster distance factor for selected partition (using full boolean-integer node ID) More...
 
std::vector< std::vector< dist_t > > getICDmatrix (const std::vector< size_t > &oldPartition, size_t branchPos=0, std::vector< size_t > branch=std::vector< size_t >(), std::vector< std::vector< dist_t > > oldMatrix=std::vector< std::vector< dist_t > >())
 Obtain pairwise intercluster distance matrix for the selected partition, or derive new icd matrix from an old one following the subdivision of one of the clusters (DEPRECATED) More...
 
float evalPartInterDist (const std::vector< size_t > &partition, const std::vector< std::vector< dist_t > > &icdMatrix) const
 Evaluate full inter cluster distance factor for selected partition (DEPRECATED) More...
 
float evalPartInterDistWeighted (const std::vector< size_t > &partition, const std::vector< std::vector< dist_t > > &icdMatrix) const
 Evaluate full weighted inter cluster distance factor for selected partition (DEPRECATED) More...
 

Private Attributes

WHtreem_tree
 tree object More...
 

Detailed Description

this class operates over the class WHtree to extract partitions and analyze partition quality it may change some non-essential members of the tree class such as saved selected partitions but the tree structure is never modified.

Definition at line 100 of file WHtreePartition.h.

Constructor & Destructor Documentation

◆ WHtreePartition()

WHtreePartition::WHtreePartition ( WHtree *const  tree)
explicit

Constructor.

Parameters
treea pointer to the tree to be partitioned

Definition at line 64 of file WHtreePartition.cpp.

◆ ~WHtreePartition()

WHtreePartition::~WHtreePartition ( )

Destructor.

Definition at line 68 of file WHtreePartition.cpp.

Member Function Documentation

◆ evalPartBranchDist() [1/2]

float WHtreePartition::evalPartBranchDist ( const std::vector< nodeID_t > &  partition) const
private

Evaluate approximated inter cluster distance factor for selected partition (using full boolean-integer node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
approximated inter cluster distance factor value of the partition

Definition at line 631 of file WHtreePartition.cpp.

References WHnode::getDistLevel(), WHtree::getNode(), WHnode::getParent(), and m_tree.

+ Here is the call graph for this function:

◆ evalPartBranchDist() [2/2]

float WHtreePartition::evalPartBranchDist ( const std::vector< size_t > &  partition) const
private

Evaluate approximated inter cluster distance factor for selected partition (using only non-leaf node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
approximated inter cluster distance factor value of the partition

Definition at line 620 of file WHtreePartition.cpp.

Referenced by partitionOptimized().

+ Here is the caller graph for this function:

◆ evalPartBranchDistWeighted() [1/2]

float WHtreePartition::evalPartBranchDistWeighted ( const std::vector< nodeID_t > &  partition) const
private

Evaluate approximated weighted inter cluster distance factor for selected partition (using full boolean-integer node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
approximated weighted inter cluster distance value of the partition

Definition at line 654 of file WHtreePartition.cpp.

References WHnode::getDistLevel(), WHtree::getNode(), WHnode::getParent(), WHnode::getSize(), and m_tree.

+ Here is the call graph for this function:

◆ evalPartBranchDistWeighted() [2/2]

float WHtreePartition::evalPartBranchDistWeighted ( const std::vector< size_t > &  partition) const
private

Evaluate approximated weighted inter cluster distance factor for selected partition (using only non-leaf node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
approximated weighted inter cluster distance value of the partition

Definition at line 644 of file WHtreePartition.cpp.

Referenced by partitionOptimized().

+ Here is the caller graph for this function:

◆ evalPartClustSizeDiff() [1/2]

std::pair< float, float > WHtreePartition::evalPartClustSizeDiff ( const std::vector< nodeID_t > &  partition) const
private

Evaluate partition cluster size difference (using full boolean-integer node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
cluster size difference value of the partition

Definition at line 555 of file WHtreePartition.cpp.

References WHtree::getNode(), WHnode::getSize(), and m_tree.

+ Here is the call graph for this function:

◆ evalPartClustSizeDiff() [2/2]

std::pair< float, float > WHtreePartition::evalPartClustSizeDiff ( const std::vector< size_t > &  partition) const
private

Evaluate partition cluster size difference (using only non-leaf node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
cluster size difference value of the partition

Definition at line 545 of file WHtreePartition.cpp.

Referenced by partitionOptimized().

+ Here is the caller graph for this function:

◆ evalPartInterDist()

float WHtreePartition::evalPartInterDist ( const std::vector< size_t > &  partition,
const std::vector< std::vector< dist_t > > &  icdMatrix 
) const
private

Evaluate full inter cluster distance factor for selected partition (DEPRECATED)

Parameters
partitionvector with the partition to be evaluated
icdMatrixpairwise inter-cluster distance matrix for the selected partition
Returns
full inter cluster distance factor value of the partition

Definition at line 1307 of file WHtreePartition.cpp.

◆ evalPartInterDistWeighted()

float WHtreePartition::evalPartInterDistWeighted ( const std::vector< size_t > &  partition,
const std::vector< std::vector< dist_t > > &  icdMatrix 
) const
private

Evaluate full weighted inter cluster distance factor for selected partition (DEPRECATED)

Parameters
partitionvector with the partition to be evaluated
icdMatrixpairwise inter-cluster distance matrix for the selected partition
Returns
full weighted inter cluster distance factor value of the partition

Definition at line 1335 of file WHtreePartition.cpp.

References WHtree::getNode(), WHnode::getSize(), and m_tree.

+ Here is the call graph for this function:

◆ evalPartIntraDist() [1/2]

float WHtreePartition::evalPartIntraDist ( const std::vector< nodeID_t > &  partition) const
private

Evaluate intra cluster distance factor for selected partition (using full boolean-integer node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
intra cluster distance factor value of the partition

Definition at line 585 of file WHtreePartition.cpp.

References WHnode::getDistLevel(), WHtree::getNode(), and m_tree.

+ Here is the call graph for this function:

◆ evalPartIntraDist() [2/2]

float WHtreePartition::evalPartIntraDist ( const std::vector< size_t > &  partition) const
private

Evaluate intra cluster distance factor for selected partition (using only non-leaf node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
intra cluster distance factor value of the partition

Definition at line 574 of file WHtreePartition.cpp.

Referenced by partitionOptimized().

+ Here is the caller graph for this function:

◆ evalPartIntraDistWeighted() [1/2]

float WHtreePartition::evalPartIntraDistWeighted ( const std::vector< nodeID_t > &  partition) const
private

Evaluate weighted intra cluster distance factor for selected partition (using full boolean-integer node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
weighted intra cluster distance factor value of the partition

Definition at line 607 of file WHtreePartition.cpp.

References WHnode::getDistLevel(), WHtree::getNode(), WHnode::getSize(), and m_tree.

+ Here is the call graph for this function:

◆ evalPartIntraDistWeighted() [2/2]

float WHtreePartition::evalPartIntraDistWeighted ( const std::vector< size_t > &  partition) const
private

Evaluate weighted intra cluster distance factor for selected partition (using only non-leaf node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
weighted intra cluster distance factor value of the partition

Definition at line 597 of file WHtreePartition.cpp.

Referenced by partitionOptimized().

+ Here is the caller graph for this function:

◆ evalPartOptimal() [1/2]

float WHtreePartition::evalPartOptimal ( const std::vector< nodeID_t > &  partition) const
private

Evaluate partition quality: spread-separation index (using full boolean-integer node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
quality value of the partition

Definition at line 495 of file WHtreePartition.cpp.

References evalSSindex().

+ Here is the call graph for this function:

◆ evalPartOptimal() [2/2]

float WHtreePartition::evalPartOptimal ( const std::vector< size_t > &  partition) const
private

Evaluate partition quality: spread-separation index (using only non-leaf node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
quality value of the partition

Definition at line 485 of file WHtreePartition.cpp.

Referenced by partitionOptimized(), scanHozPartitions(), and scanOptimalPartitions().

+ Here is the caller graph for this function:

◆ evalSSindex() [1/2]

float WHtreePartition::evalSSindex ( const std::vector< nodeID_t > &  partition) const
private

Evaluate spread-separation index for selected partition (using full boolean-integer node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
spread-separation index value of the partition

Definition at line 516 of file WHtreePartition.cpp.

References WHnode::getDistLevel(), WHtree::getNode(), WHnode::getParent(), WHnode::getSize(), and m_tree.

+ Here is the call graph for this function:

◆ evalSSindex() [2/2]

float WHtreePartition::evalSSindex ( const std::vector< size_t > &  partition) const
private

Evaluate spread-separation index for selected partition (using only non-leaf node ID)

Parameters
partitionvector with the partition to be evaluated
Returns
spread-separation index value of the partition

Definition at line 506 of file WHtreePartition.cpp.

Referenced by evalPartOptimal().

+ Here is the caller graph for this function:

◆ filterMaxPartitions()

size_t WHtreePartition::filterMaxPartitions ( const unsigned int  filterRadius,
std::vector< float > *  partValPoint,
std::vector< std::vector< size_t > > *  partVectorPoint 
)

Filter a set of partitions across granularity levels in orther to keep only local maxima within a certain granularity "radius".

Parameters
filterRadiusradius (in granularity steps) within to keep the local maxima
partValPoint(is a return value) pointer to the partition value vector to be decimated
partVectorPoint(is a return value) pointer to the partition vector to be decimated
Returns
the index of the partition with the absolute maximum of quality vaule

Definition at line 402 of file WHtreePartition.cpp.

◆ getICDmatrix()

std::vector< std::vector< dist_t > > WHtreePartition::getICDmatrix ( const std::vector< size_t > &  oldPartition,
size_t  branchPos = 0,
std::vector< size_t >  branch = std::vector<size_t>(),
std::vector< std::vector< dist_t > >  oldMatrix = std::vector< std::vector< dist_t > >() 
)
private

Obtain pairwise intercluster distance matrix for the selected partition, or derive new icd matrix from an old one following the subdivision of one of the clusters (DEPRECATED)

Parameters
oldPartitionvector with the partition to be evaluated or the previously evaluated partition
branchPosindex of the cluster that was further subdivided if considerign a previously calculated matrix, 0 if no previous calculation exists (default)
branchvector with sub-clusters to replace original cluster after subdivision, empty if no previous calculation exists (default)
oldMatrixicd matrix from previous calculation, empty if no previous calculation exists (default)
Returns
pairwise inter cluster distance matrix for the selected (or derived) parititon

Definition at line 1252 of file WHtreePartition.cpp.

References WHtree::getCommonAncestor(), WHnode::getDistLevel(), WHtree::getNode(), and m_tree.

+ Here is the call graph for this function:

◆ level2granularity() [1/2]

void WHtreePartition::level2granularity ( std::vector< nodeID_t > *  partition) const

obtain the partition corresponding to the second lowest level of granularity of a tree (using full boolean-integer node ID) that is, those those clusters correspondign to nodes having only one branching in between them and single leaves

Parameters
partitionvector where the return partition is saved

Definition at line 1368 of file WHtreePartition.cpp.

◆ level2granularity() [2/2]

void WHtreePartition::level2granularity ( std::vector< size_t > *  partition) const

obtain the partition corresponding to the second lowest level of granularity of a tree (using only non-leaf node ID) that is, those those clusters correspondign to nodes having only one branching in between them and single leaves

Parameters
partitionvector where the return partition is saved

Definition at line 1383 of file WHtreePartition.cpp.

References WHnode::getChildren(), WHnode::getHLevel(), WHtree::getNode(), WHtree::getNumNodes(), WHnode::getParent(), WHtree::getRootBaseNodes(), and m_tree.

+ Here is the call graph for this function:

◆ partitionClassic()

float WHtreePartition::partitionClassic ( float  compValue,
std::vector< nodeID_t > *const  partition,
const HT_PARTMODE  mode,
const HT_CONDITION  condition,
const bool  excludeLeaves,
const size_t  root 
) const

Gets a classic partition for the tree (those where clusters are further subdivided until a condition is met, based on number of clusters, level or biggest cluster size)

Parameters
compValuecomparison value to select partition
partition(is a return value) vector where to save the partition
modetipe of data on which to base the partition (distance, size h. level)
conditioncondition on which to build the partition (condition value or number of clusters)
excludeLeavesif set base nodes will not be further partitioned
rootroot of the subtree where to find the aprtition
Returns
value at wich partition was found

Definition at line 672 of file WHtreePartition.cpp.

References WHnode::getChildren(), WHnode::getDistLevel(), WHnode::getFullID(), WHnode::getHLevel(), WHnode::getID(), WHtree::getNode(), WHtree::getNumNodes(), WHtree::getRoot(), WHnode::getSize(), WHnode::isLeaf(), WHnode::isRoot(), m_tree, WHtree::sortByHLevel(), and WHtree::sortBySize().

Referenced by WMHierchClustDisplay::clusterSelection(), scanHozPartitions(), and scanOptimalPartitions().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ partitionOptimized()

float WHtreePartition::partitionOptimized ( float  compValue,
std::vector< nodeID_t > *const  partition,
const HT_PARTMODE2  mode,
const HT_CONDITION  condition,
const bool  excludeLeaves,
const size_t  root,
const size_t  levelDepth 
) const

Gets an optimized partition for the tree (those where a partition characteristic must be cosnidered for several partitions and levels at a time to decide which subset of the tree to continue navigating, until a condition is met)

Parameters
compValuecomparison value to select partition
partition(is a return value) vector where to save the partition
modetipe of data on which to base the partition ( spread-separation index, minimum size difference, maximum allowed intra cluster distance, maximum allowed weighted intra cluster distance, minimum required inter cluster distance, minimum required weighted inter cluster distance)
conditioncondition on which to build the partition (condition value or number of clusters)
excludeLeavesif set base nodes will not be further partitioned
rootroot of the subtree where to find the aprtition
levelDepthnumber of levels down where to search for the best branching decision
Returns
value at wich partition was found

Definition at line 828 of file WHtreePartition.cpp.

References evalPartBranchDist(), evalPartBranchDistWeighted(), evalPartClustSizeDiff(), evalPartIntraDist(), evalPartIntraDistWeighted(), evalPartOptimal(), WHtree::getBranching(), WHnode::getDistLevel(), WHnode::getFullID(), WHnode::getID(), WHtree::getNode(), WHtree::getNumNodes(), WHtree::getRoot(), WHnode::getSize(), and m_tree.

Referenced by WMHierchClustDisplay::clusterSelection().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ partitionSharp()

float WHtreePartition::partitionSharp ( const float  compValue,
std::vector< nodeID_t > *const  partition,
const bool  excludeLeaves,
const size_t  root,
const bool  normalized 
) const

Finds clusters with sharp boundaries (long branches) the tree.

Parameters
compValuecomparison value to select partition
partition(is a return value) vector where to save the partition
excludeLeavesif set base nodes will not be further partitioned
rootroot of the subtree where to find the aprtition
normalizedflag to indicate whether the absolute length of the brancghwes should be considered of if they should be normalized by distance level in the tree
Returns
value at wich partition was found

Definition at line 1090 of file WHtreePartition.cpp.

References WHnode::getChildren(), WHnode::getDistLevel(), WHnode::getFullID(), WHnode::getHLevel(), WHnode::getID(), WHtree::getNode(), WHtree::getNumNodes(), WHtree::getRoot(), WHnode::isLeaf(), and m_tree.

Referenced by WMHierchClustDisplay::clusterSelection().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ partitionSmooth()

float WHtreePartition::partitionSmooth ( const float  compValue,
std::vector< nodeID_t > *const  partition,
const bool  excludeLeaves,
const size_t  root 
) const

Finds regions without sharp inner boundaries the tree.

Parameters
compValuecomparison value to select partition
partition(is a return value) vector where to save the partition
excludeLeavesif set base nodes will not be further partitioned
rootroot of the subtree where to find the aprtition
Returns
value at wich partition was found

Definition at line 1156 of file WHtreePartition.cpp.

References WHtree::getBaseNodes(), WHnode::getChildren(), WHnode::getDistLevel(), WHnode::getFullID(), WHnode::getID(), WHtree::getLeaf(), WHtree::getNode(), WHtree::getNumLeaves(), WHtree::getNumNodes(), WHnode::getParent(), WHtree::getRoot(), WHnode::isRoot(), and m_tree.

+ Here is the call graph for this function:

◆ scanHozPartitions()

void WHtreePartition::scanHozPartitions ( std::vector< float > *  partitionValuesPointer,
std::vector< std::vector< size_t > > *  patitionVectorPointer,
const bool  verbose = false 
)

Obtain the partition quality values for the classic partitions at each granulairty of the tree.

Parameters
partitionValuesPointervector where to save the partition quality values
patitionVectorPointervector where to save the partition actual partitions
verboseflag to activate debug output

Definition at line 316 of file WHtreePartition.cpp.

References evalPartOptimal(), WHnode::getChildren(), WHnode::getID(), WHtree::getRoot(), m_tree, and partitionClassic().

+ Here is the call graph for this function:

◆ scanOptimalPartitions()

void WHtreePartition::scanOptimalPartitions ( const size_t  levelDepth,
std::vector< float > *  partitionValuesPointer,
std::vector< std::vector< size_t > > *  patitionVectorPointer,
const bool  verbose = false 
)

Obtain the partition quality values for the optimized (inter vs weighted intra cluster distance) partitions at each granulairty of the tree.

Parameters
levelDepthnumber of levels down where to search for the best branching decision
partitionValuesPointervector where to save the partition quality values
patitionVectorPointervector where to save the partition actual partitions
verboseflag to activate debug output

Definition at line 75 of file WHtreePartition.cpp.

References evalPartOptimal(), WHtree::getBranching(), WHnode::getChildren(), WHnode::getDistLevel(), WHnode::getID(), WHtree::getNode(), WHtree::getRoot(), m_tree, and partitionClassic().

+ Here is the call graph for this function:

◆ writePartitionSet()

void WHtreePartition::writePartitionSet ( std::string  partFileName,
const std::vector< float > &  partitionValues,
const std::vector< std::vector< size_t > > &  patitionVector 
)

write a set of partitions and their quality values to a text file

Parameters
partFileNamefile name where to write the partition selection
partitionValuespartition value vector to be written
patitionVectorpartition vector to be written

Definition at line 458 of file WHtreePartition.cpp.

Member Data Documentation

◆ m_tree

WHtree& WHtreePartition::m_tree
private

The documentation for this class was generated from the following files: