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