HOG2
LoadedCliqueAbstraction.cpp
Go to the documentation of this file.
1 /*
2  * $Id: LoadedCliqueAbstraction.cpp
3  * hog2
4  *
5  * Created by Nathan Sturtevant on 3/10/06.
6  * Modified by Nathan Sturtevant on 02/29/20.
7  *
8  * This file is part of HOG2. See https://github.com/nathansttt/hog2 for licensing information.
9  *
10  */
11 
12 #include "LoadedCliqueAbstraction.h"
13 
14 using namespace std;
15 using namespace GraphAbstractionConstants;
16 
17 #include "Heap.h"
18 #include "FPUtil.h"
19 #include <cmath>
20 #include <memory>
21 #include <vector>
22 #include <assert.h>
23 #include <string.h>
24 
25 enum {
26  kQuiet = 0x00,
27  kBuildGraph = 0x01,
28  kRepairGraph = 0x02,
29  kMiscMessages = 0x04
30 };
31 
32 const static int verbose = kMiscMessages;//kMiscMessages;//kRepairGraph;
33 
40 LoadedCliqueAbstraction::LoadedCliqueAbstraction(char *fname)
41 :GraphAbstraction()
42 {
43  levelDraw = 1;
44  buildAbstractions(loadGraph(fname));
45 }
46 
47 LoadedCliqueAbstraction::LoadedCliqueAbstraction( Graph *g )
48 :GraphAbstraction()
49 {
50  assert( g != NULL );
51  levelDraw = 1;
52  buildAbstractions( g );
53 }
54 
55 LoadedCliqueAbstraction::~LoadedCliqueAbstraction()
56 {
57  cleanMemory();
58 }
59 
60 double LoadedCliqueAbstraction::h(node *a, node *b)
61 {
62  // const double root2m1 = sqrt(2.0)-1;
63  // double answer;// = sqrt((rv1.x-rv2.x)*(rv1.x-rv2.x)+(rv1.y-rv2.y)*(rv1.y-rv2.y)+(rv1.z-rv2.z)*(rv1.z-rv2.z));
64  // if (fabs(rv1.x-rv2.x) < fabs(rv1.y-rv2.y)) {
65  // answer = root2m1*fabs(rv1.x-rv2.x)+fabs(rv1.y-rv2.y);
66  // } else {
67  // answer = root2m1*fabs(rv1.y-rv2.y)+fabs(rv1.x-rv2.x);
68  // }
69  // return answer;
70  if (a->GetLabelF(kXCoordinate) == kUnknownPosition)
71  GetNodeLoc(a);
72  if (b->GetLabelF(kXCoordinate) == kUnknownPosition)
73  GetNodeLoc(b);
74  double d1 = a->GetLabelF(kXCoordinate)-b->GetLabelF(kXCoordinate);
75  double d2 = a->GetLabelF(kYCoordinate)-b->GetLabelF(kYCoordinate);
76  double d3 = a->GetLabelF(kZCoordinate)-b->GetLabelF(kZCoordinate);
77  return sqrt(d1*d1+d2*d2+d3*d3);
78 }
79 
80 void LoadedCliqueAbstraction::ToggleDrawAbstraction(int which)
81 {
82  bool drawThis = ((levelDraw>>which)&0x1);
83  if (!drawThis)
84  levelDraw |= (1<<which);
85  else
86  levelDraw = levelDraw&(~(1<<which));
87 }
88 
89 void LoadedCliqueAbstraction::OpenGLDraw() const
90 {
91  glDisable(GL_LIGHTING);
92  for (unsigned int x = 0; x < abstractions.size(); x++)
93  {
94  if ((levelDraw >> x) & 1)
95  DrawGraph(abstractions[x]);
96  //glCallList(displayLists[x]);
97  }
98  glEnable(GL_LIGHTING);
99 }
100 
101 void LoadedCliqueAbstraction::DrawGraph(Graph *g) const
102 {
103  if ((g == 0) || (g->GetNumNodes() == 0)) return;
104 
105  int abLevel = g->GetNode(0)->GetLabelL(kAbstractionLevel);
106 
107  glBegin(GL_LINES);
108  glNormal3f(0, 1, 0);
109  node_iterator ni;
110  edge_iterator ei = g->getEdgeIter();
111  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
112  {
113  node *n;
114  n = g->GetNode(e->getFrom());
115 
116  if (e->GetLabelL(kEdgeCapacity) == 0) glColor4f(.5, .5, .5, 1);
117  else if (e->GetLabelL(kEdgeCapacity) <= 0) glColor4f(.2, .2, .2, 1);
118  else if (e->getMarked()) glColor4f(1, 1, 1, 1);
119  else if (abLevel%2)
120  glColor4f(1-((GLfloat)(abLevel%15)/15.0), ((GLfloat)(abLevel%15)/15.0), 0, 1);
121  else glColor4f(((GLfloat)(abLevel%15)/15.0), 1-((GLfloat)(abLevel%15)/15.0), 0, 1);
122  recVec rv = GetNodeLoc(n);
123  glVertex3f(rv.x, rv.y, rv.z);
124 
125  n = g->GetNode(e->getTo());
126  rv = GetNodeLoc(n);
127 
128  glVertex3f(rv.x, rv.y, rv.z);
129  }
130  ni = g->getNodeIter();
131  for (node *n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
132  DrawLevelConnections(n);
133  glEnd();
134  // if (verbose&kBuildGraph) printf("Done\n");
135 }
136 
137 void LoadedCliqueAbstraction::DrawLevelConnections(node *n) const
138 {
139  // int x, y;
140  // double offsetx, offsety;
141  // recVec ans;
142  //if (n->getNumOutgoingEdges()+n->getNumIncomingEdges() == 0) return;
143 
144  if (n->GetLabelL(kAbstractionLevel) == 0) return;
145  else {
146  glColor4f(.6, .6, .6, .6);
147  recVec v = GetNodeLoc(n);
148  for (int cnt = 0; cnt < n->GetLabelL(kNumAbstractedNodes); cnt++)
149  {
150  recVec v1 = GetNodeLoc(abstractions[n->GetLabelL(kAbstractionLevel)-1]->GetNode(n->GetLabelL(kFirstData+cnt)));
151  glVertex3f(v.x, v.y, v.z);
152  glVertex3f(v1.x, v1.y, v1.z);
153  }
154  }
155  //return ans;
156 }
157 
158 recVec LoadedCliqueAbstraction::GetNodeLoc(node *n) const
159 {
160  // double offsetx, offsety;
161  recVec ans;
162 
163  if (n->GetLabelF(kXCoordinate) != kUnknownPosition)
164  {
165  ans.x = n->GetLabelF(kXCoordinate);
166  ans.y = n->GetLabelF(kYCoordinate);
167  ans.z = n->GetLabelF(kZCoordinate);
168  return ans;
169  }
170 
171  int totNodes = 0;
172  ans.x = ans.y = ans.z = 0;
173  for (int cnt = 0; cnt < n->GetLabelL(kNumAbstractedNodes); cnt++)
174  {
175  int absLevel = n->GetLabelL(kAbstractionLevel)-1;
176  node *nextChild = abstractions[absLevel]->GetNode(n->GetLabelL(kFirstData+cnt));
177  recVec tmp = GetNodeLoc(nextChild);
178  int weight = nextChild->GetLabelL(kNumAbstractedNodes);
179  totNodes += weight;
180  ans.x += weight*tmp.x;
181  ans.y += weight*tmp.y;
182  ans.z += weight*tmp.z;
183  }
184  ans.x /= totNodes;//n->GetLabelL(kNumAbstractedNodes);
185  ans.y /= totNodes;//n->GetLabelL(kNumAbstractedNodes);
186  ans.z /= totNodes;//n->GetLabelL(kNumAbstractedNodes);
187 
188  n->SetLabelF(kXCoordinate, ans.x);
189  n->SetLabelF(kYCoordinate, ans.y);
190  n->SetLabelF(kZCoordinate, ans.z);
191  return ans;
192 }
193 
194 
195 Graph *LoadedCliqueAbstraction::loadGraph(char *fname)
196 {
197  FILE *f = fopen(fname, "r");
198  if (!f)
199  {
200  printf("Error opening %s for loading\n", fname);
201  exit(1);
202  }
203  char nextLine[255];
204  std::vector<unsigned int> IDS;
205  bool nodes = true;
206  Graph *g = new Graph();
207  fgets(nextLine, 255, f);
208  const double VERSION = 1.0;
209  double version;
210  sscanf(nextLine, "VERSION %lf", &version);
211  if (version != VERSION)
212  {
213  printf("Got %lf; code can only handle version 1.0\n", version);
214  exit(1);
215  }
216 
217  while ((!feof(f)) && fgets(nextLine, 255, f))
218  {
219  if (nextLine[0] == '#')
220  continue;
221  if (strncmp("edges", nextLine, 5) == 0)
222  {
223  nodes = false;
224  continue;
225  }
226  if (nodes)
227  {
228  // ID x y z
229  int ID;
230  double x, y, z;
231  sscanf(nextLine, "%d %lf %lf %lf", &ID, &x, &y, &z);
232  //printf("Loaded node %d\n", ID);
233  if (IDS.size() <= (unsigned int)ID)
234  IDS.resize(ID+1);
235  node *n;
236  IDS[ID] = g->AddNode(n = new node("l1"));
237  n->SetLabelL(kAbstractionLevel, 0); // level in abstraction tree
238  n->SetLabelL(kNumAbstractedNodes, 1); // number of abstracted nodes
239  n->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
240  n->SetLabelF(kXCoordinate, x);
241  n->SetLabelF(kYCoordinate, y);
242  n->SetLabelF(kZCoordinate, z);
243  n->SetLabelL(kNodeBlocked, 0);
244  }
245  else {
246  int ID1, ID2;
247  sscanf(nextLine, "%d %d", &ID1, &ID2);
248  g->AddEdge(new edge(IDS[ID1], IDS[ID2], h(g->GetNode(ID1), g->GetNode(ID2))));
249  //printf("Loaded edge between %d and %d\n", ID1, ID2);
250  }
251  }
252  return g;
253 }
254 
255 void LoadedCliqueAbstraction::VerifyHierarchy()
256 {
257  cout << "VERIFY START" << endl;
258  for (unsigned int x = 0; x < abstractions.size(); x++)
259  {
260  // first make sure Graph is ok
261  abstractions[x]->verifyGraph();
262  // then make sure abstraction is ok
263  node_iterator ni = abstractions[x]->getNodeIter();
264  for (node *n = abstractions[x]->nodeIterNext(ni); n; n = abstractions[x]->nodeIterNext(ni))
265  {
266  // verify Graph, because there may be issues...
267  if (n->GetLabelL(kParent) != -1)
268  {
269  Graph *g = abstractions[x+1];
270  node *parent = g->GetNode(n->GetLabelL(kParent));
271  bool found = false;
272  for (int y = 0; y < parent->GetLabelL(kNumAbstractedNodes); y++)
273  {
274  if (parent->GetLabelL(kFirstData+y) == (long)n->GetNum())
275  { found = true; break; }
276  }
277  if (!found)
278  {
279  cout << "VERIFY: Graph doesn't verify; child:" << endl << *n << endl;
280  cout << "VERIFY: Graph doesn't verify; parent:" << endl << *parent << endl;
281  }
282  }
283  if (x > 0)
284  {
285  Graph *g = abstractions[x-1];
286  for (int y = 0; y < n->GetLabelL(kNumAbstractedNodes); y++)
287  {
288  node *child = g->GetNode(n->GetLabelL(kFirstData+y));
289  if (!child)
290  {
291  cout << "VERIFY: Graph doesn't verify; CHILD is null, parent:" << endl << *n << endl;
292  }
293  else if (child->GetLabelL(kParent) != (long)n->GetNum())
294  {
295  cout << "VERIFY: Graph doesn't verify; parent:" << endl << *n << endl;
296  cout << "VERIFY: Graph doesn't verify; child:" << endl << *child << endl;
297  }
298  }
299  }
300  else {
301  // int x1, y1;
302  // GetTileFromNode(n, x1, y1);
303  // if (n != GetNodeFromMap(x1, y1))
304  // cout << "VERIFY: node doesn't correspond to underlying map" << endl << *n << endl;
305  }
306  }
307  // verify edges
308  edge_iterator ei = abstractions[x]->getEdgeIter();
309  for (edge *e = abstractions[x]->edgeIterNext(ei); e; e = abstractions[x]->edgeIterNext(ei))
310  {
311  node *p1, *p2;
312  p1 = findNodeParent(abstractions[x]->GetNode(e->getFrom()));
313  p2 = findNodeParent(abstractions[x]->GetNode(e->getTo()));
314  if (p1 == p2)
315  continue;
316  if ((p1 == 0) || (p2 == 0))
317  {
318  cout << "VERIFY: One edge parent is null, and the other isn't " << *e << endl << *p1 << endl << *p2 << endl;
319  continue;
320  }
321  if (!abstractions[x+1]->FindEdge(p1->GetNum(), p2->GetNum()))
322  {
323  cout << "Didn't find parent edge of " << *e << " at abslevel " << x << endl;
324  cout << *p1 << endl << *p2 << endl;
325  }
326  p1 = abstractions[x]->GetNode(e->getFrom());
327  p2 = abstractions[x]->GetNode(e->getTo());
328  // VERIFY edge weights
329  if (!fequal(e->GetWeight(), h(p1, p2)))
330  {
331  cout << "VERIFY: Edge weight doesn't match heuristic cost. Level: " << x << endl;
332  cout << *p1 << endl << *p2 << endl << *e << endl;
333  cout << "P1: (" << p1->GetLabelF(kXCoordinate) << ", " << p1->GetLabelF(kYCoordinate)
334  << ", " << p1->GetLabelF(kZCoordinate) << ")" << endl;
335  if (p1->GetLabelL(kAbstractionLevel) == 0)
336  cout << "P1: (" << p1->GetLabelL(kFirstData) << ", " << p1->GetLabelL(kFirstData+1) << ")" << endl;
337  cout << "P2: (" << p2->GetLabelF(kXCoordinate) << ", " << p2->GetLabelF(kYCoordinate)
338  << ", " << p2->GetLabelF(kZCoordinate) << ")" << endl;
339  if (p2->GetLabelL(kAbstractionLevel) == 0)
340  cout << "P2: (" << p2->GetLabelL(kFirstData) << ", " << p2->GetLabelL(kFirstData+1) << ")" << endl;
341  cout << "weight: " << e->GetWeight() << " heuristic " << h(p1, p2) << endl;
342  }
343  // VERIFY edge weights
344  if (e->GetLabelL(kEdgeCapacity) == 0)
345  cout << "VERIFY: Edge capacity is 0?!? " << e << endl;
346  if (x > 0) // we can verify the capacity
347  {
348  int count = 0;
349  // we should find kEdgeCapacity edges between the children of p1 and p2
350  p1 = abstractions[x]->GetNode(e->getFrom());
351  p2 = abstractions[x]->GetNode(e->getTo());
352  for (int c1 = 0; c1 < p1->GetLabelL(kNumAbstractedNodes); c1++)
353  {
354  for (int c2 = 0; c2 < p2->GetLabelL(kNumAbstractedNodes); c2++)
355  {
356  if (abstractions[x-1]->FindEdge(p1->GetLabelL(kFirstData+c1),
357  p2->GetLabelL(kFirstData+c2)))
358  {
359  count++;
360  }
361  }
362  }
363  if (count != e->GetLabelL(kEdgeCapacity))
364  {
365  cout << "VERIFY: Edge capactiy of " << *e << " is "
366  << e->GetLabelL(kEdgeCapacity) << " but we only found " << count
367  << " edges below that abstract into it." << endl;
368  }
369  }
370  }
371  }
372  cout << "VERIFY END" << endl;
373 }
374 
375 void LoadedCliqueAbstraction::cleanMemory()
376 {
377  while (abstractions.size() > 0)
378  {
379  delete abstractions.back();
380  abstractions.pop_back();
381  }
382  clearDisplayLists();
383  while (displayLists.size() > 0)
384  displayLists.pop_back();
385 }
386 
387 void LoadedCliqueAbstraction::clearDisplayLists()
388 {
389  for (unsigned int x = 0; x < displayLists.size(); x++)
390  {
391  if (displayLists[x] != 0) glDeleteLists(displayLists[x], 1);
392  displayLists[x] = 0;
393  }
394 }
395 
396 void LoadedCliqueAbstraction::buildAbstractions(Graph *_g)
397 {
398  int totalNodes = 0;
399  cleanMemory();
400  abstractions.push_back(_g);
401  Graph *g = abstractions[0];
402  if (displayLists.size() != 1)
403  displayLists.push_back(0);
404  //if (verbose)
405  printf("Base Graph (0) has %d nodes\n", g->GetNumNodes());
406  g->printStats();
407 
408  for (int x = 1; ; x++)
409  {
410  if (g->GetNumEdges() == 0) break;
411  if (verbose&kMiscMessages) printf("Building abstraction #%2d\n", x);
412  abstractions.push_back(abstractGraph(g));
413  g = abstractions.back();
414  if (verbose&kMiscMessages)
415  {
416  printf("Abstract Graph #%2d has %d nodes\n", x, g->GetNumNodes());
417  g->printStats();
418  }
419  totalNodes += g->GetNumNodes();
420  displayLists.push_back(0);
421  }
422  // printf("%d nodes, excluding bottom level", totalNodes);
423 }
424 
425 Graph *LoadedCliqueAbstraction::abstractGraph(Graph *g)
426 {
427  return cliqueAbstractGraph(g);
428 }
429 
430 Graph *LoadedCliqueAbstraction::neighborAbstractGraph(Graph *g, int width)
431 {
432  std::vector<node *> remainingNodes;
433  Graph *aGraph = new Graph();
434  node_iterator ni = g->getNodeIter();
435  node *newNode;
436 
437  // do we want to abstract big nodes first?
438  ni = g->getNodeIter();
439  for (node *n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
440  {
441  if (n->GetLabelL(kParent) != -1) continue;
442  newNode = new node("");
443  aGraph->AddNode(newNode);
444 
445  newNode->SetLabelL(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
446  newNode->SetLabelL(kNumAbstractedNodes, 0); // number of abstracted nodes
447  newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
448  newNode->SetLabelL(kNodeBlocked, 0);
449  newNode->SetLabelF(kXCoordinate, kUnknownPosition);
450 
451  addNodesToParent(g, n, newNode, width);
452  }
453 
454  // now add all the edges
455  edge_iterator ei = g->getEdgeIter();
456  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
457  {
458  int from = g->GetNode(e->getFrom())->GetLabelL(kParent);
459  int to = g->GetNode(e->getTo())->GetLabelL(kParent);
460  edge *f=0;//, *g=0;
461  if ((from != to) && (!(f = aGraph->FindEdge(to, from))))
462  {
463  double weight = h(aGraph->GetNode(from), aGraph->GetNode(to));
464  f = new edge(from, to, weight);
465  f->SetLabelL(kEdgeCapacity, 1);
466  aGraph->AddEdge(f);
467  }
468  else if (f) f->SetLabelL(kEdgeCapacity, f->GetLabelL(kEdgeCapacity)+1);
469  // else if (g)
470  // g->setLabel(kEdgeCapacity, g->GetLabelL(kEdgeCapacity)+1);
471  }
472 
473  return aGraph;
474 }
475 
476 void LoadedCliqueAbstraction::addNodesToParent(Graph *g, node *n, node *parent, int width)
477 {
478  if (n->GetLabelL(kParent) != -1)
479  return;
480 
481  // add this node; add all neighbors
482  int oldChildren = parent->GetLabelL(kNumAbstractedNodes);
483  parent->SetLabelL(kFirstData+oldChildren, n->GetNum());
484  parent->SetLabelL(kNumAbstractedNodes, oldChildren+1);
485  n->SetLabelL(kParent, parent->GetNum());
486 
487  if (width <= 0)
488  return;
489  edge_iterator ei = n->getEdgeIter();
490  for (edge *e = n->edgeIterNext(ei); e; e = n->edgeIterNext(ei))
491  {
492  if (e->getFrom() == n->GetNum())
493  addNodesToParent(g, g->GetNode(e->getTo()), parent, width-1);
494  else
495  addNodesToParent(g, g->GetNode(e->getFrom()), parent, width-1);
496  }
497 }
498 
499 
500 Graph *LoadedCliqueAbstraction::cliqueAbstractGraph(Graph *g)
501 {
502  // int abLevel = g->GetNode(0)->GetLabelL(kAbstractionLevel);
503  // if (g != abstractions[0])
504  // return GraphAbstraction::abstractGraph(g);
505 
506  // printf("Doing special map abstraction at level %d\n", (int)g->GetNode(0)->GetLabelL(kAbstractionLevel));
507 
508  // 1) join singly linked paths into single nodes
509  // 2) join 4-cliques
510  // 3) join 3-cliques
511  // 4) join 2-cliques
512  std::vector<node *> remainingNodes;
513  Graph *aGraph = new Graph();
514  node_iterator ni = g->getNodeIter();
515  node *newNode;
516 
517  ni = g->getNodeIter();
518  for (node *n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
519  {
520  if (n->GetLabelL(kParent) != -1) continue;
521  int numEdges = n->GetNumEdges();//getNumOutgoingEdges() + n->getNumIncomingEdges();
522 
523  if (numEdges == 1)
524  {
525  // add to stack; we will merge these after we've finished everything else
526  remainingNodes.push_back(n);
527  continue;
528  }
529 
530  std::vector<int> neighbor(numEdges);
531  edge *e;
532  edge_iterator ei = n->getEdgeIter();
533  for (int x = 0; x < numEdges; x++)
534  {
535  e = n->edgeIterNext(ei);
536  if (e == 0)
537  {
538  cout << "That's impossible; we were told we had "
539  << numEdges << ":(" << n->getNumOutgoingEdges()
540  << "+" << n->getNumIncomingEdges()
541  << ") edges, we're on #" << x << " and we got nil!"
542  << endl;
543  numEdges = x;
544  continue;
545  }
546  if (e->getFrom() == n->GetNum()) neighbor[x] = e->getTo();
547  else neighbor[x] = e->getFrom();
548  }
549 
550  // check for all cliques involving 4 nodes
551  for (int x = 0; x < numEdges-2; x++)
552  {
553  if (g->GetNode(neighbor[x])->GetLabelL(kParent) != -1) continue;
554  for (int y = x+1; y < numEdges-1; y++)
555  {
556  if (g->GetNode(neighbor[y])->GetLabelL(kParent) != -1) continue;
557  for (int z = y+1; z < numEdges; z++)
558  {
559  if (g->GetNode(neighbor[z])->GetLabelL(kParent) != -1) continue;
560  // each node has edge to us; now we also must have
561  // x<->y, y<->z, x<->z
562  // if ((g->FindEdge(neighbor[x], neighbor[y]) || g->FindEdge(neighbor[y], neighbor[x])) &&
563  // (g->FindEdge(neighbor[y], neighbor[z]) || g->FindEdge(neighbor[z], neighbor[y])) &&
564  // (g->FindEdge(neighbor[z], neighbor[x]) || g->FindEdge(neighbor[x], neighbor[z])))
565  if (g->FindEdge(neighbor[x], neighbor[y]) &&
566  g->FindEdge(neighbor[y], neighbor[z]) &&
567  g->FindEdge(neighbor[z], neighbor[x]))
568  {
569  // we have a 4-clique!
570  int nnum = aGraph->AddNode(newNode = new node("4c"));
571  n->SetLabelL(kParent, nnum);
572  g->GetNode(neighbor[x])->SetLabelL(kParent, nnum);
573  g->GetNode(neighbor[y])->SetLabelL(kParent, nnum);
574  g->GetNode(neighbor[z])->SetLabelL(kParent, nnum);
575 
576  newNode->SetLabelL(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
577  newNode->SetLabelL(kNumAbstractedNodes, 4); // number of abstracted nodes
578  newNode->SetLabelL(kNodeBlocked, 0);
579  newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
580  newNode->SetLabelF(kXCoordinate, kUnknownPosition);
581  newNode->SetLabelL(kFirstData, n->GetNum()); // nodes stored here
582  newNode->SetLabelL(kFirstData+1, neighbor[x]); // nodes stored here
583  newNode->SetLabelL(kFirstData+2, neighbor[y]); // nodes stored here
584  newNode->SetLabelL(kFirstData+3, neighbor[z]); // nodes stored here
585 
586  x = y = numEdges;
587  break;
588  }
589  }
590  }
591  }
592 
593  // check for all cliques involving 3 nodes
594  if (n->GetLabelL(kParent) == -1)
595  {
596  for (int x = 0; x < numEdges-1; x++)
597  {
598  if (g->GetNode(neighbor[x])->GetLabelL(kParent) != -1) continue;
599  for (int y = x+1; y < numEdges; y++)
600  {
601  if (g->GetNode(neighbor[y])->GetLabelL(kParent) != -1) continue;
602  // each node has edge to us; now we also must have
603  // x<->y
604  // if (g->FindEdge(neighbor[x], neighbor[y]) || g->FindEdge(neighbor[y], neighbor[x]))
605  if (g->FindEdge(neighbor[x], neighbor[y]))
606  {
607  // we have a 3-clique!
608  int nnum = aGraph->AddNode(newNode = new node("3c"));
609  n->SetLabelL(kParent, nnum);
610  g->GetNode(neighbor[x])->SetLabelL(kParent, nnum);
611  g->GetNode(neighbor[y])->SetLabelL(kParent, nnum);
612 
613  newNode->SetLabelL(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
614  newNode->SetLabelL(kNumAbstractedNodes, 3); // number of abstracted nodes
615  newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
616  newNode->SetLabelL(kNodeBlocked, 0);
617  newNode->SetLabelF(kXCoordinate, kUnknownPosition);
618  newNode->SetLabelL(kFirstData, n->GetNum()); // nodes stored here
619  newNode->SetLabelL(kFirstData+1, neighbor[x]); // nodes stored here
620  newNode->SetLabelL(kFirstData+2, neighbor[y]); // nodes stored here
621 
622  x = numEdges;
623  break;
624  }
625  }
626  }
627  }
628 
629  // if (n->GetLabelL(kParent) == -1)
630  // {
631  // // check for all cliques involving 2 nodes
632  // for (int x = 0; x < numEdges; x++)
633  // {
634  // if (g->GetNode(neighbor[x])->GetLabelL(kParent) != -1)
635  // continue;
636  // // we have a 2-clique!
637  // int nnum = aGraph->AddNode(newNode = new node("2c"));
638  // n->setLabel(kParent, nnum);
639  // g->GetNode(neighbor[x])->setLabel(kParent, nnum);
640  //
641  // newNode->setLabel(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
642  // newNode->setLabel(kNumAbstractedNodes, 2); // number of abstracted nodes
643  // newNode->setLabel(kNodeBlocked, 0);
644  // newNode->setLabel(kXCoordinate, -1);
645  // newNode->setLabel(kParent, -1); // parent of this node in abstraction hierarchy
646  // newNode->setLabel(kFirstData, n->GetNum()); // nodes stored here
647  // newNode->setLabel(kFirstData+1, neighbor[x]); // nodes stored here
648  // break;
649  // }
650  // }
651 
652  // we didn't find a 3 or 4 clique
653  if (n->GetLabelL(kParent) == -1) remainingNodes.push_back(n);
654  }
655 
656  while (remainingNodes.size() > 0)
657  {
658  node *orphan = (node*)remainingNodes.back();
659  if (!orphan) break;
660  remainingNodes.pop_back();
661  if (orphan->GetLabelL(kParent) != -1) continue;
662  int numEdges = orphan->getNumOutgoingEdges() + orphan->getNumIncomingEdges();
663  if (numEdges == 0) continue;
664 
665  edge_iterator ei = orphan->getEdgeIter();
666  for (edge *e = orphan->edgeIterNext(ei); e; e = orphan->edgeIterNext(ei))
667  {
668  int neighbor = (e->getFrom() == orphan->GetNum())?e->getTo():e->getFrom();
669  if (g->GetNode(neighbor)->GetLabelL(kParent) == -1)
670  {
671  unsigned int pNum;
672  pNum = aGraph->AddNode(newNode = new node("2c"));
673  orphan->SetLabelL(kParent, pNum);
674  g->GetNode(neighbor)->SetLabelL(kParent, pNum);
675 
676  newNode->SetLabelL(kAbstractionLevel, orphan->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
677  newNode->SetLabelL(kNumAbstractedNodes, 2); // number of abstracted nodes
678  newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
679  newNode->SetLabelL(kNodeBlocked, 0);
680  newNode->SetLabelF(kXCoordinate, kUnknownPosition);
681  newNode->SetLabelL(kFirstData, orphan->GetNum()); // nodes stored here
682  newNode->SetLabelL(kFirstData+1, neighbor); // nodes stored here
683  break;
684  }
685  }
686  if ((orphan->GetLabelL(kParent) == -1) && (orphan->GetNumEdges() == 1))
687  {
688  ei = orphan->getEdgeIter();
689  for (edge *e = orphan->edgeIterNext(ei); e; e = orphan->edgeIterNext(ei))
690  {
691  int neighbor = (e->getFrom() == orphan->GetNum())?e->getTo():e->getFrom();
692  //printf("merging %d into %d (%d)\n", orphan->GetNum(), neighbor, g->GetNode(neighbor)->GetLabelL(kParent));
693  node *adoptee = g->GetNode(neighbor);
694  orphan->SetLabelL(kParent, adoptee->GetLabelL(kParent));
695 
696  node *adopteeParent = aGraph->GetNode(adoptee->GetLabelL(kParent));
697  adopteeParent->SetLabelL(kFirstData+adopteeParent->GetLabelL(kNumAbstractedNodes), orphan->GetNum());
698  adopteeParent->SetLabelL(kNumAbstractedNodes, adopteeParent->GetLabelL(kNumAbstractedNodes)+1);
699  break;
700  }
701  }
702  if (orphan->GetLabelL(kParent) == -1)
703  {
704  orphan->SetLabelL(kParent, aGraph->AddNode(newNode = new node("stranded*")));
705  newNode->SetLabelL(kAbstractionLevel, orphan->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
706  newNode->SetLabelL(kNumAbstractedNodes, 1); // number of abstracted nodes
707  newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
708  newNode->SetLabelL(kNodeBlocked, 0);
709  newNode->SetLabelF(kXCoordinate, kUnknownPosition);
710  newNode->SetLabelL(kFirstData, orphan->GetNum()); // nodes stored here
711  }
712  }
713 
714  // now add all the edges
715  edge_iterator ei = g->getEdgeIter();
716  for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei))
717  {
718  int from = g->GetNode(e->getFrom())->GetLabelL(kParent);
719  int to = g->GetNode(e->getTo())->GetLabelL(kParent);
720  edge *f=0;//, *g=0;
721  //if ((from != to) && (!(f = aGraph->FindEdge(to, from))) && (!(g = aGraph->FindEdge(from, to))))
722  if ((from != to) && (!(f = aGraph->FindEdge(to, from))))
723  {
724  // double weight = (aGraph->GetNode(from)->GetLabelL(kNumAbstractedNodes))+
725  // (aGraph->GetNode(to)->GetLabelL(kNumAbstractedNodes));
726  // weight /= 2;
727  // weight += e->GetWeight();
728  double weight = h(aGraph->GetNode(from), aGraph->GetNode(to));
729  f = new edge(from, to, weight);
730  f->SetLabelL(kEdgeCapacity, 1);
731  aGraph->AddEdge(f);
732  if (verbose&kBuildGraph)
733  printf("Adding edge from %d (%d) to %d (%d) weight %1.2f\n", from, e->getFrom(), to, e->getTo(), weight);
734  }
735  else if (f) f->SetLabelL(kEdgeCapacity, f->GetLabelL(kEdgeCapacity)+1);
736  // else if (g)
737  // g->setLabel(kEdgeCapacity, g->GetLabelL(kEdgeCapacity)+1);
738  }
739 
740  return aGraph;
741 }
742 
743 
744 //Graph *LoadedCliqueAbstraction::cliqueAbstractGraph(Graph *g)
745 //{
746 // //printf("getting abstract Graph of level %d\n", g->GetNode(0)->GetLabelL(kAbstractionLevel));
747 //
748 // // 1) join singly linked paths into single nodes
749 // // 2) join 4-cliques
750 // // 3) join 3-cliques
751 // // 4) join 2-cliques
752 // std::vector<node *> remainingNodes;
753 // Graph *aGraph = new Graph();
754 // node_iterator ni = g->getNodeIter();
755 // node *newNode;
756 //
757 // // no tunnels for now -- they aren't cliques
758 // // for (node *n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni))
759 // // {
760 // // if (n->GetLabelL(kParent) != -1)
761 // // continue;
762 // // if (n->GetNumEdges() == 2)
763 // // {
764 // // neighbor_iterator nbi = n->getNeighborIter();
765 // // int n1 = n->nodeNeighborNext(nbi);
766 // // int n2 = n->nodeNeighborNext(nbi);
767 // // if ((g->GetNode(n1)->GetNumEdges() == 2) || (g->GetNode(n2)->GetNumEdges() == 2))
768 // // {
769 // // int nnum = aGraph->AddNode(newNode = new node("tunnel"));
770 // // n->setLabel(kParent, nnum);
771 // //
772 // // newNode->setLabel(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
773 // // newNode->setLabel(kNumAbstractedNodes, 1); // number of abstracted nodes
774 // // newNode->setLabel(kParent, -1); // parent of this node in abstraction hierarchy
775 // // newNode->setLabel(kNodeBlocked, 0);
776 // // newNode->setLabel(kXCoordinate, -1);
777 // // newNode->setLabel(kFirstData, n->GetNum()); // nodes stored here
778 // //
779 // // addTunnel(n, g, newNode);
780 // // }
781 // // }
782 // // }
783 // ni = g->getNodeIter();
784 // for (node *n = g->nodeIterNext(ni); n; n = g->nodeIterNext(ni)) {
785 // if (n->GetLabelL(kParent) != -1) continue;
786 // int numEdges = n->GetNumEdges();//getNumOutgoingEdges() + n->getNumIncomingEdges();
787 //
788 // // why abstract solo nodes; they just get confusing later?
789 // // if (numEdges == 0)
790 // // {
791 // // n->setLabel(kParent, aGraph->AddNode(newNode = new node("1c")));
792 // // newNode->setLabel(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
793 // // newNode->setLabel(kNumAbstractedNodes, 1); // number of abstracted nodes
794 // // newNode->setLabel(kParent, -1); // parent of this node in abstraction hierarchy
795 // // newNode->setLabel(kNodeBlocked, 0);
796 // // newNode->setLabel(kXCoordinate, -1);
797 // // newNode->setLabel(kFirstData, n->GetNum()); // nodes stored here
798 // // continue;
799 // // }
800 // if (numEdges == 1) {
801 // // add to stack; we will merge these after we've finished everything else
802 // remainingNodes.push_back(n);
803 // continue;
804 // }
805 //
806 // int neighbor[numEdges];
807 // edge *e;
808 // edge_iterator ei = n->getEdgeIter();
809 // for (int x = 0; x < numEdges; x++) {
810 // e = n->edgeIterNext(ei);
811 // if (e == 0) {
812 // cout << "That's impossible; we were told we had "
813 // << numEdges << ":(" << n->getNumOutgoingEdges()
814 // << "+" << n->getNumIncomingEdges()
815 // << ") edges, we're on #" << x << " and we got nil!"
816 // << endl;
817 // numEdges = x;
818 // continue;
819 // }
820 // if (e->getFrom() == n->GetNum()) neighbor[x] = e->getTo();
821 // else neighbor[x] = e->getFrom();
822 // }
823 //
824 // // check for all cliques involving 4 nodes
825 // for (int x = 0; x < numEdges-2; x++) {
826 // if (g->GetNode(neighbor[x])->GetLabelL(kParent) != -1) continue;
827 // for (int y = x+1; y < numEdges-1; y++) {
828 // if (g->GetNode(neighbor[y])->GetLabelL(kParent) != -1) continue;
829 // for (int z = y+1; z < numEdges; z++) {
830 // if (g->GetNode(neighbor[z])->GetLabelL(kParent) != -1) continue;
831 // // each node has edge to us; now we also must have
832 // // x<->y, y<->z, x<->z
833 // // if ((g->FindEdge(neighbor[x], neighbor[y]) || g->FindEdge(neighbor[y], neighbor[x])) &&
834 // // (g->FindEdge(neighbor[y], neighbor[z]) || g->FindEdge(neighbor[z], neighbor[y])) &&
835 // // (g->FindEdge(neighbor[z], neighbor[x]) || g->FindEdge(neighbor[x], neighbor[z])))
836 // if (g->FindEdge(neighbor[x], neighbor[y]) &&
837 // g->FindEdge(neighbor[y], neighbor[z]) &&
838 // g->FindEdge(neighbor[z], neighbor[x])) {
839 // // we have a 4-clique!
840 // int nnum = aGraph->AddNode(newNode = new node("4c"));
841 // n->SetLabelL(kParent, nnum);
842 // g->GetNode(neighbor[x])->SetLabelL(kParent, nnum);
843 // g->GetNode(neighbor[y])->SetLabelL(kParent, nnum);
844 // g->GetNode(neighbor[z])->SetLabelL(kParent, nnum);
845 //
846 // newNode->SetLabelL(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
847 // newNode->SetLabelL(kNumAbstractedNodes, 4); // number of abstracted nodes
848 // newNode->SetLabelL(kNodeBlocked, 0);
849 // newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
850 // newNode->SetLabelF(kXCoordinate, -1);
851 // newNode->SetLabelL(kFirstData, n->GetNum()); // nodes stored here
852 // newNode->SetLabelL(kFirstData+1, neighbor[x]); // nodes stored here
853 // newNode->SetLabelL(kFirstData+2, neighbor[y]); // nodes stored here
854 // newNode->SetLabelL(kFirstData+3, neighbor[z]); // nodes stored here
855 //
856 // x = y = numEdges;
857 // break;
858 // }
859 // }
860 // }
861 // }
862 //
863 // // check for all cliques involving 3 nodes
864 // if (n->GetLabelL(kParent) == -1) {
865 // for (int x = 0; x < numEdges-1; x++) {
866 // if (g->GetNode(neighbor[x])->GetLabelL(kParent) != -1) continue;
867 // for (int y = x+1; y < numEdges; y++) {
868 // if (g->GetNode(neighbor[y])->GetLabelL(kParent) != -1) continue;
869 // // each node has edge to us; now we also must have
870 // // x<->y
871 // // if (g->FindEdge(neighbor[x], neighbor[y]) || g->FindEdge(neighbor[y], neighbor[x]))
872 // if (g->FindEdge(neighbor[x], neighbor[y])) {
873 // // we have a 3-clique!
874 // int nnum = aGraph->AddNode(newNode = new node("3c"));
875 // n->SetLabelL(kParent, nnum);
876 // g->GetNode(neighbor[x])->SetLabelL(kParent, nnum);
877 // g->GetNode(neighbor[y])->SetLabelL(kParent, nnum);
878 //
879 // newNode->SetLabelL(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
880 // newNode->SetLabelL(kNumAbstractedNodes, 3); // number of abstracted nodes
881 // newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
882 // newNode->SetLabelL(kNodeBlocked, 0);
883 // newNode->SetLabelF(kXCoordinate, -1);
884 // newNode->SetLabelL(kFirstData, n->GetNum()); // nodes stored here
885 // newNode->SetLabelL(kFirstData+1, neighbor[x]); // nodes stored here
886 // newNode->SetLabelL(kFirstData+2, neighbor[y]); // nodes stored here
887 //
888 // x = numEdges;
889 // break;
890 // }
891 // }
892 // }
893 // }
894 //
895 // // if (n->GetLabelL(kParent) == -1)
896 // // {
897 // // // check for all cliques involving 2 nodes
898 // // for (int x = 0; x < numEdges; x++)
899 // // {
900 // // if (g->GetNode(neighbor[x])->GetLabelL(kParent) != -1)
901 // // continue;
902 // // // we have a 2-clique!
903 // // int nnum = aGraph->AddNode(newNode = new node("2c"));
904 // // n->setLabel(kParent, nnum);
905 // // g->GetNode(neighbor[x])->setLabel(kParent, nnum);
906 // //
907 // // newNode->setLabel(kAbstractionLevel, n->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
908 // // newNode->setLabel(kNumAbstractedNodes, 2); // number of abstracted nodes
909 // // newNode->setLabel(kNodeBlocked, 0);
910 // // newNode->setLabel(kXCoordinate, -1);
911 // // newNode->setLabel(kParent, -1); // parent of this node in abstraction hierarchy
912 // // newNode->setLabel(kFirstData, n->GetNum()); // nodes stored here
913 // // newNode->setLabel(kFirstData+1, neighbor[x]); // nodes stored here
914 // // break;
915 // // }
916 // // }
917 //
918 // // we didn't find a 3 or 4 clique
919 // if (n->GetLabelL(kParent) == -1) remainingNodes.push_back(n);
920 // }
921 //
922 // while (remainingNodes.size() > 0) {
923 // node *orphan = (node*)remainingNodes.back();
924 // if (!orphan) break;
925 // remainingNodes.pop_back();
926 // if (orphan->GetLabelL(kParent) != -1) continue;
927 // int numEdges = orphan->getNumOutgoingEdges() + orphan->getNumIncomingEdges();
928 // if (numEdges == 0) continue;
929 //
930 // edge_iterator ei = orphan->getEdgeIter();
931 // for (edge *e = orphan->edgeIterNext(ei); e; e = orphan->edgeIterNext(ei)) {
932 // int neighbor = (e->getFrom() == orphan->GetNum())?e->getTo():e->getFrom();
933 // if (g->GetNode(neighbor)->GetLabelL(kParent) == -1) {
934 // unsigned int pNum;
935 // pNum = aGraph->AddNode(newNode = new node("2c"));
936 // orphan->SetLabelL(kParent, pNum);
937 // g->GetNode(neighbor)->SetLabelL(kParent, pNum);
938 //
939 // newNode->SetLabelL(kAbstractionLevel, orphan->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
940 // newNode->SetLabelL(kNumAbstractedNodes, 2); // number of abstracted nodes
941 // newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
942 // newNode->SetLabelL(kNodeBlocked, 0);
943 // newNode->SetLabelF(kXCoordinate, -1);
944 // newNode->SetLabelL(kFirstData, orphan->GetNum()); // nodes stored here
945 // newNode->SetLabelL(kFirstData+1, neighbor); // nodes stored here
946 // break;
947 // }
948 // }
949 // if ((orphan->GetLabelL(kParent) == -1) && (orphan->GetNumEdges() == 1)) {
950 // ei = orphan->getEdgeIter();
951 // for (edge *e = orphan->edgeIterNext(ei); e; e = orphan->edgeIterNext(ei)) {
952 // int neighbor = (e->getFrom() == orphan->GetNum())?e->getTo():e->getFrom();
953 // //printf("merging %d into %d (%d)\n", orphan->GetNum(), neighbor, g->GetNode(neighbor)->GetLabelL(kParent));
954 // node *adoptee = g->GetNode(neighbor);
955 // orphan->SetLabelL(kParent, adoptee->GetLabelL(kParent));
956 //
957 // node *adopteeParent = aGraph->GetNode(adoptee->GetLabelL(kParent));
958 // adopteeParent->SetLabelL(kFirstData+adopteeParent->GetLabelL(kNumAbstractedNodes), orphan->GetNum());
959 // adopteeParent->SetLabelL(kNumAbstractedNodes, adopteeParent->GetLabelL(kNumAbstractedNodes)+1);
960 // break;
961 // }
962 // }
963 // if (orphan->GetLabelL(kParent) == -1) {
964 // orphan->SetLabelL(kParent, aGraph->AddNode(newNode = new node("stranded*")));
965 // newNode->SetLabelL(kAbstractionLevel, orphan->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
966 // newNode->SetLabelL(kNumAbstractedNodes, 1); // number of abstracted nodes
967 // newNode->SetLabelL(kParent, -1); // parent of this node in abstraction hierarchy
968 // newNode->SetLabelL(kNodeBlocked, 0);
969 // newNode->SetLabelF(kXCoordinate, -1);
970 // newNode->SetLabelL(kFirstData, orphan->GetNum()); // nodes stored here
971 // }
972 //
973 //
974 // // // we aren't going to push nodes into their neighbors for the moment, because it ruins the
975 // // // clique property of nodes.
976 // //// else {
977 // //// //printf("merging %d into %d (%d)\n", orphan->GetNum(), neighbor, g->GetNode(neighbor)->GetLabelL(kParent));
978 // //// node *adoptee = g->GetNode(neighbor);
979 // //// orphan->setLabel(kParent, adoptee->GetLabelL(kParent));
980 // ////
981 // //// node *adopteeParent = aGraph->GetNode((int)adoptee->GetLabelL(kParent));
982 // //// adopteeParent->setLabel(kFirstData+(int)adopteeParent->GetLabelL(kNumAbstractedNodes), orphan->GetNum());
983 // //// adopteeParent->setLabel(kNumAbstractedNodes, adopteeParent->GetLabelL(kNumAbstractedNodes)+1);
984 // //// }
985 // // }
986 // // else
987 // // if (orphan->GetLabelL(kParent) == -1)
988 // // {
989 // // orphan->setLabel(kParent, aGraph->AddNode(newNode = new node("stranded*")));
990 // // newNode->setLabel(kAbstractionLevel, orphan->GetLabelL(kAbstractionLevel)+1); // level in abstraction tree
991 // // newNode->setLabel(kNumAbstractedNodes, 1); // number of abstracted nodes
992 // // newNode->setLabel(kParent, -1); // parent of this node in abstraction hierarchy
993 // // newNode->setLabel(kNodeBlocked, 0);
994 // // newNode->setLabel(kXCoordinate, -1);
995 // // newNode->setLabel(kFirstData, orphan->GetNum()); // nodes stored here
996 // // }
997 // }
998 //
999 // // now add all the edges
1000 // edge_iterator ei = g->getEdgeIter();
1001 // for (edge *e = g->edgeIterNext(ei); e; e = g->edgeIterNext(ei)) {
1002 // int from = g->GetNode(e->getFrom())->GetLabelL(kParent);
1003 // int to = g->GetNode(e->getTo())->GetLabelL(kParent);
1004 // edge *f=0;//, *g=0;
1005 // //if ((from != to) && (!(f = aGraph->FindEdge(to, from))) && (!(g = aGraph->FindEdge(from, to))))
1006 // if ((from != to) && (!(f = aGraph->FindEdge(to, from)))) {
1007 // // double weight = (aGraph->GetNode(from)->GetLabelL(kNumAbstractedNodes))+
1008 // // (aGraph->GetNode(to)->GetLabelL(kNumAbstractedNodes));
1009 // // weight /= 2;
1010 // // weight += e->GetWeight();
1011 // double weight = h(aGraph->GetNode(from), aGraph->GetNode(to));
1012 // f = new edge(from, to, weight);
1013 // f->SetLabelL(kEdgeCapacity, 1);
1014 // aGraph->AddEdge(f);
1015 // if (verbose&kBuildGraph)
1016 // printf("Adding edge from %d (%d) to %d (%d) weight %1.2f\n", from, e->getFrom(), to, e->getTo(), weight);
1017 // }
1018 // else if (f) f->SetLabelL(kEdgeCapacity, f->GetLabelL(kEdgeCapacity)+1);
1019 // // else if (g)
1020 // // g->setLabel(kEdgeCapacity, g->GetLabelL(kEdgeCapacity)+1);
1021 // }
1022 //
1023 // return aGraph;
1024 //}
1025 
1026 
1027 void LoadedCliqueAbstraction::addTunnel(node *n, Graph *g, node *newNode)
1028 {
1029  if (verbose&kBuildGraph) printf("Adding node %d to tunnel\n", n->GetNum());
1030  // check to see if we have neighbors with bf 2 which we can merge with
1031  neighbor_iterator nbi = n->getNeighborIter();
1032  int n1 = n->nodeNeighborNext(nbi);
1033  int n2 = n->nodeNeighborNext(nbi);
1034  if ((g->GetNode(n1)->GetLabelL(kParent) == -1) && (g->GetNode(n1)->GetNumEdges() == 2))
1035  {
1036  newNode->SetLabelL(kFirstData+newNode->GetLabelL(kNumAbstractedNodes), n1); // nodes stored here
1037  newNode->SetLabelL(kNumAbstractedNodes, newNode->GetLabelL(kNumAbstractedNodes)+1);
1038  g->GetNode(n1)->SetLabelL(kParent, newNode->GetNum());
1039  addTunnel(g->GetNode(n1), g, newNode);
1040  }
1041  if ((g->GetNode(n2)->GetLabelL(kParent) == -1) && (g->GetNode(n2)->GetNumEdges() == 2))
1042  {
1043  newNode->SetLabelL(kFirstData+newNode->GetLabelL(kNumAbstractedNodes), n2); // nodes stored here
1044  newNode->SetLabelL(kNumAbstractedNodes, newNode->GetLabelL(kNumAbstractedNodes)+1);
1045  g->GetNode(n2)->SetLabelL(kParent, newNode->GetNum());
1046  addTunnel(g->GetNode(n2), g, newNode);
1047  }
1048 }
1049 
1050 bool LoadedCliqueAbstraction::Pathable(unsigned int from, unsigned int to)
1051 {
1052  return Pathable(abstractions[0]->GetNode(from), abstractions[0]->GetNode(to));
1053 }
1054 
1055 bool LoadedCliqueAbstraction::Pathable(node *from, node *to)
1056 {
1057  //printf("At nodes #%d and %d\n", from->GetNum(), to->GetNum());
1058  while (from != to)
1059  {
1060  if ((!from) || (!to) ||
1061  (abstractions[from->GetLabelL(kAbstractionLevel)]->GetNumEdges() == 0))
1062  return false;
1063 
1064  from = abstractions[from->GetLabelL(kAbstractionLevel)+1]->
1065  GetNode(from->GetLabelL(kParent));
1066  to = abstractions[to->GetLabelL(kAbstractionLevel)+1]->
1067  GetNode(to->GetLabelL(kParent));
1068  }
1069  if ((from == 0) || (to == 0))
1070  return false;
1071  return true;
1072 }
1073 
1074 //path *LoadedCliqueAbstraction::getQuickPath(node *from, node *to)
1075 //{
1076 // if (absMethod != kloadedCliqueAbstraction)
1077 // return 0;
1078 // std::vector<node *> fromChain, toChain;
1079 // GetNumAbstractGraphs(from, to, fromChain, toChain);
1080 //
1081 // if (!GetAbstractGraph(fromChain.back()->GetLabelL(kAbstractionLevel))->
1082 // FindEdge(fromChain.back()->GetNum(), toChain.back()->GetNum()))
1083 // return 0;
1084 //
1085 // path *p = new path(fromChain.back(), new path(toChain.back()));
1086 // fromChain.pop_back(); toChain.pop_back();
1087 // while (fromChain.size() > 0)
1088 // {
1089 // // 1 if we have an edge to the next node in path, add it
1090 // // 2 if we have bf 1, add neighbor and repeat
1091 // // 2 otherwise check each of our neighbors, and add the one that
1092 // // has the path to the neighbor as well as that edge
1093 // return 0;
1094 // }
1095 // return p;
1096 //}
1097 
1098 void LoadedCliqueAbstraction::AddNode(node *)
1099 {
1100  assert(false);
1101 }
1102 
1103 void LoadedCliqueAbstraction::AddEdge(edge *, unsigned int)
1104 {
1105  assert(false);
1106 }
1107 
1108 // for now we'll immediately handle splits, but in the future we should queue up splits
1109 // and process them in batch form(?)
1110 void LoadedCliqueAbstraction::RemoveEdge(edge *e, unsigned int absLevel)
1111 {
1112  if (e == 0)
1113  return;
1114  edge *ep = findEdgeParent(e, absLevel);
1115  if (ep)
1116  {
1117  ep->SetLabelL(kEdgeCapacity, ep->GetLabelL(kEdgeCapacity)-1);
1118  if (ep->GetLabelL(kEdgeCapacity) == 0) RemoveEdge(ep, absLevel+1);
1119  //printf("Removing edge %p in abstract Graph %d\n", e, absLevel);
1120  abstractions[absLevel]->RemoveEdge(e);
1121  delete e;
1122  return;
1123  }
1124 
1125  // it's an internal edge, so it might break a link in a parent abstract node
1126  if (absLevel+1 < abstractions.size())
1127  {
1128  node *pNode = abstractions[absLevel+1]->GetNode(abstractions[absLevel]->GetNode(e->getFrom())->GetLabelL(kParent));
1129  addNodeToRepairQ(pNode);
1130  }
1131 
1132  //printf("Removing edge %p in abstract Graph %d\n", e, absLevel);
1133  abstractions[absLevel]->RemoveEdge(e);
1134  delete e;
1135  return;
1136 }
1137 
1138 void LoadedCliqueAbstraction::addNodeToRepairQ(node *n)
1139 {
1140  // key is unsigned, so it has to be >= 0
1141  if (n)
1142  {
1143  if ((n->key >= modifiedNodeQ.size()) ||
1144  ((n->key < modifiedNodeQ.size()) && (modifiedNodeQ[n->key] != n)))
1145  // if ((n->key < 0) || (n->key >= modifiedNodeQ.size()) ||
1146  // ((n->key >= 0) && (n->key < modifiedNodeQ.size()) && (modifiedNodeQ[n->key] != n)))
1147  {
1148  n->key = modifiedNodeQ.size();
1149  if (verbose&kRepairGraph)
1150  cout << "REM: Adding " << *n << " to modified queue" << endl;
1151  modifiedNodeQ.push_back(n);
1152  }
1153  }
1154 }
1155 
1156 void LoadedCliqueAbstraction::removeNodeFromRepairQ(node *n)
1157 {
1158  // key is unsigned, so it has to be >= 0
1159  // if ((n->key >= 0) && (n->key < modifiedNodeQ.size()) &&
1160  // (modifiedNodeQ[n->key] == n))
1161  if ((n->key < modifiedNodeQ.size()) && (modifiedNodeQ[n->key] == n))
1162  {
1163  modifiedNodeQ[n->key] = modifiedNodeQ.back();
1164  modifiedNodeQ[n->key]->key = n->key;
1165  modifiedNodeQ.pop_back();
1166  }
1167 }
1168 
1169 void LoadedCliqueAbstraction::RemoveNode(node *n)
1170 {
1171  if (n == 0) return;
1172  if (verbose&kRepairGraph)
1173  cout << "REM: Removing " << *n << endl;
1174  removeNodeFromRepairQ(n);
1175  edge_iterator ei;
1176  ei = n->getEdgeIter();
1177  unsigned int absLevel = n->GetLabelL(kAbstractionLevel);
1178  for (edge *e = n->edgeIterNext(ei); e; e = n->edgeIterNext(ei))
1179  {
1180  edge *ep = findEdgeParent(e, absLevel);
1181  if (!ep)// edge is internal to a node
1182  {
1183  node *pNode = abstractions[absLevel+1]->GetNode(n->GetLabelL(kParent));
1184  if (!pNode) continue;
1185  addNodeToRepairQ(pNode);
1186  continue;
1187  }
1188  ep->SetLabelL(kEdgeCapacity, ep->GetLabelL(kEdgeCapacity)-1);
1189  if (ep->GetLabelL(kEdgeCapacity) == 0)
1190  {
1191  RemoveEdge(ep, n->GetLabelL(kAbstractionLevel)+1);
1192  }
1193  }
1194 
1195  node *np = findNodeParent(n);
1196  if (np)
1197  {
1198  resetLocationCache(np);
1199  //np->setLabel(kXCoordinate, -1);
1200  if (np->GetLabelL(kNumAbstractedNodes) == 1)
1201  {
1202  // our parent might be in the modified node Q. If it is,
1203  // we can just take it out
1204  removeNodeFromRepairQ(np);
1205 
1206  if (verbose&kRepairGraph)
1207  printf("Removing parent!\n");
1208  RemoveNode(np);
1209  n->SetLabelL(kParent, -1);
1210  } else {
1211  // find this node (n) and removed it from the list
1212  for (int x = 0; x < np->GetLabelL(kNumAbstractedNodes); x++)
1213  {
1214  if (np->GetLabelL(kFirstData+x) == (long)n->GetNum())
1215  {
1216  np->SetLabelL(kFirstData+x,
1217  np->GetLabelL((kFirstData+np->GetLabelL(kNumAbstractedNodes)-1)));
1218  break;
1219  }
1220  }
1221  np->SetLabelL(kNumAbstractedNodes, np->GetLabelL(kNumAbstractedNodes)-1);
1222  resetLocationCache(np);
1223  }
1224  }
1225  unsigned int oldID;
1226  // now we can safely remove this node from the Graph
1227  node *changed = abstractions[absLevel]->RemoveNode(n, oldID);
1228  // have to handle changing node here...rename it in the parent & children if necessary
1229  if (changed)
1230  {
1231  renameNodeInAbstraction(changed, oldID);
1232  }
1233 }
1234 
1235 void LoadedCliqueAbstraction::RepairAbstraction()
1236 {
1237  // actually want to sort items...based on abstraction level, doing
1238  // lowest abstraction level first
1239  while (modifiedNodeQ.size() > 0)
1240  {
1241  node *temp, *changed = modifiedNodeQ.back();
1242  modifiedNodeQ.pop_back();
1243  // selection sort...assuming that modifiedNodeQ is small for now
1244  for (unsigned int x = 0; x < modifiedNodeQ.size(); x++)
1245  {
1246  if (modifiedNodeQ[x]->GetLabelL(kAbstractionLevel) <
1247  changed->GetLabelL(kAbstractionLevel))
1248  {
1249  temp = modifiedNodeQ[x];
1250  modifiedNodeQ[x] = changed;
1251  changed->key = x;
1252  changed = temp;
1253  }
1254  }
1255  if (verbose&kRepairGraph)
1256  cout << "REM: Choosing to repair: " << *changed << endl;
1257  int count = getChildGroups(changed);
1258  if (count != 1)
1259  {
1260  if (verbose&kRepairGraph)
1261  cout << "REM: We got " << count << " groups out of " << *changed << endl;
1262  splitNode(changed, count);
1263  }
1264  }
1265 }
1266 
1267 /*
1268  * Takes a node and does a simple bfs on its children to find connected
1269  * components. Marks the group of each child with kTemporary label &
1270  * returns the number of groups found.
1271  */
1272 int LoadedCliqueAbstraction::getChildGroups(node *which)
1273 {
1274  std::vector<node *> seenStack;
1275  seenStack.reserve(which->GetLabelL(kNumAbstractedNodes));
1276  unsigned int absLevel = which->GetLabelL(kAbstractionLevel);
1277  if (absLevel == 0)
1278  return 0;
1279  Graph *g = abstractions[absLevel-1];
1280  for (int x = 0; x < which->GetLabelL(kNumAbstractedNodes); x++)
1281  {
1282  node *nextChild = g->GetNode(which->GetLabelL(kFirstData+x));
1283  nextChild->SetLabelL(kTemporaryLabel, -1);
1284  }
1285  int currGroup = -1;
1286  for (int x = 0; x < which->GetLabelL(kNumAbstractedNodes); x++)
1287  {
1288  node *nextChild = g->GetNode(which->GetLabelL(kFirstData+x));
1289 
1290  if (nextChild->GetLabelL(kTemporaryLabel) != -1)
1291  continue;
1292 
1293  currGroup++;
1294  nextChild->SetLabelL(kTemporaryLabel, currGroup);
1295  if (verbose&kRepairGraph)
1296  cout << *nextChild << " now assigned to group " << currGroup << endl;
1297  do {
1298  if (seenStack.size() > 0)
1299  {
1300  nextChild = seenStack.back();
1301  seenStack.pop_back();
1302  }
1303  edge_iterator ei = nextChild->getEdgeIter();
1304  for (edge *e = nextChild->edgeIterNext(ei); e; e = nextChild->edgeIterNext(ei))
1305  {
1306  unsigned int neighbor = (e->getFrom() == nextChild->GetNum()) ?
1307  (e->getTo()):(e->getFrom());
1308  if ((g->GetNode(neighbor)->GetLabelL(kParent) == (long)which->GetNum()) &&
1309  (g->GetNode(neighbor)->GetLabelL(kTemporaryLabel) == -1))
1310  {
1311  g->GetNode(neighbor)->SetLabelL(kTemporaryLabel, currGroup);
1312  if (verbose&kRepairGraph)
1313  cout << *g->GetNode(neighbor) << " now added to group " << currGroup << endl;
1314  seenStack.push_back(g->GetNode(neighbor));
1315  }
1316  }
1317  } while (seenStack.size() > 0);
1318  }
1319  return currGroup+1;
1320 }
1321 
1322 
1323 /*
1324  * Takes a node & splits it so that it is connected.
1325  */
1326 void LoadedCliqueAbstraction::splitNode(node *parent, int numGroups)
1327 {
1328  // get all children nodes that we are re-assigning
1329  std::vector<node *> children;
1330  children.reserve(parent->GetLabelL(kNumAbstractedNodes));
1331  for (int x = 0; x < parent->GetLabelL(kNumAbstractedNodes); x++)
1332  {
1333  children[x] = abstractions[parent->GetLabelL(kAbstractionLevel)-1]->
1334  GetNode(parent->GetLabelL(kFirstData+x));
1335  }
1336 
1337  // 1. if parent has no neighbors, we can just split the parent into separate pieces
1338  // since it has already been split. Then we're done.
1339  if (parent->GetNumEdges() == 0)
1340  {
1341  if (verbose&kRepairGraph)
1342  cout << "REM: parent has no neighbors, just splitting and ending" << endl;
1343  for (int x = 1; x < numGroups; x++)
1344  extractGroupIntoNewNode(parent, x);
1345  return;
1346  }
1347 
1348  std::vector<int> groupSize(numGroups);
1349  for (int x = 0; x < numGroups; x++) groupSize[x] = getGroupSize(parent, x);
1350  // now, progress through the following steps until we are done
1351  // 2. all single nodes with bf 1 should merge into neighbors
1352  // 3. other single nodes should try to join nodes if they can form a clique
1353  // 4. remaining single nodes abstract by themselves
1354  int reassigned = 0;
1355  for (int x = 0; x < numGroups; x++)
1356  {
1357  if (reassigned == numGroups-1) // done when we assign all but 1
1358  break;
1359  if (groupSize[x] == 1)
1360  {
1361  node *n = getNodeInGroup(parent, x);
1362  if (n->GetNumEdges() == 0)
1363  {
1364  if (verbose&kRepairGraph)
1365  cout << "REM: Reassigning group " << reassigned << " by splitting off group " << x << endl;
1366  extractGroupIntoNewNode(parent, x);
1367  reassigned++;
1368  }
1369  else if (n->GetNumEdges() == 1)
1370  {
1371  if (verbose&kRepairGraph)
1372  cout << "REM: Reassigning group " << reassigned << " by (neighbor) merging group " << x << endl;
1373  mergeGroupIntoNeighbor(parent, x);
1374  reassigned++;
1375  }
1376  else { // (n->GetNumEdges() > 1)
1377  node *neighbor;
1378  if ((neighbor = findNeighborCliques(parent, x)))
1379  {
1380  if (verbose&kRepairGraph)
1381  cout << "REM: Reassigning group " << reassigned << " by (neighbor) merging " << x << endl;
1382  mergeGroupIntoNeighbor(parent, x, neighbor);
1383  }
1384  else {
1385  if (verbose&kRepairGraph)
1386  cout << "REM: Reassigning group " << reassigned << " by extraction " << x << endl;
1387  extractGroupIntoNewNode(parent, x);
1388  }
1389  reassigned++;
1390  }
1391  }
1392  }
1393  // 5. all groups >= 2 nodes should break off by themselves
1394  // we do this last so that we make sure to abstract off any single nodes properly
1395  // no use leaving them sitting here alone if they could have gone off with another node,
1396  // and we sent a 2+ group off instead
1397  for (int x = 0; x < numGroups; x++)
1398  {
1399  if (reassigned == numGroups-1) // done when we assign all but 1
1400  break;
1401  if (getGroupSize(parent, x) > 0)
1402  {
1403  if (verbose&kRepairGraph)
1404  cout << "REM: Reassigning (big) group " << reassigned << " by extracting " << x << endl;
1405  extractGroupIntoNewNode(parent, x);
1406  reassigned++;
1407  }
1408  }
1409 }
1410 
1411 /*
1412  * Find any node in parent that is a member of "group"
1413  */
1414 node *LoadedCliqueAbstraction::getNodeInGroup(node *parent, int group)
1415 {
1416  Graph *g = abstractions[parent->GetLabelL(kAbstractionLevel)-1];
1417  for (int x = 0; x < parent->GetLabelL(kNumAbstractedNodes); x++)
1418  {
1419  node *nextChild = g->GetNode(parent->GetLabelL(kFirstData+x));
1420 
1421  if (nextChild->GetLabelL(kTemporaryLabel) == group)
1422  return nextChild;
1423  }
1424  return 0;
1425 }
1426 
1427 /*
1428  * Count how many nodes are a member of "group"
1429  */
1430 int LoadedCliqueAbstraction::getGroupSize(node *parent, int group)
1431 {
1432  Graph *g = abstractions[parent->GetLabelL(kAbstractionLevel)-1];
1433  int answer = 0;
1434  for (int x = 0; x < parent->GetLabelL(kNumAbstractedNodes); x++)
1435  {
1436  node *nextChild = g->GetNode(parent->GetLabelL(kFirstData+x));
1437  if (nextChild->GetLabelL(kTemporaryLabel) == group)
1438  answer++;
1439  }
1440  return answer;
1441 }
1442 
1443 /*
1444  * check to see if the node in the group can be merged into another
1445  * node as part of a clique. Returns the neighbor node at the child level
1446  */
1447 // PRECOND: group only has 1 node
1448 node *LoadedCliqueAbstraction::findNeighborCliques(node *parent, int group)
1449 {
1450  node *child = 0;
1451  Graph *g = abstractions[parent->GetLabelL(kAbstractionLevel)-1];
1452  for (int x = 0; x < parent->GetLabelL(kNumAbstractedNodes); x++)
1453  {
1454  node *nextChild = g->GetNode(parent->GetLabelL(kFirstData+x));
1455  if (nextChild->GetLabelL(kTemporaryLabel) == group)
1456  {
1457  child = nextChild;
1458  break;
1459  }
1460  }
1461  if (child)
1462  return findNeighborCliques(child);
1463  return 0;
1464 }
1465 
1466 /*
1467  * check to see if the node can be merged into another
1468  * node as part of a clique. Returns the neighbor node.
1469  */
1470 node *LoadedCliqueAbstraction::findNeighborCliques(node *child)
1471 {
1472  Graph *g = abstractions[child->GetLabelL(kAbstractionLevel)];
1473  edge_iterator ei = child->getEdgeIter();
1474  for (edge *e = child->edgeIterNext(ei); e; e = child->edgeIterNext(ei))
1475  {
1476  node *nextNode = g->GetNode((e->getFrom() == child->GetNum())?(e->getTo()):(e->getFrom()));
1477  if (checkNeighborClique(child, nextNode))
1478  return nextNode;
1479  }
1480  return 0;
1481 }
1482 
1483 /*
1484  * check to see if the node is connected to every other node in the group of
1485  * the neighbor. If a node has only 1 neighbor it doesn't have to be connected to
1486  * it, but it must be connected to at least 1 node and every node of degree 2 or greater
1487  */
1488 bool LoadedCliqueAbstraction::checkNeighborClique(node *child, node *neighbor)
1489 {
1490  node *neighborParent = abstractions[neighbor->GetLabelL(kAbstractionLevel)+1]->GetNode(neighbor->GetLabelL(kParent));
1491  if (neighborParent == 0)
1492  return false;
1493  Graph *g = abstractions[child->GetLabelL(kAbstractionLevel)];
1494  int matches = 0;
1495  for (int x = 0; x < neighborParent->GetLabelL(kNumAbstractedNodes); x++)
1496  {
1497  node *nextChild = g->GetNode(neighborParent->GetLabelL(kFirstData+x));
1498  // we only require that we connect to every node in the abstraction
1499  // that has more than 1 neighbor
1500  if (g->FindEdge(nextChild->GetNum(), child->GetNum()))
1501  matches++;
1502  else if (nextChild->GetNumEdges() > 1)
1503  return false;
1504  }
1505 
1506  if (matches) return true;
1507 
1508  return false;
1509 }
1510 
1511 /*
1512  * Take all nodes in group of parent and move them into neighbor's group
1513  * neighbor is one level lower than the parent
1514  */
1515 void LoadedCliqueAbstraction::mergeGroupIntoNeighbor(node *parent, int group, node *neighbor)
1516 {
1517  Graph *g;
1518  if (neighbor == 0)
1519  { // only 1 possible neighbor, so find it
1520  g = abstractions[parent->GetLabelL(kAbstractionLevel)-1];
1521  for (int x = 0; x < parent->GetLabelL(kNumAbstractedNodes); x++)
1522  {
1523  node *nextChild = g->GetNode(parent->GetLabelL(kFirstData+x));
1524  if (nextChild->GetLabelL(kTemporaryLabel) == group)
1525  {
1526  edge_iterator ei = nextChild->getEdgeIter();
1527  edge *e = nextChild->edgeIterNext(ei);
1528  if (e->getFrom() == nextChild->GetNum())
1529  neighbor = g->GetNode(e->getTo());
1530  else
1531  neighbor = g->GetNode(e->getFrom());
1532  break;
1533  }
1534  }
1535  }
1536  assert(neighbor->GetLabelL(kAbstractionLevel)+1 == parent->GetLabelL(kAbstractionLevel));
1537  if (verbose&kRepairGraph)
1538  cout << "Merging group " << group << " into " << *neighbor << endl;
1539  g = abstractions[parent->GetLabelL(kAbstractionLevel)];
1540  node *newParent = g->GetNode(neighbor->GetLabelL(kParent));
1541  if (verbose&kRepairGraph)
1542  cout << "(Child of " << *newParent << ")" << endl;
1543  // what happens if that node has no parent???
1544  if (newParent == 0)
1545  {
1546  printf("GOTTA HANDLE THE NO PARENT CASE IN mergeGroupIntoNeighbor --- but logic says we shouldn't hit this unless we add edges\n");
1547  exit(0);
1548  }
1549  if (newParent == parent)
1550  {
1551  printf("HOW DID THAT HAPPEN? oldParent = newParent\n");
1552  exit(0);
1553  }
1554  else {
1555  assert(parent->GetLabelL(kAbstractionLevel) == newParent->GetLabelL(kAbstractionLevel));
1556  transferGroup(group, parent, newParent);
1557  }
1558 }
1559 
1560 /*
1561  * take all member of group in parent and make them their own node
1562  */
1563 void LoadedCliqueAbstraction::extractGroupIntoNewNode(node *parent, int group)
1564 {
1565  // make new node...
1566  node *newNode;
1567  Graph *g = abstractions[parent->GetLabelL(kAbstractionLevel)];
1568 
1569  /*unsigned int gpNum = */g->AddNode(newNode = new node("split node"));
1570  newNode->SetLabelL(kAbstractionLevel, parent->GetLabelL(kAbstractionLevel));
1571  newNode->SetLabelL(kNumAbstractedNodes, 0);
1572  newNode->SetLabelL(kParent, -1);
1573  newNode->SetLabelF(kXCoordinate, kUnknownPosition);
1574  newNode->SetLabelL(kNodeBlocked, 0);
1575 
1576  transferGroup(group, parent, newNode);
1577 
1578  // now, what do I do with newNode? It needs to see if it can be combine with it's neighbors, etc...
1579  insertNodeIntoHierarchy(newNode);
1580 }
1581 
1582 /*
1583  * Given a new node that is connected, but doesn't have a parent or have its edges
1584  * abstracted, and insert it into Graph.
1585  */
1586 void LoadedCliqueAbstraction::insertNodeIntoHierarchy(node *newNode)
1587 {
1588  node *neighbor;
1589  if (newNode->GetNumEdges() == 0)
1590  return;
1591  if (newNode->GetNumEdges() == 1)
1592  {
1593  Graph *g = abstractions[newNode->GetLabelL(kAbstractionLevel)];
1594  edge *e = newNode->getEdge(0);
1595  node *newParent = g->GetNode((e->getFrom() == newNode->GetNum())?(e->getTo()):(e->getFrom()));
1596  checkAndCreateParent(newParent);
1597  g = abstractions[newNode->GetLabelL(kAbstractionLevel)+1];
1598  newParent = g->GetNode(newParent->GetLabelL(kParent));
1599 
1600  newParent->SetLabelL(kFirstData+newParent->GetLabelL(kNumAbstractedNodes), newNode->GetNum());
1601  newParent->SetLabelL(kNumAbstractedNodes, newParent->GetLabelL(kNumAbstractedNodes)+1);
1602  //newParent->setLabel(kXCoordinate, -1);
1603  resetLocationCache(newParent);
1604  if (verbose&kRepairGraph)
1605  {
1606  printf("Collapsing node into neighbor: ");
1607  printf("New parent (%d) now has %ld abstracted nodes\n", newParent->GetNum(),
1608  newParent->GetLabelL(kNumAbstractedNodes));
1609  }
1610  newNode->SetLabelL(kParent, newParent->GetNum());
1611  }
1612  else if ((neighbor = findNeighborCliques(newNode)))
1613  { // add newnode to neighbor's parent
1614  checkAndCreateParent(neighbor);
1615  node *parent = abstractions[neighbor->GetLabelL(kAbstractionLevel)+1]->GetNode(neighbor->GetLabelL(kParent));
1616  newNode->SetLabelL(kParent, parent->GetNum());
1617  parent->SetLabelL(kFirstData+parent->GetLabelL(kNumAbstractedNodes), newNode->GetNum());
1618  parent->SetLabelL(kNumAbstractedNodes, parent->GetLabelL(kNumAbstractedNodes)+1);
1619  //parent->setLabel(kXCoordinate, -1);
1620  resetLocationCache(parent);
1621  if (verbose&kRepairGraph)
1622  {
1623  printf("Cliquing node into neighbor: ");
1624  printf("New parent (%d) now has %ld abstracted nodes\n", parent->GetNum(),
1625  parent->GetLabelL(kNumAbstractedNodes));
1626  }
1627 
1628  unsigned int absLevel = newNode->GetLabelL(kAbstractionLevel);
1629  edge_iterator ei = newNode->getEdgeIter();
1630  for (edge *e = newNode->edgeIterNext(ei); e; e = newNode->edgeIterNext(ei))
1631  {
1632  abstractUpEdge(absLevel, e);
1633  }
1634  }
1635  else {
1636  if (verbose&kRepairGraph)
1637  cout << "We stay lonely: " << *newNode << endl;
1638  // add direct parent
1639  checkAndCreateParent(newNode);
1640  // add edges...
1641  unsigned int absLevel = newNode->GetLabelL(kAbstractionLevel);
1642  edge_iterator ei = newNode->getEdgeIter();
1643  for (edge *e = newNode->edgeIterNext(ei); e; e = newNode->edgeIterNext(ei))
1644  {
1645  abstractUpEdge(absLevel, e);
1646  }
1647  Graph *g = abstractions[absLevel+1];
1648  insertNodeIntoHierarchy(g->GetNode(newNode->GetLabelL(kParent)));
1649  }
1650 }
1651 
1652 /*
1653  * Check to see if a node has a parent. If it doesn't, create one, and optionally
1654  * extend the abstraction level of the Graph as well.
1655  */
1656 void LoadedCliqueAbstraction::checkAndCreateParent(node *which)
1657 {
1658  if (which->GetLabelL(kParent) != -1)
1659  return;
1660  unsigned int absLevel = which->GetLabelL(kAbstractionLevel);
1661  if (absLevel+1 == abstractions.size())
1662  {
1663  abstractions.push_back(new Graph());
1664  }
1665  node *parent;
1666  unsigned int id = abstractions[absLevel+1]->AddNode(parent = new node("created"));
1667  which->SetLabelL(kParent, id);
1668  parent->SetLabelL(kAbstractionLevel, absLevel+1);
1669  parent->SetLabelL(kNumAbstractedNodes, 1);
1670  parent->SetLabelL(kParent, -1);
1671  parent->SetLabelF(kXCoordinate, kUnknownPosition);
1672  parent->SetLabelL(kNodeBlocked, 0);
1673  parent->SetLabelL(kFirstData, which->GetNum());
1674 }
1675 
1676 /*
1677  * take all nodes in a group of old parent and move them into newParent
1678  */
1679 void LoadedCliqueAbstraction::transferGroup(int group, node *oldParent, node *newParent)
1680 {
1681  std::vector<node *> groupies;
1682 
1683  assert(oldParent->GetLabelL(kAbstractionLevel) == newParent->GetLabelL(kAbstractionLevel));
1684 
1685  groupies.reserve(oldParent->GetLabelL(kNumAbstractedNodes));
1686  Graph *g = abstractions[oldParent->GetLabelL(kAbstractionLevel)-1];
1687  for (int x = 0; x < oldParent->GetLabelL(kNumAbstractedNodes); x++)
1688  {
1689  node *nextNode = g->GetNode(oldParent->GetLabelL(kFirstData+x));
1690  if (nextNode->GetLabelL(kTemporaryLabel) == group)
1691  {
1692  groupies.push_back(nextNode);
1693 
1694  // before I move this node over, I have to change its old edges...FIRST
1695  edge_iterator ei = nextNode->getEdgeIter();
1696  for (edge *e = nextNode->edgeIterNext(ei); e; e = nextNode->edgeIterNext(ei))
1697  {
1698  edge *ep = findEdgeParent(e, nextNode->GetLabelL(kAbstractionLevel));
1699  if (ep)
1700  {
1701  ep->SetLabelL(kEdgeCapacity, ep->GetLabelL(kEdgeCapacity)-1);
1702  if (ep->GetLabelL(kEdgeCapacity) == 0)
1703  {
1704  RemoveEdge(ep, nextNode->GetLabelL(kAbstractionLevel)+1);
1705  }
1706  }
1707  }
1708 
1709  oldParent->SetLabelL(kFirstData+x, oldParent->GetLabelL(kFirstData+oldParent->GetLabelL(kNumAbstractedNodes)-1));
1710  oldParent->SetLabelL(kNumAbstractedNodes, oldParent->GetLabelL(kNumAbstractedNodes)-1);
1711  if (verbose&kRepairGraph)
1712  printf("Old parent (%d) now has %ld abstracted nodes\n", oldParent->GetNum(), oldParent->GetLabelL(kNumAbstractedNodes));
1713  newParent->SetLabelL(kFirstData+newParent->GetLabelL(kNumAbstractedNodes), nextNode->GetNum());
1714  newParent->SetLabelL(kNumAbstractedNodes, newParent->GetLabelL(kNumAbstractedNodes)+1);
1715  if (verbose&kRepairGraph)
1716  printf("New parent (%d) now has %ld abstracted nodes\n", newParent->GetNum(), newParent->GetLabelL(kNumAbstractedNodes));
1717  nextNode->SetLabelL(kParent, newParent->GetNum());
1718  resetLocationCache(oldParent);
1719  resetLocationCache(newParent);
1720  //oldParent->setLabel(kXCoordinate, -1);
1721  //newParent->setLabel(kXCoordinate, -1);
1722  x--;
1723  }
1724  }
1725 
1726  // g = abstractions[oldParent->GetLabelL(kAbstractionLevel)-1];
1727  for (unsigned int x = 0; x < groupies.size(); x++)
1728  {
1729  node *which = groupies[x];
1730  // now, re-add parent edges
1731  edge_iterator ei = which->getEdgeIter();
1732  for (edge *e = which->edgeIterNext(ei); e; e = which->edgeIterNext(ei))
1733  {
1734  if (verbose&kRepairGraph)
1735  cout << "Group member: " << *which << " has edge " << *e << " which we want to abstract up" << endl;
1736  abstractUpEdge(which->GetLabelL(kAbstractionLevel), e);
1737  }
1738  }
1739 
1740 }
1741 
1742 /*
1743  * given an edge e at a particular abstraction level, keep abstracting the edge
1744  * until it disappears...
1745  *
1746  * note that if we connect an orphan node (ie one with degree 1) we might
1747  * break the assumptions of the abstraction & then want to break a node out
1748  *
1749  * same thing with connecting a node with degree 0 to a node with degree 1
1750  */
1751 void LoadedCliqueAbstraction::abstractUpEdge(unsigned int absLevel, edge *e)
1752 {
1753  // 1 find edge in parent
1754  Graph *g = abstractions[absLevel];
1755  Graph *pg = abstractions[absLevel+1];
1756  int par1, par2;
1757  par1 = g->GetNode(e->getFrom())->GetLabelL(kParent);
1758  par2 = g->GetNode(e->getTo())->GetLabelL(kParent);
1759  if (par1 == par2)
1760  return;
1761  if (par1 == -1)
1762  { //addNodeToRepairQ(g->GetNode(e->getFrom()));
1763  if (verbose&kRepairGraph)
1764  cout << "This node has " << g->GetNode(e->getFrom())->GetNumEdges() <<
1765  " edge(s), but no parent: " << endl << *g->GetNode(e->getFrom()) << endl;
1766  return;
1767  }
1768  if (par2 == -1)
1769  { //addNodeToRepairQ(g->GetNode(e->getFrom()));
1770  if (verbose&kRepairGraph)
1771  cout << "This node has " << g->GetNode(e->getTo())->GetNumEdges() <<
1772  " edge(s), but no parent: " << endl << *g->GetNode(e->getTo()) << endl;
1773  return;
1774  }
1775  edge *pe = pg->FindEdge(par1, par2);
1776 
1777  // 2 if it exists, just add to the count
1778  if (pe)
1779  pe->SetLabelL(kEdgeCapacity, pe->GetLabelL(kEdgeCapacity)+1);
1780  // 3 if it doesn't exist, add it, and recurse
1781  else {
1782  pg->AddEdge(pe = new edge(par1, par2, h(pg->GetNode(par1), pg->GetNode(par2))));
1783  pe->SetLabelL(kEdgeCapacity, 1);
1784  if (verbose&kRepairGraph)
1785  cout << "*** Abstracting " << *e << " with edge " << *pe << endl;
1786  abstractUpEdge(absLevel+1, pe);
1787  }
1788 }
1789 
1790 void LoadedCliqueAbstraction::resetLocationCache(node *n)
1791 {
1792  unsigned int absLevel = n->GetLabelL(kAbstractionLevel);
1793  while (true)
1794  {
1795  n->SetLabelF(kXCoordinate, kUnknownPosition);
1796  int parent = n->GetLabelL(kParent);
1797  if (parent == -1)
1798  break;
1799  absLevel++;
1800  n = abstractions[absLevel]->GetNode(parent);
1801  }
1802 }
1803 
1804 node *LoadedCliqueAbstraction::findNodeParent(node *n)
1805 {
1806  unsigned int absLevel = n->GetLabelL(kAbstractionLevel);
1807  if (absLevel < abstractions.size()-1)
1808  return abstractions[absLevel+1]->GetNode(n->GetLabelL(kParent));
1809  return 0;
1810 }
1811 
1812 /*
1813  * Given an edge at a level of abstraction, find the edge that
1814  * this edge abstracts into.
1815  */
1816 edge *LoadedCliqueAbstraction::findEdgeParent(edge *e, unsigned int absLevel)
1817 {
1818  if (absLevel >= abstractions.size()-1) return 0;
1819 
1820  Graph *g = abstractions[absLevel];
1821 
1822  node *from = g->GetNode(e->getFrom());
1823  node *to = g->GetNode(e->getTo());
1824 
1825  g = abstractions[absLevel+1];
1826  from = g->GetNode(from->GetLabelL(kParent));
1827  to = g->GetNode(to->GetLabelL(kParent));
1828 
1829  if (from == to) return 0;
1830  return g->FindEdge(from->GetNum(), to->GetNum());
1831  // edge *ee = g->FindEdge(from->GetNum(), to->GetNum());
1832  // if (ee)
1833  // return ee;
1834  // return g->FindEdge(to->GetNum(), from->GetNum());
1835 }
1836 
1837 void LoadedCliqueAbstraction::renameNodeInAbstraction(node *which, unsigned int oldID)
1838 {
1839  unsigned int absLevel = which->GetLabelL(kAbstractionLevel);
1840 
1841  // adjust children
1842  if (absLevel > 0)
1843  {
1844  for (int x = 0; x < which->GetLabelL(kNumAbstractedNodes); x++)
1845  {
1846  abstractions[absLevel-1]->GetNode(which->GetLabelL(kFirstData+x))->SetLabelL(kParent, which->GetNum());
1847  }
1848  }
1849 
1850  // adjust parent
1851  if (absLevel < abstractions.size()-1)
1852  {
1853  node *parent = abstractions[absLevel+1]->GetNode(which->GetLabelL(kParent));
1854  if (parent)
1855  {
1856  for (int x = 0; x < parent->GetLabelL(kNumAbstractedNodes); x++)
1857  {
1858  if (parent->GetLabelL(kFirstData+x) == (long)oldID)
1859  {
1860  parent->SetLabelL(kFirstData+x, which->GetNum());
1861  break;
1862  }
1863  }
1864  }
1865  }
1866 }
LoadedCliqueAbstraction::getGroupSize
int getGroupSize(node *parent, int group)
Definition: LoadedCliqueAbstraction.cpp:1430
LoadedCliqueAbstraction::insertNodeIntoHierarchy
void insertNodeIntoHierarchy(node *newNode)
Definition: LoadedCliqueAbstraction.cpp:1586
Graph::AddNode
int AddNode(node *)
Definition: Graph.cpp:136
LoadedCliqueAbstraction::renameNodeInAbstraction
void renameNodeInAbstraction(node *which, unsigned int oldID)
Definition: LoadedCliqueAbstraction.cpp:1837
GraphAbstraction
A generic class for basic operations on Graph abstractions.
Definition: GraphAbstraction.h:63
LoadedCliqueAbstraction::splitNode
void splitNode(node *which, int numGroups)
Definition: LoadedCliqueAbstraction.cpp:1326
GraphAbstractionConstants
Definition: GraphAbstraction.h:22
node::SetLabelL
void SetLabelL(unsigned int index, long val) const
Definition: Graph.cpp:702
LoadedCliqueAbstraction::GetNodeLoc
recVec GetNodeLoc(node *n) const
Definition: LoadedCliqueAbstraction.cpp:158
LoadedCliqueAbstraction::loadGraph
Graph * loadGraph(char *fname)
Definition: LoadedCliqueAbstraction.cpp:195
LoadedCliqueAbstraction::abstractGraph
virtual Graph * abstractGraph(Graph *g)
Definition: LoadedCliqueAbstraction.cpp:425
node::SetLabelF
void SetLabelF(unsigned int index, double val) const
Definition: Graph.cpp:687
graphMove
Definition: GraphEnvironment.h:34
edge::getFrom
unsigned int getFrom() const
Definition: Graph.h:146
edge::getTo
unsigned int getTo() const
Definition: Graph.h:147
Graph::FindEdge
edge * FindEdge(unsigned int from, unsigned int to)
Finds an edge between nodes with ids from and to, no matter which direction.
Definition: Graph.cpp:230
recVec
A generic vector (essentially the same as a point, but offers normalization)
Definition: GLUtil.h:78
neighbor_iterator
unsigned int neighbor_iterator
Definition: Graph.h:34
graph_object::key
unsigned int key
Definition: Graph.h:54
recVec::z
GLdouble z
Definition: GLUtil.h:98
Heap.h
LoadedCliqueAbstraction::buildAbstractions
void buildAbstractions(Graph *)
Definition: LoadedCliqueAbstraction.cpp:396
LoadedCliqueAbstraction::levelDraw
unsigned long levelDraw
Definition: LoadedCliqueAbstraction.h:87
LoadedCliqueAbstraction::AddNode
virtual void AddNode(node *n)
add node to abstraction
Definition: LoadedCliqueAbstraction.cpp:1098
LoadedCliqueAbstraction::RepairAbstraction
void RepairAbstraction()
This must be called after any of the above add/remove operations.
Definition: LoadedCliqueAbstraction.cpp:1235
LoadedCliqueAbstraction::removeNodeFromRepairQ
void removeNodeFromRepairQ(node *n)
Definition: LoadedCliqueAbstraction.cpp:1156
Graph::AddEdge
void AddEdge(edge *)
Definition: Graph.cpp:170
LoadedCliqueAbstraction::VerifyHierarchy
virtual void VerifyHierarchy()
verify that the hierarchy is consistent
Definition: LoadedCliqueAbstraction.cpp:255
Graph::nodeIterNext
node * nodeIterNext(node_iterator &) const
Definition: Graph.cpp:303
edge_iterator
std::vector< edge * >::const_iterator edge_iterator
Definition: Graph.h:30
LoadedCliqueAbstraction::abstractUpEdge
void abstractUpEdge(unsigned int absLevel, edge *e)
Definition: LoadedCliqueAbstraction.cpp:1751
FPUtil.h
width
int width
Definition: SFML_HOG.cpp:54
LoadedCliqueAbstraction::cleanMemory
void cleanMemory()
Definition: LoadedCliqueAbstraction.cpp:375
GraphAbstractionConstants::kEdgeCapacity
@ kEdgeCapacity
Definition: GraphAbstraction.h:53
LoadedCliqueAbstraction::h
double h(node *a, node *b)
heuristic cost between any two nodes
Definition: LoadedCliqueAbstraction.cpp:60
neighbor
graphMove neighbor
Definition: RoadMap.h:17
LoadedCliqueAbstraction::DrawGraph
void DrawGraph(Graph *g) const
Definition: LoadedCliqueAbstraction.cpp:101
LoadedCliqueAbstraction::modifiedNodeQ
std::vector< node * > modifiedNodeQ
Definition: LoadedCliqueAbstraction.h:95
Graph
A generic Graph class.
Definition: Graph.h:66
Graph::GetNode
node * GetNode(unsigned long num)
Definition: Graph.cpp:152
node::getEdge
edge * getEdge(unsigned int which)
Definition: Graph.cpp:794
Graph::edgeIterNext
edge * edgeIterNext(edge_iterator &) const
Definition: Graph.cpp:320
GraphAbstractionConstants::kZCoordinate
@ kZCoordinate
Definition: GraphAbstraction.h:32
node_iterator
std::vector< node * >::const_iterator node_iterator
Definition: Graph.h:33
LoadedCliqueAbstraction.h
GraphAbstractionConstants::kNumAbstractedNodes
@ kNumAbstractedNodes
Definition: GraphAbstraction.h:26
edge::GetLabelL
long GetLabelL(unsigned int index) const
Definition: Graph.h:138
LoadedCliqueAbstraction::clearDisplayLists
void clearDisplayLists()
Definition: LoadedCliqueAbstraction.cpp:387
LoadedCliqueAbstraction::extractGroupIntoNewNode
void extractGroupIntoNewNode(node *parent, int group)
Definition: LoadedCliqueAbstraction.cpp:1563
node::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:749
LoadedCliqueAbstraction::mergeGroupIntoNeighbor
void mergeGroupIntoNeighbor(node *parent, int group, node *neighbor=0)
Definition: LoadedCliqueAbstraction.cpp:1515
Graph::getEdgeIter
edge_iterator getEdgeIter() const
Definition: Graph.cpp:315
LoadedCliqueAbstraction::RemoveEdge
void RemoveEdge(edge *e, unsigned int absLevel)
remove edge from abstraction
Definition: LoadedCliqueAbstraction.cpp:1110
GraphAbstractionConstants::kFirstData
@ kFirstData
Definition: GraphAbstraction.h:34
LoadedCliqueAbstraction::~LoadedCliqueAbstraction
virtual ~LoadedCliqueAbstraction()
Definition: LoadedCliqueAbstraction.cpp:55
verbose
const static int verbose
Definition: LoadedCliqueAbstraction.cpp:32
LoadedCliqueAbstraction::OpenGLDraw
void OpenGLDraw() const
Definition: LoadedCliqueAbstraction.cpp:89
LoadedCliqueAbstraction::displayLists
std::vector< GLuint > displayLists
Definition: LoadedCliqueAbstraction.h:92
Graph::GetNumEdges
int GetNumEdges()
Definition: Graph.cpp:397
LoadedCliqueAbstraction::findEdgeParent
edge * findEdgeParent(edge *e, unsigned int absLevel)
Definition: LoadedCliqueAbstraction.cpp:1816
edge::SetLabelL
void SetLabelL(unsigned int index, long val)
Definition: Graph.cpp:598
GraphAbstractionConstants::kAbstractionLevel
@ kAbstractionLevel
Definition: GraphAbstraction.h:25
LoadedCliqueAbstraction::LoadedCliqueAbstraction
LoadedCliqueAbstraction(char *)
Construct a new Graph hierarchy.
Definition: LoadedCliqueAbstraction.cpp:40
LoadedCliqueAbstraction::transferGroup
void transferGroup(int group, node *oldParent, node *newParent)
Definition: LoadedCliqueAbstraction.cpp:1679
kBuildGraph
@ kBuildGraph
Definition: LoadedCliqueAbstraction.cpp:27
LoadedCliqueAbstraction::getNodeInGroup
node * getNodeInGroup(node *parent, int group)
Definition: LoadedCliqueAbstraction.cpp:1414
GraphAbstractionConstants::kYCoordinate
@ kYCoordinate
Definition: GraphAbstraction.h:31
LoadedCliqueAbstraction::ToggleDrawAbstraction
void ToggleDrawAbstraction(int which)
Definition: LoadedCliqueAbstraction.cpp:80
kMiscMessages
@ kMiscMessages
Definition: LoadedCliqueAbstraction.cpp:29
Graph::GetNumNodes
int GetNumNodes()
Definition: Graph.cpp:403
LoadedCliqueAbstraction::RemoveNode
virtual void RemoveNode(node *n)
remove node from abstraction
Definition: LoadedCliqueAbstraction.cpp:1169
Graph::getNodeIter
node_iterator getNodeIter() const
Definition: Graph.cpp:298
LoadedCliqueAbstraction::findNeighborCliques
node * findNeighborCliques(node *parent, int group)
Definition: LoadedCliqueAbstraction.cpp:1448
node::nodeNeighborNext
int nodeNeighborNext(neighbor_iterator &) const
Definition: Graph.cpp:807
kQuiet
@ kQuiet
Definition: LoadedCliqueAbstraction.cpp:26
LoadedCliqueAbstraction::DrawLevelConnections
void DrawLevelConnections(node *n) const
Definition: LoadedCliqueAbstraction.cpp:137
LoadedCliqueAbstraction::checkAndCreateParent
void checkAndCreateParent(node *which)
Definition: LoadedCliqueAbstraction.cpp:1656
GraphAbstraction::abstractions
std::vector< Graph * > abstractions
Definition: GraphAbstraction.h:122
GraphAbstractionConstants::kXCoordinate
@ kXCoordinate
Definition: GraphAbstraction.h:30
node::GetLabelF
double GetLabelF(unsigned int index) const
Definition: Graph.h:215
Graph::printStats
void printStats()
Definition: Graph.cpp:467
std
Definition: CanonicalGraphEnvironment.h:26
GraphAbstractionConstants::kNodeBlocked
@ kNodeBlocked
Definition: GraphAbstraction.h:33
node::GetNum
unsigned int GetNum() const
Definition: Graph.h:176
GraphAbstractionConstants::kTemporaryLabel
@ kTemporaryLabel
Definition: GraphAbstraction.h:29
LoadedCliqueAbstraction::addNodesToParent
void addNodesToParent(Graph *g, node *n, node *parent, int width)
Definition: LoadedCliqueAbstraction.cpp:476
LoadedCliqueAbstraction::resetLocationCache
void resetLocationCache(node *n)
Definition: LoadedCliqueAbstraction.cpp:1790
LoadedCliqueAbstraction::findNodeParent
node * findNodeParent(node *n)
Definition: LoadedCliqueAbstraction.cpp:1804
GraphAbstractionConstants::kParent
@ kParent
Definition: GraphAbstraction.h:27
node::GetLabelL
long GetLabelL(unsigned int index) const
Definition: Graph.h:220
LoadedCliqueAbstraction::addTunnel
void addTunnel(node *n, Graph *g, node *newNode)
Definition: LoadedCliqueAbstraction.cpp:1027
node::getNeighborIter
neighbor_iterator getNeighborIter() const
Definition: Graph.cpp:802
GraphAbstractionConstants::kUnknownPosition
const double kUnknownPosition
Definition: GraphAbstraction.h:56
LoadedCliqueAbstraction::AddEdge
virtual void AddEdge(edge *e, unsigned int absLevel)
add edge to abstraction
Definition: LoadedCliqueAbstraction.cpp:1103
LoadedCliqueAbstraction::cliqueAbstractGraph
virtual Graph * cliqueAbstractGraph(Graph *g)
Definition: LoadedCliqueAbstraction.cpp:500
recVec::y
GLdouble y
Definition: GLUtil.h:98
kRepairGraph
@ kRepairGraph
Definition: LoadedCliqueAbstraction.cpp:28
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
node::edgeIterNext
edge * edgeIterNext(edge_iterator &) const
Definition: Graph.cpp:754
LoadedCliqueAbstraction::addNodeToRepairQ
void addNodeToRepairQ(node *n)
Definition: LoadedCliqueAbstraction.cpp:1138
recVec::x
GLdouble x
Definition: GLUtil.h:98
LoadedCliqueAbstraction::neighborAbstractGraph
virtual Graph * neighborAbstractGraph(Graph *g, int width=1)
Definition: LoadedCliqueAbstraction.cpp:430
node::getNumIncomingEdges
int getNumIncomingEdges()
Definition: Graph.cpp:789
node::GetNumEdges
int GetNumEdges()
Definition: Graph.h:204
LoadedCliqueAbstraction::Pathable
bool Pathable(node *from, node *to)
is there a legal path between these 2 nodes?
Definition: LoadedCliqueAbstraction.cpp:1055
VERSION
static const float VERSION
Definition: LinearRegression.cpp:20
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
node::getNumOutgoingEdges
int getNumOutgoingEdges()
Definition: Graph.cpp:784
LoadedCliqueAbstraction::getChildGroups
int getChildGroups(node *which)
Definition: LoadedCliqueAbstraction.cpp:1272
LoadedCliqueAbstraction::checkNeighborClique
bool checkNeighborClique(node *child, node *neighbor)
Definition: LoadedCliqueAbstraction.cpp:1488
edge
Edge class for connections between node in a Graph.
Definition: Graph.h:129
Generated by   doxygen 1.8.17