HOG2
Propagation.h
Go to the documentation of this file.
1 /*
2  * Propagation.h
3  * hog2
4  *
5  * by Zhifu Zhang
6  *
7  * This code emphasizes on correctness.
8  */
9 
10 #ifndef PROPAGATION_H
11 #define PROPAGATION_H
12 
13 #include <math.h>
14 #include <cstdlib>
15 #include "GraphAlgorithm.h"
16 #include "SearchEnvironment.h"
17 #include "GraphEnvironment.h"
18 #include <deque>
19 #include <unordered_map>
20 #include "FPUtil.h"
21 #include "OpenListB.h"
22 
23 #ifndef UINT32_MAX
24 #define UINT32_MAX 4294967295U
25 #endif
26 
27 #define PROP_A 0
28 #define PROP_B 1
29 #define PROP_BP 2
30 #define PROP_APPROX 3
31 #define PROP_BFS 4
32 #define PROP_DELAY 5
33 #define PROP_DP 7 // 6 is AStarDelay
34 #define PROP_BPMX 8
35 #define PROP_DPMX 9
36 #define PROP_BPMXE 10
37 
38 #define PROP_DPDLMX 11 // DP + Delay + MX
39 
40 namespace PropUtil
41 {
42  class SearchNode {
43  public:
44  /* the no parameter constructor will be called by OpenListB, and should construct invalid objects */
45  //SearchNode()
46  //:fCost(0),gCost(0),currNode((graphState)-1),prevNode((graphState)-1),lastExpanded(0),expansions(0),threshold(1) {}
47 
48  SearchNode(double _fCost=0, double _gCost=0, graphState curr=UINT32_MAX, graphState prev=UINT32_MAX)
49  :fCost(_fCost), gCost(_gCost), currNode(curr), prevNode(prev), isGoal(false) {}
50 
51  SearchNode(graphState curr)
52  :fCost(0), gCost(0), currNode(curr), prevNode(curr), isGoal(false) {}
53 
54 
55  void copy(double f, double g, graphState curr, graphState prev) {
56  fCost = f;
57  gCost = g;
58  currNode = curr;
59  prevNode = prev;
60  }
61 
62  double fCost;
63  double gCost;
64  graphState currNode;
65  graphState prevNode;
66 
67  bool isGoal; // is it goal?
68 
69  //bool rxp;
70  };
71 
72  struct SearchNodeEX {
73  SearchNode sn;
74  double weight;
75 
76  SearchNodeEX(SearchNode& n, double w) {
77  sn = n;
78  weight = w;
79  }
80  };
81 
82  struct StateEX {
83  graphState gs;
84  double weight;
85 
86  StateEX(graphState s, double w) {
87  gs = s;
88  weight = w;
89  }
90  };
91 
92  struct SearchNodeEqual {
93  bool operator()(const SearchNode &i1, const SearchNode &i2) const
94  { return (i1.currNode == i2.currNode); }
95  };
96 
97  // comparing f value
98  struct SearchNodeCompare { // true means i2 is preferable over i1
99  // in favor of goal when f ties
100  // prefering larger g, i.e. smaller h is also in favor of goal nodes
101  bool operator()(const SearchNode &i1, const SearchNode &i2) const
102  {
103  if (fequal(i1.fCost, i2.fCost))
104  {
105  if (i2.isGoal) // always prefer a goal node in tie
106  return true;
107  if (i1.isGoal)
108  return false;
109  return fless(i1.gCost, i2.gCost); // favor larger g
110  }
111  return (fgreater(i1.fCost, i2.fCost));
112  }
113  };
114 
115  struct GGreater {
116  bool operator()(const SearchNode &i1, const SearchNode &i2) const
117  {
118  if (fequal(i1.gCost,i2.gCost)) {
119  //if (i2.isGoal) // always prefer a goal node in tie
120  // return true;
121  //if (i1.isGoal)
122  // return false;
123 
124  return fgreater(i1.fCost,i2.fCost);
125  }
126 
127  return fgreater(i1.gCost,i2.gCost);
128  }
129  };
130 
131  struct TGreater {
132  bool operator()(const SearchNode &, const SearchNode &) const
133  {
134  assert(false); // parameters ignored, this code must be wrong
135  //if (i1.threshold == i2.threshold) // threshold is integer
136  // return fgreater(i1.gCost,i2.gCost);
137  //return i1.threshold > i2.threshold;
138  return true;
139  }
140  };
141 
142  struct FExtract {
143  double operator()(const SearchNode &i) const
144  {
145  return i.fCost;
146  }
147  };
148 
149  struct SearchNodeHash {
150  size_t operator()(const SearchNode &x) const
151  { return (size_t)(x.currNode); }
152  };
153 
154  struct graphGenerator {
155  static void SetLoc(node *n, double x, double y, double z)
156  {
157  n->SetLabelF(GraphSearchConstants::kXCoordinate, x);
158  n->SetLabelF(GraphSearchConstants::kYCoordinate, y);
159  n->SetLabelF(GraphSearchConstants::kZCoordinate, z);
160 // std::cout << *n << std::endl;
161 // printf("(%f, %f, %f)\n", x, y, z);
162  }
163 
164  static void GetLoc(node *n, double &x, double &y, double &z)
165  {
166  x = n->GetLabelF(GraphSearchConstants::kXCoordinate);
167  y = n->GetLabelF(GraphSearchConstants::kYCoordinate);
168  z = n->GetLabelF(GraphSearchConstants::kZCoordinate);
169  }
170 
171  static Graph* genFig1(unsigned int N)
172  {
173  // h(0) = h(1) = 0;
174  // h(i) = 2^(i-1) + 2i - 3, for 1<i<=N
175  // c(i,j) = 2^(i-2) + i - 2^(j-1) - j, for 1<=j<i<=N
176  // c(1,0) = 2^(N-1) + N - 2
177  assert(N >= 3);
178 
179  Graph *g = new Graph();
180 
181  // add nodes
182 
183  for (unsigned int nodeID = 0; nodeID <= N; nodeID++)
184  {
185  node *n = new node("");
186  if (nodeID == 0 || nodeID == 1)
187  {
188  n->SetLabelF(GraphSearchConstants::kHCost, 0);
189  }
190  else {
191  double h = pow(2,nodeID-1) + 2*nodeID - 3;
192  n->SetLabelF(GraphSearchConstants::kHCost,h);
193  }
194  g->AddNode(n); // the real nodeID is assigned here
195 
196  if (nodeID == 0)
197  {
198  SetLoc(n,-1,-1,0);
199  }
200  else // nodes 1 - N will be drawn along 3/4 circle
201  {
202  double alpha = ((double)N - nodeID) * 1.5*PI /(N - 1.0);
203  double beta = alpha - 0.5*PI;
204  SetLoc(n,cos(beta),sin(beta),0);
205  }
206  }
207 
208  // add edges
209  double c = pow(2,N-1) + N - 2;
210  edge *e = new edge(1,0,c);
211  g->AddEdge(e);
212  for (unsigned int j = 1; j < N; j++)
213  {
214  for (unsigned int i = j+1; i <= N; i++)
215  {
216  c = pow(2,i-2) + i - pow(2,j-1) - j;
217  e = new edge(i,j,c);
218  g->AddEdge(e);
219  }
220  }
221 
222  return g;
223  }
224 
225  /* fig 2 is a variant of fig 1 by changing h(N) from 23 to 0 */
226  static Graph* genFig2(unsigned int N)
227  {
228  // h(0) = h(1) = 0;
229  // h(i) = 2^(i-1) + 2i - 3, for 1<i<=N
230  // c(i,j) = 2^(i-2) + i - 2^(j-1) - j, for 1<=j<i<=N
231  // c(1,0) = 2^(N-1) + N - 2
232  assert(N >= 3);
233 
234  Graph *g = new Graph();
235 
236  // add nodes
237 
238  for (unsigned int nodeID = 0; nodeID <= N; nodeID++)
239  {
240  node *n = new node("");
241  if (nodeID == 0 || nodeID == 1 || nodeID==N)
242  {
243  n->SetLabelF(GraphSearchConstants::kHCost, 0);
244  }
245  else {
246  double h = pow(2,nodeID-1) + 2*nodeID - 3;
247  n->SetLabelF(GraphSearchConstants::kHCost,h);
248  }
249  g->AddNode(n); // the real nodeID is assigned here
250 
251  if (nodeID == 0)
252  {
253  SetLoc(n,-1,-1,0);
254  }
255  else // nodes 1 - N will be drawn along 3/4 circle
256  {
257  double alpha = ((double)N - nodeID) * 1.5*PI /(N - 1.0);
258  double beta = alpha - 0.5*PI;
259  SetLoc(n,cos(beta),sin(beta),0);
260  }
261  }
262 
263  // add edges
264  double c = pow(2,N-1) + N - 2;
265  edge *e = new edge(1,0,c);
266  g->AddEdge(e);
267  for (unsigned int j = 1; j < N; j++)
268  {
269  for (unsigned int i = j+1; i <= N; i++)
270  {
271  c = pow(2,i-2) + i - pow(2,j-1) - j;
272  e = new edge(i,j,c);
273  g->AddEdge(e);
274  }
275  }
276 
277  return g;
278  }
279 
280  static Graph* genFig3(unsigned int N)
281  {
282  // h(0) = h(2N-1) = 0
283  // h(i) = 2(N-1)^2 - N - i + 2, for i = 1,...,N-1
284  // h(N+j) = 2(N-1)(N-2-j) + 1, for j = 0,...,N-2
285  // c(0,i) = 1, for i = 1,...,N-1
286  // c(i,N) = 2(N-1)(i-1) + 1, for i = 1,...,N-1
287  // c(i,i+1) = 2N - 2, for i = N,...,2N-1 (should it be 2N-2 ?)
288  assert(N >= 2);
289 
290  Graph* g = new Graph();
291 
292  // add nodes
293  node* n = new node("");
294  n->SetLabelF(GraphSearchConstants::kHCost,0);
295  SetLoc(n, 0, -0.9, 0);
296  g->AddNode(n);
297 
298  for (unsigned int i=1;i<=N-1;i++)
299  {
300  n = new node("");
301  double h = 2*(N-1)*(N-1) - N - i + 2;
302  n->SetLabelF(GraphSearchConstants::kHCost,h);
303  g->AddNode(n);
304  SetLoc(n, -1+(double)(i-1)*2.0/((double)N-2.0), 0.0, 0);
305  }
306 
307  for (unsigned int j=0; j<=N-2; j++)
308  {
309  n = new node("");
310  double h = 0; // 2*(N-1)*(N-2-j) + 1;
311  n->SetLabelF(GraphSearchConstants::kHCost,h);
312  g->AddNode(n);
313  SetLoc(n, -(double)j/((double)N-1.0), 0.9+((j%2)?0.1:0.0), 0);
314  }
315 
316  n = new node(""); // the last node (2N-1)
317  n->SetLabelF(GraphSearchConstants::kHCost,0);
318  SetLoc(n, -1, 1, 0);
319  g->AddNode(n);
320 
321  // add edges
322 
323  // type 1
324  for (unsigned int i=1;i<=N-1;i++)
325  {
326  edge* e = new edge(0,i,1);
327  g->AddEdge(e);
328  }
329 
330  // type 2
331  for (unsigned int i=1; i<=N-1; i++)
332  {
333  double c = 2*(N-1)*(i-1) + 1;
334  edge* e = new edge(i,N,c);
335  g->AddEdge(e);
336  }
337 
338  // type 3
339  for (unsigned int i=N; i<=2*N-2; i++)
340  {
341  double c = 2*N - 2;
342  edge* e = new edge(i,i+1,c);
343  g->AddEdge(e);
344  }
345 
346  return g;
347  }
348 
349  static Graph* genFig4(unsigned int N)
350  {
351  // h(0) = h(2N-1) = 0
352  // h(i) = N+i-1, for i = 1,...,N-1
353  // h(N+j) = 2(N-1)(N-2-j) + 1, for j = 0,...,N-2
354  // c(0,i) = 1, for i = 1,...,N-1
355  // c(i,N) = 2(N-1)(i-1) + 1, for i = 1,...,N-1
356  // c(i,i+1) = 2N - 2, for i = N,...,2N-1 (should it be 2N-2 ?)
357  assert(N >= 2);
358 
359  Graph* g = new Graph();
360 
361  // add nodes
362  node* n = new node("");
363  n->SetLabelF(GraphSearchConstants::kHCost,0);
364  SetLoc(n, 0, -0.9, 0);
365  g->AddNode(n);
366 
367  for (unsigned int i=1;i<=N-1;i++)
368  {
369  n = new node("");
370  double h = 2*N-i;
371  n->SetLabelF(GraphSearchConstants::kHCost,h);
372  g->AddNode(n);
373  SetLoc(n, -1+(double)(i-1)*2.0/((double)N-2.0), 0.0, 0);
374  }
375 
376  for (unsigned int j=0; j<=N+1; j++)
377  {
378  n = new node("");
379  double h = 0; // 2*(N-1)*(N-2-j) + 1;
380  n->SetLabelF(GraphSearchConstants::kHCost,h);
381  g->AddNode(n);
382  SetLoc(n, -(double)j/((double)N-1.0), 0.9+((j%2)?0.1:0.0), 0);
383  }
384 
385  n = new node(""); // the last node (2N-1)
386  n->SetLabelF(GraphSearchConstants::kHCost,0);
387  SetLoc(n, -1, 1, 0);
388  g->AddNode(n);
389 
390  // add edges
391 
392  // type 1
393  for (unsigned int i=1;i<=N-1;i++)
394  {
395  edge* e = new edge(0,i,1);
396  g->AddEdge(e);
397  }
398 
399  // type 2
400  for (unsigned int i=1; i<=N-1; i++)
401  {
402  double c = i;
403  edge* e = new edge(i,N,c);
404  g->AddEdge(e);
405  }
406 
407  // type 3
408  for (unsigned int i=N; i<=2*N-1; i++)
409  {
410  double c = 1;
411  edge* e = new edge(i,i+1,c);
412  g->AddEdge(e);
413  }
414  g->AddEdge(new edge(2*N, 2*N+1, N-1));
415  return g;
416  }
417  };
418 
419 
420  typedef OpenListB<PropUtil::SearchNode, PropUtil::SearchNodeHash,
421  PropUtil::SearchNodeEqual, PropUtil::SearchNodeCompare, PropUtil::GGreater, PropUtil::FExtract> PQueue;
422 
423  typedef std::unordered_map<graphState, PropUtil::SearchNode > NodeLookupTable;
424 
425  typedef OpenListB<PropUtil::SearchNode, PropUtil::SearchNodeHash,
426  PropUtil::SearchNodeEqual, PropUtil::GGreater, PropUtil::GGreater, PropUtil::FExtract> GQueue;
427 
428  typedef OpenListB<PropUtil::SearchNode, PropUtil::SearchNodeHash,
429  PropUtil::SearchNodeEqual, PropUtil::TGreater, PropUtil::GGreater, PropUtil::FExtract> TQueue;
430 }
431 
432 
433 class Prop : public GraphAlgorithm {
434 public:
435  Prop() { verID = PROP_BP; delta=0; bpmxLevel=1;} // bpmxLevel is not used if not explicitely calling bpmx root prop
436  Prop(unsigned int v) {
437  verID = v; delta=0;
438  if (verID == PROP_BPMX || verID == PROP_DPMX || verID == PROP_BPMXE || verID == PROP_DPDLMX)
439  bpmxLevel=1;
440  else
441  bpmxLevel=0;
442  } // [changed needed, regarding bpmxLevel]
443  Prop(unsigned int v, double del) {
444  verID=v; delta=del;
445  if (verID == PROP_BPMX || verID == PROP_DPMX || verID == PROP_BPMXE || verID == PROP_DPDLMX)
446  bpmxLevel=1;
447  else
448  bpmxLevel=0;
449  } //[changed needed, regarding bpmxLevel]
450  virtual ~Prop() {}
451  void GetPath(GraphEnvironment *env, Graph *_g, graphState from, graphState to, std::vector<graphState> &thePath);
452 
453  uint64_t GetNodesExpanded() { return (uint64_t)nodesExpanded; }
454  uint64_t GetNodesTouched() { return nodesTouched; }
455 
456  uint64_t GetNodesFirstExpanded() {return closedSize;}
457  uint64_t GetNodesMetaExpanded() {return metaexpanded;}
458  uint64_t GetNodesReopened() {return NodesReopened;}
459 
460  bool InitializeSearch(GraphEnvironment *env, Graph *_g, graphState from, graphState to, std::vector<graphState> &thePath);
461  bool DoSingleSearchStep(std::vector<graphState> &thePath);
462  bool DoSingleStepA(std::vector<graphState> &thePath);
463  bool DoSingleStepB(std::vector<graphState> &thePath);
464  bool DoSingleStepBP(std::vector<graphState> &thePath);
465  bool DoSingleStepApprox(std::vector<graphState> &thePath);
466  bool DoSingleStepBFS(std::vector<graphState> &thePath);
467  //void ClosedListRepair();
468  bool DoSingleStepDelay(std::vector<graphState> &thePath);
469  bool DoSingleStepDP(std::vector<graphState> &thePath);
470  bool DoSingleStepBPMX(std::vector<graphState> &thePath);
471  bool DoSingleStepDPMX(std::vector<graphState> &thePath);
472 
473  bool DoSingleStepDPDLMX(std::vector<graphState> &thePath);
474  //void CleanUpOpen(double solCost);
475  //void Categorize(std::vector<graphState>& neighbors);
476  //void Categorize2(std::vector<graphState>& neighbors, std::vector<PropUtil::SearchNode>& openN, std::vector<PropUtil::SearchNode>& closedN, std::vector<graphState>& newN);
477  void ReverseProp(PropUtil::SearchNode& topNode);
478  void ReversePropX1(PropUtil::SearchNode& topNode);
479  void ReversePropX2(PropUtil::SearchNode& topNode);
480  //bool NextNeighbor(PropUtil::SearchNode& neighborNode, graphState& neighbor, int& mode);
481  void ExtractPathToStart(graphState goalNode, std::vector<graphState> &thePath);
482 
483  void GetLowestG(PropUtil::SearchNode &gNode);
484  void GetLowestGF(PropUtil::SearchNode &gNode);
485  //bool GetLowestG(PropUtil::TQueue &wList, PropUtil::SearchNode &gNode, double fBound, long TBound);
486  bool UpdateHOnly(PropUtil::SearchNode &node, double h);
487  void ComputeNewHMero3a(double &h, double &h_tmp, graphState neighbor, PropUtil::SearchNode& neighborNode, double altH, int mode);
488  void RelaxOpenNode(double f, double g, graphState neighbor, PropUtil::SearchNode &neighborNode, graphState topNodeID);
489  void RelaxDelayNode(double f, double g, graphState neighbor, PropUtil::SearchNode &neighborNode, graphState topNodeID);
490 
491  //void OpenGLDraw() const;
492  void OpenGLDraw() const;
493  void DrawText(double x, double y, double z, float r, float g, float b, char* str);
494  void DrawEdge(unsigned int from, unsigned int to, double weight);
495 
496  //int GetReopenings() {return reopenings;}
497  double GetSolutionCost() {return solutionCost;}
498  const char* GetName() {return algname;}
499  int GetSolutionEdges() {return pathSize;}
500 
501  bool DoSingleStepBPMXE(std::vector<graphState> &thePath);
502  //void ReversePropX1E(PropUtil::SearchNode& topNode);
503  //void BroadcastFence();
504 
505  char algname[20];
506  unsigned int verID;
507  double solutionCost;
508 
509  int bpmxLevel;
510 
511  //unsigned long tickNewExp;
512  //unsigned long tickReExp;
513  //unsigned long tickBPMX;
514 
515  //unsigned long nNewExp;
516  //unsigned long nReExp;
517  //unsigned long nBPMX;
518 
519  long metaexpanded; // count reverse propagations in bpmx / dp
520 
521  PropUtil::PQueue openQueue;
522  PropUtil::NodeLookupTable closedList;
523 
524  long closedSize;
525 
526 private:
527 
528  double F;
529  double nodesExpanded;
530  uint64_t nodesTouched;
531  std::vector<graphState> neighbors;
532  //std::deque<PropUtil::SearchNode> bfsQueue;
533  graphState goal, start;
534  GraphEnvironment *env;
535 
536  PropUtil::GQueue FCache;
537  PropUtil::GQueue delayCache; //
538  int reopenings;
539 
540  int fDelay(long /*N*/) {
541  return 2;
542  }
543 
544  PropUtil::TQueue WaitList; // for delay alg
545 
546  double delta; // the threshold for approx
547 
548 
549  int pathSize;
550 
551  long NodesReopened;
552 
553  Graph *grp; // for drawing only
554 
555  graphState justExpanded; // the node that is expanded in previous round, for drawing only
556 
557  // categorize the neighbors
558  //std::vector<PropUtil::SearchNode> closedNeighbors;
559  //std::vector<PropUtil::SearchNode> openNeighbors;
560  //std::vector<PropUtil::SearchNode> waitNeighbors;
561  //std::vector<graphState> newNeighbors;
562 
563  //PropUtil::SearchNode* newParent; // new parent for topNode, default is null
564 
565  //double ET;
566  //std::deque<graphState> fifo;
567 
568  void Broadcast(int level, int levelcount);
569 
570  std::deque<graphState> fifo;
571  std::vector<graphState> myneighbors;
572 };
573 
574 
575 
576 
577 #endif
Graph::AddNode
int AddNode(node *)
Definition: Graph.cpp:136
PropUtil::graphGenerator::SetLoc
static void SetLoc(node *n, double x, double y, double z)
Definition: Propagation.h:155
PropUtil::FExtract
Definition: Propagation.h:142
Prop::DoSingleStepBFS
bool DoSingleStepBFS(std::vector< graphState > &thePath)
Definition: Propagation.cpp:1004
node::SetLabelF
void SetLabelF(unsigned int index, double val) const
Definition: Graph.cpp:687
graphMove
Definition: GraphEnvironment.h:34
Prop::grp
Graph * grp
Definition: Propagation.h:553
Prop::pathSize
int pathSize
Definition: Propagation.h:549
Prop::RelaxDelayNode
void RelaxDelayNode(double f, double g, graphState neighbor, PropUtil::SearchNode &neighborNode, graphState topNodeID)
Definition: Propagation.cpp:205
Prop::DoSingleStepBP
bool DoSingleStepBP(std::vector< graphState > &thePath)
Definition: Propagation.cpp:550
graphState
unsigned long graphState
Definition: GraphEnvironment.h:32
Prop::OpenGLDraw
void OpenGLDraw() const
Definition: Propagation.cpp:2462
Prop::DrawText
void DrawText(double x, double y, double z, float r, float g, float b, char *str)
Definition: Propagation.cpp:2560
PropUtil::SearchNode::SearchNode
SearchNode(double _fCost=0, double _gCost=0, graphState curr=UINT32_MAX, graphState prev=UINT32_MAX)
Definition: Propagation.h:48
PropUtil::SearchNode::prevNode
graphState prevNode
Definition: Propagation.h:65
Prop::ReversePropX2
void ReversePropX2(PropUtil::SearchNode &topNode)
Definition: Propagation.cpp:1126
PropUtil::GQueue
OpenListB< PropUtil::SearchNode, PropUtil::SearchNodeHash, PropUtil::SearchNodeEqual, PropUtil::GGreater, PropUtil::GGreater, PropUtil::FExtract > GQueue
Definition: Propagation.h:426
Prop::DrawEdge
void DrawEdge(unsigned int from, unsigned int to, double weight)
Definition: Propagation.cpp:2581
PropUtil::graphGenerator::genFig4
static Graph * genFig4(unsigned int N)
Definition: Propagation.h:349
Graph::AddEdge
void AddEdge(edge *)
Definition: Graph.cpp:170
Prop::GetSolutionEdges
int GetSolutionEdges()
Definition: Propagation.h:499
Prop::ReversePropX1
void ReversePropX1(PropUtil::SearchNode &topNode)
Definition: Propagation.cpp:1084
PropUtil::SearchNodeHash
Definition: Propagation.h:149
Prop::nodesExpanded
double nodesExpanded
Definition: Propagation.h:529
Prop::GetNodesTouched
uint64_t GetNodesTouched()
Definition: Propagation.h:454
Prop::DoSingleStepDPDLMX
bool DoSingleStepDPDLMX(std::vector< graphState > &thePath)
Definition: Propagation.cpp:1894
Prop::Prop
Prop()
Definition: Propagation.h:435
PROP_BP
#define PROP_BP
Definition: Propagation.h:29
Prop::GetNodesReopened
uint64_t GetNodesReopened()
Definition: Propagation.h:458
FPUtil.h
Prop::GetName
const char * GetName()
Definition: Propagation.h:498
Prop::GetNodesMetaExpanded
uint64_t GetNodesMetaExpanded()
Definition: Propagation.h:457
PropUtil::SearchNode::fCost
double fCost
Definition: Propagation.h:62
PropUtil::StateEX
Definition: Propagation.h:82
Prop::GetLowestG
void GetLowestG(PropUtil::SearchNode &gNode)
Definition: Propagation.cpp:1008
GraphSearchConstants::kXCoordinate
@ kXCoordinate
Definition: GraphEnvironment.h:51
Prop::GetLowestGF
void GetLowestGF(PropUtil::SearchNode &gNode)
Definition: Propagation.cpp:1022
Graph
A generic Graph class.
Definition: Graph.h:66
PropUtil::graphGenerator::genFig2
static Graph * genFig2(unsigned int N)
Definition: Propagation.h:226
Prop::justExpanded
graphState justExpanded
Definition: Propagation.h:555
Prop::fDelay
int fDelay(long)
Definition: Propagation.h:540
PropUtil::StateEX::gs
graphState gs
Definition: Propagation.h:83
GraphSearchConstants::kHCost
@ kHCost
Definition: GraphEnvironment.h:50
Prop::openQueue
PropUtil::PQueue openQueue
Definition: Propagation.h:521
PropUtil::graphGenerator
Definition: Propagation.h:154
Prop::ComputeNewHMero3a
void ComputeNewHMero3a(double &h, double &h_tmp, graphState neighbor, PropUtil::SearchNode &neighborNode, double altH, int mode)
Definition: Propagation.cpp:164
Prop::myneighbors
std::vector< graphState > myneighbors
Definition: Propagation.h:571
PropUtil::FExtract::operator()
double operator()(const SearchNode &i) const
Definition: Propagation.h:143
Prop::DoSingleStepDPMX
bool DoSingleStepDPMX(std::vector< graphState > &thePath)
Definition: Propagation.cpp:2215
PropUtil
Definition: Propagation.h:40
Prop::nodesTouched
uint64_t nodesTouched
Definition: Propagation.h:530
Prop::closedList
PropUtil::NodeLookupTable closedList
Definition: Propagation.h:522
PropUtil::SearchNodeHash::operator()
size_t operator()(const SearchNode &x) const
Definition: Propagation.h:150
Prop::UpdateHOnly
bool UpdateHOnly(PropUtil::SearchNode &node, double h)
Definition: Propagation.cpp:992
Prop::DoSingleStepBPMX
bool DoSingleStepBPMX(std::vector< graphState > &thePath)
Definition: Propagation.cpp:1619
Prop::DoSingleStepB
bool DoSingleStepB(std::vector< graphState > &thePath)
Definition: Propagation.cpp:375
Prop::GetNodesFirstExpanded
uint64_t GetNodesFirstExpanded()
Definition: Propagation.h:456
Prop::InitializeSearch
bool InitializeSearch(GraphEnvironment *env, Graph *_g, graphState from, graphState to, std::vector< graphState > &thePath)
Definition: Propagation.cpp:55
Prop::RelaxOpenNode
void RelaxOpenNode(double f, double g, graphState neighbor, PropUtil::SearchNode &neighborNode, graphState topNodeID)
Definition: Propagation.cpp:189
Prop::Prop
Prop(unsigned int v)
Definition: Propagation.h:436
PI
static const double PI
Definition: GLUtil.h:66
Prop::solutionCost
double solutionCost
Definition: Propagation.h:507
Prop::delayCache
PropUtil::GQueue delayCache
Definition: Propagation.h:537
PropUtil::SearchNodeEqual::operator()
bool operator()(const SearchNode &i1, const SearchNode &i2) const
Definition: Propagation.h:93
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
PropUtil::SearchNode::gCost
double gCost
Definition: Propagation.h:63
PropUtil::TGreater::operator()
bool operator()(const SearchNode &, const SearchNode &) const
Definition: Propagation.h:132
Prop::neighbors
std::vector< graphState > neighbors
Definition: Propagation.h:531
Prop::NodesReopened
long NodesReopened
Definition: Propagation.h:551
PropUtil::GGreater::operator()
bool operator()(const SearchNode &i1, const SearchNode &i2) const
Definition: Propagation.h:116
PROP_DPDLMX
#define PROP_DPDLMX
Definition: Propagation.h:38
UINT32_MAX
#define UINT32_MAX
Definition: Propagation.h:24
Prop::start
graphState start
Definition: Propagation.h:533
Prop::DoSingleStepDP
bool DoSingleStepDP(std::vector< graphState > &thePath)
Definition: Propagation.cpp:1310
PropUtil::SearchNode::SearchNode
SearchNode(graphState curr)
Definition: Propagation.h:51
Prop::goal
graphState goal
Definition: Propagation.h:533
PROP_BPMX
#define PROP_BPMX
Definition: Propagation.h:34
Prop::Broadcast
void Broadcast(int level, int levelcount)
Definition: Propagation.cpp:1185
Prop::delta
double delta
Definition: Propagation.h:546
PropUtil::StateEX::weight
double weight
Definition: Propagation.h:84
Prop::closedSize
long closedSize
Definition: Propagation.h:524
PropUtil::graphGenerator::GetLoc
static void GetLoc(node *n, double &x, double &y, double &z)
Definition: Propagation.h:164
GraphSearchConstants::kYCoordinate
@ kYCoordinate
Definition: GraphEnvironment.h:52
PropUtil::SearchNode::currNode
graphState currNode
Definition: Propagation.h:64
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
OpenListB
A simple & efficient Heap class.
Definition: OpenListB.h:28
PropUtil::StateEX::StateEX
StateEX(graphState s, double w)
Definition: Propagation.h:86
Prop::ReverseProp
void ReverseProp(PropUtil::SearchNode &topNode)
Definition: Propagation.cpp:1043
Prop::DoSingleStepA
bool DoSingleStepA(std::vector< graphState > &thePath)
Definition: Propagation.cpp:221
Prop
Definition: Propagation.h:433
Prop::WaitList
PropUtil::TQueue WaitList
Definition: Propagation.h:544
Prop::F
double F
Definition: Propagation.h:528
Prop::verID
unsigned int verID
Definition: Propagation.h:506
Prop::ExtractPathToStart
void ExtractPathToStart(graphState goalNode, std::vector< graphState > &thePath)
Definition: Propagation.cpp:2429
PropUtil::SearchNodeEX::SearchNodeEX
SearchNodeEX(SearchNode &n, double w)
Definition: Propagation.h:76
PropUtil::PQueue
OpenListB< PropUtil::SearchNode, PropUtil::SearchNodeHash, PropUtil::SearchNodeEqual, PropUtil::SearchNodeCompare, PropUtil::GGreater, PropUtil::FExtract > PQueue
Definition: Propagation.h:421
GraphAlgorithm.h
node::GetLabelF
double GetLabelF(unsigned int index) const
Definition: Graph.h:215
Prop::GetSolutionCost
double GetSolutionCost()
Definition: Propagation.h:497
PropUtil::GGreater
Definition: Propagation.h:115
PropUtil::SearchNodeEqual
Definition: Propagation.h:92
Prop::bpmxLevel
int bpmxLevel
Definition: Propagation.h:509
PropUtil::SearchNodeEX
Definition: Propagation.h:72
Prop::metaexpanded
long metaexpanded
Definition: Propagation.h:519
PropUtil::TGreater
Definition: Propagation.h:131
PropUtil::SearchNodeEX::sn
SearchNode sn
Definition: Propagation.h:73
Prop::Prop
Prop(unsigned int v, double del)
Definition: Propagation.h:443
Prop::fifo
std::deque< graphState > fifo
Definition: Propagation.h:570
PropUtil::SearchNodeEX::weight
double weight
Definition: Propagation.h:74
Prop::env
GraphEnvironment * env
Definition: Propagation.h:534
PROP_DPMX
#define PROP_DPMX
Definition: Propagation.h:35
PropUtil::SearchNode::copy
void copy(double f, double g, graphState curr, graphState prev)
Definition: Propagation.h:55
Prop::GetPath
void GetPath(GraphEnvironment *env, Graph *_g, graphState from, graphState to, std::vector< graphState > &thePath)
Definition: Propagation.cpp:33
Prop::algname
char algname[20]
Definition: Propagation.h:505
Prop::~Prop
virtual ~Prop()
Definition: Propagation.h:450
Prop::DoSingleStepBPMXE
bool DoSingleStepBPMXE(std::vector< graphState > &thePath)
Definition: Propagation.cpp:1888
GraphAlgorithm
Definition: GraphAlgorithm.h:17
Prop::DoSingleSearchStep
bool DoSingleSearchStep(std::vector< graphState > &thePath)
Definition: Propagation.cpp:120
PropUtil::NodeLookupTable
std::unordered_map< graphState, PropUtil::SearchNode > NodeLookupTable
Definition: Propagation.h:423
GraphSearchConstants::kZCoordinate
@ kZCoordinate
Definition: GraphEnvironment.h:53
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
Prop::DoSingleStepApprox
bool DoSingleStepApprox(std::vector< graphState > &thePath)
Definition: Propagation.cpp:774
PropUtil::SearchNode
Definition: Propagation.h:42
PropUtil::SearchNodeCompare::operator()
bool operator()(const SearchNode &i1, const SearchNode &i2) const
Definition: Propagation.h:101
PropUtil::graphGenerator::genFig3
static Graph * genFig3(unsigned int N)
Definition: Propagation.h:280
PropUtil::SearchNode::isGoal
bool isGoal
Definition: Propagation.h:67
OpenListB.h
Prop::reopenings
int reopenings
Definition: Propagation.h:538
PropUtil::graphGenerator::genFig1
static Graph * genFig1(unsigned int N)
Definition: Propagation.h:171
PropUtil::SearchNodeCompare
Definition: Propagation.h:98
GraphEnvironment
Definition: GraphEnvironment.h:291
PropUtil::TQueue
OpenListB< PropUtil::SearchNode, PropUtil::SearchNodeHash, PropUtil::SearchNodeEqual, PropUtil::TGreater, PropUtil::GGreater, PropUtil::FExtract > TQueue
Definition: Propagation.h:429
Prop::GetNodesExpanded
uint64_t GetNodesExpanded()
Definition: Propagation.h:453
PROP_BPMXE
#define PROP_BPMXE
Definition: Propagation.h:36
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
SearchEnvironment.h
Prop::FCache
PropUtil::GQueue FCache
Definition: Propagation.h:536
Prop::DoSingleStepDelay
bool DoSingleStepDelay(std::vector< graphState > &thePath)
Definition: Propagation.cpp:1037
GraphEnvironment.h
edge
Edge class for connections between node in a Graph.
Definition: Graph.h:129
Generated by   doxygen 1.8.17