Source code: com/port80/graph/dot/impl/Anneal.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.ArrayList;
8 import java.util.Collections;
9 import java.util.HashSet;
10 import java.util.List;
11 import java.util.Set;
12
13 import com.port80.graph.dot.impl.GridFactory.GridIterator;
14 import com.port80.util.Debug;
15 import com.port80.util.SystemWatch;
16 import com.port80.util.msg;
17 import com.port80.util.struct.Heap;
18 import com.port80.util.struct.IHeap;
19
20 /**
21 * Anneal a placement of a VirtualGraph with dynamic created grid points
22 * and meeting spacing requirements.
23 *
24 * For bus->bus and vertex->bus routes, grid start from the vertex x-coordinates
25 * and edge-edge (ESPACING) spacing apart on both sides.
26 *
27 * For vertex->vertex routes, grid start from the src x-coordinates
28 * and with (dest.x-src.x)/ESPACING divisions such that grid points are aligned
29 * with both src.x and dest.x.
30 *
31 * Each grid point is checked against existing vertices to make sure there are
32 * proper spacings.
33 *
34 * . Since Grid are now created dynamically, static data (eg. crossCost) are now moved
35 * to VirtualVertex and Grid.vertex points to the static data in the VirtualVertex. If Grid
36 * do not corresponds to a vertex Grid.vertex==null. These are the only two types of
37 * Grid: ERASED and SPACE. VirtualVertex.erased indicates that the vertex is erased
38 * for routing.
39 *
40 * . Four main data structures are used. The fGraph.ranks, fSpaceTable, fGridTable and
41 * the GridHeap.
42 *
43 * Grid points are identified using the x-coordinate and rank. fGridTable contains the
44 * coordinates->Grid object mapping. If a Grid point do not exists, check of the
45 * fSpaceTable to see if a Grid point should be allocated at the coordinate.
46 *
47 * fSpaceTable contains the vertex positions and dimensions for lookup of available space
48 * for a Grid. A binary search with an x-coordinate as key return an index such that
49 * index/2==vertex.order, index%2==0 indicates it hit the space before the vertex
50 * index%2==1 indicates it hit the vertex (or the reserved spacing around the vertex).
51 * If the coordinate hit a vertex, further check of vertex.isErased is needed to see
52 * if the space is available.
53 *
54 * If a Grid point do not exists and the coordinate is located in a space region, a Grid point
55 * can be allocated on the GridHeap by GridHeap.enqueue(). GridHeap keeps a pool of
56 * allocated Grid objects. enqueue() take a spare object from the spare pool and
57 * populate it with the provided values. Once enqueued, the Grid object should never be
58 * dequeued. A peek() at the top returns the lowest cost Grid which can be used for
59 * expansion. When new Grids are enqueued, the top Grid would be rearranged to a new
60 * priority according to its cost and a new top Grid object would automatically stay at the
61 * top of the heap for next expansion. If the cost of an existing Grid object on the heap
62 * is changed, the object should be requeue() to move it to the proper location on the heap.
63 *
64 * When the AStar algorithm is completed, the Grid list of the best path is retreived and
65 * the ERASED vertices are moved the the x-coordinates indicated by Grid.x.
66 * VirtualVertex.order are adjusted if neccessary.
67 *
68 * . Output from MinCross and Position often contains some very
69 * obvious layout problem mainly due to MinCross having no distance
70 * information consider those cases as equivalent. Especially for
71 * bus routing, there are lots of opportunities to improve the
72 * layout by taking advantage the fact that anywhere on the bus is
73 * equivalent.
74 *
75 * . shortestPath() try to find a point to line or point to point
76 * path with minimum distance in the VirtualGraph with placement.
77 * Another pass of Position may be required to compact the layout
78 * afterwards.
79 *
80 * For bus-bus connections, shortestPath() is run on both end
81 * points. For point to point connections, shortest path from
82 * either end point should be the same. However, since layout may
83 * have changed after shortestPath() is run from the first end
84 * point, it may be useful to run again on the other end point for
85 * maximum optimization.
86 *
87 * shortestPath() use A* algorithm. The layout is converted to a
88 * grid. Instead of a uniform grid, each rank is divided into
89 * segments of vertices and inter-vertex spacings. Vertex have a
90 * point coordinate and occupy the grid interval from
91 *
92 * floor(v.x-v.leftWidth-vertexSpacing/4) to
93 * ceil(v.x+v.rightWidth+vertexSpacing/4).
94 *
95 * The inter-vertex spacing is the interval between two vertices
96 * with both sides aligned to the grid and width=vertexSpacing/4.
97 *
98 * Transversal are directional, up or down. In down transversal,
99 * only cells in the lower row are neighbours.
100 *
101 * Cost of transversing from one cell to the other is consists of
102 * two costs, a static cost is pre-calculated for the current map
103 * (cross and distance cost) from one cell to the other. Another
104 * portion of the cost are determined on each visit (eg. cost for
105 * turns).
106 *
107 * The list of neighbours are determined on each visit depends on
108 * up/down transversal. Vertices occupied by old path are marked
109 * so they are candidate as neighbours. All other vertices are
110 * excluded as neighbour.
111 *
112 * Static costs:
113 *
114 * . Cross cost and distance cost for each pair of cells are
115 * pre-calculated before start. Cross cost are updated after
116 * each route changes. To reduce slope of paths, distance cost
117 * is proportional to square of grid count, so long horizontal
118 * path would be distributed as short segments in each rank.
119 *
120 * Dynamic costs:
121 *
122 * . To avoid path from zigzagging, a cost is associated with each
123 * turn.
124 *
125 * NOTE:
126 *
127 * . After an edge chain is erased before routing, the vertex cells
128 * still keep the .vertex and .crossCost fields valid and used for
129 * cross cost calculations.
130 *
131 * HISTORY:
132 *
133 * . 05/13/2002 Speed improvement by incrementally adjust crossCost
134 * information instead of recalc. on each eraseTrail (without
135 * installPath() optimization.
136 * This speed up Anneal() on 'testdot00' from ~60sec. to ~35sec.
137 * . Expand routeStraightLine() to allow offset!=0.
138 * Improves Anneal() on 'testdot00' from 35sec. to 30sec (Athlon 700MHz).
139 * . 09/13/2002 Switch from cell based to dynamic grid.
140 *
141 * TODO:
142 *
143 * . Anneal route of the longest top 10% routes.
144 * . Regression test on rank cost calculations.
145 *
146 */
147 public class Anneal {
148
149 ////////////////////////////////////////////////////////////////////////
150
151 private static final String NAME = "Anneal";
152 /** Verbose+terse intermediate results. */
153 private static final boolean TERSE = false;
154 /** Debug info. */
155 private static final boolean DEBUG = false;
156 /** Show time, statistics and final result. */
157 private static boolean VERBOSE = Debug.isVerbose();
158 /** Enable checkings. */
159 private static final boolean CHECK = Debug.isCheck();
160
161 /** Offsets that routeStraightLine() would search. */
162 private static final int[] OFFSETS = { 0, 1, -1, 2, -2, 3, -3, 4, -4 };
163 private static final float fMINPTPCOST = 1.05f;
164
165 // Instance fields /////////////////////////////////////////////////////
166 //
167
168 //
169 // Layout parameters from IGraph.
170 //
171 private int fPTP_PERCENT;
172
173 VirtualGraph fGraph;
174 int fMaxIter;
175 //
176 VirtualGraph.Rank[] fRanks;
177 int fMinRank, fMaxRank;
178 //
179 /** Set of VirtualEdge (chaintail) to be ignored (eg. alway have min. cost).*/
180 Set fIgnoreSet;
181 GridFactory fGridFactory;
182 GridHeap fOpenQueue;
183 ErasedPath fErasedPath;
184 List fNewPath;
185 Stat fStat;
186 //
187 int fRoutedCount;
188 int fImprovedCount;
189 int fStraightCount;
190 /** Sorted open cells.*/
191 private int fXSpacing;
192 private int fYSpacing;
193 private int fMaxCol;
194 //
195 /** Counters for rankCost().*/
196 private int[] fCrossCounts;
197 /** Edge chain being routed indexed by rown instead of rank.*/
198 private VirtualEdge[] fCurChain;
199
200 ////////////////////////////////////////////////////////////////////////
201
202 public static final int dot(VirtualGraph g, int griddiv, int maxiter) {
203 return new Anneal(g, griddiv).reRoute(maxiter);
204 }
205
206 public Anneal(VirtualGraph g, int griddiv) {
207 //
208 fGraph = g;
209 //
210 fRanks = fGraph.ranks;
211 fMinRank = fGraph.minRank;
212 fMaxRank = fGraph.maxRank;
213 fXSpacing = fGraph.getVertexSpacing();
214 fYSpacing = fGraph.getRankSpacing();
215 //
216 fPTP_PERCENT = fGraph.fPTP_PERCENT;
217 //
218 Grid.configure(fGraph);
219 //
220 fCurChain = new VirtualEdge[fMaxRank - fMinRank + 1];
221 fIgnoreSet = new HashSet(100);
222 fOpenQueue = new GridHeap(1024);
223 fGridFactory = new GridFactory(fGraph, griddiv);
224 fErasedPath = new ErasedPath(fGraph);
225 fStat = new Stat();
226 fNewPath=new ArrayList(20);
227 int maxvts = 0;
228 for (int r = fMinRank; r <= fMaxRank; ++r) {
229 if (fRanks[r].nVts > maxvts)
230 maxvts = fRanks[r].nVts;
231 }
232 fCrossCounts = new int[maxvts];
233 //
234 fGraph.staticCost();
235 }
236
237 public final int reRoute(int maxiter) {
238 //
239 SystemWatch timer = null;
240 if (VERBOSE)
241 timer = new SystemWatch().start();
242 //
243 fRoutedCount = 0;
244 fImprovedCount = 0;
245 //
246 VirtualEdge e;
247 VirtualEdge[] outs;
248 List chainlist=fGraph.getChainList();
249 Collections.sort(chainlist, new VirtualChain.ChainTypeComparator());
250 //
251 int totalimproved = 0;
252 totalimproved += rerouteBuses(chainlist, maxiter);
253 totalimproved += reroutePTP(chainlist, maxiter);
254 //
255 if (VERBOSE) {
256 msg.println(
257 "###\n### "
258 + NAME
259 + ".reRoute(): "
260 + totalimproved
261 + "/"
262 + (fRoutedCount)
263 + " improved routes, max allocated/queue size="
264 + fGridFactory.getMaxSize()
265 + "/"
266 + fOpenQueue.getMaxSize()+", "
267 + timer.stop().toString()
268 + "\n###\n");
269 }
270 return totalimproved;
271 }
272
273 /**
274 * Route the given edge chain.
275 *
276 * @enter fIgnoreSet, staticCost() must have been called.
277 * @return True if chain is routed with better cost than before, else false and chain routing is unchanged.
278 */
279 public boolean route(VirtualChain chain, boolean isdown, String message) {
280 boolean improved = false;
281 fStat.clear();
282 if (CHECK) {
283 msg.println(NAME + ".route(): checkCrossCosts():");
284 fGraph.checkCrossCosts();
285 }
286 float oldcost = 0;
287 oldcost = fErasedPath.erase(chain, isdown);
288 if (oldcost == 0) {
289 fIgnoreSet.add(chain);
290 if (DEBUG)
291 msg.println(NAME + ".route(): ignored\n");
292 return false;
293 }
294 Grid end = null;
295 //
296 // Attempt a straigth line routing for the path from src to dest.
297 //
298 fGridFactory.initGrid(fErasedPath.src, fErasedPath.dest);
299 if (fErasedPath.isBusRoute()) {
300 end = aStar(chain, fErasedPath, fErasedPath.fastCost());
301 if (end != null) {
302 // fIgnoreSet.add(isdown ? chain[src.rown] : chain[dest.rown]);
303 if (VERBOSE)
304 msg.println(
305 "\tFast: limit=" + fErasedPath.fastCost() + ", cost=" + end.curCost);
306 ++fStraightCount;
307 }
308 }
309 // Find route using aStar algorithm.
310 if (end == null) {
311 end = aStar(chain, fErasedPath, fErasedPath.oldCost);
312 }
313 ++fRoutedCount;
314 return routePath(end);
315 }
316
317 public void clear() {
318 fIgnoreSet.clear();
319 fErasedPath.clear();
320 fOpenQueue.clear();
321 fGridFactory.clear();
322 fStat.clear();
323 }
324
325 ////////////////////////////////////////////////////////////////////////
326
327 int rerouteBuses(List chainlist, int maxiter) {
328 SystemWatch timer = null;
329 SystemWatch timer1 = null;
330 if (VERBOSE)
331 timer = new SystemWatch().start();
332 //
333 Grid[] row;
334 Grid src;
335 int totalimproved = 0;
336 int totalstraight = 0;
337 int lastcount = 0;
338 int iter;
339 VirtualChain chain;
340 for (iter = 0; iter < maxiter; ++iter) {
341 if (VERBOSE)
342 timer1 = new SystemWatch().start();
343 fImprovedCount = 0;
344 fStraightCount = 0;
345 for (int i = 0; i < chainlist.size(); ++i) {
346 rerouteBusChain((VirtualChain) chainlist.get(i));
347 if (CHECK)
348 sanityCheck();
349 }
350 if (VERBOSE) {
351 msg.println(
352 NAME
353 + ".reRouteBuses(): pass="
354 + iter
355 + " : "
356 + fImprovedCount
357 + ","
358 + fStraightCount
359 + " improved,straight routes, "
360 + (fRoutedCount - lastcount)
361 + "/"
362 + chainlist.size()
363 + " routed, "
364 + fIgnoreSet.size()
365 + " ignores, "
366 + timer1.stop().toString());
367 }
368 if (fImprovedCount == 0)
369 break;
370 totalimproved += fImprovedCount;
371 totalstraight += fStraightCount;
372 lastcount = fRoutedCount;
373 }
374 if (iter < maxiter)
375 ++iter;
376 if (VERBOSE) {
377 msg.println(
378 "\n### "
379 + NAME
380 + ".reRouteBuses(): total passes="
381 + (iter + 1)
382 + ": "
383 + totalimproved
384 + ","
385 + totalstraight
386 + " improved,straight routes, "
387 + fRoutedCount
388 + "/"
389 + (iter * chainlist.size())
390 + " routed, "
391 + fIgnoreSet.size()
392 + " ignores, "
393 + timer.stop().toString()
394 + "\n");
395 }
396 return totalimproved;
397 }
398
399 int reroutePTP(List chainlist, int maxiter) {
400 //
401 SystemWatch timer = null;
402 //
403 int totalimproved = 0;
404 IHeap ptpheap = new Heap(new VirtualChain.PTPSlackComparator());
405 //
406 VirtualChain chain;
407 for (int iter = 0; iter < maxiter; ++iter) {
408 if (VERBOSE)
409 timer = new SystemWatch().start();
410 ptpheap.clear();
411 for (int i = 0; i < chainlist.size(); ++i) {
412 chain = (VirtualChain) chainlist.get(i);
413 if (chain.fHead.isReal()
414 && chain.fTail.isReal()
415 && (chain.fHead.rank - chain.fTail.rank > 1)) {
416 chain.updateLength();
417 if (chain.getSlack() > fMINPTPCOST)
418 ptpheap.enqueue(chain);
419 }
420 }
421 int max = (ptpheap.size() * fPTP_PERCENT) / 100;
422 if (VERBOSE)
423 msg.println(
424 NAME
425 + ".reroutePTP(): iter="
426 + iter
427 + ", total="
428 + ptpheap.size()
429 + ", candidates="
430 + max
431 + "\n");
432 int count = 0;
433 int improved = 0;
434 for (int i = 0; i < max; ++i) {
435 chain = (VirtualChain) ptpheap.dequeue();
436 ++count;
437 if (DEBUG)
438 msg.println(NAME + ".reroutePTP(): count=" + count + ": chain=" + chain);
439 if (route(chain, true, "reroutePTP(): "))
440 ++improved;
441 if (CHECK)
442 sanityCheck();
443 }
444 if (VERBOSE) {
445 msg.println(
446 "\n### "
447 + NAME
448 + ".reRoutePTP(): iter="
449 + iter
450 + ": "
451 + improved
452 + "/"
453 + count
454 + "/"
455 + max
456 + " improved/routed/candidates routes, "
457 + timer.stop().toString()
458 + "\n");
459 }
460 if (improved == 0)
461 break;
462 totalimproved += improved;
463 }
464 return totalimproved;
465 }
466
467 GridFactory getGridFactory() {
468 return fGridFactory;
469 }
470
471 ////////////////////////////////////////////////////////////////////////
472
473 boolean rerouteBusChain(VirtualChain chain) {
474 if (!(chain.fTail.isBus() || chain.fHead.isBus()))
475 return false;
476 // For now, only route VERTEX->BUS or BUS->BUS forward and backward.
477 if (fIgnoreSet.contains(chain.fChainTail)) {
478 if (DEBUG)
479 msg.println(NAME + ".rerouteBusChain(): ignored: chain=" + chain.fChainTail);
480 return false;
481 }
482 if (DEBUG)
483 msg.println(NAME + ".reRouteBusChain(): chain=" + chain);
484 boolean improved = false;
485 if (chain.fHead.isBus()) {
486 if (route(chain, true, "rerouteBusChain(): Down"))
487 improved = true;
488 }
489 if (chain.fTail.isBus()) {
490 if (route(chain, false, "rerouteBusChain(): Up"))
491 improved = true;
492 }
493 // if (!improved)
494 // fIgnoreSet.add(chain.fChainTail);
495 return improved;
496 }
497
498 ////////////////////////////////////////////////////////////////////////
499
500 boolean sanityCheck() {
501 //TODO: Check that no ERASED Grid.
502 return fGraph.checkCrossCosts();
503 }
504
505 ////////////////////////////////////////////////////////////////////////
506
507 /** Calculate crossing cost for edge from parent to child below.
508 * child.
509 *
510 * @param parent parent cell for the segment.
511 * @param child child cell (below parent) for the segment.
512 * @param beforeParent Vertex cell before parent or parent itself.
513 * @param beforeChild Vertex cell before child or the child itself.
514 * @param segment is the edge in this rank being routed.
515 *
516 * beforeParent parent
517 * v--------|
518 * beforeChild child
519 */
520 int crossAfter(
521 Grid parent,
522 Grid child,
523 VirtualVertex beforeParent,
524 VirtualVertex beforeChild,
525 VirtualEdge segment) {
526 if (beforeParent == null && beforeChild == null)
527 return 0;
528 if (beforeParent == null)
529 return crossBeforeAfter(parent, child, beforeChild, segment);
530 if (beforeChild == null)
531 return crossAfterBefore(parent, child, beforeParent, segment);
532 int ret = beforeParent.crossCost[beforeChild.order];
533 int order;
534 VirtualVertex v;
535 VirtualEdge e;
536 // Additional crossing at before parent.
537 if (parent.vertex != beforeParent) {
538 order = beforeChild.order;
539 v = beforeParent;
540 for (int i = 0; i < v.outs.length; ++i) {
541 e = v.outs[i];
542 if (e == segment)
543 continue;
544 if (e.head.order > order)
545 ret += e.xPenalty;
546 }
547 }
548 if (child.vertex != beforeChild) {
549 order = beforeParent.order;
550 v = beforeChild;
551 for (int i = 0; i < v.ins.length; ++i) {
552 e = v.ins[i];
553 if (e == segment)
554 continue;
555 if (e.tail.order > order)
556 ret += e.xPenalty;
557 }
558 }
559 if (false)
560 msg.println(
561 NAME
562 + ".crossAfter():"
563 + "\n\t parent="
564 + parent
565 + "\n\t child="
566 + child
567 + "\n\t beforeParent="
568 + beforeParent
569 + "\n\t beforeChild="
570 + beforeChild
571 + "\n\t segment="
572 + segment
573 + "\n\t ret="
574 + ret);
575 ret *= segment.xPenalty;
576 return ret;
577 }
578
579 /** Calculate crossing cost for edge from parent to space before
580 * the first vertex below. The cost=crossCost(parent,child)
581 * +e.xPenalty*(xPenalty of all edges from vertex on left of
582 * parent to child).
583 *
584 * beforeParent parent
585 * |
586 * v-------------------
587 * child vts[0](afterChild)
588 *
589 * @param parent parent cell for the route.
590 * @param child child cell (below parent) for the route.
591 * @param beforeParent Vertex cell before parent or parent itself.
592 * @param route is the edge in this rank being routed.
593 */
594 private int crossAfterBefore(Grid parent, Grid child, VirtualVertex beforeParent, VirtualEdge segment) {
595 if (beforeParent == null)
596 return 0;
597 VirtualVertex afterChild = fGraph.ranks[segment.head.rank].vts[0];
598 int ret = beforeParent.crossCost[afterChild.order];
599 int order;
600 VirtualEdge e;
601 order = 0;
602 VirtualVertex v = beforeParent;
603 if (v != parent.vertex) {
604 for (int i = 0; i < v.outs.length; ++i) {
605 e = v.outs[i];
606 if (e == segment)
607 continue;
608 if (e.head.order >= order)
609 ret += e.xPenalty;
610 }
611 }
612 order = beforeParent.order;
613 v = afterChild;
614 for (int i = 0; i < v.ins.length; ++i) {
615 e = v.ins[i];
616 if (e == segment)
617 continue;
618 if (e.tail.order < order)
619 ret += e.xPenalty;
620 }
621 ret *= segment.xPenalty;
622 if (false)
623 msg.println(
624 NAME
625 + ".crossAfterBefore():"
626 + "\n\t parent="
627 + parent
628 + "\n\t child="
629 + child
630 + "\n\t beforeParent="
631 + beforeParent
632 + "\n\t afterChild="
633 + afterChild
634 + "\n\t segment="
635 + segment
636 + "\n\t ret="
637 + ret);
638 return ret;
639 }
640
641 /**
642 *
643 * parent vts[0](afterParent)
644 * |-------------------v
645 * beforechild child
646 */
647 private int crossBeforeAfter(Grid parent, Grid child, VirtualVertex beforeChild, VirtualEdge segment) {
648 if (beforeChild == null)
649 return 0;
650 VirtualVertex afterParent = fGraph.ranks[segment.tail.rank].vts[0];
651 int ret = afterParent.crossCost[beforeChild.order];
652 int order;
653 VirtualEdge e;
654 // Additional crossing at afterParent.
655 order = beforeChild.order;
656 VirtualVertex v = afterParent;
657 for (int i = 0; i < v.outs.length; ++i) {
658 e = v.outs[i];
659 if (e == segment)
660 continue;
661 if (e.head.order <= order)
662 ret += e.xPenalty;
663 }
664 // Additional crossing at beforeChild.
665 order = 0;
666 v = beforeChild;
667 if (v != child.vertex) {
668 for (int i = 0; i < v.ins.length; ++i) {
669 e = v.ins[i];
670 if (e == segment)
671 continue;
672 if (e.tail.order > order)
673 ret += e.xPenalty;
674 }
675 }
676 ret *= segment.xPenalty;
677 if (false)
678 msg.println(
679 NAME
680 + ".crossBeforeAfter():"
681 + "\n\t parent="
682 + parent
683 + "\n\t child="
684 + child
685 + "\n\t afterParent="
686 + afterParent
687 + "\n\t beforeChild="
688 + beforeChild
689 + "\n\t segment="
690 + segment
691 + "\n\t ret="
692 + ret);
693 return ret;
694 }
695
696 ////////////////////////////////////////////////////////////////////////
697
698 /**
699 * Route path according to the newpath if cost improved,
700 * else restore old erased path.
701 *
702 * @return New dest. Grid if improved, else null.
703 */
704 private boolean routePath(Grid end) {
705
706 VirtualChain chain = fErasedPath.fChain;
707 if (end == null) {
708 fErasedPath.restore();
709 if (VERBOSE)
710 msg.println(
711 "\t" + fStat.toString() + ", allocated grids=" + fGridFactory.size() + "\n");
712 return false;
713 }
714 //
715 boolean isdown = fErasedPath.isDown();
716 float oldcost = fErasedPath.oldCost;
717 //
718 Grid grid;
719 fNewPath.clear();
720 getPath(end, isdown, fNewPath);
721 float newcost = end.curCost;
722 if (DEBUG) {
723 msg.println("# " + NAME + ".route(): newcost=" + newcost + ", newpath=");
724 for (int i = 0; i < fNewPath.size(); ++i) {
725 grid = (Grid) fNewPath.get(i);
726 msg.println("\t" + grid);
727 }
728 }
729 if (VERBOSE) {
730 msg.println(
731 NAME
732 + ".routePath(): "
733 + "e="
734 + chain.fChainTail.getOriginalName()
735 + "\n\t"
736 + ((newcost < oldcost) ? "* " : "")
737 + "oldcost="
738 + oldcost
739 + ", newcost="
740 + newcost
741 + "\n\t"
742 + fStat.toString()
743 + ", allocated grids="
744 + fGridFactory.size()
745 + "\n");
746 }
747 // Print new path as GeneralPath.
748 if (TERSE) {
749 VirtualEdge e = chain.fChainTail;
750 VirtualVertex v = e.tail;
751 StringBuffer buf = new StringBuffer();
752 for (int i = 0; i < fNewPath.size(); ++i) {
753 grid = (Grid) fNewPath.get(i);
754 if (i == 0 || i == fNewPath.size() - 1)
755 grid.toGeneralPath(buf, "black");
756 else
757 grid.toGeneralPath(buf, "green");
758 if (e != null) {
759 v = e.head;
760 e = e.next;
761 }
762 }
763 msg.println(buf.toString());
764 }
765 if (newcost >= oldcost) {
766 fErasedPath.restore();
767 return false;
768 } else {
769 installPath(fNewPath);
770 // return (isdown ? newpath.cells[newpath.size() - 1] : newpath.cells[0]);
771 return true;
772 }
773 }
774
775 /**
776 * Install the new path.
777 *
778 * Since the new route may have changed the vertex ordering in
779 * the ranks, VirtualVertex.order need to be reassigned.
780 *
781 * @param newpath New path from low rank to high rank and includes the src and dest cells.
782 */
783 private void installPath(List newpath) {
784 Grid grid;
785 VirtualVertex vertex;
786 VirtualGraph.Rank rank;
787 int x, order, neworder;
788 VirtualChain chain = fErasedPath.fChain;
789 VirtualEdge e = chain.fChainTail;
790 for (int i = 0; i < newpath.size(); ++i) {
791 vertex = fErasedPath.get(i);
792 if (vertex == null)
793 continue;
794 grid = (Grid) newpath.get(i);
795 x = vertex.x;
796 order = vertex.order;
797 //
798 // Move erased Grid to new position.
799 // The new Grid 'c' may or may not be same as the vertex Grid 'vertex'.
800 //
801 vertex.x = grid.x;
802 // Restore to proper type if ERASED.
803 vertex.restore();
804 // Update space table in case x is changed.
805 fGridFactory.updateSpaceTable(vertex);
806 //
807 // If new location >=ERASED, order is unchanged.
808 // If new location is a SPACE Grid, update order.
809 //
810 if (grid.vertex == null) {
811 neworder = 0;
812 if (grid.leftVertex != null) {
813 neworder = grid.leftVertex.order;
814 if (neworder < order)
815 ++neworder;
816 }
817 if (neworder != order) {
818 // SPACE Grid, update vertex orders.
819 rank = fRanks[vertex.rank];
820 rank.moveVertex(order, neworder);
821 fGridFactory.moveVertex(vertex, order, neworder);
822 }
823 } else if (CHECK) {
824 if (grid.vertex != vertex)
825 msg.err(
826 "Unerased vertex is used for routing:"
827 + "\n\told vertex="
828 + vertex
829 + "\n\tused vertex="
830 + grid.vertex);
831 }
832 if (e != null)
833 e = e.next;
834 if (TERSE)
835 msg.println(
836 NAME
837 + ".installPath(): old x="
838 + x
839 + ", new x="
840 + vertex.x
841 + ",old order="
842 + order
843 + ", new order="
844 + vertex.order
845 + "\n\te="
846 + e);
847 }
848 if (CHECK) {
849 fGraph.sanityCheck();
850 fGridFactory.sanityCheck();
851 }
852 // Update rank costs.
853 //
854 // NOTE: Since rankCost() calculate and save crosscost between
855 // each pair of vertices in rank r and r+1, order change in
856 // rank r affect rankCost of r-1 and r.
857 //
858 //FIXME: Since the edge is just moved, actually only imaginary
859 // edges with vertex inside the order changed region are affected.
860 // Imaginary edges that cross the region still see that edge.
861 // And imaginary edges that do not cross the region but both
862 // vertices are outside are not affected by the move.
863 if (fErasedPath.isDown())
864 for (int r = chain.fTail.rank; r <= chain.fHead.rank && r < fMaxRank; ++r)
865 fGraph.staticRankCost(r);
866 else
867 for (int r = Math.min(chain.fTail.rank - 1, fMinRank); r < chain.fHead.rank; ++r)
868 fGraph.staticRankCost(r);
869 // if (DEBUG) {
870 // msg.println(NAME + ".installPath(): checkCrossCosts():");
871 // checkCrossCosts();
872 // }
873 fImprovedCount++;
874 }
875
876 /**
877 * @return Grid path end at 'cell'.
878 * Return path always in order from low to high rank.
879 */
880 private void getPath(Grid end, boolean isdown, List ret) {
881 if (isdown) {
882 if (end.parent != null)
883 getPath(end.parent, isdown, ret);
884 ret.add(end);
885 } else {
886 ret.add(end);
887 if (end.parent != null)
888 getPath(end.parent, isdown, ret);
889 }
890 }
891
892 // AStar implementation ////////////////////////////////////////////////
893 //
894
895 /**
896 * @enter GridFactory.initGrid(src,dest) must have been called to init static Grid information before enter.
897 */
898 private Grid aStar(VirtualChain chain, ErasedPath erased, float oldcost) {
899 Grid best = null;
900 Grid.resetMarks();
901 Grid src = fGridFactory.get(erased.src);
902 VirtualVertex dest = erased.dest;
903 src.accept(null, dest, 0);
904 fOpenQueue.clear();
905 fOpenQueue.enqueue(src);
906 if (DEBUG)
907 msg.println(NAME + ".aStar(): cost limit=" + oldcost + "\n\tsrc=" + src + "\n\tdest=" + dest);
908 while (fOpenQueue.size() != 0) {
909 best = fOpenQueue.dequeue();
910 fStat.dequeue++;
911 if (best.estTotal >= oldcost)
912 break;
913 if (fOpenQueue.size() > fStat.maxQueueSize)
914 fStat.maxQueueSize = fOpenQueue.size();
915 if (DEBUG) {
916 msg.println(
917 "# best="
918 + best
919 + ", parent="
920 + best.parent
921 + ", curCost="
922 + best.curCost
923 + ", estTotal="
924 + best.estTotal);
925 }
926 if (best.reached(dest)) {
927 if (TERSE)
928 msg.println(NAME + ".route(): aStar=" + best);
929 return best;
930 }
931 //
932 if (best.rank < dest.rank)
933 expandDown(best, dest, oldcost, erased);
934 else if (best.rank > dest.rank)
935 expandUp(best, dest, oldcost, erased);
936 }
937 if (VERBOSE) {
938 msg.println(
939 NAME
940 + ".aStar(): FAILED: oldcost="
941 + oldcost
942 + ", newcost="
943 + best.estTotal
944 + "\nbest="
945 + best
946 + ", parent="
947 + best.parent
948 + ", curCost="
949 + best.curCost
950 + ", estTotal="
951 + best.estTotal);
952 }
953 return null; //no open cells and no solution
954 }
955
956 /**
957 * Expand from best to its children below.
958 * @return The next best Grid is its totalCost<=nextcost.
959 * @param best The Grid from which expansion is performed.
960 * @param next The next best to be expanded up to now.
961 * @param nextcost The cost for the next to be expanded. This may not be next.estTotal in case next==null.
962 * @param dest The destination vertex.
963 * @param oldcost The cost limit.
964 * @param e The VirtualEdge segement.
965 */
966 private void expandDown(Grid best, VirtualVertex dest, float oldcost, ErasedPath erased) {
967 // Never expand beyond the destination rank.
968 // if (best.rank>= dest.rank)
969 // return null;
970 //
971 VirtualVertex beforeParent = best.leftVertex;
972 VirtualVertex beforeChild = null;
973 VirtualEdge e = erased.edge(best.rank);
974 int ret;
975 float travelcost;
976 float crosscost = 0;
977 float cost = oldcost - best.curCost;
978 // Discard optimization.
979 // . For large graph, huge number of expanded candidates need to checked and often discarded.
980 // Large number of the candiates can be screen out by just considering their distance cost from
981 // the curent best.
982 // . The optimization decrease testDependGraph1 aneal time by 50% and
983 // number of discarded candidates are an order of magnitude less.
984 fStat.expanded++;
985 boolean crossvalid = false;
986 GridFactory.GridIterator it = fGridFactory.new GridIterator(best.rank + 1, best.x, cost);
987 for (Grid child = it.next(); child != null; child = it.next()) {
988 // Erased VERTEX cells may now be SPACE but still have
989 // cell.vertex!=null and used for cross cost
990 // calcuation.
991 if (child.leftVertex != beforeChild) {
992 beforeChild = child.leftVertex;
993 crossvalid = false;
994 }
995 while (true) {
996 cost = best.curCost;
997 // Travel cost.
998 travelcost = child.travelCostFrom(best, best.parent);
999 cost += travelcost;
1000 if (cost >= oldcost) {
1001 fStat.discarded++;
1002 if (child.x > best.x) {
1003 // Early exit, since distance cost can only increase from here.
1004 child = null;
1005 }
1006 break;
1007 }
1008 // Bus crossing cost.
1009 if (!crossvalid) {
1010 crosscost = crossAfter(best, child, beforeParent, beforeChild, e);
1011 crossvalid = true;
1012 if (TERSE)
1013 msg.println(
1014 NAME
1015 + ".expandDown(): crosscost="
1016 + crosscost
1017 + ", beforeChild="
1018 + beforeChild);
1019 }
1020 cost += crosscost;
1021 if (cost >= oldcost) {
1022 fStat.discarded++;
1023 break;
1024 }
1025 ret = child.accept(best, dest, cost);
1026 if (TERSE)
1027 msg.println(
1028 NAME
1029 + ".accept(): ret="
1030 + ret
1031 + ": oldcost="
1032 + oldcost
1033 + ", cost="
1034 + cost
1035 + ", travelcost="
1036 + travelcost
1037 + ", crosscost="
1038 + crosscost
1039 + ", child="
1040 + child.toString()
1041 + "\n\te="
1042 + e);
1043 if (ret == Grid.REJECT) {
1044 fStat.discarded++;
1045 break;
1046 }
1047 if (ret == Grid.REQUEUE) {
1048 ++fStat.reopen;
1049 fOpenQueue.requeue(child);
1050 } else {
1051 ++fStat.visited;
1052 fOpenQueue.enqueue(child);
1053 }
1054 break;
1055 }
1056 if (child == null)
1057 break;
1058 }
1059 }
1060
1061 /** Expand from best to its children above.
1062 *
1063 * @return The next best Grid is its totalCost<=nextcost.
1064 */
1065 private void expandUp(Grid best, VirtualVertex dest, float oldcost, ErasedPath erased) {
1066 // Never expand beyond the destination rank.
1067 // if (best.rown <= dest.rown)
1068 // return null;
1069 //
1070 VirtualEdge e = erased.edge(best.rank - 1);
1071 // Look for start cell by checking the travel cost.
1072 int ret;
1073 float crosscost = 0;
1074 float travelcost;
1075 float cost = oldcost - best.curCost;
1076 fStat.expanded++;
1077 boolean crossvalid = false;
1078 VirtualVertex beforeChild = best.leftVertex;
1079 VirtualVertex beforeParent = null;
1080 GridFactory.GridIterator it = fGridFactory.new GridIterator(best.rank - 1, best.x, cost);
1081 for (Grid parent = it.next(); parent != null; parent = it.next()) {
1082 if (parent.leftVertex != beforeParent) {
1083 beforeParent = parent.leftVertex;
1084 crossvalid = false;
1085 }
1086 while (true) {
1087 cost = best.curCost;
1088 // Travel cost.
1089 travelcost = parent.travelCostFrom(best, best.parent);
1090 cost += travelcost;
1091 if (cost >= oldcost) {
1092 fStat.discarded++;
1093 if (parent.x > best.x) {
1094 parent = null;
1095 }
1096 break;
1097 }
1098 // Bus crossing cost.
1099 if (!crossvalid) {
1100 crosscost = crossAfter(parent, best, beforeParent, beforeChild, e);
1101 crossvalid = true;
1102 if (TERSE)
1103 msg.println(
1104 NAME
1105 + ".expandUp(): crosscost="
1106 + crosscost
1107 + ", beforeParent="
1108 + beforeParent
1109 + ", parent="
1110 + parent);
1111 }
1112 cost += crosscost;
1113 if (cost >= oldcost) {
1114 fStat.discarded++;
1115 break;
1116 }
1117 ret = parent.accept(best, dest, cost);
1118 if (TERSE)
1119 msg.println(
1120 NAME
1121 + ".accept(): ret="
1122 + ret
1123 + ": oldcost="
1124 + oldcost
1125 + ", cost="
1126 + cost
1127 + ", travelcost="
1128 + travelcost
1129 + ", crosscost="
1130 + crosscost
1131 + ", parent="
1132 + parent.toString()
1133 + "\n\te="
1134 + e);
1135 if (ret == Grid.REJECT) {
1136 ++fStat.discarded;
1137 break;
1138 } else {
1139 if (ret == Grid.REQUEUE) {
1140 ++fStat.reopen;
1141 fOpenQueue.requeue(parent);
1142 } else {
1143 ++fStat.visited;
1144 fOpenQueue.enqueue(parent);
1145 }
1146 }
1147 break;
1148 }
1149 if (parent == null)
1150 break;
1151 }
1152 }
1153
1154 ////////////////////////////////////////////////////////////////////////
1155
1156 private String mapToGeneralPath(Grid[][] map) {
1157 StringBuffer ret = new StringBuffer("<plot>\n");
1158 for (int rn = 0; rn < map.length; ++rn) {
1159 Grid[] row = map[rn];
1160 for (int cn = 0; cn < row.length; ++cn) {
1161 Grid c = row[cn];
1162 c.toGeneralPath(ret, null);
1163 }
1164 }
1165 ret.append("</plot>\n");
1166 return ret.toString();
1167 }
1168
1169 ////////////////////////////////////////////////////////////////////////
1170
1171 final class Stat {
1172 int dequeue;
1173 int expanded;
1174 int visited;
1175 int reopen;
1176 int discarded;
1177 int maxQueueSize;
1178 public String toString() {
1179 return "expanded="
1180 + expanded
1181 + ", dequeue="
1182 + dequeue
1183 + ", visited="
1184 + visited
1185 + ", reopen="
1186 + reopen
1187 + ", discarded="
1188 + discarded
1189 + ", maxQueueSize="
1190 + maxQueueSize;
1191 }
1192 public void clear() {
1193 dequeue=0;
1194 expanded=0;
1195 visited=0;
1196 reopen=0;
1197 discarded=0;
1198 maxQueueSize=0;
1199 }
1200
1201 }
1202
1203 ////////////////////////////////////////////////////////////////////////
1204}