Minotaur::NodeHeap Class Reference

#include <NodeHeap.h>

Inheritance diagram for Minotaur::NodeHeap:

Collaboration diagram for Minotaur::NodeHeap:

Public Types
enum	Type { Value , Depth }
	Types of ordering.

Public Member Functions
	NodeHeap (Type type)
	Constructor.
virtual	~NodeHeap ()
	Destroy.
virtual bool	isEmpty () const
virtual double	getBestLB () const
virtual UInt	getDeepestLevel () const
	Find the maximum depth of all active nodes. More...
virtual void	pop ()
	Remove the best node from the heap. More...
virtual void	write (std::ostream &out) const
virtual void	push (NodePtr n)
	Add a node to the set of active nodes. More...
virtual void	setType (Type type)
	Set the type of ordering of this heap.
virtual NodePtr	top () const
	Get access to the best node in this heap. More...
virtual size_t	getSize () const
	Get the number of active nodes in the heap. More...
NodePtrIterator	nodesBegin ()
	Get iterator to the first node in the heap.
NodePtrIterator	nodesEnd ()
	Get iterator to the last node in the heap.
Public Member Functions inherited from Minotaur::ActiveNodeStore
	ActiveNodeStore ()
	Default Constructor.
virtual	~ActiveNodeStore ()
	Destroy.
virtual double	getBestLB () const =0
	Find the minimum lower bound of all the active nodes. More...
virtual UInt	getDeepestLevel () const =0
	Find the maximum depth of all active nodes. More...
virtual size_t	getSize () const =0
	Get the number of active nodes. More...
virtual bool	isEmpty () const =0
	Check if there are any active nodes left. More...
virtual void	pop ()=0
	Remove the best node from the store. More...
virtual void	push (NodePtr n)=0
	Add a node to the set of active nodes. More...
virtual NodePtr	top () const =0
	Access to the best candidate for evaluating next. More...
virtual void	write (std::ostream &out) const =0
	Display the active nodes. More...

Detailed Description

When the active nodes of the branch-and-bound tree are not explored in a last-in-first-out (LIFO) order, we store them in a heap. A heap is a binary tree with the properties:

1. Every node has a score higher than each of its children.
2. If a node is the only child of its parent, then it is the last node in the heap.

In order to create a heap, we need to have criteria for comparing nodes. These criteria are determined by the parameter for node-selection-strategy: best bound, best estimate, etc

Member Function Documentation

getBestLB()

double NodeHeap::getBestLB ( ) const

virtual

Find the minimum lower bound of all the active nodes in the heap. If the heap is ordered by best bound, then the root has the minimum value.

Implements Minotaur::ActiveNodeStore.

getDeepestLevel()

UInt NodeHeap::getDeepestLevel ( ) const

virtual

Find the maximum depth of all active nodes.

Implements Minotaur::ActiveNodeStore.

getSize()

virtual size_t Minotaur::NodeHeap::getSize ( ) const

inlinevirtual

Get the number of active nodes in the heap.

Implements Minotaur::ActiveNodeStore.

isEmpty()

virtual bool Minotaur::NodeHeap::isEmpty ( ) const

inlinevirtual

Return true if there are no active nodes in the heap, otherwise return false.

Implements Minotaur::ActiveNodeStore.

pop()

void NodeHeap::pop ( )

virtual

Remove the best node from the heap.

Implements Minotaur::ActiveNodeStore.

push()

void NodeHeap::push ( NodePtr  n )

virtual

Add a node to the set of active nodes.

Implements Minotaur::ActiveNodeStore.

top()

virtual NodePtr Minotaur::NodeHeap::top ( ) const

inlinevirtual

Get access to the best node in this heap.

Implements Minotaur::ActiveNodeStore.

write()

void NodeHeap::write ( std::ostream &  out ) const

virtual

Write in order the node ID and the criteria used to order the heap, e.g. bound value and depth.

Implements Minotaur::ActiveNodeStore.

---

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

• /home/amahajan/tmp/minotaur-test/src/base/NodeHeap.h
• /home/amahajan/tmp/minotaur-test/src/base/NodeHeap.cpp