HOG2
WeightedVertexGraph.h
Go to the documentation of this file.
1 //
2 // WeightedVertexGraph.h
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 7/1/17.
6 // Copyright © 2017 University of Denver. All rights reserved.
7 //
8 
9 #ifndef WeightedVertexGraph_h
10 #define WeightedVertexGraph_h
11 
12 #include "TemplateAStar.h"
13 #include "SVGUtil.h"
14 #include <map>
15 #include <sstream>
16 #include "StringUtils.h"
17 
18 template <class state, class action, class environment>
19 class BidirectionalProblemAnalyzer {
20 public:
21  BidirectionalProblemAnalyzer(const state &s, const state &g, environment *e,
22  Heuristic<state> *f, Heuristic<state> *b)
23  :start(s), goal(g), e(e), f(f), b(b)
24  {
25  drawFullGraph = false;
26  drawProblemInstance = true;
27  drawMinimumVC = true;
28  drawAllG = true;
29  drawStatistics = true;
30  flipBackwardsGCost = false;
31  drawSumOnEdge = false;
32  drawShortenedEdges = true;
33  BuildDataStructures();
34  }
35 
36  void BuildDataStructures()
37  {
38  std::vector<state> path;
39  astarf.SetHeuristic(f);
40  astarf.GetPath(e, start, goal, path);
41  astarb.SetHeuristic(b);
42  astarb.GetPath(e, goal, start, path);
43  optCost = e->GetPathLength(path);
44  forwardOptG = -1;
45  backwardOptG = -1;
46  forwardSum = 0;
47  backwardSum = 0;
48  optCostStr = "Optimal cost: "+std::to_string(optCost);
49  if (astarf.GetNecessaryExpansions() == 0 || astarb.GetNecessaryExpansions() == 0)
50  {
51  printf("No necessary expansions\n");
52  return;
53  }
54  for (int x = 0; x < astarf.GetNumItems(); x++)
55  {
56  const auto &i = astarf.GetItem(x);
57  if (i.where != kClosedList)
58  continue;
59  auto i2 = m_f.find(i.g);
60  if (fgreatereq(i.g+i.h, optCost))
61  {
62  if (fless(i.g, optCost) && (i2 == m_f.end()) && drawAllG)
63  {
64  m_f.insert({i.g, 0});
65  }
66  }
67  else {
68  if (i2 == m_f.end())
69  {
70  m_f.insert({i.g, 1});
71  }
72  else {
73  i2->second++;
74  }
75  }
76  }
77  if (m_f.size() == 0)
78  {
79  printf("No forward item\n");
80  return;
81  }
82  for (int x = 0; x < astarb.GetNumItems(); x++)
83  {
84  const auto &i = astarb.GetItem(x);
85  if (i.where != kClosedList)
86  continue;
87  auto i2 = m_b.find(i.g);
88  if (fgreatereq(i.g+i.h, optCost))
89  {
90  if (fless(i.g, optCost) && (i2 == m_b.end()) && drawAllG)
91  {
92  m_b.insert({i.g, 0});
93  }
94  }
95  else {
96  if (i2 == m_b.end())
97  {
98  m_b.insert({i.g, 1});
99  }
100  else {
101  i2->second++;
102  }
103  }
104  }
105  if (m_b.size() == 0)
106  {
107  printf("No backward item\n");
108  return;
109  }
110  // std::cout << "Forward\n";
111  for (auto i = m_f.begin(); i != m_f.end(); i++)
112  {
113  // std::cout << i->first << " : " << i->second << "\n";
114  forwardSum += i->second;
115  }
116  // std::cout << "Backward\n";
117  for (auto i = m_b.begin(); i != m_b.end(); i++)
118  {
119  // std::cout << i->first << " : " << i->second << "\n";
120  backwardSum += i->second;
121  }
122  height = 75*std::max(m_f.size(), m_b.size())+50;
123  width = height*0.5;
124 
125  totalWork = backwardSum;
126  const int forwardCopy = forwardSum;
127  const int backwardCopy = backwardSum;
128  // printf("--At f: %1f b:%1f work is %d\n", -1.0f, m_b.rbegin()->first, backwardSum);
129  {
130  // compute optimal partition
131  auto fi = m_f.begin();
132  auto bi = m_b.rbegin();
133  backwardOptG = bi->first;
134  forwardOptG = -1;
135  forwardSum = 0;
136 
137  // fi points to the first unused entry
138  // bi points to the last used entry
139  while (true)
140  {
141  do {
142  // Remove the next backwards entry
143  backwardSum -= bi->second;
144  // printf("Subtract %d from back\n", bi->second);
145  bi++;
146  if (bi == m_b.rend())
147  break;
148  } while (fi->first+bi->first > optCost);
149  if (bi == m_b.rend())
150  break;
151  // Find all the necessary forward entries to maintain the vertex cover
152  while (true)
153  {
154  forwardSum += fi->second;
155  // printf("--Add %d to front\n", fi->second);
156  fi++;
157  // If we reach one end, we can remove everything in the other direction
158  if (fi == m_f.end())
159  {
160  while (bi != m_b.rend())
161  {
162  backwardSum -= bi->second;
163  bi++;
164  }
165  break;
166  }
167  // printf("%1.1f+%1.1f vs %1.1f\n", fi->first, bi->first, optCost);
168  auto tmp = bi;
169  tmp--;
170  if (fi->first+(tmp)->first >= optCost)
171  break;
172 
173  }
174  // printf("Considering: %d + %d = %d\n", forwardSum, backwardSum, forwardSum+backwardSum);
175  if (fi == m_f.end())
176  break;
177  // printf("--At f: %1f b:%1f work is %d\n", fi->first, (bi == m_b.rend())?-1:bi->first, forwardSum+backwardSum);
178 
179  if (forwardSum+backwardSum < totalWork)
180  {
181  totalWork = forwardSum+backwardSum;
182  forwardOptG = fi->first;
183  if (bi == m_b.rend())
184  backwardOptG = -1;
185  else
186  backwardOptG = bi->first;
187  }
188  }
189  if (fi != m_f.end())
190  {
191  forwardSum += fi->second;
192  fi++;
193  }
194  fi--;
195  // printf("--At f: %1f b:%1f work is %d\n", fi->first, -1.0f, forwardSum+backwardSum);
196  if (forwardSum+backwardSum < totalWork)
197  {
198  totalWork = forwardSum+backwardSum;
199  forwardOptG = fi->first;
200  backwardOptG = -1;
201  }
202  }
203 
204  {
205  printf("Forward/Backward/Min: %d %d %d %s\n", forwardCopy, backwardCopy, totalWork,
206  (std::min(forwardCopy, backwardCopy)!=totalWork)?"bidirectional wins!":"" );
207  forwardSum = forwardCopy;
208  backwardSum = backwardCopy;
209  }
210  }
211 
212  int GetMinWork()
213  {
214  return totalWork;
215  }
216 
217  int GetForwardWork()
218  {
219  return forwardSum;
220  }
221 
222  int GetBackwardWork()
223  {
224  return backwardSum;
225  }
226 
227  double GetForwardMaxG()
228  {
229  return m_f.rbegin()->first;
230 
231  }
232 
233  double GetMaxG()
234  {
235  return std::max(m_f.rbegin()->first, m_b.rbegin()->first);
236  }
237 
238  double GetBackwardMaxG()
239  {
240  return m_b.rbegin()->first;
241  }
242 
243  size_t GetNumGCosts()
244  {
245  return std::max(m_f.size(), m_b.size());
246  }
247 
248  void SaveSVG(const char *filename)
249  {
250  bool eshed = false;
251  const int kLRMargin = 150;
252  const int kTopMargin = 75;
253  const int kBottomMargin = 50;
254 
255  const int kCountTextSize = 25;
256  const int kInstanceTextSize = 20;
257  const int kStatsTextSize = 20;
258  const int kNodeGSize = 30;
259 
260  const int kNodeRadius = 25;
261  const int kNodeGap = 75;
262  const int epsilon = 0;
263 
264  height = kNodeGap*std::max(m_f.size(), m_b.size())+kBottomMargin;
265  if (eshed) height += kNodeGap;
266  width = height*0.5;
267 
268 
269 // printf("Opt: %1.2f, For: %1.2f, Back: %1.2f\n", optCost, forwardOptG, backwardOptG);
270  std::string s;
271  // 10% margin on all sides of image
272  s = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width = \""+std::to_string(width)+"\" height = \""+std::to_string(height)+"\" ";
273  s += "preserveAspectRatio = \"none\" ";
274  s += ">\n";
275 
276  int fcnt = 0;
277  int64_t fsum = 0;
278 
279  if (flipBackwardsGCost && drawSumOnEdge)
280  s += SVGDrawText(width/2.0, (kTopMargin+kNodeGap*fcnt+height-kNodeGap*(m_b.size()-1)-kBottomMargin)/2.0-kCountTextSize,
281  to_string_separator(backwardSum).c_str(), Colors::black, kCountTextSize);
282 
283  // Draw Edges between sides
284  for (auto i = m_f.begin(); i != m_f.end(); i++)
285  {
286  fsum += i->second;
287  int64_t bsum = backwardSum;
288  if (drawAllG || i->second != 0)
289  {
290  int bcnt = m_b.size()-1;
291  bool drewBest = false;
292  for (auto j = m_b.rbegin(); j != m_b.rend(); j++)
293  {
294  bsum -= j->second;
295  auto tmp = i;
296  tmp++;
297 
298  if (drawFullGraph)
299  {
300  if (fless(i->first + j->first+epsilon, optCost) && j->second != 0)
301  {
302  if (flipBackwardsGCost)
303  {
304  s += SVGDrawLine(kLRMargin, kTopMargin+kNodeGap*fcnt, width-kLRMargin, height-kNodeGap*bcnt-kBottomMargin, 1, Colors::black);
305  }
306  else {
307  s += SVGDrawLine(kLRMargin, kTopMargin+kNodeGap*fcnt, width-kLRMargin, kTopMargin+kNodeGap*bcnt, 1, Colors::black);
308  }
309  }
310  }
311  else {
312  if (!drewBest &&
313  (fless(i->first + j->first+epsilon, optCost) &&
314  ((tmp) == m_f.end() || fgreatereq((tmp)->first + j->first + epsilon, optCost))
315  && (j->second != 0 || drawSumOnEdge)))
316  {
317  drewBest = true;
318  if (flipBackwardsGCost) {
319  s += SVGDrawLine(kLRMargin, kTopMargin+kNodeGap*fcnt, width-kLRMargin, height-kNodeGap*bcnt-kBottomMargin, 1, Colors::black);
320  if (drawSumOnEdge)
321  {
322  if (bsum == 0)
323  s += SVGDrawText(width/2.0, (kTopMargin+kNodeGap*fcnt+height-kNodeGap*bcnt-kBottomMargin)/2.0+kCountTextSize, to_string_separator(fsum+bsum).c_str(), Colors::black, kCountTextSize);
324  else
325  s += SVGDrawText(width/2.0, (kTopMargin+kNodeGap*fcnt+height-kNodeGap*bcnt-kBottomMargin)/2.0+kNodeGap/2.0, to_string_separator(fsum+bsum).c_str(), Colors::black, kCountTextSize);
326  }
327  }
328  else {
329  s += SVGDrawLine(kLRMargin, kTopMargin+kNodeGap*fcnt, width-kLRMargin, kTopMargin+kNodeGap*bcnt, 1, Colors::black);
330  }
331  //break;
332  }
333  else {
334  if (drawShortenedEdges)
335  {
336  if (fless(i->first + j->first + epsilon, optCost))
337  {
338  double p1x, p1y, p2x, p2y;
339  p1x = kLRMargin;
340  p1y = kTopMargin+kNodeGap*fcnt;
341  p2x = width-kLRMargin;
342 
343  if (flipBackwardsGCost)
344  {
345  p2y = height-kNodeGap*bcnt-kBottomMargin;
346  }
347  else {
348  p2y = kTopMargin+kNodeGap*bcnt;
349  }
350  double length = sqrt((p1x-p2x)*(p1x-p2x)+(p1y-p2y)*(p1y-p2y));
351  double scale = (1.5*kNodeRadius)/length;
352  s += SVGDrawLine(p1x, p1y, p1x+(p2x-p1x)*scale, p1y+(p2y-p1y)*scale, 1, Colors::black);
353  s += SVGDrawLine(p2x-(p2x-p1x)*scale, p2y-(p2y-p1y)*scale, p2x, p2y, 1, Colors::black);
354  }
355  }
356  }
357  }
358  bcnt--;
359  }
360  }
361  fcnt++;
362  }
363 
364  // Draw forward nodes
365  int cnt = 0;
366 // printf("Min forward: %1.2f; Min backward: %1.2f\n", forwardOptG, backwardOptG);
367  for (auto i = m_f.begin(); i != m_f.end(); i++)
368  {
369  if (!drawAllG && i->second == 0)
370  {
371  cnt++;
372  continue;
373  }
374  std::string tmp = std::to_string((int)i->first);
375 // std::cout << i->first << " : " << i->second << "\n";
376  if ((fless(i->first, forwardOptG) || backwardOptG == -1) && (i->second != 0 || drawSumOnEdge) && drawMinimumVC)
377  {
378  s += SVGDrawCircle(kLRMargin, kTopMargin+kNodeGap*cnt, kNodeRadius, Colors::lightblue);
379  }
380  else {
381  s += SVGDrawCircle(kLRMargin, kTopMargin+kNodeGap*cnt, kNodeRadius, Colors::lightgray);
382  }
383  s += SVGFrameCircle(kLRMargin, kTopMargin+kNodeGap*cnt, kNodeRadius, 1, Colors::black);
384  s += SVGDrawText(kLRMargin, kTopMargin+kNodeGap*cnt, tmp.c_str(), Colors::black, kNodeGSize);
385  //if (i->second != 0)
386  {
387  tmp = to_string_separator(i->second);
388  //s += SVGDrawText((kLRMargin-kNodeRadius)/2, kTopMargin+kNodeGap*cnt, tmp.c_str(), Colors::black, kCountTextSize);
389  s += SVGDrawText(kLRMargin-3*kNodeRadius/2, kTopMargin+kNodeGap*cnt, tmp.c_str(), Colors::black, kCountTextSize, 0, SVG::kRight);
390  }
391  cnt++;
392  }
393 
394  // Draw backwards nodes
395  cnt = 0;
396  for (auto i = m_b.begin(); i != m_b.end(); i++)
397  {
398  if (!drawAllG && i->second == 0)
399  {
400  cnt++;
401  continue;
402  }
403  std::string tmp = std::to_string((int)i->first);
404  //std::cout << i->first << " : " << i->second << "\n";
405  int loc = kTopMargin+kNodeGap*cnt;
406  if (flipBackwardsGCost)
407  {
408  loc = height-kBottomMargin-kNodeGap*cnt;
409  }
410  if (flesseq(i->first, backwardOptG) && (i->second != 0 || drawSumOnEdge) && drawMinimumVC)
411  s += SVGDrawCircle(width-kLRMargin, loc, kNodeRadius, Colors::lightblue);
412  else
413  s += SVGDrawCircle(width-kLRMargin, loc, kNodeRadius, Colors::lightgray);
414  s += SVGFrameCircle(width-kLRMargin, loc, kNodeRadius, 1, Colors::black);
415  s += SVGDrawText(width-kLRMargin, loc, tmp.c_str(), Colors::black, kNodeGSize);
416  //tmp = std::to_string((int)i->second);
417  //if (i->second != 0)
418  {
419  tmp = to_string_separator(i->second);
420  //s += SVGDrawText(width-(kLRMargin-kNodeRadius)/2, loc, tmp.c_str(), Colors::black, kCountTextSize, 0, SVG::kRight);
421  s += SVGDrawText(width-kLRMargin+3*kNodeRadius/2, loc, tmp.c_str(), Colors::black, kCountTextSize, 0, SVG::kLeft);
422  }
423  cnt++;
424  }
425 
426  if (drawStatistics)
427  {
428  s += SVGDrawText(width/2, height-4*kStatsTextSize, optCostStr.c_str(), Colors::black, kStatsTextSize);
429  optCostStr = "Forward A*: "+std::to_string(astarf.GetNecessaryExpansions());
430  s += SVGDrawText(width/2, height-3*kStatsTextSize, optCostStr.c_str(), Colors::black, kStatsTextSize);
431  optCostStr = "Backward A*: "+std::to_string(astarb.GetNecessaryExpansions());
432  s += SVGDrawText(width/2, height-2*kStatsTextSize, optCostStr.c_str(), Colors::black, kStatsTextSize);
433  optCostStr = "Optimal: "+std::to_string(totalWork);
434  s += SVGDrawText(width/2, height-kStatsTextSize, optCostStr.c_str(), Colors::black, kStatsTextSize);
435  }
436  if (drawProblemInstance)
437  {
438  optCostStr = "Domain: "+e->GetName();
439  s += SVGDrawText(width/2, kInstanceTextSize, optCostStr.c_str(), Colors::black, kInstanceTextSize);
440  std::stringstream tmp;
441  tmp << "Start: " << start;
442  s += SVGDrawText(width/2, 2*kInstanceTextSize, tmp.str().c_str(), Colors::black, kInstanceTextSize);
443  tmp.str("");
444  tmp << "Goal: " << goal;
445  s += SVGDrawText(width/2, 3*kInstanceTextSize, tmp.str().c_str(), Colors::black, kInstanceTextSize);
446  }
447  s += SVGDrawText(kLRMargin, kTopMargin-2*kNodeRadius, "g<tspan dy =\"15\">F</tspan>", Colors::black, kCountTextSize);
448  s += SVGDrawText(width-kLRMargin, kTopMargin-2*kNodeRadius, "g<tspan dy =\"15\">B</tspan>", Colors::black, kCountTextSize);
449 
450  if (filename != 0)
451  {
452  std::fstream svgFile;
453  svgFile.open(filename, std::fstream::out | std::fstream::trunc);
454  svgFile << s;
455  svgFile << "</svg>";
456  svgFile.close();
457  printf("Generated SVG '%s'\n", filename);
458  }
459  }
460 
461  void SaveSVG(const char *filename, int groupSize)
462  {
463  if (groupSize <= 0)
464  groupSize = 1;
465  int localHeight = 75*(std::max(m_f.size(), m_b.size())+groupSize-1)/groupSize+50;
466  int localWidth = localHeight*0.5;
467  std::string s;
468  // 10% margin on all sides of image
469  s = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width = \""+std::to_string(localWidth)+"\" height = \""+std::to_string(localHeight)+"\" ";
470  s += "preserveAspectRatio = \"none\" ";
471  s += ">\n";
472 
473  int fcnt = 0;
474  int lastF = -1, lastB = -1;
475  for (auto i = m_f.begin(); i != m_f.end(); i++)
476  {
477  //if (i->second != 0)
478  {
479  int bcnt = m_b.size()-1;
480  for (auto j = m_b.rbegin(); j != m_b.rend(); j++)
481  {
482  auto tmp = i;
483  tmp++;
484  if (drawFullGraph)
485  {
486  if (fless(i->first + j->first, optCost) && j->second != 0)
487  {
488  if (fcnt/groupSize != lastF && bcnt/groupSize != lastB)
489  {
490  s += SVGDrawLine(100, 75+75*(fcnt/groupSize), localWidth-100, 75+75*(bcnt/groupSize), 1, Colors::black);
491  lastF = fcnt/groupSize;
492  lastB = bcnt/groupSize;
493  }
494  }
495  }
496  else {
497  if (fless(i->first + j->first, optCost) &&
498  ((tmp) == m_f.end() || fgreatereq((tmp)->first + j->first, optCost))
499  && j->second != 0)
500  {
501  if (fcnt/groupSize != lastF && bcnt/groupSize != lastB)
502  {
503  s += SVGDrawLine(100, 75+75*(fcnt/groupSize), localWidth-100, 75+75*(bcnt/groupSize), 1, Colors::black);
504  lastF = fcnt/groupSize;
505  lastB = bcnt/groupSize;
506  }
507  break;
508  }
509  }
510  bcnt--;
511  }
512  }
513  fcnt++;
514  }
515 
516  int cnt = 0;
517  uint64_t nodes = 0;
518  for (auto i = m_f.begin(); i != m_f.end(); i++)
519  {
520  if (cnt%groupSize == 0)
521  {
522  //std::cout << i->first << " : " << i->second << "\n";
523  if (flesseq(i->first, forwardOptG) && i->second != 0 && drawMinimumVC)
524  s += SVGDrawCircle(100, 75+75*cnt/groupSize, 25, Colors::lightblue);
525  else
526  s += SVGDrawCircle(100, 75+75*cnt/groupSize, 25, Colors::lightgray);
527  s += SVGFrameCircle(100, 75+75*cnt/groupSize, 25, 1, Colors::black);
528 
529  std::string tmp = std::to_string((int)i->first);
530  s += SVGDrawText(100, 75+75*(cnt/groupSize), tmp.c_str(), Colors::black, 30);
531  nodes = 0;
532  }
533  nodes += i->second;
534  if (cnt%groupSize == groupSize-1)
535  {
536  std::string tmp = std::to_string((int)nodes);
537  s += SVGDrawText(37.5, 75+75*(cnt/groupSize), tmp.c_str(), Colors::black, 20);
538  }
539  cnt++;
540  }
541  if (cnt%groupSize != 0)
542  {
543  std::string tmp = std::to_string((int)nodes);
544  s += SVGDrawText(37.5, 75+75*(cnt/groupSize), tmp.c_str(), Colors::black, 20);
545  }
546  cnt = 0;
547  nodes = 0;
548  for (auto i = m_b.begin(); i != m_b.end(); i++)
549  {
550  if (cnt%groupSize == 0)
551  {
552  //std::cout << i->first << " : " << i->second << "\n";
553  if (flesseq(i->first, backwardOptG) && i->second != 0 && drawMinimumVC)
554  s += SVGDrawCircle(localWidth-100, 75+75*(cnt/groupSize), 25, Colors::lightblue);
555  else
556  s += SVGDrawCircle(localWidth-100, 75+75*(cnt/groupSize), 25, Colors::lightgray);
557  s += SVGFrameCircle(localWidth-100, 75+75*(cnt/groupSize), 25, 1, Colors::black);
558 
559  std::string tmp = std::to_string((int)i->first);
560  s += SVGDrawText(localWidth-100, 75+75*(cnt/groupSize), tmp.c_str(), Colors::black, 30);
561  nodes = 0;
562  }
563  nodes += i->second;
564  if (cnt%groupSize == groupSize-1)
565  {
566  std::string tmp = std::to_string((int)nodes);
567  s += SVGDrawText(localWidth-37.5, 75+75*(cnt/groupSize), tmp.c_str(), Colors::black, 20);
568  }
569  cnt++;
570  }
571  if (cnt%groupSize != 0)
572  {
573  std::string tmp = std::to_string((int)nodes);
574  s += SVGDrawText(localWidth-37.5, 75+75*(cnt/groupSize), tmp.c_str(), Colors::black, 20);
575  }
576 
577  if (drawStatistics)
578  {
579  s += SVGDrawText(localWidth/2, localHeight-100, optCostStr.c_str(), Colors::black, 30);
580  optCostStr = "Forward A*: "+std::to_string(astarf.GetNecessaryExpansions());
581  s += SVGDrawText(localWidth/2, localHeight-70, optCostStr.c_str(), Colors::black, 20);
582  optCostStr = "Backward A*: "+std::to_string(astarb.GetNecessaryExpansions());
583  s += SVGDrawText(localWidth/2, localHeight-45, optCostStr.c_str(), Colors::black, 20);
584  optCostStr = "Optimal: "+std::to_string(totalWork);
585  s += SVGDrawText(localWidth/2, localHeight-20, optCostStr.c_str(), Colors::black, 20);
586  }
587  if (drawProblemInstance)
588  {
589  optCostStr = "Domain: "+e->GetName();
590  s += SVGDrawText(localWidth/2, 20, optCostStr.c_str(), Colors::black, 20);
591  std::stringstream tmp;
592  tmp << "Start: " << start;
593  s += SVGDrawText(localWidth/2, 45, tmp.str().c_str(), Colors::black, 20);
594  tmp.str("");
595  tmp << "Goal: " << goal;
596  s += SVGDrawText(localWidth/2, 70, tmp.str().c_str(), Colors::black, 20);
597  }
598  s += SVGDrawText(100, 20, "g<tspan dy =\"15\">F</tspan>", Colors::black, 20);
599  s += SVGDrawText(localWidth-100, 20, "g<tspan dy =\"15\">B</tspan>", Colors::black, 20);
600 
601  if (filename != 0)
602  {
603  std::fstream svgFile;
604  svgFile.open(filename, std::fstream::out | std::fstream::trunc);
605  svgFile << s;
606  svgFile << "</svg>";
607  svgFile.close();
608  printf("Generated SVG '%s'\n", filename);
609  }
610  }
611 
612 
613  static uint64_t GetWeightedVertexGraph(const state &start, const state &goal, environment *e, Heuristic<state> *f, Heuristic<state> *b, const char *filename = 0)
614  {
615  BidirectionalProblemAnalyzer analyze(start, goal, e, f, b);
616  if (filename != 0)
617  analyze.SaveSVG(filename);
618  return analyze.totalWork;
619  }
620 private:
621  state start, goal;
622  environment *e;
623  Heuristic<state> *f, *b;
624  std::map<double, int> m_f, m_b;
625 
626  TemplateAStar<state, action, environment> astarf;
627  TemplateAStar<state, action, environment> astarb;
628  int forwardSum;
629  int backwardSum;
630  int totalWork;
631  double optCost;
632  int height, width;
633  std::string optCostStr;
634  double forwardOptG;
635  double backwardOptG;
636 
637 public:
638  bool drawFullGraph;
639  bool drawProblemInstance;
640  bool drawMinimumVC;
641  bool drawAllG;
642  bool drawStatistics;
643  bool flipBackwardsGCost;
644  bool drawSumOnEdge; // Note, this only applies if we aren't drawing the full graph and we are flipping the backwards g-costs
645  bool drawShortenedEdges; // only applies if we aren't drawing the full graph
646 };
647 
648 #endif /* WeightedVertexGraph_h */
BidirectionalProblemAnalyzer::forwardSum
int forwardSum
Definition: WeightedVertexGraph.h:628
BidirectionalProblemAnalyzer::drawMinimumVC
bool drawMinimumVC
Definition: WeightedVertexGraph.h:640
min
double min(double a, double b)
Definition: FPUtil.h:35
TemplateAStar::GetNecessaryExpansions
uint64_t GetNecessaryExpansions() const
Definition: TemplateAStar.h:584
BidirectionalProblemAnalyzer::drawAllG
bool drawAllG
Definition: WeightedVertexGraph.h:641
fgreatereq
bool fgreatereq(double a, double b)
Definition: FPUtil.h:31
TemplateAStar::SetHeuristic
void SetHeuristic(Heuristic< state > *h)
Definition: TemplateAStar.h:131
BidirectionalProblemAnalyzer::optCost
double optCost
Definition: WeightedVertexGraph.h:631
Heuristic
Definition: Heuristic.h:30
BidirectionalProblemAnalyzer::GetForwardWork
int GetForwardWork()
Definition: WeightedVertexGraph.h:217
SVGDrawText
std::string SVGDrawText(float x1, float y1, const char *txt, rgbColor c, double size, const char *typeface, SVG::svgAlignment align, SVG::svgBaseline base)
Definition: SVGUtil.cpp:227
Colors::lightblue
const rgbColor lightblue
Definition: Colors.h:144
BidirectionalProblemAnalyzer::drawShortenedEdges
bool drawShortenedEdges
Definition: WeightedVertexGraph.h:645
BidirectionalProblemAnalyzer::GetBackwardWork
int GetBackwardWork()
Definition: WeightedVertexGraph.h:222
BidirectionalProblemAnalyzer::m_f
std::map< double, int > m_f
Definition: WeightedVertexGraph.h:624
SVGDrawCircle
std::string SVGDrawCircle(double x, double y, double radius, rgbColor c)
Definition: SVGUtil.cpp:60
BidirectionalProblemAnalyzer::drawFullGraph
bool drawFullGraph
Definition: WeightedVertexGraph.h:638
BidirectionalProblemAnalyzer::drawSumOnEdge
bool drawSumOnEdge
Definition: WeightedVertexGraph.h:644
BidirectionalProblemAnalyzer::GetMaxG
double GetMaxG()
Definition: WeightedVertexGraph.h:233
BidirectionalProblemAnalyzer::totalWork
int totalWork
Definition: WeightedVertexGraph.h:630
BidirectionalProblemAnalyzer::BidirectionalProblemAnalyzer
BidirectionalProblemAnalyzer(const state &s, const state &g, environment *e, Heuristic< state > *f, Heuristic< state > *b)
Definition: WeightedVertexGraph.h:21
BidirectionalProblemAnalyzer::goal
state goal
Definition: WeightedVertexGraph.h:621
TemplateAStar::GetPath
void GetPath(environment *env, const state &from, const state &to, std::vector< state > &thePath)
Perform an A* search between two states.
Definition: TemplateAStar.h:214
BidirectionalProblemAnalyzer::f
Heuristic< state > * f
Definition: WeightedVertexGraph.h:623
loc
Definition: MapGenerators.cpp:296
Colors::black
const rgbColor black
Definition: Colors.h:119
SVGUtil.h
BidirectionalProblemAnalyzer::GetWeightedVertexGraph
static uint64_t GetWeightedVertexGraph(const state &start, const state &goal, environment *e, Heuristic< state > *f, Heuristic< state > *b, const char *filename=0)
Definition: WeightedVertexGraph.h:613
BidirectionalProblemAnalyzer::backwardOptG
double backwardOptG
Definition: WeightedVertexGraph.h:635
BidirectionalProblemAnalyzer::height
int height
Definition: WeightedVertexGraph.h:632
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
BidirectionalProblemAnalyzer::astarb
TemplateAStar< state, action, environment > astarb
Definition: WeightedVertexGraph.h:627
TemplateAStar< state, action, environment >
BidirectionalProblemAnalyzer::SaveSVG
void SaveSVG(const char *filename)
Definition: WeightedVertexGraph.h:248
BidirectionalProblemAnalyzer::GetMinWork
int GetMinWork()
Definition: WeightedVertexGraph.h:212
TemplateAStar.h
BidirectionalProblemAnalyzer::astarf
TemplateAStar< state, action, environment > astarf
Definition: WeightedVertexGraph.h:626
TemplateAStar::GetItem
const AStarOpenClosedDataWithF< state > & GetItem(unsigned int which)
Definition: TemplateAStar.h:116
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
to_string_separator
std::string to_string_separator(int i)
Definition: StringUtils.cpp:26
StringUtils.h
BidirectionalProblemAnalyzer::width
int width
Definition: WeightedVertexGraph.h:632
BidirectionalProblemAnalyzer::drawStatistics
bool drawStatistics
Definition: WeightedVertexGraph.h:642
path
std::vector< xyLoc > path
Definition: Sample.cpp:43
SVGDrawLine
std::string SVGDrawLine(float x1, float y1, float x2, float y2, float width, rgbColor c)
Definition: SVGUtil.cpp:192
BidirectionalProblemAnalyzer::e
environment * e
Definition: WeightedVertexGraph.h:622
BidirectionalProblemAnalyzer
Definition: WeightedVertexGraph.h:19
BidirectionalProblemAnalyzer::m_b
std::map< double, int > m_b
Definition: WeightedVertexGraph.h:624
BidirectionalProblemAnalyzer::GetNumGCosts
size_t GetNumGCosts()
Definition: WeightedVertexGraph.h:243
TemplateAStar::GetNumItems
const int GetNumItems()
Definition: TemplateAStar.h:115
BidirectionalProblemAnalyzer::start
state start
Definition: WeightedVertexGraph.h:621
SVG::kLeft
@ kLeft
Definition: SVGUtil.h:19
BidirectionalProblemAnalyzer::SaveSVG
void SaveSVG(const char *filename, int groupSize)
Definition: WeightedVertexGraph.h:461
BidirectionalProblemAnalyzer::optCostStr
std::string optCostStr
Definition: WeightedVertexGraph.h:633
BidirectionalProblemAnalyzer::forwardOptG
double forwardOptG
Definition: WeightedVertexGraph.h:634
BidirectionalProblemAnalyzer::drawProblemInstance
bool drawProblemInstance
Definition: WeightedVertexGraph.h:639
SVG::kRight
@ kRight
Definition: SVGUtil.h:20
BidirectionalProblemAnalyzer::BuildDataStructures
void BuildDataStructures()
Definition: WeightedVertexGraph.h:36
BidirectionalProblemAnalyzer::GetForwardMaxG
double GetForwardMaxG()
Definition: WeightedVertexGraph.h:227
path
A linked list of nodes which form a continuous path.
Definition: Path.h:20
Colors::lightgray
const rgbColor lightgray
Definition: Colors.h:125
BidirectionalProblemAnalyzer::backwardSum
int backwardSum
Definition: WeightedVertexGraph.h:629
BidirectionalProblemAnalyzer::GetBackwardMaxG
double GetBackwardMaxG()
Definition: WeightedVertexGraph.h:238
SVGFrameCircle
std::string SVGFrameCircle(double x, double y, double radius, double border, rgbColor c)
Definition: SVGUtil.cpp:51
flesseq
bool flesseq(double a, double b)
Definition: FPUtil.h:30
kClosedList
@ kClosedList
Definition: AStarOpenClosed.h:29
BidirectionalProblemAnalyzer::flipBackwardsGCost
bool flipBackwardsGCost
Definition: WeightedVertexGraph.h:643
BidirectionalProblemAnalyzer::b
Heuristic< state > * b
Definition: WeightedVertexGraph.h:623
Generated by   doxygen 1.8.17