HOG2
DVCBS.h
Go to the documentation of this file.
1 //
2 // DVCBS.h
3 // hog2 mac native demos
4 //
5 // Created by Shahaf S. Shperberg
6 //
7 
8 #ifndef DVCBS_h
9 #define DVCBS_h
10 
11 #include "DVCBSOpenClosed.h"
12 #include "FPUtil.h"
13 #include <unordered_map>
14 #include "DVCBSQueue.h"
15 //#include "NBSQueueGF.h"
16 #include <algorithm>
17 
18 using std::cout;
19 
20 
21 template <class state, class action, class environment, class dataStructure = DVCBSQueue<state>,
22 class priorityQueue = DVCBSOpenClosed<state> >
23 class DVCBS {
24 public:
25  DVCBS(int tieBreaking, bool allSolutions = false, bool leq = false)
26  {
27  forwardHeuristic = 0; backwardHeuristic = 0; env = 0; ResetNodeCount();
28  tieBreakingPolicy = tieBreaking;
29  isAllSolutions = allSolutions;
30  isLEQ = leq;
31  }
32  DVCBS(bool allSolutions = false, bool leq = false)
33  {
34  forwardHeuristic = 0; backwardHeuristic = 0; env = 0; ResetNodeCount();
35  tieBreakingPolicy = 4;
36  isAllSolutions = allSolutions;
37  isLEQ = leq;
38  }
39  virtual ~DVCBS() {}
40  void GetPath(environment *env, const state& from, const state& to,
41  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath);
42  bool InitializeSearch(environment *env, const state& from, const state& to,
43  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath);
44  bool ExpandAVertexCover(std::vector<state> &thePath);
45  bool DoSingleSearchStep(std::vector<state> &thePath);
46 
47  uint64_t getForwardUnnecessaryNodesInPath(){
48  return forwardUnnecessaryNodesInPath;
49  }
50 
51  uint64_t getBackwardUnnecessaryNodesInPath(){
52  return backwardUnnecessaryNodesInPath;
53  }
54 
55  uint64_t getForwardMeetingPoint(){
56  return forwardMeetingPoint;
57  }
58 
59  uint64_t getBackwardMeetingPoint(){
60  return backwardMeetingPoint;
61  }
62 
63  uint64_t getOptimalNumberOfExpantions(){
64  printf("curr Cost: %d\n",currentCost);
65  return queue.getMinimalVertexCover(currentCost);
66  }
67 
68 
69  virtual const char *GetName() { return "DVCBS"; }
70 
71  void ResetNodeCount() { nodesExpanded = nodesTouched = 0; counts.clear(); }
72 
73  inline const int GetNumForwardItems() { return queue.forwardQueue.size(); }
74  inline const DVCBSOpenClosedData<state> &GetForwardItem(unsigned int which) { return queue.forwardQueue.Lookat(which); }
75  inline const int GetNumBackwardItems() { return queue.backwardQueue.size(); }
76  inline const DVCBSOpenClosedData<state> &GetBackwardItem(unsigned int which) { return queue.backwardQueue.Lookat(which); }
77 
78  void SetForwardHeuristic(Heuristic<state> *h) { forwardHeuristic = h; }
79  void SetBackwardHeuristic(Heuristic<state> *h) { backwardHeuristic = h; }
80  stateLocation GetNodeForwardLocation(const state &s)
81  {
82  uint64_t childID;
83  auto l = queue.forwardQueue.Lookup(env->GetStateHash(s), childID);
84  return l;
85  }
86  stateLocation GetNodeBackwardLocation(const state &s)
87  {
88  uint64_t childID;
89  return queue.backwardQueue.Lookup(env->GetStateHash(s), childID);
90  }
91  double GetNodeForwardG(const state& s)
92  {
93 
94  uint64_t childID;
95  auto l = queue.forwardQueue.Lookup(env->GetStateHash(s), childID);
96  if (l != kUnseen)
97  return queue.forwardQueue.Lookat(childID).g;
98  return -1;
99  }
100  double GetNodeBackwardG(const state& s)
101  {
102 
103  uint64_t childID;
104  auto l = queue.backwardQueue.Lookup(env->GetStateHash(s), childID);
105  if (l != kUnseen)
106  return queue.backwardQueue.Lookat(childID).g;
107  return -1;
108  }
109  uint64_t GetNodesExpanded() const { return nodesExpanded; }
110  uint64_t GetNodesTouched() const { return nodesTouched; }
111  uint64_t GetDoubleExpansions() const;
112  uint64_t GetNecessaryExpansions() const {
113  uint64_t necessary = 0;
114  for (const auto &i : counts)
115  {
116  if (isAllSolutions){
117  if (i.first <= currentCost)
118  necessary+=i.second;
119  }
120  else{
121  if (i.first < currentCost)
122  necessary+=i.second;
123  }
124  }
125  return necessary;
126  }
127  double GetSolutionCost() const { return currentCost; }
128  double GetExpansionUntilFirstSolution() const { return expansionsUntilSolution; }
129 
130 
131  void OpenGLDraw() const;
132 
133  // void SetWeight(double w) {weight = w;}
134 private:
135  void ExtractFromMiddle(std::vector<state> &thePath);
136  double ExtractCostFromMiddle();
137  void ExtractPathToGoal(state &node, std::vector<state> &thePath)
138  { uint64_t theID; queue.backwardQueue.Lookup(env->GetStateHash(node), theID); ExtractPathToGoalFromID(theID, thePath); }
139  void ExtractPathToGoalFromID(uint64_t node, std::vector<state> &thePath)
140  {
141  do {
142  thePath.push_back(queue.backwardQueue.Lookup(node).data);
143  backwardMeetingPoint++;
144  if (queue.backwardQueue.Lookup(node).g+queue.backwardQueue.Lookup(node).h == currentCost){
145  backwardUnnecessaryNodesInPath++;
146  }
147  node = queue.backwardQueue.Lookup(node).parentID;
148  } while (queue.backwardQueue.Lookup(node).parentID != node);
149  thePath.push_back(queue.backwardQueue.Lookup(node).data);
150 
151  }
152 
153  double ExtractCostToGoal(state &node)
154  { uint64_t theID; queue.backwardQueue.Lookup(env->GetStateHash(node), theID); return ExtractCostToGoalFromID(theID); }
155  double ExtractCostToGoalFromID(uint64_t node)
156  {
157  double cost = 0;
158  do {
159  cost += queue.backwardQueue.Lookup(node).g;
160  node = queue.backwardQueue.Lookup(node).parentID;
161  } while (queue.backwardQueue.Lookup(node).parentID != node);
162  cost += queue.backwardQueue.Lookup(node).g;
163  return cost;
164  }
165 
166  void ExtractPathToStart(state &node, std::vector<state> &thePath)
167  { uint64_t theID; queue.forwardQueue.Lookup(env->GetStateHash(node), theID); ExtractPathToStartFromID(theID, thePath); }
168  void ExtractPathToStartFromID(uint64_t node, std::vector<state> &thePath)
169  {
170  do {
171  thePath.push_back(queue.forwardQueue.Lookup(node).data);
172  forwardMeetingPoint++;
173  if (queue.forwardQueue.Lookup(node).g+queue.forwardQueue.Lookup(node).h == currentCost){
174  forwardUnnecessaryNodesInPath++;
175  }
176  node = queue.forwardQueue.Lookup(node).parentID;
177  } while (queue.forwardQueue.Lookup(node).parentID != node);
178  thePath.push_back(queue.forwardQueue.Lookup(node).data);
179  }
180 
181  double ExtractCostToStart(state &node)
182  { uint64_t theID; queue.forwardQueue.Lookup(env->GetStateHash(node), theID); return ExtractCostToStartFromID(theID); }
183  double ExtractCostToStartFromID(uint64_t node)
184  {
185  double cost = 0;
186  do {
187  cost += queue.forwardQueue.Lookup(node).g;
188  printf("cost: %d ",cost);
189  node = queue.forwardQueue.Lookup(node).parentID;
190  } while (queue.forwardQueue.Lookup(node).parentID != node);
191  cost += queue.forwardQueue.Lookup(node).g;
192  return cost;
193  }
194 
195  void OpenGLDraw(const priorityQueue &queue) const;
196 
197  void Expand(uint64_t nextID,
198  priorityQueue &current,
199  priorityQueue &opposite,
200  Heuristic<state> *heuristic, const state &target);
201  uint64_t nodesTouched, nodesExpanded;
202  state middleNode;
203  double currentCost;
204  double expansionsUntilSolution;
205  double currentSolutionEstimate;
206  std::vector<state> neighbors;
207  environment *env;
208  std::unordered_map<double, int> counts;
209  bool isAllSolutions;
210  bool isLEQ;
211 
212  dataStructure queue;
213 
214  state goal, start;
215 
216  Heuristic<state> *forwardHeuristic;
217  Heuristic<state> *backwardHeuristic;
218 
219  bool expand;
220 
221  double currentPr;
222 
223  int tieBreakingPolicy;
224 
225  uint64_t forwardUnnecessaryNodesInPath;
226  uint64_t backwardUnnecessaryNodesInPath;
227  uint64_t forwardMeetingPoint;
228  uint64_t backwardMeetingPoint;
229 
230 };
231 
232 template <class state, class action, class environment, class dataStructure, class priorityQueue>
233 void DVCBS<state, action, environment, dataStructure, priorityQueue>::GetPath(environment *env, const state& from, const state& to,
234  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath)
235 {
236  if (InitializeSearch(env, from, to, forward, backward, thePath) == false)
237  return;
238 
239  while (!ExpandAVertexCover(thePath))
240  { }
241 }
242 
243 template <class state, class action, class environment, class dataStructure, class priorityQueue>
244 bool DVCBS<state, action, environment, dataStructure, priorityQueue>::InitializeSearch(environment *env, const state& from, const state& to,
245  Heuristic<state> *forward, Heuristic<state> *backward,
246  std::vector<state> &thePath)
247 {
248  this->env = env;
249  forwardHeuristic = forward;
250  backwardHeuristic = backward;
251  currentSolutionEstimate = 0;
252  forwardUnnecessaryNodesInPath = 0;
253  backwardUnnecessaryNodesInPath = 0;
254  forwardMeetingPoint = 0;
255  backwardMeetingPoint = 0;
256  currentCost = DBL_MAX;
257  expansionsUntilSolution = 0;
258  queue.Reset();
259  // queue.forwardQueue.Reset();
260  // queue.backwardQueue.Reset();
261  ResetNodeCount();
262  thePath.resize(0);
263  start = from;
264  goal = to;
265  if (start == goal)
266  return false;
267 
268  queue.forwardQueue.AddOpenNode(start, env->GetStateHash(start), 0, forwardHeuristic->HCost(start, goal));
269  queue.backwardQueue.AddOpenNode(goal, env->GetStateHash(goal), 0, backwardHeuristic->HCost(goal, start));
270 
271  return true;
272 }
273 
274 template <class state, class action, class environment, class dataStructure, class priorityQueue>
275 bool DVCBS<state, action, environment, dataStructure, priorityQueue>::ExpandAVertexCover(std::vector<state> &thePath)
276 {
277  std::vector<uint64_t> nForward, nBackward;
278  bool result = queue.getVertexCover(nForward, nBackward,tieBreakingPolicy);
279  // if failed, see if we have optimal path (but return)
280  if (result == false)
281  {
282  if (currentCost == DBL_MAX)
283  {
284  thePath.resize(0);
285  return true;
286  }
287  ExtractFromMiddle(thePath);
288  return true;
289  }
290 
291 
292  if ((!isAllSolutions && !fless(queue.GetLowerBound(), currentCost)) || (isAllSolutions && !flesseq(queue.GetLowerBound(), currentCost))){
293  ExtractFromMiddle(thePath);
294  return true;
295  }
296 
297  else if (nForward.size() > 0 &&
298  nBackward.size()> 0)
299  {
300  std::unordered_map<state*,bool> mapData;
301  for (int i =0; i< nForward.size(); i++){
302  mapData[&(queue.forwardQueue.Lookup(nForward[i]).data)] = true;
303  }
304  for (int j =0; j< nBackward.size(); j++){
305  if (mapData.find(&(queue.backwardQueue.Lookup(nBackward[j]).data)) != mapData.end()){
306  ExtractFromMiddle(thePath);
307  return true;
308  }
309  }
310 
311  }
312  struct compareBackward {
313  compareBackward(dataStructure currQueue) : queue(currQueue) {}
314  bool operator () (uint64_t i, uint64_t j) { return (queue.backwardQueue.Lookup(i).h<queue.backwardQueue.Lookup(j).h); }
315  dataStructure queue;
316  };
317  struct compareForward {
318  compareForward(dataStructure currQueue) : queue(currQueue) {}
319  bool operator () (uint64_t i, uint64_t j) { return (queue.forwardQueue.Lookup(i).h<queue.forwardQueue.Lookup(j).h); }
320  dataStructure queue;
321  };
322  double currentLowerBound = queue.GetLowerBound();
323 
324  if (nForward.size() == 0){
325  for (int j =0; j< ((int)nBackward.size());j++){
326  double oldKey = queue.backwardQueue.getFirstKey(kOpenReady);
327  if (queue.backwardQueue.Lookup(nBackward[j]).where != kClosed){
328  counts[currentLowerBound]++;
329  Expand(nBackward[j], queue.backwardQueue, queue.forwardQueue, backwardHeuristic, start);
330  }
331  if ((!isAllSolutions && !fless(queue.GetLowerBound(), currentCost)) || (isAllSolutions && !flesseq(queue.GetLowerBound(), currentCost))){
332  ExtractFromMiddle(thePath);
333  return true;
334  }
335  if (currentLowerBound != queue.GetLowerBound() || oldKey != queue.backwardQueue.getFirstKey(kOpenReady)){
336  return false;
337  }
338  }
339  }
340 
341  else if (nBackward.size() == 0){
342  for (int i =0; i< ((int)nForward.size());i++){
343  double oldKey = queue.forwardQueue.getFirstKey(kOpenReady);
344  if (queue.forwardQueue.Lookup(nForward[i]).where != kClosed){
345  counts[currentLowerBound]++;
346  Expand(nForward[i], queue.forwardQueue, queue.backwardQueue, forwardHeuristic, goal);
347  }
348  if ((!isAllSolutions && !fless(queue.GetLowerBound(), currentCost)) || (isAllSolutions && !flesseq(queue.GetLowerBound(), currentCost))){
349  ExtractFromMiddle(thePath);
350  return true;
351  }
352  if (currentLowerBound != queue.GetLowerBound() || oldKey != queue.forwardQueue.getFirstKey(kOpenReady)){
353  return false;
354  }
355  }
356  }
357  else{
358  int i = nForward.size()-1;
359  int j = nBackward.size()-1;
360  while (i >= 0 || j >=0 ){
361  if ((!isAllSolutions && !fless(queue.GetLowerBound(), currentCost)) || (isAllSolutions && !flesseq(queue.GetLowerBound(), currentCost)))
362  {
363  ExtractFromMiddle(thePath);
364  return true;
365  }
366  bool expandForward;
367  if (i < 0){
368  expandForward = false;
369  }
370  else if (j < 0){
371  expandForward = true;
372  }
373  else {
374  if (queue.forwardQueue.Lookup(nForward[i]).g >= queue.backwardQueue.Lookup(nBackward[j]).g){
375  expandForward = true;
376  }
377  else{
378  expandForward = false;
379  }
380  }
381  if (expandForward){
382  if (queue.forwardQueue.Lookup(nForward[i]).where != kClosed){
383  counts[currentLowerBound]++;
384  Expand(nForward[i], queue.forwardQueue, queue.backwardQueue, forwardHeuristic, goal);
385  }
386  i--;
387  }
388  else{
389  if (queue.backwardQueue.Lookup(nBackward[j]).where != kClosed){
390  counts[currentLowerBound]++;
391  Expand(nBackward[j], queue.backwardQueue, queue.forwardQueue, backwardHeuristic, start);
392  }
393  j--;
394  }
395  if (currentLowerBound != queue.GetLowerBound()){
396  return false;
397  }
398  }
399  }
400  return false;
401 }
402 
403 
404 template <class state, class action, class environment, class dataStructure, class priorityQueue>
405 double DVCBS<state, action, environment, dataStructure, priorityQueue>::ExtractCostFromMiddle()
406 {
407  double cost = 0;
408  printf("cost1: %d",cost);
409  cost += ExtractCostToGoal(middleNode);
410  printf("cost2: %d",cost);
411  cost += ExtractCostToStart(middleNode);
412  printf("cost3: %d",cost);
413  return cost;
414 }
415 
416 template <class state, class action, class environment, class dataStructure, class priorityQueue>
417 void DVCBS<state, action, environment, dataStructure, priorityQueue>::ExtractFromMiddle(std::vector<state> &thePath)
418 {
419 
420  std::vector<state> pFor, pBack;
421  ExtractPathToGoal(middleNode, pBack);
422  ExtractPathToStart(middleNode, pFor);
423  reverse(pFor.begin(), pFor.end());
424  thePath = pFor;
425  thePath.insert( thePath.end(), pBack.begin()+1, pBack.end() );
426 }
427 
428 template <class state, class action, class environment, class dataStructure, class priorityQueue>
429 bool DVCBS<state, action, environment, dataStructure, priorityQueue>::DoSingleSearchStep(std::vector<state> &thePath)
430 {
431  return ExpandAVertexCover(thePath);
432 }
433 
434 
435 template <class state, class action, class environment, class dataStructure, class priorityQueue>
436 void DVCBS<state, action, environment, dataStructure, priorityQueue>::Expand(uint64_t nextID,
437  priorityQueue &current,
438  priorityQueue &opposite,
439  Heuristic<state> *heuristic, const state &target)
440 {
441  if (current.Lookup(nextID).where == kClosed){
442  return;
443  }
444 
445  uint64_t tmp = current.CloseAtIndex(nextID);
446  assert(tmp == nextID);
447 
448  //this can happen when we expand a single node instead of a pair
449  if ( (!isAllSolutions && fgreatereq(current.Lookup(nextID).g + current.Lookup(nextID).h, currentCost)) || (isAllSolutions && fgreater(current.Lookup(nextID).g + current.Lookup(nextID).h, currentCost))){
450  return;
451  }
452 
453 
454  nodesExpanded++;
455  env->GetSuccessors(current.Lookup(nextID).data, neighbors);
456  for (auto &succ : neighbors)
457  {
458  nodesTouched++;
459  uint64_t childID;
460  auto loc = current.Lookup(env->GetStateHash(succ), childID);
461 
462  // screening
463  double edgeCost = env->GCost(current.Lookup(nextID).data, succ);
464  if ( (!isAllSolutions && fgreatereq(current.Lookup(nextID).g+edgeCost, currentCost)) || (isAllSolutions && fgreater(current.Lookup(nextID).g+edgeCost, currentCost))){
465  continue;
466  }
467 
468  switch (loc)
469  {
470  case kClosed: // ignore
471  break;
472  case kOpenReady: // update cost if needed
473  case kOpenWaiting:
474  {
475  if (fless(current.Lookup(nextID).g+edgeCost, current.Lookup(childID).g))
476  {
477  double oldGCost = current.Lookup(childID).g;
478  current.Lookup(childID).parentID = nextID;
479  current.Lookup(childID).g = current.Lookup(nextID).g+edgeCost;
480  if (loc == kOpenWaiting){
481  current.KeyChanged(childID,oldGCost+current.Lookup(childID).h);
482  }
483  else{
484  current.KeyChanged(childID,oldGCost);
485  }
486 
487  uint64_t reverseLoc;
488  auto loc = opposite.Lookup(env->GetStateHash(succ), reverseLoc);
489  if (loc == kOpenReady || loc == kOpenWaiting)
490  {
491  if (fless(current.Lookup(nextID).g+edgeCost + opposite.Lookup(reverseLoc).g, currentCost))
492  {
493  currentCost = current.Lookup(nextID).g+edgeCost + opposite.Lookup(reverseLoc).g;
494  expansionsUntilSolution = nodesExpanded;
495  middleNode = succ;
496  }
497  }
498  else if (loc == kClosed)
499  {
500  current.Remove(childID);
501  }
502  }
503  }
504  break;
505  case kUnseen:
506  {
507  uint64_t reverseLoc;
508  auto loc = opposite.Lookup(env->GetStateHash(succ), reverseLoc);
509  if (loc == kClosed)// then
510  {
511  break;
512  }
513  else//loc == kUnseen
514  {
515  double newNodeF = current.Lookup(nextID).g + edgeCost + heuristic->HCost(succ, target);
516  if ((!isAllSolutions && fless(newNodeF , currentCost)) || (isAllSolutions && flesseq(newNodeF , currentCost)))
517  {
518 
519  if (fless(newNodeF , queue.GetLowerBound()) || (isLEQ && flesseq(newNodeF , queue.GetLowerBound())))
520  current.AddOpenNode(succ,
521  env->GetStateHash(succ),
522  current.Lookup(nextID).g + edgeCost,
523  heuristic->HCost(succ, target),
524  nextID, kOpenReady);
525  else
526  current.AddOpenNode(succ,
527  env->GetStateHash(succ),
528  current.Lookup(nextID).g + edgeCost,
529  heuristic->HCost(succ, target),
530  nextID, kOpenWaiting);
531  }
532  if (loc == kOpenReady || loc == kOpenWaiting)
533  {
534  if (fless(current.Lookup(nextID).g + edgeCost + opposite.Lookup(reverseLoc).g, currentCost))
535  {
536  currentCost = current.Lookup(nextID).g + edgeCost + opposite.Lookup(reverseLoc).g;
537  expansionsUntilSolution = nodesExpanded;
538 
539  middleNode = succ;
540  }
541 
542  }
543  }
544 
545  }
546  break;
547  }
548  }
549 }
550 
551 
552 template <class state, class action, class environment, class dataStructure, class priorityQueue>
553 uint64_t DVCBS<state, action, environment, dataStructure, priorityQueue>::GetDoubleExpansions() const
554 {
555  uint64_t doubles = 0;
556  for (unsigned int x = 0; x < queue.forwardQueue.size(); x++)
557  {
558  uint64_t key;
559  const auto &data = queue.forwardQueue.Lookat(x);
560  if (data.where == kClosed)
561  {
562  auto loc = queue.backwardQueue.Lookup(env->GetStateHash(data.data), key);
563  if (loc == kClosed)
564  doubles++;
565  }
566 
567  }
568  return doubles;
569 }
570 
571 template <class state, class action, class environment, class dataStructure, class priorityQueue>
572 void DVCBS<state, action, environment, dataStructure, priorityQueue>::OpenGLDraw() const
573 {
574  OpenGLDraw(queue.forwardQueue);
575  OpenGLDraw(queue.backwardQueue);
576 }
577 
578 template <class state, class action, class environment, class dataStructure, class priorityQueue>
579 void DVCBS<state, action, environment, dataStructure, priorityQueue>::OpenGLDraw(const priorityQueue &q) const
580 {
581  {
582  double transparency = 0.9;
583  if (q.size() == 0)
584  return;
585  uint64_t top = -1;
586  // double minf = 1e9, maxf = 0;
587 // if (q.OpenReadySize() > 0)
588 // {
589 // top = q.Peek(kOpenReady);
590 // }
591  for (unsigned int x = 0; x < q.size(); x++)
592  {
593  const auto &data = q.Lookat(x);
594 // if (x == top)
595 // {
596 // env->SetColor(1.0, 1.0, 0.0, transparency);
597 // env->OpenGLDraw(data.data);
598 // }
599  if (data.where == kOpenWaiting)
600  {
601  env->SetColor(0.0, 0.5, 0.5, transparency);
602  env->OpenGLDraw(data.data);
603  }
604  else if (data.where == kOpenReady)
605  {
606  env->SetColor(0.0, 1.0, 0.0, transparency);
607  env->OpenGLDraw(data.data);
608  }
609  else if (data.where == kClosed)
610  {
611  if (&q == &queue.backwardQueue)
612  env->SetColor(1.0, 0.0, 1.0, transparency);
613  else
614  env->SetColor(1.0, 0.0, 0.0, transparency);
615  env->OpenGLDraw(data.data);
616  }
617  }
618  }
619 
620 }
621 
622 
623 #endif /* DVCBS_h */
DVCBS::currentCost
double currentCost
Definition: DVCBS.h:203
DVCBS
Definition: DVCBS.h:23
kOpenWaiting
@ kOpenWaiting
Definition: BDOpenClosed.h:24
DVCBS::GetNumForwardItems
const int GetNumForwardItems()
Definition: DVCBS.h:73
DVCBS::GetNodeBackwardG
double GetNodeBackwardG(const state &s)
Definition: DVCBS.h:100
DVCBSOpenClosedData
Definition: DVCBSOpenClosed.h:22
DVCBS::getForwardMeetingPoint
uint64_t getForwardMeetingPoint()
Definition: DVCBS.h:55
DVCBS::currentPr
double currentPr
Definition: DVCBS.h:221
fgreatereq
bool fgreatereq(double a, double b)
Definition: FPUtil.h:31
DVCBS::env
environment * env
Definition: DVCBS.h:207
Heuristic
Definition: Heuristic.h:30
DVCBSQueue.h
DVCBS::ExtractCostToStart
double ExtractCostToStart(state &node)
Definition: DVCBS.h:181
kOpenReady
@ kOpenReady
Definition: BDOpenClosed.h:23
DVCBS::GetDoubleExpansions
uint64_t GetDoubleExpansions() const
Definition: DVCBS.h:553
DVCBS::GetNumBackwardItems
const int GetNumBackwardItems()
Definition: DVCBS.h:75
DVCBS::DVCBS
DVCBS(int tieBreaking, bool allSolutions=false, bool leq=false)
Definition: DVCBS.h:25
kClosed
@ kClosed
Definition: BDOpenClosed.h:25
DVCBS::GetNodeForwardG
double GetNodeForwardG(const state &s)
Definition: DVCBS.h:91
FPUtil.h
DVCBS::isLEQ
bool isLEQ
Definition: DVCBS.h:210
DVCBS::DVCBS
DVCBS(bool allSolutions=false, bool leq=false)
Definition: DVCBS.h:32
DVCBS::GetNodeForwardLocation
stateLocation GetNodeForwardLocation(const state &s)
Definition: DVCBS.h:80
DVCBS::ExtractCostToGoalFromID
double ExtractCostToGoalFromID(uint64_t node)
Definition: DVCBS.h:155
DVCBS::queue
dataStructure queue
Definition: DVCBS.h:212
DVCBS::nodesExpanded
uint64_t nodesExpanded
Definition: DVCBS.h:201
DVCBS::GetNodesExpanded
uint64_t GetNodesExpanded() const
Definition: DVCBS.h:109
DVCBS::goal
state goal
Definition: DVCBS.h:214
DVCBS::ExtractCostFromMiddle
double ExtractCostFromMiddle()
Definition: DVCBS.h:405
DVCBS::GetPath
void GetPath(environment *env, const state &from, const state &to, Heuristic< state > *forward, Heuristic< state > *backward, std::vector< state > &thePath)
Definition: DVCBS.h:233
DVCBS::start
state start
Definition: DVCBS.h:214
DVCBS::GetExpansionUntilFirstSolution
double GetExpansionUntilFirstSolution() const
Definition: DVCBS.h:128
DVCBS::SetForwardHeuristic
void SetForwardHeuristic(Heuristic< state > *h)
Definition: DVCBS.h:78
kUnseen
@ kUnseen
Definition: BDOpenClosed.h:26
DVCBS::ExtractCostToStartFromID
double ExtractCostToStartFromID(uint64_t node)
Definition: DVCBS.h:183
DVCBS::counts
std::unordered_map< double, int > counts
Definition: DVCBS.h:208
DVCBS::GetNodesTouched
uint64_t GetNodesTouched() const
Definition: DVCBS.h:110
DVCBS::~DVCBS
virtual ~DVCBS()
Definition: DVCBS.h:39
loc
Definition: MapGenerators.cpp:296
DVCBS::ResetNodeCount
void ResetNodeCount()
Definition: DVCBS.h:71
DVCBS::backwardHeuristic
Heuristic< state > * backwardHeuristic
Definition: DVCBS.h:217
DVCBS::GetForwardItem
const DVCBSOpenClosedData< state > & GetForwardItem(unsigned int which)
Definition: DVCBS.h:74
DVCBS::forwardHeuristic
Heuristic< state > * forwardHeuristic
Definition: DVCBS.h:216
stateLocation
stateLocation
Definition: BDOpenClosed.h:22
DVCBS::middleNode
state middleNode
Definition: DVCBS.h:202
DVCBS::Expand
void Expand(uint64_t nextID, priorityQueue &current, priorityQueue &opposite, Heuristic< state > *heuristic, const state &target)
Definition: DVCBS.h:436
DVCBS::GetNecessaryExpansions
uint64_t GetNecessaryExpansions() const
Definition: DVCBS.h:112
DVCBS::currentSolutionEstimate
double currentSolutionEstimate
Definition: DVCBS.h:205
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
DVCBS::ExtractPathToStartFromID
void ExtractPathToStartFromID(uint64_t node, std::vector< state > &thePath)
Definition: DVCBS.h:168
DVCBS::getForwardUnnecessaryNodesInPath
uint64_t getForwardUnnecessaryNodesInPath()
Definition: DVCBS.h:47
DVCBSOpenClosed.h
DVCBS::DoSingleSearchStep
bool DoSingleSearchStep(std::vector< state > &thePath)
Definition: DVCBS.h:429
DVCBS::ExtractFromMiddle
void ExtractFromMiddle(std::vector< state > &thePath)
Definition: DVCBS.h:417
DVCBS::expand
bool expand
Definition: DVCBS.h:219
Heuristic::HCost
virtual double HCost(const state &a, const state &b) const
Definition: Heuristic.h:73
DVCBS::backwardUnnecessaryNodesInPath
uint64_t backwardUnnecessaryNodesInPath
Definition: DVCBS.h:226
DVCBS::isAllSolutions
bool isAllSolutions
Definition: DVCBS.h:209
DVCBS::expansionsUntilSolution
double expansionsUntilSolution
Definition: DVCBS.h:204
DVCBS::backwardMeetingPoint
uint64_t backwardMeetingPoint
Definition: DVCBS.h:228
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
DVCBS::SetBackwardHeuristic
void SetBackwardHeuristic(Heuristic< state > *h)
Definition: DVCBS.h:79
DVCBS::getBackwardUnnecessaryNodesInPath
uint64_t getBackwardUnnecessaryNodesInPath()
Definition: DVCBS.h:51
DVCBS::GetNodeBackwardLocation
stateLocation GetNodeBackwardLocation(const state &s)
Definition: DVCBS.h:86
DVCBS::ExpandAVertexCover
bool ExpandAVertexCover(std::vector< state > &thePath)
Definition: DVCBS.h:275
DVCBS::GetName
virtual const char * GetName()
Definition: DVCBS.h:69
DVCBS::neighbors
std::vector< state > neighbors
Definition: DVCBS.h:206
DVCBS::ExtractPathToGoal
void ExtractPathToGoal(state &node, std::vector< state > &thePath)
Definition: DVCBS.h:137
DVCBS::OpenGLDraw
void OpenGLDraw() const
Definition: DVCBS.h:572
DVCBS::GetBackwardItem
const DVCBSOpenClosedData< state > & GetBackwardItem(unsigned int which)
Definition: DVCBS.h:76
DVCBS::InitializeSearch
bool InitializeSearch(environment *env, const state &from, const state &to, Heuristic< state > *forward, Heuristic< state > *backward, std::vector< state > &thePath)
Definition: DVCBS.h:244
DVCBS::getBackwardMeetingPoint
uint64_t getBackwardMeetingPoint()
Definition: DVCBS.h:59
DVCBS::getOptimalNumberOfExpantions
uint64_t getOptimalNumberOfExpantions()
Definition: DVCBS.h:63
DVCBS::ExtractPathToStart
void ExtractPathToStart(state &node, std::vector< state > &thePath)
Definition: DVCBS.h:166
DVCBS::ExtractPathToGoalFromID
void ExtractPathToGoalFromID(uint64_t node, std::vector< state > &thePath)
Definition: DVCBS.h:139
DVCBS::tieBreakingPolicy
int tieBreakingPolicy
Definition: DVCBS.h:223
DVCBS::ExtractCostToGoal
double ExtractCostToGoal(state &node)
Definition: DVCBS.h:153
flesseq
bool flesseq(double a, double b)
Definition: FPUtil.h:30
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
DVCBS::nodesTouched
uint64_t nodesTouched
Definition: DVCBS.h:201
DVCBS::forwardUnnecessaryNodesInPath
uint64_t forwardUnnecessaryNodesInPath
Definition: DVCBS.h:225
DVCBS::forwardMeetingPoint
uint64_t forwardMeetingPoint
Definition: DVCBS.h:227
DVCBS::GetSolutionCost
double GetSolutionCost() const
Definition: DVCBS.h:127
Generated by   doxygen 1.8.17