Alps  1.5.7
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-2019, 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 
38 
39  private:
40  AlpsNodePool(const AlpsNodePool&);
41  AlpsNodePool& operator=(const AlpsNodePool&);
42 
43  AlpsPriorityQueue<AlpsTreeNode*> candidateList_;
44 
45  AlpsSearchType searchStrategy_;
46 
47  public:
49 
50  AlpsNodePool(AlpsSearchType type) : searchStrategy_(type) {}
51 
52  virtual ~AlpsNodePool() {
53  //std::cout << "- delete nodes pool, size = " << getNumKnowledges() << std::endl;
54  if (!candidateList_.empty()) {
55  deleteGuts();
56  }
57  }
58 
60  inline int getNumKnowledges() const { return static_cast<int>
61  (candidateList_.size()); }
62 
64  inline double getBestKnowledgeValue() const {
65  const std::vector<AlpsTreeNode *>& pool=candidateList_.getContainer();
66  int k;
67  int size = static_cast<int> (pool.size());
68  double bestQuality = ALPS_OBJ_MAX;
69  AlpsTreeNode * node = NULL;
70  for (k = 0; k < size; ++k) {
71  node = pool[k];
72  if (node->getQuality() < bestQuality) {
73  bestQuality = node->getQuality();
74  }
75  }
76  return bestQuality;
77  }
78 
80  inline AlpsTreeNode *getBestNode() const {
81  const std::vector<AlpsTreeNode *>& pool=candidateList_.getContainer();
82  int k;
83  int size = static_cast<int> (pool.size());
84  double bestQuality = ALPS_OBJ_MAX;
85  AlpsTreeNode * bestNode = NULL;
86  AlpsTreeNode * node = NULL;
87 
88  if(size > 0){
89  if ((searchStrategy_ == AlpsSearchTypeBestFirst) ||
90  (searchStrategy_ == AlpsSearchTypeBreadthFirst) ||
91  (searchStrategy_ == AlpsSearchTypeHybrid)) {
92  bestNode = pool[0];
93  }
94  else{
95  for (k = 0; k < size; ++k) {
96  node = pool[k];
97  if (node->getQuality() < bestQuality) {
98  bestQuality = node->getQuality();
99  bestNode = node;
100  }
101  }
102  }
103  }
104 
105  return bestNode;
106  }
107 
109  inline bool hasKnowledge() const{ return ! (candidateList_.empty()); }
110 
112  inline std::pair<AlpsKnowledge*, double> getKnowledge() const {
113  return std::make_pair( static_cast<AlpsKnowledge *>
114  (candidateList_.top()),
115  candidateList_.top()->getQuality() );
116  }
117 
119  inline void popKnowledge() {
120  candidateList_.pop();
121  }
122 
126  inline void addKnowledge(AlpsKnowledge* node, double priority) {
127  AlpsTreeNode * nn = dynamic_cast<AlpsTreeNode*>(node);
128  // if(!nn) {
129  //AlpsTreeNode * nonnn = const_cast<AlpsTreeNode*>(nn);
130  candidateList_.push(nn);
131  // }
132  // else
133  // std::cout << "Add node failed\n";
134  // else
135  // throw CoinError();
136  }
137 
140  getCandidateList() const { return candidateList_; }
141 
143  void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>& compare) {
144  candidateList_.setComparison(compare);
145  }
146 
148  void deleteGuts() {
149  std::vector<AlpsTreeNode* > nodeVec = candidateList_.getContainer();
150  std::for_each(nodeVec.begin(), nodeVec.end(), DeletePtrObject());
151  candidateList_.clear();
152  assert(candidateList_.size() == 0);
153 
154  //std::cout << "-- delete nodes in pool" << std::endl;
155  }
156 
158  void clear() {
159  candidateList_.clear();
160  }
161 };
162 
163 #endif
164 
165 
AlpsSearchType
Search Strategies.
Definition: Alps.h:74
@ AlpsSearchTypeHybrid
Definition: Alps.h:79
@ AlpsSearchTypeBestFirst
Definition: Alps.h:75
@ AlpsSearchTypeBreadthFirst
Definition: Alps.h:76
#define ALPS_OBJ_MAX
Definition: Alps.h:145
The abstract base class of any user-defined class that Alps has to know about in order to encode/deco...
Definition: AlpsKnowledge.h:51
Node pool is used to store the nodes to be processed.
Definition: AlpsNodePool.h:37
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > &compare)
Set strategy and resort heap.
Definition: AlpsNodePool.h:143
void popKnowledge()
Remove the node with highest priority from the pool.
Definition: AlpsNodePool.h:119
AlpsNodePool(AlpsSearchType type)
Definition: AlpsNodePool.h:50
virtual ~AlpsNodePool()
Definition: AlpsNodePool.h:52
int getNumKnowledges() const
Query the number of nodes in the node pool.
Definition: AlpsNodePool.h:60
double getBestKnowledgeValue() const
Get the "best value" of the nodes in node pool.
Definition: AlpsNodePool.h:64
void deleteGuts()
Delete all the nodes in the pool and free memory.
Definition: AlpsNodePool.h:148
void addKnowledge(AlpsKnowledge *node, double priority)
Remove the node with highest priority from the pool and the elite list.
Definition: AlpsNodePool.h:126
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
Definition: AlpsNodePool.h:112
AlpsTreeNode * getBestNode() const
Get the "best" nodes in node pool.
Definition: AlpsNodePool.h:80
const AlpsPriorityQueue< AlpsTreeNode * > & getCandidateList() const
Get a constant reference to the priority queue that stores nodes.
Definition: AlpsNodePool.h:140
void clear()
Remove all the nodes in the pool (does not free memory).
Definition: AlpsNodePool.h:158
bool hasKnowledge() const
Check whether there are still nodes in the node pool.
Definition: AlpsNodePool.h:109
bool empty() const
Return true for an empty vector.
const std::vector< T > & getContainer() const
Return a const reference to the container.
void clear()
Remove all elements from the vector.
void setComparison(AlpsSearchStrategy< T > &c)
Set comparison function and resort heap.
size_t size() const
Return the size of the vector.
void pop()
Remove the top element from the heap.
T top() const
Return the top element of the heap.
void push(T x)
Add a element to the heap.
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:218