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

- File List
- File Members

AlpsTreeNode.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 AlpsTreeNode_h_
24 #define AlpsTreeNode_h_
25
26 #include <algorithm>
27 #include <utility>
28 #include <vector>
29
30 #include "CoinError.hpp"
31 #include "CoinSort.hpp"
32
33 #include "Alps.h"
34 #include "AlpsKnowledge.h"
35 #include "AlpsNodeDesc.h"
36
37 typedef int AlpsNodeIndex_t;
38
39 class AlpsKnowledgeBroker;
40 class AlpsSubTree;
41
42 //#############################################################################
48 //#############################################################################
49
50 class AlpsTreeNode : public AlpsKnowledge {
51 private:
52 AlpsTreeNode(const AlpsTreeNode&);
53 AlpsTreeNode& operator=(const AlpsTreeNode&);
54
55 protected:
57 //AlpsSubTree* subTree_;
58
60 bool active_;
61
63 AlpsNodeIndex_t index_;
64
66 int depth_;
67
69 double solEstimate_;
70
72 double quality_;
73
75 AlpsTreeNode* parent_;
76
78 AlpsNodeIndex_t parentIndex_;
79
81 int numChildren_;
82
83 #if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?
84
85 AlpsTreeNode* children_[ALPS_MAX_CHILD_NUM];
86 #else
87 AlpsTreeNode** children_;
88 #endif
89
92 int explicit_;
93
95 AlpsNodeDesc* desc_;
96
98 AlpsNodeStatus status_;
99
102 // Need broker to get incumbent value and add solution when process().
103 AlpsKnowledgeBroker* knowledgeBroker_;
104
106 // 0: default; 1: in subtree to be sent: 2: in subtree's node pool
107 int sentMark_;
108
110 bool diving_;
111
112 public:
113 AlpsTreeNode()
114 :
115 active_(false),
116 index_(-1),
117 depth_(-1),
118 solEstimate_(ALPS_OBJ_MAX),
119 quality_(ALPS_OBJ_MAX), // Smaller than default incumbentValue
120 parent_(0),
121 parentIndex_(-1),
122 numChildren_(0),
123 #if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?
124 // AlpsTreeNode* children_[ALPS_MAX_CHILD_NUM];
125 #else
126 children_(0),
127 #endif
128 explicit_(0),
129 desc_(0),
130 status_(AlpsNodeStatusCandidate),
131 knowledgeBroker_(0),
132 sentMark_(0),
133 diving_(false)
134 { setType(AlpsKnowledgeTypeNode); }
135
136 virtual ~AlpsTreeNode() {
137 assert(numChildren_ == 0);
138 //std::cout << "---- delete Alps part of node " << index_ << std::endl;
139 #if ! defined(ALPS_MAX_CHILD_NUM)
140 if (children_ != 0) {
141 delete [] children_;
142 children_ = 0;
143 }
144 #endif
145 if (desc_ != 0) {
146 delete desc_;
147 desc_ = 0;
148 }
149 }
150
151 bool operator<(const AlpsTreeNode& compNode)
152 { return quality_ < compNode.getQuality(); }
153
155 AlpsNodeDesc* modifyDesc() { return desc_; }
156 AlpsNodeDesc* getDesc() const { return desc_; }
157 void setDesc(AlpsNodeDesc* desc) { desc_ = desc; }
158
160 inline AlpsKnowledgeBroker* getKnowledgeBroker() const
161 { return knowledgeBroker_; }
162 inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb)
163 { knowledgeBroker_ = kb; }
164
167 /* FIXME: I think that we probably want the argument to be a diff'd
168 description, but this is open to debate. Maybe we should
169 overload this method and have a version that creates a diff'd
170 description, as well as one that creates an explicit
171 description. */
172 virtual AlpsTreeNode* createNewTreeNode(AlpsNodeDesc*& desc) const = 0;
173
175 inline AlpsNodeStatus getStatus() const { return status_; }
177 inline void setStatus(const AlpsNodeStatus stat) { status_ = stat; }
179
181 inline bool isCandidate() const {
183 return status_ == AlpsNodeStatusCandidate; }
184 inline bool isEvaluated() const {
185 return status_ == AlpsNodeStatusEvaluated; }
186 inline bool isPregnant() const {
187 return status_ == AlpsNodeStatusPregnant; }
188 inline bool isBranched() const {
189 return status_ == AlpsNodeStatusBranched; }
190 inline bool isFathomed() const {
191 return status_ == AlpsNodeStatusFathomed; }
192 inline bool isDiscarded() const {
193 return status_ == AlpsNodeStatusDiscarded; }
195
197 inline bool isActive() const { return active_; }
199 inline void setActive(const bool yesno) { active_ = yesno; }
201
203 inline AlpsNodeIndex_t getIndex() const { return index_; }
205 inline void setIndex(const AlpsNodeIndex_t index) { index_ = index; }
207
209 inline int getDepth() const { return depth_; }
211 inline void setDepth(const int depth) { depth_ = depth; }
213
215 inline double getSolEstimate() const { return solEstimate_; }
217 inline void setSolEstimate(double est) { solEstimate_ = est; }
219
221 inline double getQuality() const { return quality_; }
223 inline void setQuality(double quality) { quality_ = quality; }
225
227 inline int getNumChildren() const { return numChildren_; }
229 inline void setNumChildren(const int numChildren) {
230 numChildren_ = numChildren;
231 #if ! defined(ALPS_MAX_CHILD_NUM)
232 if (children_ != 0) {
233 delete [] children_;
234 children_ = 0;
235 }
236 children_ = new AlpsTreeNode*[numChildren_];
237 #endif
238 }
239 // Change by s
240 inline void modifyNumChildren(const int s) { numChildren_ += s; }
242
243 // *FIXME* : Sanity check. Maybe we should check that the argument is in
244 // the correct range, but how do we do that? This makes the code
245 // inefficient so it should be done with #ifdefs so it can be compiled
246 // out. But in that case, we should move this code to the implementation
247 // file and it won't get inlined anymore.
248
250 inline AlpsTreeNode* getChild(const int i) const { return children_[i]; }
252
253 //FIXME: Compiler complains about this second declaration. Not sure how to
254 //declare a const and a non-const version of a function with the same
255 //arguments...
256 // /** Returns a const pointer to the ith child. */
257 // const AlpsTreeNode* getChild(const int i) const { return children_[i]; }
258 inline void setChild(const int i, AlpsTreeNode* node)
259 { children_[i] = node; }
261
265 void removeChild(AlpsTreeNode*& child);
266
268 void addChild(AlpsTreeNode*& child);
269
273 void removeDescendants();
274
276 //inline AlpsSubTree* getSubTree() const { return subTree_; }
277 //inline void setSubTree(AlpsSubTree* tree) { subTree_ = tree; }
278
280 inline AlpsTreeNode* getParent() const { return parent_; }
282 inline void setParent(AlpsTreeNode* parent) { parent_ = parent; }
284
286 inline AlpsNodeIndex_t getParentIndex() const { return parentIndex_; }
288 inline void setParentIndex(AlpsNodeIndex_t index)
289 { parentIndex_ = index; }
291
294 inline int getExplicit() const { return explicit_; }
296 inline void setExplicit(int fp) { explicit_ = fp; }
298
300 virtual void convertToExplicit() {}
302 virtual void convertToRelative() {}
304
306 inline int getDiving() const { return diving_; }
308 inline void setDiving(const bool d) { diving_ = d; }
310
312 inline int getSentMark() const { return sentMark_; }
314 inline void setSentMark(const int tf) { sentMark_ = tf; }
316
346 virtual int process(bool isRoot = false, bool rampUp = false) = 0;
347
357 virtual std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, double> >
358 branch() = 0;
359
360 protected:
361
363 AlpsReturnStatus encodeAlps(AlpsEncoded *encoded) const;
364
366 AlpsReturnStatus decodeAlps(AlpsEncoded &encoded);
367
368 };
369 #endif
AlpsTreeNode::addChild
void addChild(AlpsTreeNode *&child)
Add a child to the list of children for this node.
AlpsTreeNode::setActive
void setActive(const bool yesno)
Query/set node in-process indicator.
Definition: AlpsTreeNode.h:199
AlpsKnowledgeBroker
The base class of knowledge broker class.
Definition: AlpsKnowledgeBroker.h:48
AlpsTreeNode::getDiving
int getDiving() const
If the this node is in a diving process.
Definition: AlpsTreeNode.h:307
AlpsTreeNode::isDiscarded
bool isDiscarded() const
Query functions about specific stati.
Definition: AlpsTreeNode.h:192
AlpsNodeDesc.h
AlpsTreeNode::getExplicit
int getExplicit() const
Get/set the indication of whether the node has full or differencing description.
Definition: AlpsTreeNode.h:295
AlpsTreeNode::explicit_
int explicit_
Indicate whether the node description is explicit(1) or relative(0).
Definition: AlpsTreeNode.h:92
AlpsTreeNode::getDesc
AlpsNodeDesc * getDesc() const
Definition: AlpsTreeNode.h:156
AlpsTreeNode::index_
AlpsNodeIndex_t index_
The unique index of the tree node (across the whole search tree).
Definition: AlpsTreeNode.h:63
AlpsTreeNode::getSolEstimate
double getSolEstimate() const
Query/set the solution estimate of the node.
Definition: AlpsTreeNode.h:216
AlpsTreeNode::isEvaluated
bool isEvaluated() const
Query functions about specific stati.
Definition: AlpsTreeNode.h:184
AlpsTreeNode::solEstimate_
double solEstimate_
The solution estimate.
Definition: AlpsTreeNode.h:69
AlpsNodeStatusPregnant
Definition: Alps.h:64
AlpsReturnStatus
AlpsReturnStatus
Definition: Alps.h:118
AlpsTreeNode::getParentIndex
AlpsNodeIndex_t getParentIndex() const
Get/set the index of the parent of the node.
Definition: AlpsTreeNode.h:287
AlpsTreeNode::setNumChildren
void setNumChildren(const int numChildren)
Query/set what the number of children.
Definition: AlpsTreeNode.h:229
CoinError.hpp
AlpsNodeStatusBranched
Definition: Alps.h:65
AlpsNodeStatus
AlpsNodeStatus
The possible stati for the search nodes.
Definition: Alps.h:61
AlpsTreeNode::setChild
void setChild(const int i, AlpsTreeNode *node)
Returns a const pointer to the ith child.
Definition: AlpsTreeNode.h:258
AlpsTreeNode::knowledgeBroker_
AlpsKnowledgeBroker * knowledgeBroker_
A pointer to the knowledge broker of the process where this node is processed.
Definition: AlpsTreeNode.h:103
AlpsTreeNode::setParent
void setParent(AlpsTreeNode *parent)
Get/set subtree.
Definition: AlpsTreeNode.h:282
AlpsTreeNode::operator=
AlpsTreeNode & operator=(const AlpsTreeNode &)
AlpsTreeNode::parentIndex_
AlpsNodeIndex_t parentIndex_
The index of parent of the tree node.
Definition: AlpsTreeNode.h:78
AlpsTreeNode::modifyDesc
AlpsNodeDesc * modifyDesc()
Access the desc so that can modify it.
Definition: AlpsTreeNode.h:155
AlpsSubTree
This class contains the data pertaining to a particular subtree in the search tree.
Definition: AlpsSubTree.h:47
AlpsTreeNode::operator<
bool operator<(const AlpsTreeNode &compNode)
Definition: AlpsTreeNode.h:151
AlpsNodeStatusCandidate
Definition: Alps.h:62
AlpsTreeNode::getKnowledgeBroker
AlpsKnowledgeBroker * getKnowledgeBroker() const
Functions to access/set the knwoledge broker.
Definition: AlpsTreeNode.h:160
AlpsNodeStatusEvaluated
Definition: Alps.h:63
AlpsTreeNode::setQuality
void setQuality(double quality)
Query/set the quality of the node.
Definition: AlpsTreeNode.h:223
AlpsNodeStatusFathomed
Definition: Alps.h:66
AlpsTreeNode::isBranched
bool isBranched() const
Query functions about specific stati.
Definition: AlpsTreeNode.h:188
AlpsTreeNode::isPregnant
bool isPregnant() const
Query functions about specific stati.
Definition: AlpsTreeNode.h:186
AlpsTreeNode::convertToExplicit
virtual void convertToExplicit()
Convert explicit description to difference, and vise-vesa.
Definition: AlpsTreeNode.h:301
AlpsEncoded
This data structure is to contain the packed form of an encodable knowledge.
Definition: AlpsEncoded.h:25
AlpsTreeNode::removeDescendants
void removeDescendants()
Removes all the descendants of the node.
AlpsTreeNode::getNumChildren
int getNumChildren() const
Query/set what the number of children.
Definition: AlpsTreeNode.h:228
AlpsTreeNode::setSolEstimate
void setSolEstimate(double est)
Query/set the solution estimate of the node.
Definition: AlpsTreeNode.h:217
Alps.h
AlpsTreeNode::getChild
AlpsTreeNode * getChild(const int i) const
Query/set pointer to the ith child.
Definition: AlpsTreeNode.h:251
AlpsNodeStatusDiscarded
Definition: Alps.h:67
AlpsTreeNode::setStatus
void setStatus(const AlpsNodeStatus stat)
Query/set the current status.
Definition: AlpsTreeNode.h:177
AlpsTreeNode::getSentMark
int getSentMark() const
Various marks used in parallel code.
Definition: AlpsTreeNode.h:313
AlpsTreeNode::modifyNumChildren
void modifyNumChildren(const int s)
Query/set what the number of children.
Definition: AlpsTreeNode.h:240
AlpsTreeNode
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
AlpsTreeNode::AlpsTreeNode
AlpsTreeNode()
Definition: AlpsTreeNode.h:113
AlpsTreeNode::diving_
bool diving_
When processing it, if it is in the diving processing.
Definition: AlpsTreeNode.h:110
ALPS_OBJ_MAX
#define ALPS_OBJ_MAX
Definition: Alps.h:145
AlpsTreeNode::createNewTreeNode
virtual AlpsTreeNode * createNewTreeNode(AlpsNodeDesc *&desc) const =0
The purpose of this function is be able to create the children of a node after branching.
AlpsKnowledgeTypeNode
Definition: Alps.h:91
AlpsTreeNode::sentMark_
int sentMark_
Various mark used in splitting and passing subtrees.
Definition: AlpsTreeNode.h:107
AlpsKnowledge.h
AlpsNodeIndex_t
int AlpsNodeIndex_t
Definition: AlpsTreeNode.h:37
AlpsTreeNode::setDiving
void setDiving(const bool d)
If the this node is in a diving process.
Definition: AlpsTreeNode.h:308
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
AlpsTreeNode::quality_
double quality_
The quality of this node.
Definition: AlpsTreeNode.h:72
AlpsTreeNode::~AlpsTreeNode
virtual ~AlpsTreeNode()
Definition: AlpsTreeNode.h:136
AlpsTreeNode::setDesc
void setDesc(AlpsNodeDesc *desc)
Definition: AlpsTreeNode.h:157
AlpsTreeNode::parent_
AlpsTreeNode * parent_
The parent of the tree node.
Definition: AlpsTreeNode.h:75
CoinSort.hpp
AlpsTreeNode::getStatus
AlpsNodeStatus getStatus() const
Query/set the current status.
Definition: AlpsTreeNode.h:176
AlpsTreeNode::children_
AlpsTreeNode ** children_
Definition: AlpsTreeNode.h:87
AlpsTreeNode::setIndex
void setIndex(const AlpsNodeIndex_t index)
Query/set node identifier (unique within subtree).
Definition: AlpsTreeNode.h:205
AlpsTreeNode::setParentIndex
void setParentIndex(AlpsNodeIndex_t index)
Get/set the index of the parent of the node.
Definition: AlpsTreeNode.h:288
AlpsTreeNode::isActive
bool isActive() const
Query/set node in-process indicator.
Definition: AlpsTreeNode.h:198
AlpsTreeNode::getDepth
int getDepth() const
Query/set what depth the search tree node is at.
Definition: AlpsTreeNode.h:210
AlpsTreeNode::numChildren_
int numChildren_
The number of children.
Definition: AlpsTreeNode.h:81
AlpsTreeNode::getParent
AlpsTreeNode * getParent() const
Get/set subtree.
Definition: AlpsTreeNode.h:281
AlpsTreeNode::active_
bool active_
The subtree own this node.
Definition: AlpsTreeNode.h:60
AlpsTreeNode::removeChild
void removeChild(AlpsTreeNode *&child)
Remove the pointer to given child from the list of children.
AlpsTreeNode::getIndex
AlpsNodeIndex_t getIndex() const
Query/set node identifier (unique within subtree).
Definition: AlpsTreeNode.h:204
AlpsTreeNode::status_
AlpsNodeStatus status_
The current status of the node.
Definition: AlpsTreeNode.h:98
AlpsTreeNode::isFathomed
bool isFathomed() const
Query functions about specific stati.
Definition: AlpsTreeNode.h:190
AlpsTreeNode::depth_
int depth_
The depth of the node (in the whole tree – the root is at depth 0).
Definition: AlpsTreeNode.h:66
AlpsTreeNode::convertToRelative
virtual void convertToRelative()
Convert explicit description to difference, and vise-vesa.
Definition: AlpsTreeNode.h:302
AlpsTreeNode::setDepth
void setDepth(const int depth)
Query/set what depth the search tree node is at.
Definition: AlpsTreeNode.h:211
AlpsTreeNode::setSentMark
void setSentMark(const int tf)
Various marks used in parallel code.
Definition: AlpsTreeNode.h:314
AlpsTreeNode::setKnowledgeBroker
void setKnowledgeBroker(AlpsKnowledgeBroker *kb)
Definition: AlpsTreeNode.h:162
AlpsNodeDesc
A class to refer to the description of a search tree node.
Definition: AlpsNodeDesc.h:35
AlpsTreeNode::isCandidate
bool isCandidate() const
Query functions about specific stati.
Definition: AlpsTreeNode.h:182
AlpsTreeNode::desc_
AlpsNodeDesc * desc_
The actual description of the tree node.
Definition: AlpsTreeNode.h:95
AlpsTreeNode::setExplicit
void setExplicit(int fp)
Get/set the indication of whether the node has full or differencing description.
Definition: AlpsTreeNode.h:296
AlpsKnowledge::setType
void setType(KnowledgeType t)
Definition: AlpsKnowledge.h:72
AlpsTreeNode::getQuality
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:222