This class implements a collection trees. More...

#include <Dtrees.h>

Inheritance diagram for grafalgo::Dtrees:

Collaboration diagram for grafalgo::Dtrees:

Classes
struct	PathNodePair
Public Member Functions
	Dtrees (int=100)
	Constructor for Dtrees class.
	~Dtrees ()
	Destructor for Dtrees class.
void	clear ()
	Reinitialize data structure, creating single node trees.
void	resize (int)
	Resize a Dtrees object, discarding old value.
void	expand (int)
	Expand the space available for this ojbect.
void	copyFrom (const Dtrees &)
	Copy another object to this one.
index	findroot (index)
	Return the root of a tree.
NodeCostPair	findcost (path)
	Find the last min cost node on the path to the root.
void	addcost (index, cost)
	Add to the cost of every node on the path from a node to its tree root.
void	link (tree, index)
	Link two trees.
void	cut (index)
	Divide a tree into two subtrees.
cost	nodeCost (index) const
	Get the cost of a node.
index	parent (index) const
	Get the parent of a node.
string &	path2string (path, string &) const
	Create a string representing a path.
string &	toString (string &) const
	Create a string representing all the trees in this Dtrees object.
Private Member Functions
path	expose (index)
	Expose a path in a tree.
PathNodePair	splice (PathNodePair)
	Combine two path segments.
void	makeSpace (int)
	Allocate and initialize space for Dtrees.
void	freeSpace ()
	Free dynamic storage used by Dtrees.
Private Attributes
index *	parentOf
	parentOf[i] is logical parent of i
index *	successor
	successor[i] is link to next path
PathSet *	ps
	underlying path set data structure

Detailed Description

This class implements a collection trees.

The trees are defined on nodes with node numbers 1..n where n is specified when the object is constructed. Each node is in one tree at a time. Each node has an integer cost and methods are provided for restructuring trees and manipulating costs

Definition at line 28 of file Dtrees.h.

Constructor & Destructor Documentation

grafalgo::Dtrees::Dtrees ( int size = 100 )

Constructor for Dtrees class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 18 of file Dtrees.cpp.

Here is the call graph for this function:

grafalgo::Dtrees::~Dtrees ( )

Destructor for Dtrees class.

Definition at line 23 of file Dtrees.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::Dtrees::addcost	(	index	i,
		cost	x
	)

Add to the cost of every node on the path from a node to its tree root.

Parameters:

i	is a node in some tree
x	is an increment to be added to the costs of the nodes on the path from i to the tree root

Definition at line 147 of file Dtrees.cpp.

Here is the call graph for this function:

void grafalgo::Dtrees::clear ( ) [virtual]

Reinitialize data structure, creating single node trees.

Implements grafalgo::Adt.

Definition at line 49 of file Dtrees.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Dtrees::copyFrom ( const Dtrees & source )

Copy another object to this one.

Parameters:

source is object to be copied to this one

Definition at line 79 of file Dtrees.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Dtrees::cut ( index i )

Divide a tree into two subtrees.

Parameters:

i	is a node in some tree. The operation removes the edge from i to its parent.

Definition at line 166 of file Dtrees.cpp.

Here is the call graph for this function:

void grafalgo::Dtrees::expand ( int size ) [virtual]

Expand the space available for this ojbect.

Rebuilds old value in new space.

Parameters:

size	is the size of the expanded object.

Implements grafalgo::Adt.

Definition at line 71 of file Dtrees.cpp.

Here is the call graph for this function:

path grafalgo::Dtrees::expose ( index i ) [private]

Expose a path in a tree.

Parameters:

i is a node

Returns:: a path from i to the root of the tree Restructures underlying path set, so the path from i to the root is a single path.

Definition at line 97 of file Dtrees.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

NodeCostPair grafalgo::Dtrees::findcost ( path )

Find the last min cost node on the path to the root.

Parameters:

i	is a node in some tree

Returns:: a pair consisting of the last min cost node on the path from i to the root and its cost

Definition at line 136 of file Dtrees.cpp.

Here is the call graph for this function:

index grafalgo::Dtrees::findroot ( index i )

Return the root of a tree.

Parameters:

i	is a node in some tree

Returns:: the root of the tree containing i

Definition at line 124 of file Dtrees.cpp.

Here is the call graph for this function:

void grafalgo::Dtrees::freeSpace ( ) [private]

Free dynamic storage used by Dtrees.

Definition at line 44 of file Dtrees.cpp.

Here is the caller graph for this function:

void grafalgo::Dtrees::link	(	tree	t,
		index	i
	)

Link two trees.

Parameters:

t	is the root of some tree
i	is a node in some other tree the tree t to the tree containing i at i. This operation makes i the parent of t.

Definition at line 157 of file Dtrees.cpp.

Here is the call graph for this function:

void grafalgo::Dtrees::makeSpace ( int size ) [private]

Allocate and initialize space for Dtrees.

Parameters:

size	is number of index values to provide space for

Definition at line 28 of file Dtrees.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

cost grafalgo::Dtrees::nodeCost ( index i ) const [inline]

Get the cost of a node.

Parameters:

i	is a node in a tree

Returns:: the cost of i

Definition at line 75 of file Dtrees.h.

Here is the call graph for this function:

index grafalgo::Dtrees::parent ( index i ) const [inline]

Get the parent of a node.

Parameters:

i	is a node in a tree

Returns:: the parent of i or 0 if i is at tree root

Definition at line 69 of file Dtrees.h.

string & grafalgo::Dtrees::path2string	(	path	q,
		string &	s
	)		const

Create a string representing a path.

Parameters:

q	is a path in some tree
s	is a string in which the result is returned

Returns:: a reference to s

Definition at line 180 of file Dtrees.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Dtrees::resize ( int size ) [virtual]

Resize a Dtrees object, discarding old value.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 59 of file Dtrees.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Dtrees::PathNodePair grafalgo::Dtrees::splice ( PathNodePair pnPair ) [private]

Combine two path segments.

Splice is a private method used by the expose method.

Parameters:

pnPair is a pair containing a path .p and its successor .i

Returns:: a new pnPair that can be used in next step of expose operation The operation splits the path containing i and then joins p to the last part of the path originally containing i, effectively extending p furtrher up the tree.

Definition at line 112 of file Dtrees.cpp.

Here is the call graph for this function: