- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

AlpsNodePool.h
Go to the documentation of this file.
1 /*===========================================================================*
2 * This file is part of the Abstract Library for Parallel Search (ALPS). *
3 * *
4 * ALPS is distributed under the Eclipse Public License as part of the *
5 * COIN-OR repository (http://www.coin-or.org). *
6 * *
7 * Authors: *
8 * *
9 * Yan Xu, Lehigh University *
10 * Ted Ralphs, Lehigh University *
11 * *
12 * Conceptual Design: *
13 * *
14 * Yan Xu, Lehigh University *
15 * Ted Ralphs, Lehigh University *
16 * Laszlo Ladanyi, IBM T.J. Watson Research Center *
17 * Matthew Saltzman, Clemson University *
18 * *
19 * *
20 * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs. *
21 *===========================================================================*/
22
23 #ifndef AlpsNodePool_h_
24 #define AlpsNodePool_h_
25
26 #include <vector>
27
28 #include "AlpsHelperFunctions.h"
29 #include "AlpsPriorityQueue.h"
30 #include "AlpsTreeNode.h"
31 #include "AlpsKnowledgePool.h"
32
33 //#############################################################################
35 //#############################################################################
36
37 class AlpsNodePool : public AlpsKnowledgePool {
38
39 private:
40 AlpsNodePool(const AlpsNodePool&);
41 AlpsNodePool& operator=(const AlpsNodePool&);
42
43 AlpsPriorityQueue<AlpsTreeNode*> candidateList_;
44
45 public:
46 AlpsNodePool() {}
47 virtual ~AlpsNodePool() {
48 //std::cout << "- delete nodes pool, size = " << getNumKnowledges() << std::endl;
49 if (!candidateList_.empty()) {
50 deleteGuts();
51 }
52 }
53
55 inline int getNumKnowledges() const { return static_cast<int> (candidateList_.size()); }
56
58 inline double getBestKnowledgeValue() const {
59 const std::vector<AlpsTreeNode *>& pool=candidateList_.getContainer();
60 int k;
61 int size = static_cast<int> (pool.size());
62 double bestQuality = ALPS_OBJ_MAX;
63 AlpsTreeNode * node = NULL;
64 for (k = 0; k < size; ++k) {
65 node = pool[k];
66 if (node->getQuality() < bestQuality) {
67 bestQuality = node->getQuality();
68 }
69 }
70 return bestQuality;
71 }
72
74 inline AlpsTreeNode *getBestNode() const {
75 const std::vector<AlpsTreeNode *>& pool=candidateList_.getContainer();
76 int k;
77 int size = static_cast<int> (pool.size());
78 double bestQuality = ALPS_OBJ_MAX;
79 AlpsTreeNode * bestNode = NULL;
80 AlpsTreeNode * node = NULL;
81
82 for (k = 0; k < size; ++k) {
83 node = pool[k];
84 if (node->getQuality() < bestQuality) {
85 bestQuality = node->getQuality();
86 bestNode = node;
87 }
88 }
89 return bestNode;
90 }
91
93 inline bool hasKnowledge() const{ return ! (candidateList_.empty()); }
94
96 inline std::pair<AlpsKnowledge*, double> getKnowledge() const {
97 return std::make_pair( static_cast<AlpsKnowledge *>
98 (candidateList_.top()),
99 candidateList_.top()->getQuality() );
100 }
101
103 inline void popKnowledge() {
104 candidateList_.pop();
105 }
106
110 inline void addKnowledge(AlpsKnowledge* node, double priority) {
111 AlpsTreeNode * nn = dynamic_cast<AlpsTreeNode*>(node);
112 // if(!nn) {
113 //AlpsTreeNode * nonnn = const_cast<AlpsTreeNode*>(nn);
114 candidateList_.push(nn);
115 // }
116 // else
117 // std::cout << "Add node failed\n";
118 // else
119 // throw CoinError();
120 }
121
123 inline const AlpsPriorityQueue<AlpsTreeNode*>&
124 getCandidateList() const { return candidateList_; }
125
127 void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>& compare) {
128 candidateList_.setComparison(compare);
129 }
130
132 void deleteGuts() {
133 std::vector<AlpsTreeNode* > nodeVec = candidateList_.getContainer();
134 std::for_each(nodeVec.begin(), nodeVec.end(), DeletePtrObject());
135 candidateList_.clear();
136 assert(candidateList_.size() == 0);
137
138 //std::cout << "-- delete nodes in pool" << std::endl;
139 }
140
142 void clear() {
143 candidateList_.clear();
144 }
145 };
146
147 #endif
148
149
AlpsPriorityQueue< AlpsTreeNode * >
AlpsNodePool::getNumKnowledges
int getNumKnowledges() const
Query the number of nodes in the node pool.
Definition: AlpsNodePool.h:55
AlpsHelperFunctions.h
AlpsNodePool::setNodeSelection
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > &compare)
Set strategy and resort heap.
Definition: AlpsNodePool.h:127
AlpsPriorityQueue::getContainer
const std::vector< T > & getContainer() const
Return a const reference to the container.
Definition: AlpsPriorityQueue.h:50
AlpsNodePool::getKnowledge
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
Definition: AlpsNodePool.h:96
AlpsPriorityQueue::push
void push(T x)
Add a element to the heap.
Definition: AlpsPriorityQueue.h:62
AlpsPriorityQueue::setComparison
void setComparison(AlpsSearchStrategy< T > &c)
Set comparison function and resort heap.
Definition: AlpsPriorityQueue.h:53
AlpsNodePool::operator=
AlpsNodePool & operator=(const AlpsNodePool &)
AlpsPriorityQueue::pop
void pop()
Remove the top element from the heap.
Definition: AlpsPriorityQueue.h:68
AlpsPriorityQueue::empty
bool empty() const
Return true for an empty vector.
Definition: AlpsPriorityQueue.h:74
AlpsNodePool::clear
void clear()
Remove all the nodes in the pool (does not free memory).
Definition: AlpsNodePool.h:142
AlpsPriorityQueue.h
AlpsKnowledgePool.h
AlpsNodePool::getBestKnowledgeValue
double getBestKnowledgeValue() const
Get the &quot;best value&quot; of the nodes in node pool.
Definition: AlpsNodePool.h:58
AlpsNodePool::addKnowledge
void addKnowledge(AlpsKnowledge *node, double priority)
Remove the node with highest priority from the pool and the elite list.
Definition: AlpsNodePool.h:110
AlpsTreeNode
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
AlpsPriorityQueue::size
size_t size() const
Return the size of the vector.
Definition: AlpsPriorityQueue.h:79
AlpsNodePool::popKnowledge
void popKnowledge()
Remove the node with highest priority from the pool.
Definition: AlpsNodePool.h:103
DeletePtrObject
Definition: AlpsHelperFunctions.h:62
ALPS_OBJ_MAX
#define ALPS_OBJ_MAX
Definition: Alps.h:145
AlpsNodePool::getBestNode
AlpsTreeNode * getBestNode() const
Get the &quot;best&quot; nodes in node pool.
Definition: AlpsNodePool.h:74
AlpsKnowledgePool
Definition: AlpsKnowledgePool.h:36
AlpsNodePool::deleteGuts
void deleteGuts()
Delete all the nodes in the pool and free memory.
Definition: AlpsNodePool.h:132
AlpsKnowledge
The abstract base class of any user-defined class that Alps has to know about in order to encode/deco...
Definition: AlpsKnowledge.h:51
AlpsNodePool::~AlpsNodePool
virtual ~AlpsNodePool()
Definition: AlpsNodePool.h:47
AlpsNodePool::candidateList_
AlpsPriorityQueue< AlpsTreeNode * > candidateList_
Definition: AlpsNodePool.h:43
AlpsTreeNode.h
AlpsNodePool
Node pool is used to store the nodes to be processed.
Definition: AlpsNodePool.h:37
AlpsNodePool::hasKnowledge
bool hasKnowledge() const
Check whether there are still nodes in the node pool.
Definition: AlpsNodePool.h:93
AlpsPriorityQueue::clear
void clear()
Remove all elements from the vector.
Definition: AlpsPriorityQueue.h:84
AlpsNodePool::getCandidateList
const AlpsPriorityQueue< AlpsTreeNode * > & getCandidateList() const
Get a constant reference to the priority queue that stores nodes.
Definition: AlpsNodePool.h:124
AlpsPriorityQueue::top
T top() const
Return the top element of the heap.
Definition: AlpsPriorityQueue.h:59
AlpsNodePool::AlpsNodePool
AlpsNodePool()
Definition: AlpsNodePool.h:46
AlpsTreeNode::getQuality
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:222