AlpsSubTree Class Reference

This class contains the data pertaining to a particular subtree in the search tree. More...

#include <AlpsSubTree.h>

Inheritance diagram for AlpsSubTree:

[legend]

Collaboration diagram for AlpsSubTree:

[legend]

List of all members.

Public Member Functions
	AlpsSubTree ()
	Default constructor.
	AlpsSubTree (AlpsKnowledgeBroker *kb)
	Useful constructor.
virtual	~AlpsSubTree ()
	Destructor.
AlpsTreeNode *	activeNode ()
	Get pointer to active node.
void	setActiveNode (AlpsTreeNode *activeNode)
	Set pointer to active node.
void	createChildren (AlpsTreeNode parent, std::vector< CoinTriple< AlpsNodeDesc , AlpsNodeStatus, double > > &children, AlpsNodePool *kidNodePool=NULL)
	Create children nodes from the given parent node.
AlpsSubTree *	splitSubTree (int &returnSize, int size=10)
	The function split the subtree and return a subtree of the specified size or available size.
virtual AlpsReturnStatus	exploreSubTree (AlpsTreeNode *root, int nodeLimit, double timeLimit, int &numNodesProcesse, int &depth)
	Explore the subtree from `root` as the root of the subtree for given number of nodes or time, depending on which one reach first.
AlpsReturnStatus	exploreUnitWork (bool leaveAsIt, int unitWork, double unitTime, AlpsExitStatus &solStatus, int &numNodesProcessed, int &depth, bool &betterSolution)
	Explore the subtree for certain amount of work/time.
virtual int	rampUp (int minNumNodes, int requiredNumNodes, int &depth, AlpsTreeNode *root=NULL)
	Generate required number (specified by a parameter) of nodes.
virtual AlpsEncoded *	encode () const
	This method should encode the content of the subtree and return a pointer to the encoded form.
virtual AlpsKnowledge *	decode (AlpsEncoded &encoded) const
	This method should decode and return a pointer to a brand new object, i.e., the method must create a new object on the heap from the decoded data instead of filling up the object for which the method was invoked.
virtual AlpsSubTree *	newSubTree () const
	Create a AlpsSubtree object dynamically.
void	clearNodePools ()
	Remove nodes in pools in the subtree.
void	nullRootActiveNode ()
	Set root and active node to null.
void	reset ()
	Move nodes in node pool, null active node.
query and set member functions

AlpsTreeNode *	getRoot () const
	Get the root node of this subtree.
void	setRoot (AlpsTreeNode *r)
	Set the root node of this subtree.
AlpsNodePool *	nodePool ()
	Access the node pool.
AlpsNodePool *	diveNodePool ()
	Access the node pool.
void	setNodePool (AlpsNodePool *np)
	Set node pool.
void	changeNodePool (AlpsNodePool *np)
	Set node pool.
double	getBestKnowledgeValue () const
	Get the quality of the best node in the subtree.
AlpsTreeNode *	getBestNode () const
	Get the "best" node in the subtree.
AlpsKnowledgeBroker *	getKnowledgeBroker () const
	Get the knowledge broker.
void	setKnowledgeBroker (AlpsKnowledgeBroker *kb)
	Set a pointer to the knowledge broker.
double	getQuality () const
	Get the quality of this subtree.
double	getSolEstimate () const
	Get the emtimated quality of this subtree.
void	incDiveDepth (int num=1)
	Increment dive depth.
int	getDiveDepth ()
	Get dive depth.
void	setDiveDepth (int num)
	Set dive depth.
double	calculateQuality ()
	Calcuate and return the quality of this subtree, which is measured by the quality of the specified number of nodes.
int	nextIndex ()
	Get the root node of this subtree.
int	getNextIndex () const
	Get the index of the next generated node.
void	setNextIndex (int next)
	Set the index of the next generated node.
int	getNumNodes () const
	Return the number of nodes on this subtree.
void	setNodeSelection (AlpsSearchStrategy< AlpsTreeNode * > *nc)
	Set the node comparision rule.
Protected Member Functions
void	removeDeadNodes (AlpsTreeNode *&node)
	The purpose of this method is to remove nodes that are not needed in the description of the subtree.
void	replaceNode (AlpsTreeNode oldNode, AlpsTreeNode newNode)
	This function replaces `oldNode` with `newNode` in the tree.
Protected Attributes
AlpsTreeNode *	root_
	The root of the sub tree.
AlpsNodePool *	nodePool_
	A node pool containing the leaf nodes awaiting processing.
AlpsNodePool *	diveNodePool_
	A node pool used when diving.
AlpsSearchStrategy < AlpsTreeNode * > *	diveNodeRule_
	Diving node comparing rule.
int	diveDepth_
	Diving depth.
AlpsTreeNode *	activeNode_
	The next index to be assigned to a new search tree node.
double	quality_
	A quantity indicating how good this subtree is.
AlpsKnowledgeBroker *	broker_
	A pointer to the knowledge broker of the process where this subtree is processed.

Detailed Description

This class contains the data pertaining to a particular subtree in the search tree.

In order to improve scalability, we will try to deal with entire subtrees as much as possible. They will be the basic unit of work that will be passed between processes.

Definition at line 47 of file AlpsSubTree.h.

Constructor & Destructor Documentation

AlpsSubTree::AlpsSubTree ( )

Default constructor.

AlpsSubTree::AlpsSubTree ( AlpsKnowledgeBroker * kb )

Useful constructor.

virtual AlpsSubTree::~AlpsSubTree ( ) [virtual]

Destructor.

Member Function Documentation

void AlpsSubTree::removeDeadNodes ( AlpsTreeNode *& node ) [protected]

The purpose of this method is to remove nodes that are not needed in the description of the subtree.

The argument node must have status fathomed. First, the argument node is removed, and then the parent is examined to determine whether it has any children left. If it has none, then this function is called recursively on the parent. This removes all nodes that are no longer needed.

void AlpsSubTree::replaceNode	(	AlpsTreeNode *	oldNode,
		AlpsTreeNode *	newNode
	)			`[protected]`

This function replaces oldNode with newNode in the tree.

AlpsTreeNode* AlpsSubTree::activeNode ( ) [inline]

Get pointer to active node.

Definition at line 108 of file AlpsSubTree.h.

void AlpsSubTree::setActiveNode ( AlpsTreeNode * activeNode ) [inline]

Set pointer to active node.

Definition at line 111 of file AlpsSubTree.h.

void AlpsSubTree::createChildren	(	AlpsTreeNode *	parent,
		std::vector< CoinTriple< AlpsNodeDesc *, AlpsNodeStatus, double > > &	children,
		AlpsNodePool *	kidNodePool = `NULL`
	)

Create children nodes from the given parent node.

AlpsTreeNode* AlpsSubTree::getRoot ( ) const [inline]

Get the root node of this subtree.

Definition at line 124 of file AlpsSubTree.h.

void AlpsSubTree::setRoot ( AlpsTreeNode * r ) [inline]

Set the root node of this subtree.

Definition at line 127 of file AlpsSubTree.h.

AlpsNodePool* AlpsSubTree::nodePool ( ) [inline]

Access the node pool.

Definition at line 130 of file AlpsSubTree.h.

AlpsNodePool* AlpsSubTree::diveNodePool ( ) [inline]

Access the node pool.

Definition at line 133 of file AlpsSubTree.h.

void AlpsSubTree::setNodePool ( AlpsNodePool * np ) [inline]

Set node pool.

Delete previous node pool and nodes in pool if exit.

Definition at line 136 of file AlpsSubTree.h.

void AlpsSubTree::changeNodePool ( AlpsNodePool * np ) [inline]

Set node pool.

Delete previous node pool, but not the nodes in pool.

Definition at line 145 of file AlpsSubTree.h.

double AlpsSubTree::getBestKnowledgeValue ( ) const

Get the quality of the best node in the subtree.

AlpsTreeNode* AlpsSubTree::getBestNode ( ) const

Get the "best" node in the subtree.

AlpsKnowledgeBroker* AlpsSubTree::getKnowledgeBroker ( ) const [inline]

Get the knowledge broker.

Definition at line 164 of file AlpsSubTree.h.

void AlpsSubTree::setKnowledgeBroker ( AlpsKnowledgeBroker * kb ) [inline]

Set a pointer to the knowledge broker.

Definition at line 167 of file AlpsSubTree.h.

double AlpsSubTree::getQuality ( ) const [inline]

Get the quality of this subtree.

Definition at line 173 of file AlpsSubTree.h.

double AlpsSubTree::getSolEstimate ( ) const [inline]

Get the emtimated quality of this subtree.

Definition at line 176 of file AlpsSubTree.h.

void AlpsSubTree::incDiveDepth ( int num = 1 ) [inline]

Increment dive depth.

Definition at line 186 of file AlpsSubTree.h.

int AlpsSubTree::getDiveDepth ( ) [inline]

Get dive depth.

Definition at line 189 of file AlpsSubTree.h.

void AlpsSubTree::setDiveDepth ( int num ) [inline]

Set dive depth.

Definition at line 192 of file AlpsSubTree.h.

double AlpsSubTree::calculateQuality ( )

Calcuate and return the quality of this subtree, which is measured by the quality of the specified number of nodes.

int AlpsSubTree::nextIndex ( )

Get the root node of this subtree.

int AlpsSubTree::getNextIndex ( ) const

Get the index of the next generated node.

void AlpsSubTree::setNextIndex ( int next )

Set the index of the next generated node.

int AlpsSubTree::getNumNodes ( ) const [inline]

Return the number of nodes on this subtree.

Definition at line 209 of file AlpsSubTree.h.

void AlpsSubTree::setNodeSelection ( AlpsSearchStrategy< AlpsTreeNode * > * nc ) [inline]

Set the node comparision rule.

Definition at line 223 of file AlpsSubTree.h.

AlpsSubTree* AlpsSubTree::splitSubTree	(	int &	returnSize,
		int	size = `10`
	)

The function split the subtree and return a subtree of the specified size or available size.

virtual AlpsReturnStatus AlpsSubTree::exploreSubTree	(	AlpsTreeNode *	root,
		int	nodeLimit,
		double	timeLimit,
		int &	numNodesProcesse,
		int &	depth
	)			`[virtual]`

Explore the subtree from root as the root of the subtree for given number of nodes or time, depending on which one reach first.

Only for serial code.

AlpsReturnStatus AlpsSubTree::exploreUnitWork	(	bool	leaveAsIt,
		int	unitWork,
		double	unitTime,
		AlpsExitStatus &	solStatus,
		int &	numNodesProcessed,
		int &	depth,
		bool &	betterSolution
	)

Explore the subtree for certain amount of work/time.

leaveAsIt means exit immediately after reseach limits: do not put activeNode_ in pool, do not move nodes in divePool_ in regular pool.

virtual int AlpsSubTree::rampUp	(	int	minNumNodes,
		int	requiredNumNodes,
		int &	depth,
		AlpsTreeNode *	root = `NULL`
	)			`[virtual]`

Generate required number (specified by a parameter) of nodes.

This function is used by master and hubs.

virtual AlpsEncoded* AlpsSubTree::encode ( ) const [virtual]

This method should encode the content of the subtree and return a pointer to the encoded form.

Only parallel code need this function.

Reimplemented from AlpsKnowledge.

virtual AlpsKnowledge* AlpsSubTree::decode ( AlpsEncoded & encoded ) const [virtual]

This method should decode and return a pointer to a brand new object, i.e., the method must create a new object on the heap from the decoded data instead of filling up the object for which the method was invoked.

Only parallel code need this function.

Reimplemented from AlpsKnowledge.

virtual AlpsSubTree* AlpsSubTree::newSubTree ( ) const [inline, virtual]

Create a AlpsSubtree object dynamically.

Only parallel code need this function.

Definition at line 274 of file AlpsSubTree.h.

void AlpsSubTree::clearNodePools ( ) [inline]

Remove nodes in pools in the subtree.

Do not free memory.

Definition at line 279 of file AlpsSubTree.h.

void AlpsSubTree::nullRootActiveNode ( ) [inline]

Set root and active node to null.