Alps 1.5.11
Loading...
Searching...
No Matches
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-2023, 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
37typedef int AlpsNodeIndex_t;
38
40class AlpsSubTree;
41
42//#############################################################################
48//#############################################################################
49
50class AlpsTreeNode : public AlpsKnowledge {
51 private:
54
55 protected:
57 //AlpsSubTree* subTree_;
58
60 bool active_;
61
64
66 int depth_;
67
70
72 double quality_;
73
76
79
82
83#if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?
85 AlpsTreeNode* children_[ALPS_MAX_CHILD_NUM];
86#else
88#endif
89
93
96
99
102 // Need broker to get incumbent value and add solution when process().
104
106 // 0: default; 1: in subtree to be sent: 2: in subtree's node pool
108
109 public:
111 :
112 active_(false),
113 index_(-1),
114 depth_(-1),
116 quality_(ALPS_OBJ_MAX), // Smaller than default incumbentValue
117 parent_(0),
118 parentIndex_(-1),
119 numChildren_(0),
120#if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?
121 // AlpsTreeNode* children_[ALPS_MAX_CHILD_NUM];
122#else
123 children_(0),
124#endif
125 explicit_(0),
126 desc_(0),
129 sentMark_(0)
131
132 virtual ~AlpsTreeNode() {
133 assert(numChildren_ == 0);
134 //std::cout << "---- delete Alps part of node " << index_ << std::endl;
135#if ! defined(ALPS_MAX_CHILD_NUM)
136 if (children_ != 0) {
137 delete [] children_;
138 children_ = 0;
139 }
140#endif
141 if (desc_ != 0) {
142 delete desc_;
143 desc_ = 0;
144 }
145 }
146
147 bool operator<(const AlpsTreeNode& compNode)
148 { return quality_ < compNode.getQuality(); }
149
152 AlpsNodeDesc* getDesc() const { return desc_; }
153 void setDesc(AlpsNodeDesc* desc) { desc_ = desc; }
154
160
163 /* FIXME: I think that we probably want the argument to be a diff'd
164 description, but this is open to debate. Maybe we should
165 overload this method and have a version that creates a diff'd
166 description, as well as one that creates an explicit
167 description. */
168 virtual AlpsTreeNode* createNewTreeNode(AlpsNodeDesc*& desc) const = 0;
169
172 inline AlpsNodeStatus getStatus() const { return status_; }
173 inline void setStatus(const AlpsNodeStatus stat) { status_ = stat; }
175
178 inline bool isCandidate() const {
180 inline bool isEvaluated() const {
182 inline bool isPregnant() const {
184 inline bool isBranched() const {
186 inline bool isFathomed() const {
188 inline bool isDiscarded() const {
191
194 inline bool isActive() const { return active_; }
195 inline void setActive(const bool yesno) { active_ = yesno; }
197
200 inline AlpsNodeIndex_t getIndex() const { return index_; }
201 inline void setIndex(const AlpsNodeIndex_t index) { index_ = index; }
203
206 inline int getDepth() const { return depth_; }
207 inline void setDepth(const int depth) { depth_ = depth; }
209
212 inline double getSolEstimate() const { return solEstimate_; }
213 inline void setSolEstimate(double est) { solEstimate_ = est; }
215
218 inline double getQuality() const { return quality_; }
219 inline void setQuality(double quality) { quality_ = quality; }
221
224 inline int getNumChildren() const { return numChildren_; }
225 inline void setNumChildren(const int numChildren) {
226 numChildren_ = numChildren;
227#if ! defined(ALPS_MAX_CHILD_NUM)
228 if (children_ != 0) {
229 delete [] children_;
230 children_ = 0;
231 }
233#endif
234 }
235 // Change by s
236 inline void modifyNumChildren(const int s) { numChildren_ += s; }
238
239 // *FIXME* : Sanity check. Maybe we should check that the argument is in
240 // the correct range, but how do we do that? This makes the code
241 // inefficient so it should be done with #ifdefs so it can be compiled
242 // out. But in that case, we should move this code to the implementation
243 // file and it won't get inlined anymore.
244
247 inline AlpsTreeNode* getChild(const int i) const { return children_[i]; }
248
249 //FIXME: Compiler complains about this second declaration. Not sure how to
250 //declare a const and a non-const version of a function with the same
251 //arguments...
252 // /** Returns a const pointer to the ith child. */
253 // const AlpsTreeNode* getChild(const int i) const { return children_[i]; }
254 inline void setChild(const int i, AlpsTreeNode* node)
255 { children_[i] = node; }
257
262
264 void addChild(AlpsTreeNode*& child);
265
270
272 //inline AlpsSubTree* getSubTree() const { return subTree_; }
273 //inline void setSubTree(AlpsSubTree* tree) { subTree_ = tree; }
274
277 inline AlpsTreeNode* getParent() const { return parent_; }
278 inline void setParent(AlpsTreeNode* parent) { parent_ = parent; }
280
283 inline AlpsNodeIndex_t getParentIndex() const { return parentIndex_; }
284 inline void setParentIndex(AlpsNodeIndex_t index)
285 { parentIndex_ = index; }
287
291 inline int getExplicit() const { return explicit_; }
292 inline void setExplicit(int fp) { explicit_ = fp; }
294
297 virtual void convertToExplicit() {}
298 virtual void convertToRelative() {}
300
303 inline int getSentMark() const { return sentMark_; }
304 inline void setSentMark(const int tf) { sentMark_ = tf; }
306
336 virtual int process(bool isRoot = false, bool rampUp = false) = 0;
337
347 virtual std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, double> >
348 branch() = 0;
349
350 protected:
351
353 AlpsReturnStatus encodeAlps(AlpsEncoded *encoded) const;
354
356 AlpsReturnStatus decodeAlps(AlpsEncoded &encoded);
357
358};
359#endif
int AlpsNodeIndex_t
AlpsReturnStatus
Definition Alps.h:118
@ AlpsKnowledgeTypeNode
Definition Alps.h:91
AlpsNodeStatus
The possible stati for the search nodes.
Definition Alps.h:61
@ AlpsNodeStatusDiscarded
Definition Alps.h:67
@ AlpsNodeStatusCandidate
Definition Alps.h:62
@ AlpsNodeStatusFathomed
Definition Alps.h:66
@ AlpsNodeStatusPregnant
Definition Alps.h:64
@ AlpsNodeStatusEvaluated
Definition Alps.h:63
@ AlpsNodeStatusBranched
Definition Alps.h:65
#define ALPS_OBJ_MAX
Definition Alps.h:145
This data structure is to contain the packed form of an encodable knowledge.
Definition AlpsEncoded.h:25
The base class of knowledge broker class.
The abstract base class of any user-defined class that Alps has to know about in order to encode/deco...
void setType(KnowledgeType t)
A class to refer to the description of a search tree node.
This class contains the data pertaining to a particular subtree in the search tree.
Definition AlpsSubTree.h:47
This class holds one node of the search tree.
AlpsNodeDesc * getDesc() const
void addChild(AlpsTreeNode *&child)
Add a child to the list of children for this node.
void removeDescendants()
Removes all the descendants of the node.
AlpsTreeNode * getParent() const
Get/set subtree.
double solEstimate_
The solution estimate.
AlpsTreeNode ** children_
int getNumChildren() const
Query/set what the number of children.
int sentMark_
Various mark used in splitting and passing subtrees.
AlpsNodeDesc * modifyDesc()
Access the desc so that can modify it.
bool isBranched() const
void setParent(AlpsTreeNode *parent)
int getSentMark() const
Various marks used in parallel code.
AlpsNodeIndex_t getIndex() const
Query/set node identifier (unique within subtree).
AlpsNodeStatus status_
The current status of the node.
void setDesc(AlpsNodeDesc *desc)
void setKnowledgeBroker(AlpsKnowledgeBroker *kb)
bool isPregnant() const
AlpsTreeNode * getChild(const int i) const
Query/set pointer to the ith child.
AlpsNodeStatus getStatus() const
Query/set the current status.
void setStatus(const AlpsNodeStatus stat)
AlpsNodeIndex_t parentIndex_
The index of parent of the tree node.
int numChildren_
The number of children.
AlpsNodeIndex_t index_
The unique index of the tree node (across the whole search tree).
AlpsNodeIndex_t getParentIndex() const
Get/set the index of the parent of the node.
AlpsNodeDesc * desc_
The actual description of the tree node.
void setActive(const bool yesno)
bool isCandidate() const
Query functions about specific stati.
void setChild(const int i, AlpsTreeNode *node)
Returns a const pointer to the ith child.
void removeChild(AlpsTreeNode *&child)
Remove the pointer to given child from the list of children.
bool isDiscarded() const
int depth_
The depth of the node (in the whole tree – the root is at depth 0).
AlpsTreeNode * parent_
The parent of the tree node.
double getQuality() const
Query/set the quality of the node.
bool isEvaluated() const
AlpsTreeNode(const AlpsTreeNode &)
void setSentMark(const int tf)
void setNumChildren(const int numChildren)
void setQuality(double quality)
double quality_
The quality of this node.
AlpsTreeNode & operator=(const AlpsTreeNode &)
bool isFathomed() const
int explicit_
Indicate whether the node description is explicit(1) or relative(0).
int getDepth() const
Query/set what depth the search tree node is at.
double getSolEstimate() const
Query/set the solution estimate of the node.
void setDepth(const int depth)
int getExplicit() const
Get/set the indication of whether the node has full or differencing description.
void setExplicit(int fp)
bool active_
The subtree own this node.
void setParentIndex(AlpsNodeIndex_t index)
virtual void convertToRelative()
void modifyNumChildren(const int s)
virtual ~AlpsTreeNode()
AlpsKnowledgeBroker * getKnowledgeBroker() const
Functions to access/set the knwoledge broker.
virtual AlpsTreeNode * createNewTreeNode(AlpsNodeDesc *&desc) const =0
The purpose of this function is be able to create the children of a node after branching.
virtual void convertToExplicit()
Convert explicit description to difference, and vise-vesa.
void setSolEstimate(double est)
AlpsKnowledgeBroker * knowledgeBroker_
A pointer to the knowledge broker of the process where this node is processed.
bool isActive() const
Query/set node in-process indicator.
bool operator<(const AlpsTreeNode &compNode)
void setIndex(const AlpsNodeIndex_t index)