TopDag< DataType > Class Template Reference

A binary DAG that is specialised to be a top tree's minimal DAG. More...

#include <TopDag.h>

Collaboration diagram for TopDag< DataType >:

Public Member Functions
	TopDag (const size_t n, const LabelsT< DataType > &labels)
	Create a new binary DAG. More...
int	addCluster (int left, int right, const MergeType mergeType, const DataType *label=NULL)
void	finishCreation ()
	Call this to clean up temporary data structures once the DAG is final. More...
int	countEdges () const
	Count the number of edges in the DAG. More...
template<typename T , typename Callback >
T	inPostOrder (const Callback &callback) const
template<typename T , typename Callback >
T	traverseDagPostOrder (const int nodeId, const Callback &callback) const
	Helper for inPostOrder(), you shouldn't need to call this directly. More...

Public Attributes
int	maxClusterId
vector< DagNode< DataType > >	nodes
const LabelsT< DataType > &	labels
std::unordered_map< DagNode< DataType >, int, SubtreeHasher< DataType >, SubtreeEquality< DataType > >	nodeMap
vector< int >	clusterToDag

Protected Member Functions
int	addCluster_ (int left, int right, const MergeType mergeType, const DataType *label=NULL)
	Add a node. More...
int	addNode (int left, int right, MergeType mergeType, const DataType *label)
void	popNode ()
	Remove the last node. More...
int	addNodes (const int n)

Friends
std::ostream &	operator<< (std::ostream &os, const TopDag< DataType > &dag)

Detailed Description

template<typename DataType>
class TopDag< DataType >

A binary DAG that is specialised to be a top tree's minimal DAG.

Definition at line 46 of file TopDag.h.

Constructor & Destructor Documentation

template<typename DataType>

TopDag< DataType >::TopDag ( const size_t  n, const LabelsT< DataType > &  labels  )

inline

Create a new binary DAG.

Definition at line 49 of file TopDag.h.

Member Function Documentation

template<typename DataType>

int TopDag< DataType >::addCluster ( int  left, int  right, const MergeType  mergeType, const DataType *  label = NULL  )

inline

Add a cluster and return its cluster ID (!= node ID!). If the cluster already exists in the DAG, it is not created again.

Parameters

left	cluster ID of the left child cluster
right	cluster ID of the right child cluster
mergeType	the cluster's merge type
label	the cluster's label (if any)

Definition at line 75 of file TopDag.h.

template<typename DataType>

int TopDag< DataType >::addCluster_ ( int  left, int  right, const MergeType  mergeType, const DataType *  label = NULL  )

inlineprotected

Add a node.

Definition at line 128 of file TopDag.h.

template<typename DataType>

int TopDag< DataType >::addNode ( int  left, int  right, MergeType  mergeType, const DataType *  label  )

inlineprotected

Add a node

Parameters

left	left child
right	right child
label	a label pointer
mergeType	the original node's merge type (for use with a TopTree)

Definition at line 157 of file TopDag.h.

template<typename DataType>

int TopDag< DataType >::addNodes ( const int  n )

inlineprotected

Add multiple nodes

Parameters

n	the number of nodes to add

Returns

the ID of the first node added

Definition at line 170 of file TopDag.h.

template<typename DataType>

int TopDag< DataType >::countEdges ( ) const

inline

Count the number of edges in the DAG.

Definition at line 87 of file TopDag.h.

template<typename DataType>

void TopDag< DataType >::finishCreation ( )

inline

Call this to clean up temporary data structures once the DAG is final.

Definition at line 82 of file TopDag.h.

template<typename DataType>

template<typename T , typename Callback >

T TopDag< DataType >::inPostOrder ( const Callback &  callback ) const

inline

Traverse the dag in post-order

Parameters

callback

a callback to be called with the node ID and the results of the calls to its children

Definition at line 99 of file TopDag.h.

template<typename DataType>

void TopDag< DataType >::popNode ( )

inlineprotected

Remove the last node.

Definition at line 163 of file TopDag.h.

template<typename DataType>

template<typename T , typename Callback >

T TopDag< DataType >::traverseDagPostOrder ( const int  nodeId, const Callback &  callback  ) const

inline

Helper for inPostOrder(), you shouldn't need to call this directly.

Definition at line 105 of file TopDag.h.

Friends And Related Function Documentation

template<typename DataType>

std::ostream& operator<< ( std::ostream &  os, const TopDag< DataType > &  dag  )

friend

Definition at line 118 of file TopDag.h.

Member Data Documentation

template<typename DataType>

vector<int> TopDag< DataType >::clusterToDag

Definition at line 180 of file TopDag.h.

template<typename DataType>

const LabelsT<DataType>& TopDag< DataType >::labels

Definition at line 178 of file TopDag.h.

template<typename DataType>

int TopDag< DataType >::maxClusterId

Definition at line 176 of file TopDag.h.

template<typename DataType>

std::unordered_map<DagNode<DataType>, int, SubtreeHasher<DataType>, SubtreeEquality<DataType> > TopDag< DataType >::nodeMap

Definition at line 179 of file TopDag.h.

template<typename DataType>

vector<DagNode<DataType> > TopDag< DataType >::nodes

Definition at line 177 of file TopDag.h.

---

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

• TopDag.h