Ordered tree data structure. More...

#include <OrderedTree.h>

Collaboration diagram for OrderedTree< NodeType, EdgeType >:

Public Types
typedef NodeType	nodeType
	the node type used in this tree More...

typedef EdgeType	edgeType
	the type of the edges used in this tree More...

Public Member Functions
	OrderedTree (const int n=0, const int m=0)

	OrderedTree (const OrderedTree< NodeType, EdgeType > &other)

EdgeType *	firstEdge ()
	pointer to the dummy edge More...

EdgeType *	firstEdge (const int u)

const EdgeType *	firstEdge (const int u) const

EdgeType *	lastEdge ()
	pointer to the last edge More...

EdgeType *	lastEdge (const int u)

const EdgeType *	lastEdge (const int u) const

int	nodeId (const NodeType *node)

int	edgeId (const EdgeType *edge)

int	addNode ()

int	addNodes (const int n)

EdgeType *	addEdge (const int from, const int to, const int extraSpace=0)

void	killNodes ()

void	removeEdge (const int from, const int edge, const bool compact=true)

void	removeEdgeTo (const int from, const int to, const bool compact=true)

void	mergeSiblings (const EdgeType leftEdge, const EdgeType rightEdge, int &newNode, MergeType &mergeType)

void	mergeChain (const int middleId, MergeType &mergeType)

template<typename LabelType >
bool	isEqual (const OrderedTree< NodeType, EdgeType > &other, LabelType &labels, LabelType &otherLabels, const bool verbose=false) const

template<typename LabelType >
bool	nodesEqual (const OrderedTree< NodeType, EdgeType > &other, LabelType &labels, LabelType &otherLabels, const int nodeId, const int otherNodeId, const bool verbose=false) const
	Recursive node comparison helper function used by isEqual(). You should not need to use this directly. More...

string	summary () const
	A one-line summary of the tree. More...

string	shortString () const

string	toString () const
	String representation of the tree, including all nodes and edges. More...

void	checkConsistency ()

void	compact (const bool verbose=true, const int factor=1)

void	compactNode (const int nodeId)

void	inplaceCompact (const bool verbose=true)

void	inplaceCompact (std::vector< bool > &dirty, const bool verbose=true)

template<typename T , typename Fold , typename Callback >
const T	foldLeftPostOrder (const Callback &callback, const Fold &fold, const T initial) const

template<typename T , typename Fold , typename Callback >
const T	traverseFoldLeftPostOrder (const int nodeId, const Callback &callback, const Fold &fold, const T initial) const
	This does the work for foldLeftPostOrder() and should not be used directly. More...

int	height () const

double	avgDepth () const

void	clear ()

Public Attributes
std::vector< NodeType >	nodes

std::vector< EdgeType >	edges

int	_firstFreeNode

int	_firstFreeEdge

int	_numNodes

int	_numEdges

Protected Member Functions
void	initialise (const int n, const int m)

EdgeType *	_prepareEdge (const int edgeId, const int from, const int to)
	Helper method for inserting new edges. More...

Friends
std::ostream &	operator<< (std::ostream &os, const OrderedTree< NodeType, EdgeType > &tree)

Detailed Description

template<typename NodeType, typename EdgeType>
class OrderedTree< NodeType, EdgeType >

Ordered tree data structure.

Holds an ordered tree

The tree is implemented as an adjacency array (See section 8.2 of http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GraphRep.pdf)

You can define your own node and edge types, e.g. add labels to the nodes or values to the edges if you wish

Definition at line 37 of file OrderedTree.h.

Member Typedef Documentation

template<typename NodeType, typename EdgeType>

typedef EdgeType OrderedTree< NodeType, EdgeType >::edgeType

the type of the edges used in this tree

Definition at line 42 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

typedef NodeType OrderedTree< NodeType, EdgeType >::nodeType

the node type used in this tree

Definition at line 40 of file OrderedTree.h.

Constructor & Destructor Documentation

template<typename NodeType, typename EdgeType>

OrderedTree< NodeType, EdgeType >::OrderedTree	(	const int	n = `0`,
		const int	m = `0`
	)

inline

Definition at line 44 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

OrderedTree< NodeType, EdgeType >::OrderedTree ( const OrderedTree< NodeType, EdgeType > & other )

inline

Definition at line 48 of file OrderedTree.h.

Member Function Documentation

template<typename NodeType, typename EdgeType>

EdgeType* OrderedTree< NodeType, EdgeType >::_prepareEdge	(	const int	edgeId,
		const int	from,
		const int	to
	)

inlineprotected

Helper method for inserting new edges.

Definition at line 613 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

EdgeType* OrderedTree< NodeType, EdgeType >::addEdge	(	const int	from,
		const int	to,
		const int	extraSpace = `0`
	)

inline

Add an edge to the tree

Parameters

from	tail (source) node ID
to	head (destination) node ID
extraSpace	extra space to allocate for more outgoing edges of 'from' if more edges need to be allocated

Definition at line 130 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::addNode ( )

inline

Add a node to the tree

Returns: the new node's ID

Definition at line 105 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::addNodes ( const int n )

inline

Add multiple nodes

Parameters

n	the number of nodes to add

Returns: the ID of the first node added

Definition at line 118 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

double OrderedTree< NodeType, EdgeType >::avgDepth ( ) const

inline

Calculate the average depth of the nodes in the tree. Uses foldLeftPostOrder() and worth looking at as slightly more complex example for a fold

Definition at line 579 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::checkConsistency ( )

inline

Perform a few consistency checks. NOP if NDEBUG is set

Definition at line 400 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::clear ( )

inline

Definition at line 587 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::compact	(	const bool	verbose = `true`,
		const int	factor = `1`
	)

inline

Compress the edge vector, removing gaps

Parameters

verbose	whether to print some debug information
factor	how many times the number of its outgoing edges a node's edge space shall be allocated. If you set this to 2, for example, space for another edge will be reserved for each edge that there is, so that inserting an edge does not cause moving or reallocation.

Definition at line 418 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::compactNode ( const int nodeId )

inline

Definition at line 461 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::edgeId ( const EdgeType * edge )

inline

Get edge ID from pointer

Parameters

edge	an edge pointer

Returns: the edge's ID (index in the edge vector)

Definition at line 99 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

EdgeType* OrderedTree< NodeType, EdgeType >::firstEdge ( )

inline

pointer to the dummy edge

Definition at line 57 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

EdgeType* OrderedTree< NodeType, EdgeType >::firstEdge ( const int u )

inline

Pointer to a node's first edge. Does not check whether the node actually has outgoing edges.

Parameters

u	a node ID (index in the node vector)

Returns: a pointer to u's first outgoing edge

Definition at line 63 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

const EdgeType* OrderedTree< NodeType, EdgeType >::firstEdge ( const int u ) const

inline

const pointer to a node's first edge. Does not check whether the node actually has outgoing edges.

Parameters

u	a node ID (index in the node vector)

Returns: a const pointer to u's first outgoing edge

Definition at line 69 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

template<typename T , typename Fold , typename Callback >

const T OrderedTree< NodeType, EdgeType >::foldLeftPostOrder	(	const Callback &	callback,
		const Fold &	fold,
		const T	initial
	)		const

inline

Perform a left fold over each node's children in post-order

Parameters

callback	a callback to be called for each node with the result of the last fold operation
fold	the fold function. Parameters: previous value, current value
initial	inital value for the first folding

Definition at line 553 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::height ( ) const

inline

Calculate the height of the tree (i.e., the maximum depth of a node). Uses foldLeftPostOrder() and worth looking at as a simple example of a fold

Definition at line 571 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::initialise	(	const int	n,
		const int	m
	)

inlineprotected

Initialise the tree

Parameters

n	number of nodes to reserve space for
m	number of edges to reserve space for

Definition at line 595 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::inplaceCompact ( const bool verbose = true )

inline

Do an inplace compaction of each node's vertices This is faster than rebuilding compaction.

Definition at line 483 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::inplaceCompact	(	std::vector< bool > &	dirty,
		const bool	verbose = `true`
	)

inline

Do an inplace compaction of only the dirty vertices This is faster than rebuilding compaction.

Definition at line 515 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

template<typename LabelType >

bool OrderedTree< NodeType, EdgeType >::isEqual	(	const OrderedTree< NodeType, EdgeType > &	other,
		LabelType &	labels,
		LabelType &	otherLabels,
		const bool	verbose = `false`
	)		const

inline

Check whether this tree is equal to another tree.

Parameters

other	the other tree
labels	the labels for this tree. Label type is kept very general deliberately
otherLabels	the other tree's labels
verbose	whether to print an error traceback if the trees are not equal

Definition at line 313 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::killNodes ( )

inline

Definition at line 182 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

EdgeType* OrderedTree< NodeType, EdgeType >::lastEdge ( )

inline

pointer to the last edge

Definition at line 74 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

EdgeType* OrderedTree< NodeType, EdgeType >::lastEdge ( const int u )

inline

Pointer to a node's last edge. Does not check wether the node actually has outgoing edges.

Parameters

u	a node ID (index in the node vector)

Returns: a pointer to u's last outgoing edge

Definition at line 80 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

const EdgeType* OrderedTree< NodeType, EdgeType >::lastEdge ( const int u ) const

inline

const ointer to a node's last edge. Does not check wether the node actually has outgoing edges.

Parameters

u	a node ID (index in the node vector)

Returns: a const pointer to u's last outgoing edge

Definition at line 86 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::mergeChain	(	const int	middleId,
		MergeType &	mergeType
	)

inline

Merge two chained edges like this: a -> b -> c will become a -> b, where b and c are the only children of their parents. Any potential children of c will be attached to b.

Parameters

middleId	the middle node's ID in this merge (b in the example)
mergeType	will be set to the type of the merge performed

Definition at line 279 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::mergeSiblings	(	const EdgeType *	leftEdge,
		const EdgeType *	rightEdge,
		int &	newNode,
		MergeType &	mergeType
	)

inline

Merge two descendants of the same node (i.e., siblings)

Parameters

leftEdge	pointer to the edge leading to the left child
rightEdge	pointer to the edge leading to the right edge
newNode	will hold the ID of the merged node after this function returns
mergeType	will hold the type of the merge that was done after this returns

Definition at line 242 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::nodeId ( const NodeType * node )

inline

Get node ID from pointer

Parameters

node	a node pointer

Returns: the node's ID (index in the node vector)

Definition at line 93 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

template<typename LabelType >

bool OrderedTree< NodeType, EdgeType >::nodesEqual	(	const OrderedTree< NodeType, EdgeType > &	other,
		LabelType &	labels,
		LabelType &	otherLabels,
		const int	nodeId,
		const int	otherNodeId,
		const bool	verbose = `false`
	)		const

inline

Recursive node comparison helper function used by isEqual(). You should not need to use this directly.

Definition at line 322 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::removeEdge	(	const int	from,
		const int	edge,
		const bool	compact = `true`
	)

inline

Remove an edge from the tree

Parameters

from	the edge's tail (source) node
edge	the edge's ID
compact	whether to consolidate 'from's outgoing edges

Definition at line 193 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

void OrderedTree< NodeType, EdgeType >::removeEdgeTo	(	const int	from,
		const int	to,
		const bool	compact = `true`
	)

inline

Remove an edge between to nodes from the tree. Finds and removes the first edge from 'from' to 'to'

Parameters

from	tail (source) node ID
to	head (destination) node ID
compact	wether to consolidate 'from's outgoing edges after removal

Definition at line 226 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

string OrderedTree< NodeType, EdgeType >::shortString ( ) const

inline

A rather compact representation of the tree as a string. Comprises nodes with children or a parent, and valid edges. Format: " ID/(node or edge)"

Definition at line 357 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

string OrderedTree< NodeType, EdgeType >::summary ( ) const

inline

A one-line summary of the tree.

Definition at line 348 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

string OrderedTree< NodeType, EdgeType >::toString ( ) const

inline

String representation of the tree, including all nodes and edges.

Definition at line 373 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

template<typename T , typename Fold , typename Callback >

const T OrderedTree< NodeType, EdgeType >::traverseFoldLeftPostOrder	(	const int	nodeId,
		const Callback &	callback,
		const Fold &	fold,
		const T	initial
	)		const

inline

This does the work for foldLeftPostOrder() and should not be used directly.

Definition at line 559 of file OrderedTree.h.

Friends And Related Function Documentation

template<typename NodeType, typename EdgeType>

std::ostream& operator<<	(	std::ostream &	os,
		const OrderedTree< NodeType, EdgeType > &	tree
	)

friend

Definition at line 386 of file OrderedTree.h.

Member Data Documentation

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::_firstFreeEdge

Definition at line 628 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::_firstFreeNode

Definition at line 627 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::_numEdges

Definition at line 630 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

int OrderedTree< NodeType, EdgeType >::_numNodes

Definition at line 629 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

std::vector<EdgeType> OrderedTree< NodeType, EdgeType >::edges

Definition at line 626 of file OrderedTree.h.

template<typename NodeType, typename EdgeType>

std::vector<NodeType> OrderedTree< NodeType, EdgeType >::nodes

Definition at line 625 of file OrderedTree.h.

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

OrderedTree.h

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Friends

Detailed Description

template<typename NodeType, typename EdgeType> class OrderedTree< NodeType, EdgeType >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<typename NodeType, typename EdgeType>
class OrderedTree< NodeType, EdgeType >