Source code: com/port80/graph/dot/impl/Untangle.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.*;
8 import com.port80.util.*;
9
10 /** Untangle a placement of a VirtualGraph.
11 *
12 * Global cross reduction using shortest path algoirthm on output of
13 * MinCross.
14 *
15 * . This is adapted from Anneal except that without actual
16 * coordinates, the distance and turn cost are not used. Instead of
17 * find the actual shortest path, the goal is just to go around
18 * crossings.
19 *
20 * Instead of using a grid, the map opens a channel between each
21 * pair of vertices for routing.
22 *
23 * NOTE:
24 *
25 * . After an edge chain is erased before routing, the vertex cells
26 * still keep the .vertex and .crossCost fields valid and used for
27 * cross cost calculations.
28 *
29 */
30 public class Untangle {
31
32 ////////////////////////////////////////////////////////////////////////
33
34 private static final String NAME = "Untangle";
35 private static final boolean DEBUG = false;
36 /** 1=time only, 2=1+stat, 3=2+result, 4=3+intermediate results.*/
37 private static final int VERBOSE = 1;
38
39 private static final int BASICFACTOR = 1; /** Min. cross from one cell to another.*/
40
41 // Nested classes //////////////////////////////////////////////////////
42 //
43
44 private final class Cell {
45
46 private static final String NAME = "Cell";
47
48 public static final int SPACE = 0; /** Available for routing.*/
49 public static final int ERASED = 2; /** Erased vertex cell for path being routed.*/
50 /** Vertex center, type>VERTEX are occupied by a VirtualVertex, not avaiable for routing.*/
51 public static final int VERTEX = 3;
52 public static final int VIRTUAL = 4; /** Virtual vertex (EDGE,EDGELABEL) center.*/
53 public static final int BUS = 5; /** Bus vertex (BUS) center.*/
54
55 ////////////////////////////////////////////////////////////////////////
56
57 /** The vertex at this cell. */
58 VirtualVertex vertex;
59 int type;
60 int rown; /** rown is same as rank if graph.minRank==0.*/
61 int coln; /** coln is the equivalent of VirtualVertex.order for cells in the map.*/
62 /** Mark that cell has been visited. Each routing increment a
63 * counter for the mark and thus no need to reset the mark
64 * after each routing.
65 */
66 int mark;
67 int[] crossCost;
68 /** Sum of all xPenalty crossing this edge (but not yet multiplied by xPenalty of the edge).*/
69 int curCost; /** Current total cost from src. to this cell.*/
70 int estTotal; /** Estimated total=curCost+est.*/
71 Cell parent; /** Parent cell on the best path to this cell.*/
72 Cell leftVertex; /** The first VERTEX cell to the left of this.*/
73
74 ////////////////////////////////////////////////////////////////////////
75
76 Cell(int rn, int cn) {
77 this.type = SPACE;
78 this.rown = rn;
79 this.coln = cn;
80 }
81
82 Cell(int type, int rn, int cn, VirtualVertex v) {
83 this.type = type;
84 this.rown = rn;
85 this.coln = cn;
86 this.vertex = v;
87 }
88
89 Cell(int rn, int cn, VirtualVertex v) {
90 this(VIRTUAL, rn, cn, v);
91 if(v.isReal()) this.type=VERTEX;
92 else if(v.isBus()) this.type=BUS;
93 }
94
95 ////////////////////////////////////////////////////////////////////////
96
97 VirtualVertex getVertex() {
98 return vertex;
99 }
100 Cell save() {
101 return new Cell(type, rown, coln, vertex);
102
103 }
104 /** Restore cell from previous save state.
105 * Only type and vertex may have changed.
106 */
107 void restore(Cell c) {
108 this.type = c.type;
109 this.vertex = c.vertex;
110 }
111 /** Reset to init. state. */
112 void reset() {}
113 /** Set a cell to vertex 'v'.*/
114 void setVertex(VirtualVertex v) {
115 if(v.isReal()) this.type = VERTEX;
116 else if(v.isBus()) this.type = BUS;
117 else if(v.isVirtual()) this.type = VIRTUAL;
118 else {
119 msg.err(
120 NAME
121 + ".setVertex(): Invalid type for VERTEX cell: v="
122 + v.getName()
123 + ", type="
124 + v.getType());
125 this.type = VERTEX;
126 }
127 this.vertex = v;
128 }
129 /** Estimate cost to destination.
130 */
131 int estimate(Cell dest) {
132 if (rown < dest.rown)
133 return (dest.rown - rown) * BASICFACTOR;
134 else
135 return (rown - dest.rown) * BASICFACTOR;
136 }
137 void setLeftVertex(Cell c) {
138 leftVertex = c;
139 }
140 /** @return First VERTEX/BUS/VIRTUAL cell to the left of this
141 * or this if this is a VERTEX/BUS/VIRTUAL.
142 */
143 Cell findLeftVertex() {
144 Cell[] r = theMap[rown];
145 Cell c;
146 for (int cn = coln; cn >= 0; --cn) {
147 c = r[cn];
148 if (c.type >= ERASED) {
149 leftVertex = c;
150 return leftVertex;
151 }
152 }
153 return null;
154 }
155 /** Convert this cell and cells controlled by this cell to
156 * SPACE.
157 * @return Append clone of old cell states to 'ret' list.
158 */
159 void erase(CellList ret) {
160 if (vertex == null)
161 msg.err(NAME + ".erase(): vertex==null: cell=" + this);
162 ret.add(save());
163 type = ERASED;
164 }
165 /** Check if this cell is one of the destination.
166 *
167 * FIXME: For now, we always have line destination.
168 */
169 boolean reached(Cell dest) {
170 if (rown == dest.rown)
171 return true;
172 return false;
173 }
174 /** Visit this cell from parent through the edge chain 'chain'.
175 */
176 boolean accept(
177 Cell parent,
178 Cell dest,
179 VirtualEdge segment,
180 int crosscost,
181 int oldcost,
182 CellHeap queue) {
183 int cost = parent.curCost;
184 // Bus crossing cost.
185 cost += crosscost;
186 // Travel cost.
187 cost += BASICFACTOR;
188 if (DEBUG)
189 msg.println(
190 NAME
191 + ".accept(): parent.curCost="
192 + parent.curCost
193 + ", crosscost="
194 + crosscost
195 + ", oldcost="
196 + oldcost
197 + ", cost="
198 + cost
199 + ", "
200 + toString());
201 if (mark == markCounter) {
202 // Visited before.
203 if (cost < curCost) {
204 // The new visit have lower cost, requeue it.
205 curCost = cost;
206 estTotal = curCost + estimate(dest);
207 this.parent = parent;
208 if (VERBOSE > 1)
209 stat.reopen++;
210 return true;
211 }
212 } else {
213 mark = markCounter;
214 curCost = cost;
215 estTotal = cost + estimate(dest);
216 this.parent = parent;
217 //if(estTotal>=oldcost) return false;
218 if (VERBOSE > 1)
219 stat.visited++;
220 return true;
221 }
222 if (VERBOSE > 1)
223 stat.discarded++;
224 return false;
225 }
226 /** @return true if this is lower priority (higher cost) than
227 * given 'state'.*/
228 public int compareTo(Object a) {
229 int t = ((Cell) a).estTotal;
230 int c = ((Cell) a).curCost;
231 if (estTotal < t)
232 return 1;
233 if (estTotal > t)
234 return -1;
235 if (curCost > c)
236 return 1;
237 if (curCost < c)
238 return -1;
239 return 0;
240 }
241 void toGeneralPath(StringBuffer buf, String fill) {
242 final int unit = 10;
243 int xx = coln * unit;
244 int yy = rown * unit;
245 if (fill == null) {
246 fill = "red";
247 if (type == SPACE)
248 fill = "lightgray";
249 else if (type == VERTEX)
250 fill = "black";
251 else if (type == BUS)
252 fill = "blue";
253 else if (type == VIRTUAL)
254 fill = "deepskyblue";
255 else if (type == ERASED)
256 fill = "pink";
257 }
258 buf.append("<rect color=\"white\" fill=\"" + fill + "\">" + xx + "," + yy);
259 buf.append(" " + unit + "," + unit);
260 buf.append("</rect>\n");
261 }
262
263 public String toString() {
264 String ret = "SPACE";
265 String order = "";
266 if (type == ERASED)
267 ret = "ERASED ";
268 if (vertex != null) {
269 ret = vertex.getName();
270 order = " " + vertex.order + " ";
271 }
272 return ret + " (" + rown + "," + coln + order + " cost=" + curCost + "/" + estTotal + ")";
273 }
274 }
275
276 ////////////////////////////////////////////////////////////////////////
277
278 private final class Stat {
279 int visited;
280 int expanded;
281 int dequeue;
282 int enqueue;
283 int reopen;
284 int discarded;
285 int maxQueueSize;
286 int hit;
287 public void reset() {
288 visited = 0;
289 expanded = 0;
290 dequeue = 0;
291 enqueue = 0;
292 reopen = 0;
293 discarded = 0;
294 maxQueueSize = 0;
295 hit = 0;
296 }
297 public String toString() {
298 return "visited="
299 + visited
300 + ", maxQueueSize="
301 + maxQueueSize
302 + ", expanded="
303 + expanded
304 + ", enqueue="
305 + enqueue
306 + ", reopen="
307 + reopen
308 + ", discarded="
309 + discarded
310 + ", dequeue="
311 + dequeue
312 + ", hit="
313 + hit;
314 }
315 }
316
317 ////////////////////////////////////////////////////////////////////////
318
319 /** A simple ArrayList never deallocate on clear and have direct
320 * access to array.*/
321 private final class CellList {
322 Cell[] cells;
323 int size = 0;
324 CellList() {
325 this(300);
326 }
327 CellList(int n) {
328 cells = new Cell[n];
329 }
330 void add(Cell c) {
331 if (size >= cells.length) {
332 Cell[] a = new Cell[cells.length * 3 / 2];
333 System.arraycopy(cells, 0, a, 0, size);
334 cells = a;
335 }
336 cells[size++] = c;
337 }
338 void clear() {
339 size = 0;
340 }
341 }
342
343 ////////////////////////////////////////////////////////////////////////
344
345 /** Heap/priority queue of Cell.*/
346 private final class CellHeap {
347 private static final String NAME = "CellHeap";
348
349 public int size;
350 Cell[] heap;
351
352 public CellHeap() {
353 heap = new Cell[100];
354 }
355 public int size() {
356 return size;
357 }
358 public Cell get(int i) {
359 return heap[i + 1];
360 }
361 public void reset() {
362 size = 0;
363 }
364 public void clear() {
365 size = 0;
366 }
367 public void enqueue(Cell a) {
368 if (false)
369 msg.println(NAME + ".enqueue(): " + a);
370 if (++size >= heap.length)
371 growTo(heap.length * 2);
372 // Only keep the top 100.
373 // . Suprisingly, this is not faster, actually it is about 25%
374 // slower than let the heap grow!
375 //if(++size>=heap.length) size=heap.length-1;
376 int i = 1;
377 if (size > 1) {
378 for (i = size; i > 1 && heap[i / 2].compareTo(a) < 0; i /= 2)
379 heap[i] = heap[i / 2];
380 }
381 heap[i] = a;
382 }
383 /** @return the highest priority (lowest cost) item.
384 * @enter (existing item count >= 1) && (item != NULL)
385 * @exit item has been deleted.
386 */
387 public Cell dequeue() {
388 if (size == 0) {
389 msg.err("CellHeap.dequeue(): size==0");
390 return null;
391 }
392 Cell ret = heap[1]; // Save the root.
393 heap[1] = heap[size--]; // Put the last item in the root.
394 moveDown(1); // Move the new root down if necessary.
395 return ret;
396 }
397 private void moveDown(int k) {
398 int left = 2 * k;
399 if (left <= size) {
400 int right = 2 * k + 1;
401 if (right <= size && heap[right].compareTo(heap[left]) > 0)
402 left = right;
403 if (heap[k].compareTo(heap[left]) < 0) {
404 Cell a = heap[k];
405 heap[k] = heap[left];
406 heap[left] = a;
407 moveDown(left);
408 }
409 }
410 }
411 private void growTo(int n) {
412 Cell[] a = new Cell[n];
413 //NOTE: size has been incremented to ==heap.length.
414 System.arraycopy(heap, 0, a, 0, size);
415 heap = a;
416 }
417 }
418
419 // Instance fields /////////////////////////////////////////////////////
420 //
421
422 VirtualGraph graph;
423 Cell[][] theMap;
424 int markCounter;
425 int nImproved;
426 /** Set of VirtualEdge (chainhead) to be ignored (eg. alway have min. cost).*/
427 Set ignoreSet;
428 /** Sorted open cells.*/
429 private CellHeap openQueue;
430 private int minRank, maxRank;
431 private int maxCol;
432 private Stat stat;
433 //
434 /** Counters for rankCost().*/
435 private int[] crossCounts;
436 /** Edge chain being routed indexed by rown instead of rank.*/
437 private VirtualEdge[] curChain;
438
439 ////////////////////////////////////////////////////////////////////////
440
441 public static final int dot(VirtualGraph g, int maxiter) {
442 return new Untangle().reRoute(g, maxiter);
443 }
444
445 public final int reRoute(VirtualGraph g, int maxiter) {
446 // Construct a map from the VirtualGraph.
447 SystemWatch timer = null;
448 SystemWatch timer1 = null;
449 if (VERBOSE > 0)
450 timer = new SystemWatch().start();
451 this.graph = g;
452 this.openQueue = new CellHeap();
453 createMap();
454 if (false)
455 msg.println(mapToGeneralPath(theMap));
456 Cell[] row;
457 Cell src, dest;
458 VirtualVertex v, head, tail;
459 VirtualEdge e;
460 int totalimproved = 0;
461 int lastcount = 0;
462 int iter;
463 for (iter = 0; iter < maxiter; ++iter) {
464 if (VERBOSE > 0)
465 timer1 = new SystemWatch().start();
466 nImproved = 0;
467 for (int rn = 0; rn < theMap.length; ++rn) {
468 row = theMap[rn];
469 for (int cn = 0; cn < row.length; ++cn) {
470 src = theMap[rn][cn];
471 // For now, only route VERTEX->BUS or BUS<->BUS forward and backward.
472 if (src.type == Cell.VERTEX || src.type == Cell.BUS) {
473 v = src.vertex;
474 //if(!v.getName().startsWith("#dotneato/dotgen/init")) continue;
475 for (int i = 0; i < v.outs.length; ++i) {
476 e = v.outs[i];
477 if (ignoreSet.contains(e))
478 continue;
479 head = e.getChainHead();
480 if (head.rank - v.rank <= 2) {
481 ignoreSet.add(e);
482 continue;
483 }
484 if (head.isBus()) {
485 dest = theMap[head.rank - minRank][head.order * 2 + 1];
486 reRouteDown(src, dest, e);
487 }
488 }
489 for (int i = 0; i < v.ins.length; ++i) {
490 e = v.ins[i];
491 while (e.prev != null)
492 e = e.prev;
493 if (ignoreSet.contains(e))
494 continue;
495 tail = e.tail;
496 if (v.rank - tail.rank <= 2) {
497 ignoreSet.add(e);
498 continue;
499 }
500 if (tail.isBus()) {
501 dest = theMap[tail.rank - minRank][tail.order * 2 + 1];
502 reRouteUp(src, dest, e);
503 }
504 }
505 }
506 }
507 }
508 if (VERBOSE > 0)
509 msg.println(
510 NAME
511 + ".reRoute(): pass="
512 + iter
513 + " : "
514 + nImproved
515 + "/"
516 + (markCounter - lastcount)
517 + " improved routes, "
518 + timer1.stop().toString());
519 if (nImproved == 0)
520 break;
521 totalimproved += nImproved;
522 lastcount = markCounter;
523 }
524 if (VERBOSE > 0)
525 msg.println(
526 NAME
527 + ".reRoute(): total passes="
528 + (iter + 1)
529 + ": "
530 + totalimproved
531 + "/"
532 + (markCounter)
533 + " improved routes, "
534 + timer.stop().toString());
535 clear();
536 return totalimproved;
537 }
538
539 /** @return New dest. cell if improved, else null.
540 */
541 private Cell reRouteDown(Cell src, Cell dest, VirtualEdge chainhead) {
542 //NOTE: Bus vertex always have one and only one edge.
543 if (VERBOSE > 1)
544 msg.println(
545 NAME
546 + ".reRouteDown(): src="
547 + src.vertex.getName()
548 + ", dest="
549 + dest.vertex.getName());
550 CellList erased = new CellList(10);
551 int oldcost = eraseTrail(chainhead, src.vertex, curChain, erased);
552 if (oldcost == 0)
553 return null;
554 CellList newpath = routePointToLine(src, dest, oldcost, curChain, true);
555 return routePath(newpath, oldcost, chainhead, erased, true);
556 }
557 private Cell reRouteUp(Cell src, Cell dest, VirtualEdge chainhead) {
558 if (VERBOSE > 1)
559 msg.println(
560 NAME + ".reRouteUp(): src=" + src.vertex.getName() + ", dest=" + dest.vertex.getName());
561 CellList erased = new CellList(10);
562 int oldcost = eraseTrail(chainhead, src.vertex, curChain, erased);
563 if (oldcost == 0)
564 return null;
565 CellList newpath = routePointToLine(src, dest, oldcost, curChain, false);
566 return routePath(newpath, oldcost, chainhead, erased, false);
567 }
568 /** Create the map from 'g'. */
569 private void createMap() {
570 VirtualGraph.Rank rank;
571 VirtualVertex v;
572 Cell[] row;
573 int rn, cn;
574 int maxv = 0; // Max. vertices in a rank.
575 this.minRank = graph.minRank;
576 this.maxRank = graph.maxRank;
577 this.maxCol = 0;
578 this.ignoreSet = new HashSet(50);
579 rn = maxRank - minRank + 1;
580 if (DEBUG)
581 msg.println(NAME + ".createMap(): rows=" + rn);
582 curChain = new VirtualEdge[rn];
583 theMap = new Cell[rn][];
584 markCounter = 0;
585 nImproved = 0;
586 rn = 0;
587 for (int r = graph.minRank; r <= graph.maxRank; ++r, ++rn) {
588 rank = graph.ranks[r];
589 cn = rank.nVts * 2 + 1;
590 if (cn > maxCol)
591 maxCol = cn;
592 if (rank.nVts > maxv)
593 maxv = rank.nVts;
594 row = new Cell[cn];
595 theMap[rn] = row;
596 row[0] = new Cell(rn, 0);
597 cn = 1;
598 for (int i = 0; i < rank.nVts; ++i) {
599 v = rank.vts[i];
600 row[cn] = new Cell(rn, cn, v);
601 ++cn;
602 row[cn] = new Cell(rn, cn);
603 ++cn;
604 }
605 }
606 this.crossCounts = new int[maxv];
607 }
608
609 ////////////////////////////////////////////////////////////////////////
610
611 /**
612 * @param ignore An edge to be ignored.
613 *
614 * //FIXME: Need cost for imaginary edge from every vertices on
615 * top to every vertices at bottom instead of for only the real
616 * edges.
617 */
618 private int rankCost(int r, VirtualEdge ignore) {
619 if (r < minRank || r >= maxRank)
620 return 0;
621 int ranktotal = 0;
622 VirtualVertex v, head;
623 VirtualEdge e;
624 Cell cell;
625 int min, max;
626 int order;
627 int cost;
628 VirtualGraph.Rank rank = graph.ranks[r];
629 VirtualGraph.Rank rank1 = graph.ranks[r + 1];
630 Cell[] row = theMap[r - minRank];
631 for (int i = 0; i < rank1.nVts; ++i)
632 crossCounts[i] = 0;
633 max = 0;
634 // Left to right.
635 for (int c = 0, cn = 1; c < rank.nVts; ++c, cn += 2) {
636 v = rank.vts[c];
637 cell = row[cn];
638 if (cell.crossCost == null)
639 cell.crossCost = new int[rank1.nVts];
640 else
641 for (int i = 0; i < rank1.nVts; ++i)
642 cell.crossCost[i] = 0;
643 for (int c1 = 0; c1 < max; ++c1) {
644 head = rank1.vts[c1];
645 order = head.order;
646 cost = 0;
647 for (int i = order + 1; i <= max; ++i)
648 cost += crossCounts[i];
649 if (false && ignore != 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 + head.getName()
661 + "("
662 + head.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 == ignore)
672 continue;
673 order = e.head.order;
674 if (order > max)
675 max = order;
676 crossCounts[order] += e.xPenalty;
677 }
678 }
679 // right to left.
680 for (int i = 0; i < rank1.nVts; ++i)
681 crossCounts[i] = 0;
682 min = rank1.nVts;
683 for (int c = rank.nVts - 1, cn = rank.nVts * 2 - 1; c >= 0; --c, cn -= 2) {
684 v = rank.vts[c];
685 cell = row[cn];
686 for (int c1 = min + 1; c1 < rank1.nVts; ++c1) {
687 head = rank1.vts[c1];
688 order = head.order;
689 cost = 0;
690 for (int i = min; i < order; ++i)
691 cost += crossCounts[i];
692 if (false && ignore != 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 + head.getName()
704 + "("
705 + head.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 == ignore)
715 continue;
716 order = e.head.order;
717 if (order < min)
718 min = order;
719 crossCounts[order] += e.xPenalty;
720 }
721 }
722 if (DEBUG)
723 msg.println(NAME + ".rankCost(): r=" + r + ",ignore=" + ignore + ", rank total=" + ranktotal);
724 return ranktotal;
725 }
726
727 /** Calculate crossing cost for edge from parent to space before
728 * the first vertex below. The cost=crossCost(parent,child)
729 * +e.xPenalty*(xPenalty of all edges from vertex on left of
730 * parent to child).
731 *
732 * beforeParent parent
733 * v-------------------|
734 * child vts[0](afterChild)
735 *
736 * @param parent parent cell for the route.
737 * @param child child cell (below parent) for the route.
738 * @param beforeParent Vertex cell before parent or parent itself.
739 * @param route is the edge in this rank being routed.
740 */
741 private int crossAfterBefore(Cell parent, Cell child, Cell beforeParent, VirtualEdge segment) {
742 if (beforeParent == null)
743 return 0;
744 VirtualVertex v = graph.ranks[segment.head.rank].vts[0];
745 Cell afterChild = theMap[v.rank - minRank][1];
746 int ret = beforeParent.crossCost[afterChild.vertex.order];
747 int order;
748 VirtualEdge e;
749 order = 0;
750 v = beforeParent.vertex;
751 for (int i = 0; i < v.outs.length; ++i) {
752 e = v.outs[i];
753 if (e == segment)
754 continue;
755 if (e.head.order >= order)
756 ret += e.xPenalty;
757 }
758 order = beforeParent.vertex.order;
759 v = afterChild.vertex;
760 for (int i = 0; i < v.ins.length; ++i) {
761 e = v.ins[i];
762 if (e == segment)
763 continue;
764 if (e.tail.order < order)
765 ret += e.xPenalty;
766 }
767 ret *= segment.xPenalty;
768 if (false)
769 msg.println(
770 NAME
771 + ".crossAfterBefore():"
772 + "\n\t parent="
773 + parent
774 + "\n\t child="
775 + child
776 + "\n\t beforeParent="
777 + beforeParent
778 + "\n\t afterChild="
779 + afterChild
780 + "\n\t segment="
781 + segment
782 + "\n\t ret="
783 + ret);
784 return ret;
785 }
786
787 /**
788 *
789 * parent vts[0](afterParent)
790 * |-------------------v
791 * beforechild child
792 */
793 private int crossBeforeAfter(Cell parent, Cell child, Cell beforeChild, VirtualEdge segment) {
794 if (beforeChild == null)
795 return 0;
796 VirtualVertex v = graph.ranks[segment.tail.rank].vts[0];
797 Cell afterParent = theMap[v.rank - minRank][1];
798 int ret = afterParent.crossCost[beforeChild.vertex.order];
799 int order;
800 VirtualEdge e;
801 // Additional crossing at afterParent.
802 order = beforeChild.vertex.order;
803 v = afterParent.vertex;
804 for (int i = 0; i < v.outs.length; ++i) {
805 e = v.outs[i];
806 if (e == segment)
807 continue;
808 if (e.head.order <= order)
809 ret += e.xPenalty;
810 }
811 // Additional crossing at beforeChild.
812 order = 0;
813 v = beforeChild.vertex;
814 for (int i = 0; i < v.ins.length; ++i) {
815 e = v.ins[i];
816 if (e == segment)
817 continue;
818 if (e.tail.order > order)
819 ret += e.xPenalty;
820 }
821 ret *= segment.xPenalty;
822 if (false)
823 msg.println(
824 NAME
825 + ".crossBeforeAfter():"
826 + "\n\t parent="
827 + parent
828 + "\n\t child="
829 + child
830 + "\n\t afterParent="
831 + afterParent
832 + "\n\t beforeChild="
833 + beforeChild
834 + "\n\t segment="
835 + segment
836 + "\n\t ret="
837 + ret);
838 return ret;
839 }
840
841 /** Calculate crossing cost for edge from parent to child below.
842 * child.
843 *
844 * @param parent parent cell for the segment.
845 * @param child child cell (below parent) for the segment.
846 * @param beforeParent Vertex cell before parent or parent itself.
847 * @param beforeChild Vertex cell before child or the child itself.
848 * @param segment is the edge in this rank being routed.
849 *
850 * beforeParent parent
851 * v--------|
852 * beforeChild child
853 */
854 private int crossAfter(Cell parent, Cell child, Cell beforeParent, Cell beforeChild, VirtualEdge segment) {
855 if (beforeParent == null && beforeChild == null)
856 return 0;
857 if (beforeParent == null)
858 return crossBeforeAfter(parent, child, beforeChild, segment);
859 if (beforeChild == null)
860 return crossAfterBefore(parent, child, beforeParent, segment);
861 if (true && beforeParent.crossCost == null)
862 msg.println(NAME + ".crossAfter(): beforeParent:" + beforeParent);
863 int ret = beforeParent.crossCost[beforeChild.vertex.order];
864 int order;
865 VirtualVertex v;
866 VirtualEdge e;
867 // Additional crossing at before parent.
868 if (parent != beforeParent) {
869 order = beforeChild.vertex.order;
870 v = beforeParent.vertex;
871 for (int i = 0; i < v.outs.length; ++i) {
872 e = v.outs[i];
873 if (e == segment)
874 continue;
875 if (e.head.order > order)
876 ret += e.xPenalty;
877 }
878 }
879 if (child != beforeChild) {
880 order = beforeParent.vertex.order;
881 v = beforeChild.vertex;
882 for (int i = 0; i < v.ins.length; ++i) {
883 e = v.ins[i];
884 if (e == segment)
885 continue;
886 if (e.tail.order > order)
887 ret += e.xPenalty;
888 }
889 }
890 if (DEBUG && VERBOSE > 3)
891 msg.println(
892 NAME
893 + ".crossAfter():"
894 + "\n\t parent="
895 + parent
896 + "\n\t child="
897 + child
898 + "\n\t beforeParent="
899 + beforeParent
900 + "\n\t beforeChild="
901 + beforeChild
902 + "\n\t segment="
903 + segment
904 + "\n\t ret="
905 + ret);
906 ret *= segment.xPenalty;
907
908 return ret;
909 }
910
911 /** If newpath is better than oldpath, install path according to
912 * newpath and clean up, else restore oldpath.
913 *
914 * @return New dest. cell if improved, else null.
915 */
916 private Cell routePath(CellList newpath, int oldcost, VirtualEdge chainhead, CellList erased, boolean isdown) {
917 if (newpath == null) {
918 restorePath(erased, chainhead);
919 return null;
920 }
921 int newcost = isdown ? newpath.cells[newpath.size - 1].curCost : newpath.cells[0].curCost;
922 if (newcost <= newpath.size)
923 ignoreSet.add(chainhead);
924 if (VERBOSE > 1)
925 msg.println(NAME + ".routePath(): " + ", oldcost=" + oldcost + ", newcost=" + newcost);
926 if (VERBOSE > 2) {
927 //msg.println(mapToGeneralPath(theMap));
928 msg.println(NAME + ".routePath(): path=");
929 StringBuffer buf = new StringBuffer();
930 VirtualEdge e = chainhead;
931 VirtualVertex v = e.tail;
932 for (int i = 0; i < newpath.size; ++i) {
933 buf.append("#\t" + newpath.cells[i].toString() + ", v=" + v.getName() + "\n");
934 if (e != null) {
935 v = e.head;
936 e = e.next;
937 }
938 }
939 e = chainhead;
940 v = e.tail;
941 for (int i = 0; i < newpath.size; ++i) {
942 if (i == 0 || i == newpath.size - 1)
943 newpath.cells[i].toGeneralPath(buf, "black");
944 else
945 newpath.cells[i].toGeneralPath(buf, "green");
946 if (e != null) {
947 v = e.head;
948 e = e.next;
949 }
950 }
951 msg.println(buf.toString());
952 }
953 if (newcost >= oldcost) {
954 restorePath(erased, chainhead);
955 return null;
956 } else {
957 installPath(newpath, chainhead);
958 return (isdown ? newpath.cells[newpath.size - 1] : newpath.cells[0]);
959 }
960 }
961
962 private void restorePath(CellList erased, VirtualEdge chainhead) {
963 Cell c;
964 for (int i = 0; i < erased.size; ++i) {
965 c = erased.cells[i];
966 theMap[c.rown][c.coln].restore(c);
967 }
968 }
969 /** Install the new path.
970 *
971 * Since the new route may have changed the vertex ordering in
972 * the ranks, VirtualVertex.order need to be reassigned. Also
973 * need to reorder cells to put SPACE cells on both side of the
974 * new vertex.
975 *
976 * @param newpath New path from low rank to high rank and includes
977 * the src and dest cells.
978 * @param chainhead The edge chain for the route (from low rank
979 * to high rank).
980 */
981 private void installPath(CellList newpath, VirtualEdge chainhead) {
982 Cell c;
983 Cell[] row;
984 VirtualVertex v;
985 VirtualGraph.Rank rank;
986 int old, left, right, cn;
987 VirtualEdge e = chainhead;
988 VirtualVertex head = e.tail;
989 nImproved++;
990 for (int i = 0; i < newpath.size; ++i) {
991 c = newpath.cells[i];
992 // All cells on the path except the source vertex cell
993 // should be SPACE||ERASED. If ERASED cell is reused,
994 // orders are not changed.
995 if (c.type == Cell.ERASED) {
996 c.setVertex(head);
997 if (false)
998 msg.println(NAME + ".installPath():\n\tvertex=" + head + "\n\told==new=" + c);
999 } else if (c.type == Cell.SPACE) {
1000 // Update vertex orders.
1001 rank = graph.ranks[head.rank];
1002 row = theMap[head.rank - minRank];
1003 old = head.order;
1004 left = -1;
1005 if (c.leftVertex != null)
1006 left = c.leftVertex.vertex.order;
1007 if (left > old) {
1008 // New vertex is on right of old
1009 right = left;
1010 left = old;
1011 // Move affected vertex forward.
1012 // vts[left+1,right]->[left,right-1]
1013 cn = left * 2 + 1;
1014 for (int j = left; j < right; ++j) {
1015 v = rank.vts[j + 1];
1016 rank.vts[j] = v;
1017 v.order = j;
1018 row[cn].type = row[cn + 2].type;
1019 row[cn].vertex = v;
1020 cn += 2;
1021 }
1022 rank.vts[right] = head;
1023 head.order = right;
1024 row[cn].setVertex(head);
1025 } else {
1026 // New vertex is on left of old.
1027 if (left != old)
1028 left = left + 1;
1029 right = old;
1030 // Move backward.
1031 cn = right * 2 + 1;
1032 for (int j = right; j > left; --j) {
1033 v = rank.vts[j - 1];
1034 rank.vts[j] = v;
1035 v.order = j;
1036 row[cn].type = row[cn - 2].type;
1037 row[cn].vertex = v;
1038 cn -= 2;
1039 }
1040 rank.vts[left] = head;
1041 head.order = left;
1042 row[cn].setVertex(head);
1043 }
1044 if (false)
1045 msg.println(
1046 NAME
1047 + ".installPath():\n\tvertex="
1048 + head
1049 + "\n\told="
1050 + old
1051 + "\n\tnew="
1052 + cn);
1053 }
1054 if (e != null) {
1055 // Update rank costs.
1056 head = e.head;
1057 e = e.next;
1058 }
1059 }
1060 }
1061
1062 ////////////////////////////////////////////////////////////////////////
1063
1064 private String mapToGeneralPath(Cell[][] map) {
1065 StringBuffer ret = new StringBuffer("<plot>\n");
1066 for (int rn = 0; rn < map.length; ++rn) {
1067 Cell[] row = map[rn];
1068 for (int cn = 0; cn < row.length; ++cn) {
1069 Cell c = row[cn];
1070 c.toGeneralPath(ret, null);
1071 }
1072 }
1073 ret.append("</plot>\n");
1074 return ret.toString();
1075 }
1076
1077 // AStar implementation ////////////////////////////////////////////////
1078 //
1079
1080 public CellList routePointToLine(Cell src, Cell dest, int oldcost, VirtualEdge[] chain, boolean isdown) {
1081 // Attempt a straigth line routing for the path from src to dest.
1082 stat = new Untangle.Stat();
1083 Cell end = aStar(src, dest, oldcost, chain);
1084 if (end == null)
1085 return null;
1086 CellList ret = new CellList(10);
1087 getPath(end, isdown, ret);
1088 if (VERBOSE > 1)
1089 msg.println(stat.toString());
1090 return ret;
1091 }
1092
1093 /** Erase route for edge chain started at 'e'.
1094 *
1095 * . Update cross cost in all ranks affected.
1096 * . Mark vertices on the path as SPACE.
1097 *
1098 * Note that removing an edge currently have no cross cost still
1099 * affect cross cost of imaginary edges which have counted this
1100 * edge.
1101 *
1102 * @param e The first segement (at tail) of an edge chain.
1103 * @param src The src node of the path that should not be erased.
1104 * @param chain Return the chain erased.
1105 * @return The cost of the old path. The edge chain erased in
1106 * 'chain' and the Cells erased in 'erased'.
1107 */
1108 public int eraseTrail(VirtualEdge chainhead, VirtualVertex src, VirtualEdge[] retchain, CellList erased) {
1109 VirtualVertex tail, head = null;
1110 VirtualEdge e;
1111 Cell cell;
1112 CellList oldpath = new CellList(10);
1113 // Find cost of old path.
1114 for (e = chainhead; e != null; e = e.next) {
1115 tail = e.tail;
1116 head = e.head;
1117 cell = theMap[tail.rank - minRank][tail.order * 2 + 1];
1118 retchain[cell.rown] = e;
1119 oldpath.add(cell);
1120 }
1121 oldpath.add(theMap[head.rank - minRank][head.order * 2 + 1]);
1122 //
1123 //
1124 // Calc. rank costs.
1125 //
1126 for (e = chainhead; e != null; e = e.next)
1127 rankCost(e.tail.rank, e);
1128 //
1129 int oldcost = pathCost(chainhead, oldpath);
1130 // Calc. min cost from src to dest.
1131 int mincost = (oldpath.size - 1) * BASICFACTOR;
1132 if (oldcost <= mincost) {
1133 ignoreSet.add(chainhead);
1134 return 0;
1135 }
1136 //
1137 // Erase old path.
1138 for (int i = 0; i < oldpath.size; ++i) {
1139 cell = oldpath.cells[i];
1140 if (cell.vertex != src)
1141 cell.erase(erased);
1142 }
1143 if (DEBUG) {
1144 msg.println(NAME + ".eraseTrail(): erased:");
1145 for (int i = 0; i < erased.size; ++i) {
1146 msg.println("\t" + erased.cells[i]);
1147 }
1148 if (true)
1149 msg.println(mapToGeneralPath(theMap));
1150 }
1151 return oldcost;
1152 }
1153
1154 /** Determine cost of the given path.
1155 * @param path The cell path from tail(lower rank) to head.
1156 */
1157 public int pathCost(VirtualEdge chainhead, CellList path) {
1158 int cost = 0;
1159 Cell hcell;
1160 VirtualEdge e = chainhead;
1161 Cell tcell = path.cells[0];
1162 if (VERBOSE > 3)
1163 msg.println(NAME + ".pathCost(): i=0" + ", tcell=" + tcell);
1164 for (int i = 1; i < path.size; ++i) {
1165 hcell = path.cells[i];
1166 int cc = tcell.crossCost[hcell.vertex.order] * e.xPenalty;
1167 if (DEBUG)
1168 msg.println("\tcross=" + cc + ", e.xPenalty=" + e.xPenalty);
1169 cost += cc;
1170 cost += BASICFACTOR;
1171 if (VERBOSE > 3)
1172 msg.println(NAME + ".pathCost(): i=" + i + ", hcell=" + hcell + ",cost=" + cost);
1173 tcell = hcell;
1174 e = e.next;
1175 }
1176 if (VERBOSE > 3) {
1177 msg.println(NAME + ".pathCost(): cost=" + cost);
1178 }
1179 return cost;
1180 }
1181
1182 public void clear() {
1183 openQueue = null;
1184 crossCounts = null;
1185 theMap = null;
1186 }
1187
1188 ////////////////////////////////////////////////////////////////////////
1189
1190 private Cell aStar(Cell src, Cell dest, int oldcost, VirtualEdge[] chain) {
1191 if (src == dest) {
1192 msg.err(NAME + ".aStar(): src==dest: src=" + src + ", dest=" + dest);
1193 return null;
1194 }
1195 Cell best = null;
1196 Cell next = null;
1197 int nextbest; // The next best total cost in openQueue.
1198 if (markCounter >= Integer.MAX_VALUE) {
1199 msg.err(NAME + ".aStar(): markCounter>=Integer.MAX_VALUE");
1200 markCounter = 0;
1201 }
1202 markCounter++;
1203 src.setLeftVertex(src);
1204 src.mark = markCounter;
1205 src.curCost = 0;
1206 src.estTotal = Integer.MAX_VALUE;
1207 src.parent = null;
1208 openQueue.reset();
1209 openQueue.enqueue(src);
1210 while (openQueue.size() != 0 || next != null) {
1211 if (next == null) {
1212 best = (Cell) openQueue.dequeue();
1213 if (VERBOSE > 1)
1214 stat.dequeue++;
1215 } else {
1216 best = next;
1217 next = null;
1218 stat.hit++;
1219 }
1220 if (best.estTotal >= oldcost)
1221 break;
1222 if (openQueue.size() != 0)
1223 nextbest = openQueue.get(0).estTotal;
1224 else
1225 nextbest = Integer.MAX_VALUE;
1226 if (VERBOSE > 1)
1227 if (openQueue.size > stat.maxQueueSize)
1228 stat.maxQueueSize = openQueue.size;
1229 if (DEBUG)
1230 msg.println(
1231 "# best="
1232 + best
1233 + ", parent="
1234 + best.parent
1235 + ", curCost="
1236 + best.curCost
1237 + ", estTotal="
1238 + best.estTotal
1239 + ", nextbest="
1240 + nextbest
1241 + "\n\topenQueue.size="
1242 + openQueue.size);
1243 if (best.reached(dest))
1244 return best;
1245 //
1246 if (VERBOSE > 1)
1247 stat.expanded++;
1248 if (DEBUG)
1249 if (best.rown == dest.rown)
1250 msg.err(
1251 NAME
1252 + ".aStar(): best.rown==dest.rown, best="
1253 + best
1254 + ", dest="
1255 + dest);
1256 if (dest.rown > best.rown)
1257 next = expandDown(best, next, nextbest, dest, oldcost, chain);
1258 else
1259 next = expandUp(best, next, nextbest, dest, oldcost, chain);
1260 //
1261 if (DEBUG)
1262 msg.println("# next=" + next + ((next == null) ? "" : ", estTotal=" + next.estTotal));
1263 }
1264 return null; //no open cells and no solution
1265 }
1266
1267 /** Expand from best to its children below.
1268 *
1269 * @return The next best Cell is its totalCost<=nextbest.
1270 */
1271 private Cell expandDown(Cell best, Cell next, int nextbest, Cell dest, int oldcost, VirtualEdge[] chain) {
1272 // Never expand beyond the destination rank.
1273 if (best.rown >= dest.rown)
1274 return null;
1275 //
1276 VirtualEdge e = chain[best.rown];
1277 int crosscost = 0;
1278 Cell beforeParent = best.leftVertex;
1279 Cell beforeChild = null;
1280 Cell[] children = theMap[best.rown + 1];
1281 Cell child;
1282 for (int c = 0; c < children.length; ++c) {
1283 // All SPACE cells below best and the dest. are children.
1284 child = children[c];
1285 // Erased VERTEX cells may now be SPACE but still have
1286 // cell.vertex!=null and used for cross cost
1287 // calcuation.
1288 if (child.type >= Cell.ERASED)
1289 beforeChild = child;
1290 if (child.type == Cell.SPACE || child.type == Cell.ERASED) {
1291 crosscost = crossAfter(best, child, beforeParent, beforeChild, e);
1292 if (DEBUG)
1293 msg.println(
1294 NAME
1295 + ".expandDown(): crosscost="
1296 + crosscost
1297 + ", beforeChild="
1298 + beforeChild);
1299 if (best.curCost + crosscost < oldcost
1300 && child.accept(best, dest, e, crosscost, oldcost, openQueue)) {
1301 next = enqueue(child, nextbest, next);
1302 if (next != null)
1303 nextbest = next.estTotal;
1304 child.setLeftVertex(beforeChild);
1305 }
1306 }
1307 }
1308 return next;
1309 }
1310
1311 /** Expand from best to its children above.
1312 *
1313 * @return The next best Cell is its totalCost<=nextbest.
1314 */
1315 private Cell expandUp(Cell best, Cell next, int nextbest, Cell dest, int oldcost, VirtualEdge[] chain) {
1316 // Never expand beyond the destination rank.
1317 if (best.rown <= dest.rown)
1318 return null;
1319 //
1320 int crosscost = 0;
1321 Cell beforeChild = best.leftVertex;
1322 Cell beforeParent = null;
1323 Cell[] parents = theMap[best.rown - 1];
1324 Cell parent;
1325 VirtualEdge e = chain[best.rown - 1];
1326 for (int c = 0; c < parents.length; ++c) {
1327 // All SPACE cells above best are reachable.
1328 parent = parents[c];
1329 // Erased VERTEX cells may now be SPACE but still have
1330 // cell.vertex!=null and used for cross cost
1331 // calcuation.
1332 if (parent.type >= Cell.ERASED)
1333 beforeParent = parent;
1334 if (parent.type == Cell.SPACE || parent.type == Cell.ERASED) {
1335 crosscost = crossAfter(parent, best, beforeParent, beforeChild, e);
1336 if (DEBUG)
1337 msg.println(
1338 NAME
1339 + ".expandUp(): crosscost="
1340 + crosscost
1341 + ", beforeParent="
1342 + beforeParent
1343 + ", parent="
1344 + parent);
1345 if (best.curCost + crosscost < oldcost
1346 && parent.accept(best, dest, e, crosscost, oldcost, openQueue)) {
1347 next = enqueue(parent, nextbest, next);
1348 if (next != null)
1349 nextbest = next.estTotal;
1350 parent.setLeftVertex(beforeParent);
1351 }
1352 }
1353 }
1354 return next;
1355 }
1356
1357 /** Enqueue cell if cell is not the next candidate for expansion.
1358 * @return Next candidate for expansion, or null.
1359 */
1360 private Cell enqueue(Cell cell, int nextbest, Cell next) {
1361 if (cell.estTotal <= nextbest) {
1362 if (next != null) {
1363 openQueue.enqueue(next);
1364 if (VERBOSE > 1)
1365 stat.enqueue++;
1366 }
1367 next = cell;
1368 } else {
1369 openQueue.enqueue(cell);
1370 if (VERBOSE > 1)
1371 stat.enqueue++;
1372 }
1373 return next;
1374 }
1375
1376 /** @return Path end at 'cell'. Return path always in order from
1377 * low to high rank.
1378 */
1379 private void getPath(Cell end, boolean isdown, CellList ret) {
1380 if (isdown) {
1381 if (end.parent != null)
1382 getPath(end.parent, isdown, ret);
1383 ret.add(end);
1384 } else {
1385 ret.add(end);
1386 if (end.parent != null)
1387 getPath(end.parent, isdown, ret);
1388 }
1389 }
1390
1391 // Obsolete ////////////////////////////////////////////////////////////
1392 //
1393
1394 /** Pre-calculate static costs for each possible path segments.
1395 * Vertex/spacing to vertex/spacing.
1396 *
1397 * Crossing cost are calculated in two passes, from left to right
1398 * and then right to left as follow.
1399 *
1400 * NOTE: Since we have to recalculate the rank cost after
1401 * eraseTrail() each time, there is no need to pre-calculate any
1402 * rank cost.
1403 */
1404 private void staticCost() {
1405 int total = 0;
1406 for (int r = graph.minRank, rn = 0; r < graph.maxRank; ++r, ++rn) {
1407 total += rankCost(r, null);
1408 }
1409 if (DEBUG)
1410 msg.println(NAME + ".staticCost(): total=" + total);
1411 }
1412
1413 private void updateRankCost(VirtualEdge chainhead, boolean isdown) {
1414 // Update rank costs.