RePairCombiner< TreeType, DataType > Class Template Reference

Transform a tree into its top tree. More...

#include <RePairCombiner.h>

Collaboration diagram for RePairCombiner< TreeType, DataType >:

Public Member Functions
	RePairCombiner (TreeType &tree, TopDag< DataType > &topDag, const bool verbose=true, const bool extraVerbose=false)
void	construct (DebugInfo *debugInfo=NULL, const double minRatio=1.2)

Protected Member Functions
void	mergeCallback (const int u, const int v, const int n, const MergeType type)
void	doMerges (DebugInfo *debugInfo, const double minRatio=1.2)
uint	getRePairHash (const EdgeType *edge) const
void	prepareRePair (SimpleRePair::HashMap< Pair > &hashMap, SimpleRePair::PriorityQueue< Pair > &queue)
void	horizontalMergesRePair (const int iteration)
void	normalHorizontalMerges (const int iteration)
void	verticalMerges (const int iteration)
	Perform an iteration of vertical (chain) merges (step 2) More...

Protected Attributes
TreeType &	tree
TopDag< DataType > &	topDag
const bool	verbose
const bool	extraVerbose
vector< int >	nodeIds
NodeHasher< TreeType, DataType >	hasher
vector< bool >	dirty

Detailed Description

template<typename TreeType, typename DataType>
class RePairCombiner< TreeType, DataType >

Transform a tree into its top tree.

Given a tree (currently, only OrderedTree is supported), construct its top tree iteratively.

The original tree will be modified heavily in the process! When transformation is complete, only one edge will remain and nodes' parent values will be lost as well. In short, this destroys the input tree.

Definition at line 31 of file RePairCombiner.h.

Constructor & Destructor Documentation

template<typename TreeType, typename DataType>

RePairCombiner< TreeType, DataType >::RePairCombiner ( TreeType &  tree, TopDag< DataType > &  topDag, const bool  verbose = true, const bool  extraVerbose = false  )

inline

Instantiate a top tree constructor

Parameters

tree	the tree which shall be transformed. WILL BE MODIFIED
topDag	the output top tree
verbose	whether to print detailed information about the iterations
extraVerbose	whether to print the tree in each iteration

Definition at line 50 of file RePairCombiner.h.

Member Function Documentation

template<typename TreeType, typename DataType>

void RePairCombiner< TreeType, DataType >::construct ( DebugInfo *  debugInfo = NULL, const double  minRatio = 1.2  )

inline

Perform the top tree construction procedure

Parameters

debugInfo

pointer to a DebugInfo object, should you wish logging of debug information

Definition at line 59 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

void RePairCombiner< TreeType, DataType >::doMerges ( DebugInfo *  debugInfo, const double  minRatio = 1.2  )

inlineprotected

do iterated merges to construct a top tree

Parameters

mergeCallback	the callback that will be called for every pair of merged nodes (clusters). Its arguments are the ids of the two merged nodes and the new id (usually one of the two old ones) as well as the type of the merge
debugInfo	the DebugInfo object or NULL
verbose	whether to print detailed information about the iterations
extraVerbose	whether to print the tree in each iteration

Definition at line 77 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

uint RePairCombiner< TreeType, DataType >::getRePairHash ( const EdgeType *  edge ) const

inlineprotected

Definition at line 127 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

void RePairCombiner< TreeType, DataType >::horizontalMergesRePair ( const int  iteration )

inlineprotected

Definition at line 154 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

void RePairCombiner< TreeType, DataType >::mergeCallback ( const int  u, const int  v, const int  n, const MergeType  type  )

inlineprotected

Definition at line 64 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

void RePairCombiner< TreeType, DataType >::normalHorizontalMerges ( const int  iteration )

inlineprotected

Definition at line 208 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

void RePairCombiner< TreeType, DataType >::prepareRePair ( SimpleRePair::HashMap< Pair > &  hashMap, SimpleRePair::PriorityQueue< Pair > &  queue  )

inlineprotected

Definition at line 133 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

void RePairCombiner< TreeType, DataType >::verticalMerges ( const int  iteration )

inlineprotected

Perform an iteration of vertical (chain) merges (step 2)

Definition at line 255 of file RePairCombiner.h.

Member Data Documentation

template<typename TreeType, typename DataType>

vector<bool> RePairCombiner< TreeType, DataType >::dirty

protected

Definition at line 308 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

const bool RePairCombiner< TreeType, DataType >::extraVerbose

protected

Definition at line 305 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

NodeHasher<TreeType, DataType> RePairCombiner< TreeType, DataType >::hasher

protected

Definition at line 307 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

vector<int> RePairCombiner< TreeType, DataType >::nodeIds

protected

Definition at line 306 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

TopDag<DataType>& RePairCombiner< TreeType, DataType >::topDag

protected

Definition at line 304 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

TreeType& RePairCombiner< TreeType, DataType >::tree

protected

Definition at line 303 of file RePairCombiner.h.

template<typename TreeType, typename DataType>

const bool RePairCombiner< TreeType, DataType >::verbose

protected

Definition at line 305 of file RePairCombiner.h.

---

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

• RePairCombiner.h