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:
41 AlpsNodePool& operator=(const AlpsNodePool&);
42
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
const AlpsPriorityQueue< AlpsTreeNode * > & getCandidateList() const
Get a constant reference to the priority queue that stores nodes.
Definition: AlpsNodePool.h:140
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
AlpsTreeNode * getBestNode() const
Get the "best" nodes in node pool.
Definition: AlpsNodePool.h:80
void addKnowledge(AlpsKnowledge *node, double priority)
Remove the node with highest priority from the pool and the elite list.
Definition: AlpsNodePool.h:126
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
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
Definition: AlpsNodePool.h:112
bool empty() const
Return true for an empty vector.
void clear()
Remove all elements from the vector.
void setComparison(AlpsSearchStrategy< T > &c)
Set comparison function and resort heap.
const std::vector< T > & getContainer() const
Return a const reference to the container.
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