Source code: com/port80/graph/dot/impl/AnnealWithCell.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.Arrays;
9 import java.util.Collections;
10 import java.util.HashMap;
11 import java.util.HashSet;
12 import java.util.List;
13 import java.util.Map;
14 import java.util.Set;
15
16 import com.port80.util.Debug;
17 import com.port80.util.SystemWatch;
18 import com.port80.util.msg;
19 import com.port80.util.struct.Heap;
20 import com.port80.util.struct.IHeap;
21
22 /** Anneal a placement of a VirtualGraph.
23 *
24 * . Output from MinCross and Position often contains some very
25 * obvious layout problem mainly due to MinCross having no distance
26 * information consider those cases as equivalent. Especially for
27 * bus routing, there are lots of opportunities to improve the
28 * layout by taking advantage the fact that anywhere on the bus is
29 * equivalent.
30 *
31 * . shortestPath() try to find a point to line or point to point
32 * path with minimum distance in the VirtualGraph with placement.
33 * Another pass of Position may be required to compact the layout
34 * afterwards.
35 *
36 * For bus-bus connections, shortestPath() is run on both end
37 * points. For point to point connections, shortest path from
38 * either end point should be the same. However, since layout may
39 * have changed after shortestPath() is run from the first end
40 * point, it may be useful to run again on the other end point for
41 * maximum optimization.
42 *
43 * shortestPath() use A* algorithm. The layout is converted to a
44 * grid. Instead of a uniform grid, each rank is divided into
45 * segments of vertices and inter-vertex spacings. Vertex have a
46 * point coordinate and occupy the grid interval from
47 *
48 * floor(v.x-v.leftWidth-vertexSpacing/4) to
49 * ceil(v.x+v.rightWidth+vertexSpacing/4).
50 *
51 * The inter-vertex spacing is the interval between two vertices
52 * with both sides aligned to the grid and width=vertexSpacing/4.
53 *
54 * Transversal are directional, up or down. In down transversal,
55 * only cells in the lower row are neighbours.
56 *
57 * Cost of transversing from one cell to the other is consists of
58 * two costs, a static cost is pre-calculated for the current map
59 * (cross and distance cost) from one cell to the other. Another
60 * portion of the cost are determined on each visit (eg. cost for
61 * turns).
62 *
63 * The list of neighbours are determined on each visit depends on
64 * up/down transversal. Vertices occupied by old path are marked
65 * so they are candidate as neighbours. All other vertices are
66 * excluded as neighbour.
67 *
68 * Static costs:
69 *
70 * . Cross cost and distance cost for each pair of cells are
71 * pre-calculated before start. Cross cost are updated after
72 * each route changes. To reduce slope of paths, distance cost
73 * is proportional to square of grid count, so long horizontal
74 * path would be distributed as short segments in each rank.
75 *
76 * Dynamic costs:
77 *
78 * . To avoid path from zigzagging, a cost is associated with each
79 * turn.
80 *
81 * NOTE:
82 *
83 * . After an edge chain is erased before routing, the vertex cells
84 * still keep the .vertex and .crossCost fields valid and used for
85 * cross cost calculations.
86 *
87 * HISTORY:
88 *
89 * . 05/13/2002 Speed improvement by incrementally adjust crossCost
90 * information instead of recalc. on each eraseTrail (without
91 * installPath() optimization.
92 * This speed up Anneal() on 'testdot00' from ~60sec. to ~35sec.
93 * . Expand routeStraightLine() to allow offset!=0.
94 * Improves Anneal() on 'testdot00' from 35sec. to 30sec.
95 *
96 * TODO:
97 *
98 * . Anneal route of the longest top 10% routes.
99 * . Regression test on rank cost calculations.
100 *
101 */
102 public class AnnealWithCell {
103
104 ////////////////////////////////////////////////////////////////////////
105
106 private static final String NAME = "AnnealWithCell";
107 /** Verbose+intermediate results. */
108 private static final boolean TERSE = false;
109 /** Terse+debug info. */
110 private static final boolean DEBUG = false;
111 /** Show time, status. */
112 private static boolean VERBOSE = Debug.isVerbose();
113 private static boolean CHECK = Debug.isCheck();
114
115 /** These are tunable instance parameters, put here for convenient.
116 */
117 //private int[] OFFSETS ={0,1,-1,2,-2,4,-4,8,-8};
118 private final int[] OFFSETS = { 0, 1, -1, 2, -2, 3, -3, 4, -4 };
119 /** Number of tries straight vertical route search.*/
120 private final int N_OFFSET = 9;
121
122 /** Max slack allowed for route to be considered done.*/
123 private final int MAXSLACK = 0;
124
125 // Instance fields /////////////////////////////////////////////////////
126 //
127
128 VirtualGraph fGraph;
129 int fMinRank, fMaxRank;
130 Cell[][] fMap;
131 int fMapWidth;
132 int fMapHeight;
133 /** VirtualVertex->cell mapping.*/
134 Map fCellTable;
135 private CellHeap fOpenQueue;
136 int fRoutedCount;
137 int fImprovedCount;
138 int fStraightCount;
139 /** Set of VirtualEdge (chaintail) to be ignored (eg. alway have min. cost).*/
140 Set fIgnoreSet;
141 /** Sorted open cells.*/
142 private int fXSpacing;
143 private int fYSpacing;
144 private int fXOffset;
145 private int fMaxCol;
146 private Stat fStat;
147 //
148 /** Counters for rankCost().*/
149 private int[] fCrossCounts;
150 /** Edge chain being routed indexed by rown instead of rank.*/
151 private VirtualEdge[] fCurChain;
152 IHeap fPTPHeap;
153
154 private int YDIST;
155 private float fMINPTPCOST = 1.05f;
156
157 //
158 // Layout parameters from IGraph.
159 //
160 private int fCELL_XDIV;
161 private int fCELL_BASICCOST;
162 //
163 private int fPTP_PERCENT;
164
165 ////////////////////////////////////////////////////////////////////////
166
167 public static final int dot(VirtualGraph g, int maxiter) {
168 return new AnnealWithCell().reRoute(g, maxiter);
169 }
170
171 public final int reRoute(VirtualGraph g, int maxiter) {
172 SystemWatch timer = null;
173 if (VERBOSE)
174 timer = new SystemWatch().start();
175 // Construct a cell map from the VirtualGraph.
176 fGraph = g;
177 //
178 fMinRank = fGraph.minRank;
179 fMaxRank = fGraph.maxRank;
180 fXSpacing = fGraph.getVertexSpacing();
181 fYSpacing = fGraph.getRankSpacing();
182 YDIST = fYSpacing * fYSpacing;
183 fCELL_XDIV = fGraph.fCELL_XDIV;
184 fCELL_BASICCOST = fGraph.fCELL_BASICFACTOR;
185 fPTP_PERCENT = fGraph.fPTP_PERCENT;
186 fXOffset = fXSpacing / (fCELL_XDIV * 2);
187 Cell.configure(fGraph);
188 //
189 fPTPHeap = new Heap(new VirtualChain.PTPSlackComparator());
190 fCurChain = new VirtualEdge[fMaxRank - fMinRank + 1];
191 fIgnoreSet = new HashSet(50);
192 fRoutedCount = 0;
193 fImprovedCount = 0;
194 fOpenQueue = new CellHeap(1024);
195 fCellTable = new HashMap(100);
196 createMap(fGraph);
197 //
198 //
199 VirtualVertex v;
200 VirtualEdge e;
201 VirtualEdge[] outs;
202 VirtualVertex[] vts = fGraph.getVertices();
203 List chainlist = new ArrayList(vts.length);
204 for (int i = 0; i < vts.length; ++i) {
205 v = vts[i];
206 outs = v.outs;
207 for (int k = 0; k < outs.length; ++k) {
208 e = outs[k];
209 if (e.prev == null)
210 chainlist.add(new VirtualChain(e));
211 }
212 }
213 Collections.sort(chainlist, new VirtualChain.ChainTypeComparator());
214 int totalimproved = 0;
215 totalimproved += rerouteBus(chainlist, maxiter);
216 totalimproved += reroutePTP(chainlist, maxiter);
217
218 if (VERBOSE) {
219 msg.println(
220 "###\n### "
221 + NAME
222 + ".reRoute(): "
223 + totalimproved
224 + "/"
225 + (fRoutedCount)
226 + " improved routes, max queue size="
227 + fOpenQueue.getMaxSize()+", "
228 + timer.stop().toString()
229 + "\n###\n");
230 }
231 return totalimproved;
232 }
233
234 ////////////////////////////////////////////////////////////////////////
235
236 private int rerouteBus(List chainlist, int maxiter) {
237 SystemWatch timer = null;
238 SystemWatch timer1 = null;
239 if (VERBOSE)
240 timer = new SystemWatch().start();
241 if (false)
242 msg.println(mapToGeneralPath(fMap));
243 //
244 staticCost();
245 //
246 Cell[] row;
247 Cell src;
248 int totalimproved = 0;
249 int totalstraight = 0;
250 int lastcount = 0;
251 int iter;
252 VirtualChain chain;
253 for (iter = 0; iter < maxiter; ++iter) {
254 if (VERBOSE)
255 timer1 = new SystemWatch().start();
256 fImprovedCount = 0;
257 fStraightCount = 0;
258 for (int i = 0; i < chainlist.size(); ++i) {
259 rerouteBusFor((VirtualChain) chainlist.get(i));
260 }
261 // for (int rn = 0; rn < fMap.length; ++rn) {
262 // row = fMap[rn];
263 // for (int cn = 0; cn < row.length; ++cn) {
264 // src = fMap[rn][cn];
265 // if (src.type == Cell.VERTEX || src.type == Cell.BUS)
266 // rerouteBusFrom(src);
267 // }
268 // }
269 if (VERBOSE) {
270 msg.println(
271 NAME
272 + ".reRouteBus(): pass="
273 + iter
274 + " : "
275 + fImprovedCount
276 + ","
277 + fStraightCount
278 + " improved,straight routes, "
279 + (fRoutedCount - lastcount)
280 + "/"
281 + chainlist.size()
282 + " routed, "
283 + fIgnoreSet.size()
284 + " ignores, "
285 + timer1.stop().toString());
286 }
287 if (fImprovedCount == 0)
288 break;
289 totalimproved += fImprovedCount;
290 totalstraight += fStraightCount;
291 lastcount = fRoutedCount;
292 }
293 if (iter < maxiter)
294 ++iter;
295 if (VERBOSE) {
296 msg.println(
297 "\n### "
298 + NAME
299 + ".reRouteBus(): total passes="
300 + (iter + 1)
301 + ": "
302 + totalimproved
303 + ","
304 + totalstraight
305 + " improved,straight routes, "
306 + fRoutedCount
307 + "/"
308 + (iter * chainlist.size())
309 + " routed, "
310 + fIgnoreSet.size()
311 + " ignores, "
312 + timer.stop().toString()
313 + "\n");
314 }
315 return totalimproved;
316 }
317
318 private void rerouteBusFrom(Cell src) {
319 Cell dest;
320 VirtualVertex v;
321 VirtualVertex head;
322 VirtualVertex tail;
323 VirtualEdge e;
324 // For now, only route VERTEX->BUS or BUS->BUS forward and backward.
325 if (src.type == Cell.VERTEX || src.type == Cell.BUS) {
326 v = src.vertex;
327 //DEBUG: if(!v.getName().startsWith("/graph/src/com/port80/graph/dot/impl/Anneal.java")) return;
328 //DEBUG: if(!v.getName().equals("#graph/graph.2125")) continue;
329 for (int i = 0; i < v.outs.length; ++i) {
330 e = v.outs[i];
331 if (DEBUG)
332 msg.println(NAME + ".rerouteBusFrom(): out: e=" + e);
333 if (fIgnoreSet.contains(e)) {
334 if (DEBUG)
335 msg.println(NAME + ".rerouteBusFrom(): out: ignored: e=" + e);
336 continue;
337 }
338 head = e.getChainHead();
339 if (head.isBus()) {
340 dest = (Cell) fCellTable.get(head);
341 reRouteDown(src, dest, e);
342 }
343 }
344 for (int i = 0; i < v.ins.length; ++i) {
345 e = v.ins[i];
346 while (e.prev != null)
347 e = e.prev;
348 if (DEBUG)
349 msg.println(NAME + ".rerouteBusFrom(): in: e=" + e);
350 if (fIgnoreSet.contains(e)) {
351 if (DEBUG)
352 msg.println(NAME + ".rerouteBusFrom(): in: ignored: e=" + e);
353 continue;
354 }
355 tail = e.tail;
356 if (tail.isBus()) {
357 dest = (Cell) fCellTable.get(tail);
358 reRouteUp(src, dest, e);
359 }
360 }
361 }
362 }
363
364 private boolean rerouteBusFor(VirtualChain chain) {
365 Cell src, dest;
366 if (!(chain.fTail.isBus() || chain.fHead.isBus()))
367 return false;
368 // For now, only route VERTEX->BUS or BUS->BUS forward and backward.
369 if (fIgnoreSet.contains(chain.fChainTail)) {
370 if (DEBUG)
371 msg.println(NAME + ".rerouteBusFor(): ignored: chaintail=" + chain.fChainTail);
372 return false;
373 }
374 boolean improved = false;
375 if (chain.fHead.isBus()) {
376 src = (Cell) fCellTable.get(chain.fTail);
377 dest = (Cell) fCellTable.get(chain.fHead);
378 improved = improved || reRouteDown(src, dest, chain.fChainTail);
379 }
380 if (chain.fTail.isBus()) {
381 src = (Cell) fCellTable.get(chain.fHead);
382 dest = (Cell) fCellTable.get(chain.fTail);
383 improved = improved || reRouteUp(src, dest, chain.fChainTail);
384 }
385 if (!improved)
386 fIgnoreSet.add(chain.fChainTail);
387 return improved;
388 }
389
390 private int reroutePTP(List chainlist, int maxiter) {
391 SystemWatch timer = null;
392 if (VERBOSE)
393 timer = new SystemWatch().start();
394 int improved = 0;
395 VirtualChain chain;
396 for (int i = 0; i < chainlist.size(); ++i) {
397 chain = (VirtualChain) chainlist.get(i);
398 if (chain.fHead.isReal() && chain.fTail.isReal() && chain.fHead.rank - chain.fTail.rank > 1) {
399 chain.updateLength();
400 fPTPHeap.enqueue(chain);
401 }
402 }
403 int max = (fPTPHeap.size() * fPTP_PERCENT) / 100;
404 if (VERBOSE)
405 msg.println(NAME + ".reroutePTP(): total=" + fPTPHeap.size() + ", candidates=" + max + "\n");
406 int count = 0;
407 for (int i = 0; i < max; ++i) {
408 VirtualChain c = (VirtualChain) fPTPHeap.dequeue();
409 if (c.getSlack() < fMINPTPCOST)
410 break;
411 ++count;
412 if (VERBOSE)
413 msg.println(NAME + ".reroutePTP(): chain=" + c);
414 Cell src = (Cell) fCellTable.get(c.fTail);
415 Cell dst = (Cell) fCellTable.get(c.fHead);
416 if (src == null || dst == null) {
417 msg.warn(
418 NAME
419 + ".reroutePTP(): "
420 + ((src == null) ? "src not found: " : "src=")
421 + c.fTail.getName()
422 + ((dst == null) ? "dst not found:" : "dst=")
423 + c.fHead.getName());
424 }
425 if (TERSE)
426 msg.println(
427 NAME
428 + ".reroutePTP(): src="
429 + src.vertex.getName()
430 + "("
431 + src.vertex.rank
432 + ")"
433 + ", dest="
434 + dst.vertex.getName()
435 + "("
436 + dst.vertex.rank
437 + ")");
438 CellList erased = new CellList(10);
439 int oldcost = eraseTrail(c.fChainTail, src, dst, fCurChain, erased);
440 if (oldcost == 0)
441 continue;
442 CellList newpath = route(src, dst, oldcost, fCurChain, true);
443 if (routePath(newpath, oldcost, c.fChainTail, erased, true, "" + count))
444 ++improved;
445 }
446 if (VERBOSE) {
447 msg.println(
448 "\n### "
449 + NAME
450 + ".reRoutePTP(): "
451 + improved
452 + "/"
453 + count
454 + "/"
455 + max
456 + " improved/routed/candidates routes, "
457 + timer.stop().toString()
458 + "\n");
459 }
460 return improved;
461 }
462
463 /**
464 * @return New dest. cell if improved, else null.
465 */
466 private boolean reRouteDown(Cell src, Cell dest, VirtualEdge chaintail) {
467 //NOTE: Bus vertex always have one and only one edge.
468 if (TERSE)
469 msg.println(
470 NAME
471 + ".reRouteDown(): src="
472 + src.vertex.getName()
473 + "("
474 + src.vertex.rank
475 + ")"
476 + ", dest="
477 + dest.vertex.getName()
478 + "("
479 + dest.vertex.rank
480 + ")");
481 CellList erased = new CellList(10);
482 int oldcost = eraseTrail(chaintail, src, null, fCurChain, erased);
483 if (oldcost == 0)
484 return false;
485 CellList newpath = route(src, dest, oldcost, fCurChain, true);
486 return routePath(newpath, oldcost, chaintail, erased, true, "rerouteDown");
487 }
488
489 /**
490 * ReRoute a bus from bottom (src) to top (dest).
491 */
492 private boolean reRouteUp(Cell src, Cell dest, VirtualEdge chaintail) {
493 if (src.rown <= dest.rown)
494 msg.err("src.rown=" + src.rown + ", dest.rown=" + dest.rown);
495 if (TERSE)
496 msg.println(
497 NAME
498 + ".reRouteUp(): src="
499 + src.vertex.getName()
500 + "("
501 + src.vertex.rank
502 + ")"
503 + ", dest="
504 + dest.vertex.getName()
505 + "("
506 + dest.vertex.rank
507 + ")");
508 CellList erased = new CellList(10);
509 int oldcost = eraseTrail(chaintail, src, null, fCurChain, erased);
510 if (oldcost == 0)
511 return false;
512 CellList newpath = route(src, dest, oldcost, fCurChain, false);
513 return routePath(newpath, oldcost, chaintail, erased, false, "rerouteUp");
514 }
515
516 /** Create the map from given VirtualGraph. */
517 private void createMap(VirtualGraph graph) {
518 VirtualGraph.Rank rank;
519 VirtualVertex v;
520 Cell cell;
521 Cell[] row;
522 int x, left, right = 0;
523 int width = (fCELL_XDIV * graph.getWidth()) / fXSpacing + 1;
524 int maxv = 0;
525 //FIXME: How about the xMargins.
526 int rn = graph.maxRank - graph.minRank + 1;
527 if (TERSE)
528 msg.println(NAME + ".createMap(): rows=" + rn + ",columns=" + width);
529 fMap = new Cell[rn][width];
530 fMapWidth = width;
531 fMapHeight = rn;
532 rn = 0;
533 for (int r = graph.minRank; r <= graph.maxRank; ++r, ++rn) {
534 rank = graph.ranks[r];
535 row = fMap[rn];
536 x = 0; // grid cell index.
537 if (rank.nVts > maxv)
538 maxv = rank.nVts;
539 for (int i = 0; i < rank.nVts; ++i) {
540 v = rank.vts[i];
541 left = fCELL_XDIV * (v.x - v.leftWidth) / fXSpacing;
542 right = fCELL_XDIV * (v.x + v.rightWidth) / fXSpacing + 1;
543 if (left < 0)
544 left = 0;
545 if (right >= width)
546 right = width - 1;
547 // Reserve a gap on both side.
548 if (left <= x && (right - left) > 2) {
549 if (left < width - 1)
550 ++left;
551 if (right > 0)
552 --right;
553 }
554 newSpaceCells(row, rn, x, left);
555 cell = newVertexCells(row, rn, left, right, v);
556 fCellTable.put(v, cell);
557 x = right;
558 }
559 newSpaceCells(row, rn, right, width);
560 }
561 fCrossCounts = new int[maxv];
562 }
563
564 private void newSpaceCells(Cell[] row, int rn, int start, int end) {
565 for (int i = start; i < end; ++i) {
566 row[i] = Cell.newSpaceCell(rn, i);
567 }
568 }
569
570 /**
571 * Populate cells [left..right) occupied by v.
572 * @return The cell occupied by the Vertex center.
573 */
574 private Cell newVertexCells(Cell[] row, int rn, int left, int right, VirtualVertex v) {
575 Cell ret = null;
576 int type;
577 for (int cn = left; cn < right; ++cn) {
578 if (cn == (left + right) / 2) {
579 ret = Cell.newVertexCell(rn, cn, v);
580 row[cn] = ret;
581 } else {
582 row[cn] = Cell.newBlockedCell(rn, cn, v);
583 }
584 }
585 return ret;
586 }
587
588 ////////////////////////////////////////////////////////////////////////
589
590 /** Pre-calculate static costs for each possible path segments.
591 * Vertex/spacing to vertex/spacing.
592 *
593 * Crossing cost are calculated in two passes, from left to right
594 * and then right to left as follow.
595 *
596 * NOTE: Since we have to recalculate the rank cost after
597 * eraseTrail() each time, there is no need to pre-calculate any
598 * rank cost.
599 */
600 private void staticCost() {
601 int total = 0;
602 for (int r = fGraph.minRank, rn = 0; r < fGraph.maxRank; ++r, ++rn) {
603 total += rankCost(r, null);
604 fGraph.ranks[r].valid = true;
605 }
606 if (DEBUG)
607 msg.println(NAME + ".staticCost(): total=" + total);
608 }
609
610 ////////////////////////////////////////////////////////////////////////
611 /**
612 * @param r The rank whose cost is to be calculated.
613 * @param segment An edge to be ignored.
614 *
615 * Cross cost for imaginary edge from every vertices on
616 * top to every vertices at bottom instead of for only the real
617 * edges.
618 */
619 private int rankCost(int r, VirtualEdge segment) {
620 int ranktotal = 0;
621 VirtualVertex v;
622 VirtualEdge e;
623 Cell cell;
624 int min, max;
625 int order;
626 int cost;
627 VirtualGraph.Rank rank = fGraph.ranks[r];
628 VirtualGraph.Rank rank1 = fGraph.ranks[r + 1];
629 if (rank1.nVts > fCrossCounts.length)
630 fCrossCounts = new int[rank1.nVts];
631 else
632 Arrays.fill(fCrossCounts, 0);
633 max = 0;
634 // Left to right.
635 for (int c = 0; c < rank.nVts; ++c) {
636 v = rank.vts[c];
637 cell = (Cell) fCellTable.get(v);
638 if (CHECK && cell == null) {
639 msg.err("cell==null: v=" + v.getName());
640 }
641 if (cell.crossCost == null || cell.crossCost.length < rank1.nVts)
642 cell.crossCost = new int[rank1.nVts];
643 else
644 Arrays.fill(cell.crossCost, 0);
645 for (order = 0; order < max; ++order) {
646 cost = 0;
647 for (int i = order + 1; i <= max; ++i)
648 cost += fCrossCounts[i];
649 if (DEBUG && segment != null)
650 msg.println(
651 NAME
652 + ".rankCost(): LEFT: r="
653 + r
654 + ", v="
655 + v.getName()
656 + "("
657 + v.order
658 + ")"
659 + ", head="
660 + rank1.vts[order].getName()
661 + "("
662 + order
663 + ")"
664 + ", cost="
665 + cost);
666 cell.crossCost[order] = cost;
667 ranktotal += cost;
668 }
669 for (int n = 0; n < v.outs.length; ++n) {
670 e = v.outs[n];
671 if (e == segment)
672 continue;
673 order = e.head.order;
674 if (order > max)
675 max = order;
676 fCrossCounts[order] += e.xPenalty;
677 }
678 }
679 // right to left.
680 Arrays.fill(fCrossCounts, 0);
681 min = rank1.nVts;
682 for (int c = rank.nVts - 1; c >= 0; --c) {
683 v = rank.vts[c];
684 cell = (Cell) fCellTable.get(v);
685 if (CHECK && cell == null) {
686 msg.err("cell==null: v=" + v.getName());
687 }
688 for (order = min + 1; order < rank1.nVts; ++order) {
689 cost = 0;
690 for (int i = min; i < order; ++i)
691 cost += fCrossCounts[i];
692 if (DEBUG && segment != null)
693 msg.println(
694 NAME
695 + ".rankCost(): RIGHT: r="
696 + r
697 + ", v="
698 + v.getName()
699 + "("
700 + v.order
701 + ")"
702 + ", head="
703 + rank1.vts[order].getName()
704 + "("
705 + order
706 + ")"
707 + ", cost="
708 + cost);
709 cell.crossCost[order] += cost;
710 ranktotal += cost;
711 }
712 for (int n = 0; n < v.outs.length; ++n) {
713 e = v.outs[n];
714 if (e == segment)
715 continue;
716 order = e.head.order;
717 if (order < min)
718 min = order;
719 fCrossCounts[order] += e.xPenalty;
720 }
721 }
722 if (DEBUG)
723 msg.println(NAME + ".rankCost(): r=" + r + ",segment=" + segment + ", rank total=" + ranktotal);
724 return ranktotal;
725 }
726
727 /**
728 * Adjust rankCost on removal of a segemnt.
729 * Deduct the xPenalty of the removed segment from all imaginary
730 * edges that crossed the segment.
731 */
732 private void rankCostRemoveEdge(VirtualEdge segment) {
733 int r = segment.tail.rank;
734 int xpenalty = segment.xPenalty;
735 VirtualGraph.Rank rank = fGraph.ranks[r];
736 VirtualGraph.Rank rank1 = fGraph.ranks[r + 1];
737 Cell cell;
738 int torder = segment.tail.order;
739 int horder = segment.head.order;
740 for (int tn = 0; tn < torder; ++tn) {
741 cell = (Cell) fCellTable.get(rank.vts[tn]);
742 for (int hn = horder + 1; hn < rank1.nVts; ++hn) {
743 cell.crossCost[hn] -= xpenalty;
744 if (CHECK && cell.crossCost[hn] < 0) {
745 msg.err(
746 "crossCost<0"
747 + ": tn="
748 + tn
749 + ", hn="
750 + hn
751 + ", cost="
752 + cell.crossCost[hn]
753 + "\n\tcell="
754 + cell
755 + "\n\te="
756 + segment);
757 }
758 }
759 }
760 for (int tn = torder + 1; tn < rank.nVts; ++tn) {
761 cell = (Cell) fCellTable.get(rank.vts[tn]);
762 for (int hn = 0; hn < horder; ++hn) {
763 cell.crossCost[hn] -= xpenalty;
764 if (CHECK && cell.crossCost[hn] < 0)
765 msg.err(
766 "crossCost<0"
767 + ": tn="
768 + tn
769 + ", hn="
770 + hn
771 + ", cost="
772 + cell.crossCost[hn]
773 + "\n\tcell="
774 + cell
775 + "\n\te="
776 + segment);
777 }
778 }
779 }
780
781 /** Take a snapshot of rank cost in the given rank 'r'.*/
782 private void saveRankCost(int r) {
783 Cell[] row = fMap[r - fMinRank];
784 for (int i = 0; i < row.length; ++i) {
785 if (row[i].type >= Cell.ERASED)
786 row[i].saveCrossCost();
787 }
788 }
789
790 /** Restore crossCost of cell in the given rank 'r'.*/
791 private void restoreRankCost(int r) {
792 Cell[] row = fMap[r - fMinRank];
793 for (int i = 0; i < row.length; ++i) {
794 if (row[i].type >= Cell.ERASED)
795 row[i].restoreCrossCost();
796 }
797 }
798
799 private boolean checkCrossCosts() {
800 for (int r = fMinRank; r < fMaxRank; ++r) {
801 Cell[] row = fMap[r - fMinRank];
802 for (int i = 0; i < row.length; ++i) {
803 if (row[i].type >= Cell.ERASED)
804 row[i].saveCrossCost();
805 }
806 }
807 for (int r = fMinRank; r < fMaxRank; ++r) {
808 rankCost(r, null);
809 }
810 boolean ok = true;
811 for (int r = fMinRank; r < fMaxRank; ++r) {
812 Cell[] row = fMap[r - fMinRank];
813 for (int i = 0; i < row.length; ++i) {
814 if (row[i].type >= Cell.ERASED) {
815 ok = ok && row[i].checkSavedCrossCost();
816 row[i].restoreCrossCost();
817 }
818 }
819 }
820 return ok;
821 }
822
823 /** Calculate crossing cost for edge from parent to space before
824 * the first vertex below. The cost=crossCost(parent,child)
825 * +e.xPenalty*(xPenalty of all edges from vertex on left of
826 * parent to child).
827 *
828 * beforeParent parent
829 * |
830 * v-------------------
831 * child vts[0](afterChild)
832 *
833 * @param parent parent cell for the route.
834 * @param child child cell (below parent) for the route.
835 * @param beforeParent Vertex cell before parent or parent itself.
836 * @param route is the edge in this rank being routed.
837 */
838 private int crossAfterBefore(Cell parent, Cell child, Cell beforeParent, VirtualEdge segment) {
839 if (beforeParent == null)
840 return 0;
841 VirtualVertex v = fGraph.ranks[segment.head.rank].vts[0];
842 Cell afterChild = (Cell) fCellTable.get(v);
843 int ret = beforeParent.crossCost[afterChild.vertex.order];
844 int order;
845 VirtualEdge e;
846 order = 0;
847 v = beforeParent.vertex;
848 if (v != parent.vertex) {
849 for (int i = 0; i < v.outs.length; ++i) {
850 e = v.outs[i];
851 if (e == segment)
852 continue;
853 if (e.head.order >= order)
854 ret += e.xPenalty;
855 }
856 }
857 order = beforeParent.vertex.order;
858 v = afterChild.vertex;
859 for (int i = 0; i < v.ins.length; ++i) {
860 e = v.ins[i];
861 if (e == segment)
862 continue;
863 if (e.tail.order < order)
864 ret += e.xPenalty;
865 }
866 ret *= segment.xPenalty;
867 if (false)
868 msg.println(
869 NAME
870 + ".crossAfterBefore():"
871 + "\n\t parent="
872 + parent
873 + "\n\t child="
874 + child
875 + "\n\t beforeParent="
876 + beforeParent
877 + "\n\t afterChild="
878 + afterChild
879 + "\n\t segment="
880 + segment
881 + "\n\t ret="
882 + ret);
883 return ret;
884 }
885
886 /**
887 *
888 * parent vts[0](afterParent)
889 * |
890 * -------------------v
891 * beforechild child
892 */
893 private int crossBeforeAfter(Cell parent, Cell child, Cell beforeChild, VirtualEdge segment) {
894 if (beforeChild == null)
895 return 0;
896 VirtualVertex v = fGraph.ranks[segment.tail.rank].vts[0];
897 Cell afterParent = (Cell) fCellTable.get(v);
898 int ret = afterParent.crossCost[beforeChild.vertex.order];
899 int order;
900 VirtualEdge e;
901 // Additional crossing at afterParent.
902 order = beforeChild.vertex.order;
903 v = afterParent.vertex;
904 for (int i = 0; i < v.outs.length; ++i) {
905 e = v.outs[i];
906 if (e == segment)
907 continue;
908 if (e.head.order <= order)
909 ret += e.xPenalty;
910 }
911 // Additional crossing at beforeChild.
912 order = 0;
913 v = beforeChild.vertex;
914 if (v != child.vertex) {
915 for (int i = 0; i < v.ins.length; ++i) {
916 e = v.ins[i];
917 if (e == segment)
918 continue;
919 if (e.tail.order > order)
920 ret += e.xPenalty;
921 }
922 }
923 ret *= segment.xPenalty;
924 if (false)
925 msg.println(
926 NAME
927 + ".crossBeforeAfter():"
928 + "\n\t parent="
929 + parent
930 + "\n\t child="
931 + child
932 + "\n\t afterParent="
933 + afterParent
934 + "\n\t beforeChild="
935 + beforeChild
936 + "\n\t segment="
937 + segment
938 + "\n\t ret="
939 + ret);
940 return ret;
941 }
942
943 /** Calculate crossing cost for edge from parent to child below.
944 * child.
945 *
946 * @param parent parent cell for the segment.
947 * @param child child cell (below parent) for the segment.
948 * @param beforeParent Vertex cell before parent or parent itself.
949 * @param beforeChild Vertex cell before child or the child itself.
950 * @param segment is the edge in this rank being routed.
951 *
952 * beforeParent parent
953 * v--------|
954 * beforeChild child
955 */
956 private int crossAfter(Cell parent, Cell child, Cell beforeParent, Cell beforeChild, VirtualEdge segment) {
957 if (beforeParent == null && beforeChild == null)
958 return 0;
959 if (beforeParent == null)
960 return crossBeforeAfter(parent, child, beforeChild, segment);
961 if (beforeChild == null)
962 return crossAfterBefore(parent, child, beforeParent, segment);
963 int ret = beforeParent.crossCost[beforeChild.vertex.order];
964 int order;
965 VirtualVertex v;
966 VirtualEdge e;
967 // Additional crossing at before parent.
968 if (parent != beforeParent) {
969 order = beforeChild.vertex.order;
970 v = beforeParent.vertex;
971 for (int i = 0; i < v.outs.length; ++i) {
972 e = v.outs[i];
973 if (e == segment)
974 continue;
975 if (e.head.order > order)
976 ret += e.xPenalty;
977 }
978 }
979 if (child != beforeChild) {
980 order = beforeParent.vertex.order;
981 v = beforeChild.vertex;
982 for (int i = 0; i < v.ins.length; ++i) {
983 e = v.ins[i];
984 if (e == segment)
985 continue;
986 if (e.tail.order > order)
987 ret += e.xPenalty;
988 }
989 }
990 if (false)
991 msg.println(
992 NAME
993 + ".crossAfter():"
994 + "\n\t parent="
995 + parent
996 + "\n\t child="
997 + child
998 + "\n\t beforeParent="
999 + beforeParent
1000 + "\n\t beforeChild="
1001 + beforeChild
1002 + "\n\t segment="
1003 + segment
1004 + "\n\t ret="
1005 + ret);
1006 ret *= segment.xPenalty;
1007 return ret;
1008 }
1009
1010 /**
1011 * Route path according to the newpath if cost improved,
1012 * else restore old erased path.
1013 *
1014 * @return New dest. cell if improved, else null.
1015 */
1016 private boolean routePath(
1017 CellList newpath,
1018 int oldcost,
1019 VirtualEdge chaintail,
1020 CellList erased,
1021 boolean isdown,
1022 String message) {
1023 if (newpath == null) {
1024 restorePath(erased, chaintail);
1025 return false;
1026 }
1027 int newcost = isdown ? newpath.cells[newpath.size() - 1].curCost : newpath.cells[0].curCost;
1028 // if (newcost <= (newpath.size() - 1) * fCELL_BASICCOST + MAXSLACK)
1029 // fIgnoreSet.add(chaintail);
1030 if (VERBOSE) {
1031 msg.println(
1032 NAME
1033 + ".routePath(): "
1034 + message
1035 + ": e="
1036 + chaintail.getOriginalName()
1037 + "\n\t"
1038 + ((newcost < oldcost) ? "* " : "")
1039 + "oldcost="
1040 + oldcost
1041 + ", newcost="
1042 + newcost
1043 + "\n\t"
1044 + fStat.toString()
1045 + "\n");
1046 }
1047 // Print new path as GeneralPath.
1048 if (DEBUG) {
1049 //msg.println(mapToGeneralPath(theMap));
1050 msg.println(NAME + ".routePath(): path=");
1051 StringBuffer buf = new StringBuffer();
1052 VirtualEdge e = chaintail;
1053 VirtualVertex v = e.tail;
1054 for (int i = 0; i < newpath.size(); ++i) {
1055 buf.append("#\t" + newpath.cells[i].toString() + ", v=" + v.getName() + "\n");
1056 if (e != null) {
1057 v = e.head;
1058 e = e.next;
1059 }
1060 }
1061 }
1062 if (TERSE) {
1063 VirtualEdge e = chaintail;
1064 VirtualVertex v = e.tail;
1065 StringBuffer buf = new StringBuffer();
1066 for (int i = 0; i < newpath.size(); ++i) {
1067 if (i == 0 || i == newpath.size() - 1)
1068 newpath.cells[i].toGeneralPath(buf, "black");
1069 else
1070 newpath.cells[i].toGeneralPath(buf, "green");
1071 if (e != null) {
1072 v = e.head;
1073 e = e.next;
1074 }
1075 }
1076 msg.println(buf.toString());
1077 }
1078 if (newcost >= oldcost) {
1079 restorePath(erased, chaintail);
1080 return false;
1081 } else {
1082 installPath(newpath, chaintail, isdown);
1083 // return (isdown ? newpath.cells[newpath.size() - 1] : newpath.cells[0]);
1084 return true;
1085 }
1086 }
1087
1088 private void restorePath(CellList erased, VirtualEdge chaintail) {
1089 Cell c;
1090 for (int i = 0; i < erased.size(); ++i) {
1091 c = erased.cells[i];
1092 fMap[c.rown][c.coln].restore(c);
1093 }
1094 if (chaintail.tail.rank > fMinRank)
1095 restoreRankCost(chaintail.tail.rank - 1);
1096 for (VirtualEdge e = chaintail; e != null; e = e.next)
1097 restoreRankCost(e.tail.rank);
1098 if (DEBUG) {
1099 msg.println(NAME + ".restorePath(): checkCrossCosts():");
1100 checkCrossCosts();
1101 }
1102 }
1103 /**
1104 * Install the new path.
1105 *
1106 * Since the new route may have changed the vertex ordering in
1107 * the ranks, VirtualVertex.order need to be reassigned.
1108 *
1109 * @param newpath New path from low rank to high rank and includes the src and dest cells.
1110 * @param chaintail The edge chain for the route (from low rank to high rank).
1111 * @param isdown True if chaintail is at low rank (numerically smaller).
1112 */
1113 private void installPath(CellList newpath, VirtualEdge chaintail, boolean isdown) {
1114 Cell c, oldcell;
1115 VirtualVertex v;
1116 VirtualGraph.Rank rank;
1117 int old, left, right;
1118 VirtualEdge e = chaintail;
1119 VirtualVertex head = e.tail;
1120 fImprovedCount++;
1121 for (int i = 0; i < newpath.size(); ++i) {
1122 c = newpath.cells[i];
1123 // All cells on the path except the source vertex cell
1124 // should be SPACE||ERASED. If ERASED cell is reused,
1125 // order is not changed.
1126 // FIXME:
1127 if (c.type == Cell.SPACE || c.type == Cell.ERASED) {
1128 // Update vertex orders.
1129 rank = fGraph.ranks[head.rank];
1130 old = head.order;
1131 left = -1;
1132 if (c.leftVertex != null)
1133 left = c.leftVertex.vertex.order;
1134 if (left > old) {
1135 // New vertex is on right of old
1136 right = left;
1137 left = old;
1138 // Move affected vertex forward.
1139 for (int j = left; j < right; ++j) {
1140 v = rank.vts[j + 1];
1141 rank.vts[j] = v;
1142 v.order = j;
1143 }
1144 rank.vts[right] = head;
1145 head.order = right;
1146 } else {
1147 // New vertex is on left of old.
1148 if (left != old)
1149 left = left + 1;
1150 right = old;
1151 // Move backward.
1152 for (int j = right; j > left; --j) {
1153 v = rank.vts[j - 1];
1154 rank.vts[j] = v;
1155 v.order = j;
1156 }
1157 rank.vts[left] = head;
1158 head.order = left;
1159 }
1160 //
1161 oldcell = (Cell) fCellTable.get(head);
1162 int x = (c.coln * fXSpacing) / fCELL_XDIV + fXOffset;
1163 c.setVertex(head, fMap);
1164 if (TERSE)
1165 msg.println(
1166 NAME
1167 + ".installPath(): old x="
1168 + head.x
1169 + ", new x="
1170 + x
1171 + ",old order="
1172 + old
1173 + ", new order="
1174 + head.order
1175 + "\n\told="
1176 + oldcell
1177 + "\n\told.leftVertex="
1178 + oldcell.leftVertex
1179 + "\n\tnew="
1180 + c
1181 + "\n\tc.leftVertex="
1182 + c.leftVertex
1183 + "\n");
1184 head.x = x;
1185 if (oldcell != c) {
1186 // Reusing the array, c.crossCost would be cleared and recalc. again.
1187 c.crossCost = oldcell.crossCost;
1188 oldcell.type = Cell.SPACE;
1189 oldcell.crossCost = null;
1190 oldcell.vertex = null;
1191 fCellTable.put(head, c);
1192 }
1193 }
1194 if (e != null) {
1195 // Update rank costs.
1196 head = e.head;
1197 e = e.next;
1198 }
1199 }
1200 // Update rank costs.
1201 //
1202 // NOTE: Since rankCost() calculate and save crosscost between
1203 // each pair of vertices in rank r and r+1, order change in
1204 // rank r affect rankCost of r-1 and r.
1205 //
1206 //FIXME: Since the edge is just moved, actually only imaginary
1207 // edges with vertex inside the order changed region are affected.
1208 // Imaginary edges that cross the region still see that edge.
1209 // And imaginary edges that do not cross the region but both
1210 // vertices are outside are not affected by the move.
1211 VirtualVertex tail = chaintail.tail;
1212 if (isdown)
1213 for (int r = tail.rank; r <= head.rank && r < fMaxRank; ++r)
1214 rankCost(r, null);
1215 else
1216 for (int r = Math.min(tail.rank - 1, fMinRank); r < head.rank; ++r)
1217 rankCost(r, null);
1218 if (DEBUG) {
1219 msg.println(NAME + ".installPath(): checkCrossCosts():");
1220 checkCrossCosts();
1221 }
1222 }
1223
1224 ////////////////////////////////////////////////////////////////////////
1225
1226 private String mapToGeneralPath(Cell[][] map) {
1227 StringBuffer ret = new StringBuffer("<plot>\n");
1228 for (int rn = 0; rn < map.length; ++rn) {
1229 Cell[] row = map[rn];
1230 for (int cn = 0; cn < row.length; ++cn) {
1231 Cell c = row[cn];
1232 c.toGeneralPath(ret, null);
1233 }
1234 }
1235 ret.append("</plot>\n");
1236 return ret.toString();
1237 }
1238
1239 // AStar implementation ////////////////////////////////////////////////
1240 //
1241
1242 public CellList route(Cell src, Cell dest, int oldcost, VirtualEdge[] chain, boolean isdown) {
1243 // Attempt a straigth line routing for the path from src to dest.
1244 CellList ret = null;
1245 fStat = new AnnealWithCell.Stat();
1246 if (TERSE)
1247 msg.println(NAME + ".route(): dest=" + dest);
1248 Cell end = null;
1249 if (dest.vertex.isBus()) {
1250 end = routeStraightLine(src, dest, oldcost, chain, isdown);
1251 if (TERSE)
1252 msg.println(NAME + ".route(): straight=" + end);
1253 if (end != null) {
1254 // fIgnoreSet.add(isdown ? chain[src.rown] : chain[dest.rown]);
1255 if (VERBOSE)
1256 msg.println("\tstraight: cost=" + end.curCost);
1257 ++fStraightCount;
1258 }
1259 }
1260 // Find route using aStar algorithm.
1261 if (end == null) {
1262 end = aStar(src, dest, oldcost, chain);
1263 if (TERSE)
1264 msg.println(NAME + ".route(): aStar=" + end);
1265 }
1266 ++fRoutedCount;
1267 if (end != null) {
1268 ret = new CellList(10);
1269 getPath(end, isdown, ret);
1270 }
1271 if (TERSE) {
1272 msg.println("# " + NAME + ".route(): \n");
1273 for (int i = 0; i < ret.cells.length; ++i) {
1274 Cell c = ret.cells[i];
1275 if (c != null)
1276 msg.println("# " + c.toString());
1277 }
1278 }
1279 return ret;
1280 }
1281
1282 ////////////////////////////////////////////////////////////////////////
1283
1284 private Cell routeStraightLine(Cell src, Cell dest, int oldcost, VirtualEdge[] chain, boolean isdown) {
1285 Cell end = null;
1286 Cell grandparent, parent, child, beforeParent, beforeChild;
1287 src.init();
1288 for (int on = 0; end == null && on < N_OFFSET; ++on) {
1289 int offset = OFFSETS[on];
1290 if (isdown) {
1291 for (int rn = src.rown + 1, cn = src.coln + offset;
1292 rn != dest.rown + 1 && rn < fMapHeight && cn >= 0 && cn < fMapWidth;
1293 ++rn) {
1294 end = fMap[rn][cn];
1295 if (end.type == Cell.SPACE || end.type == Cell.ERASED)
1296 continue;
1297 end = null;
1298 break;
1299 }
1300 if (end != null) {
1301 grandparent = null;
1302 parent = src;
1303 beforeParent = src.findLeftVertex(fMap);
1304 for (int rn = src.rown + 1, cn = src.coln + offset;
1305 rn != dest.rown + 1 && rn < fMapHeight && cn >= 0 && cn < fMapWidth;
1306 ++rn) {
1307 end = fMap[rn][cn];
1308 beforeChild = end.findLeftVertex(fMap);
1309 if (crossAfter(parent,
1310 end,
1311 beforeParent,
1312 beforeChild,
1313 chain[parent.rown])
1314 == 0) {
1315 end.parent = parent;
1316 end.leftVertex = beforeChild;
1317 end.curCost =
1318 parent.curCost
1319 + end.travelCostFrom(parent, grandparent);
1320 grandparent = parent;
1321 parent = end;
1322 beforeParent = beforeChild;
1323 continue;
1324 }
1325 on = N_OFFSET;
1326 end = null;
1327 break;
1328 }
1329 }
1330 } else {
1331 for (int rn = src.rown - 1, cn = src.coln + offset;
1332 rn != dest.rown - 1 && rn >= 0 && cn >= 0 && cn < fMapWidth;
1333 --rn) {
1334 end = fMap[rn][cn];
1335 if (end.type == Cell.SPACE || end.type == Cell.ERASED)
1336 continue;
1337 end = null;
1338 break;
1339 }
1340 if (end != null) {
1341 grandparent = null;
1342 child = src;
1343 beforeChild = src.findLeftVertex(fMap);
1344 for (int rn = src.rown - 1, cn = src.coln + offset;
1345 rn != dest.rown - 1 && rn >= 0 && cn >= 0 && cn < fMapWidth;
1346 --rn) {
1347 end = fMap[rn][cn];
1348 beforeParent = end.findLeftVertex(fMap);
1349 if (crossAfter(end, child, beforeParent, beforeChild, chain[end.rown])
1350 == 0) {
1351 end.parent = child;
1352 end.leftVertex = beforeParent;
1353 end.curCost =
1354 child.curCost + end.travelCostFrom(child, grandparent);
1355 grandparent = child;
1356 child = end;
1357 beforeChild = beforeParent;
1358 continue;
1359 }
1360 on = N_OFFSET;
1361 end = null;
1362 break;
1363 }
1364 }
1365 }
1366 }
1367 return end;
1368 }
1369
1370 /**
1371 * Erase route for edge chain started at 'chaintail' to prepare for reroute.
1372 * All cells on the route are marked as SPACE except the src cell.
1373 *
1374 * . Update cross cost in all ranks affected.
1375 * . Mark vertices on the path as SPACE.
1376 *
1377 * Note that removing an edge currently have no cross cost still
1378 * affect cross cost of imaginary edges which have counted this
1379 * edge.
1380 *
1381 * @return The cost of the old path, the edge chain erased in
1382 * 'retchain' and the Cells erased in 'erased'.
1383 * @param e The first segement (at tail) of an edge chain.
1384 * @param src The src Cell of the path that should not be erased.
1385 * @param dest The dest Cell of the path that should not be erased, null to erase dest.
1386 * @param retchain Return the array of VirtualEdge erased indexed by rown.
1387 * @param erased The List of Cells that is erased (NOT include src and dest that should not be moved).
1388 */
1389 private int eraseTrail(VirtualEdge chaintail, Cell src, Cell dest, VirtualEdge[] retchain, CellList erased) {
1390 VirtualEdge e;
1391 Cell cell;
1392 CellList oldpath = new CellList(10);
1393 // Save old path.
1394 VirtualVertex tail;
1395 VirtualVertex head = null;
1396 for (e = chaintail; e != null; e = e.next) {
1397 tail = e.tail;
1398 head = e.head;
1399 cell = (Cell) fCellTable.get(tail);
1400 retchain[cell.rown] = e;
1401 oldpath.add(cell);
1402 }
1403 oldpath.add((Cell) fCellTable.get(head));
1404 //
1405 int oldcost = pathCost(chaintail, oldpath);
1406 // Calc. min cost from src to dest.
1407 int mincost = (oldpath.size() - 1) * fCELL_BASICCOST + MAXSLACK;
140