Source code: com/port80/graph/dot/impl/MinCross.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.Arrays;
8
9 import com.port80.util.Debug;
10 import com.port80.util.PseudoRandom;
11 import com.port80.util.StopWatch;
12 import com.port80.util.msg;
13 import com.port80.util.sprint;
14
15 /** Find an ordering with minimum edge crossing for a ranked graph with
16 * clusters are expanded.
17 *
18 * . The rank structure is global (not allocated per cluster)
19 * because mincross may compare nodes in different clusters.
20 *
21 */
22
23 public class MinCross {
24
25 // Static fields ///////////////////////////////////////////////////////
26 //
27
28 private static final String NAME = "MinCross";
29 //
30 private static final boolean DEBUG = false;
31 private static final boolean CHECK = true;
32 private static boolean VERBOSE = Debug.isVerbose();
33 //
34 private static final int MCSCALE = 8;
35 private static final double convergence = 0.995;
36 private static MinCross instance = null;
37
38 // Instance fields /////////////////////////////////////////////////////
39 //
40 int niter = 0;
41 double fDISTCOST;
42
43 // Static methods //////////////////////////////////////////////////////
44 //
45
46 public static MinCross getInstance() {
47 if (instance == null)
48 instance = new MinCross();
49 return instance;
50 }
51
52 public static int dot(VirtualGraph g, int startpass, int endpass, int seed) {
53 return getInstance().minCross(g, startpass, endpass, seed);
54 }
55
56 // Instance methods ////////////////////////////////////////////////////
57 //
58
59 /** Run minCross algorithm on given graph 'g'.
60 *
61 * . Even passes use out edges from minRank to maxRank.
62 * . Odd passes use in edges from maxRank to minRank.
63 * . Run MaxIter iterations for each pass.
64 *
65 * @return The result min. cost.
66 */
67 private int minCross(VirtualGraph g, int startpass, int endpass, int seed) {
68 int maxiter, trying;
69 int cost, bestcost, lastbest;
70 StopWatch timer = null;
71
72 fDISTCOST = g.fDISTCOST;
73
74 if (VERBOSE)
75 timer = new StopWatch().start();
76 //
77 if (startpass > 1) {
78 for (int i = g.minRank; i <= g.maxRank; ++i) {
79 g.ranks[i].valid = false;
80 }
81 cost = bestcost = g.totalCost();
82 if (VERBOSE)
83 msg.println(NAME + ".minCross(): startpass=" + startpass + ", bestcost=" + bestcost);
84 g.saveOrder();
85 } else {
86 cost = bestcost = Integer.MAX_VALUE;
87 }
88 if (startpass < 6) {
89 for (int pass = startpass; pass <= endpass && cost > 0; ++pass) {
90 lastbest = bestcost;
91 maxiter = g.maxIter;
92 if (pass <= 1) {
93 //maxiter=Math.min(4,g.maxIter);
94 int n = 4;
95 if (seed < 0)
96 n += (-seed) % 13;
97 maxiter = Math.min(n, g.maxIter);
98 if (DEBUG)
99 msg.println(NAME + ".minCross(): maxiter=" + maxiter);
100 g.buildRanks(pass);
101 if (g.totalCost() > 0)
102 transpose(g, false);
103 if (pass == 0)
104 g.breakFlatCycles();
105 g.initFlatOrder();
106 if (seed > 0)
107 permutate(g, seed);
108 cost = g.totalCost();
109 if (cost <= bestcost) {
110 bestcost = cost;
111 g.saveOrder();
112 }
113 } else if (cost > bestcost) {
114 if (DEBUG)
115 msg.println(
116 NAME
117 + ".minCross(): restore"
118 + ": pass="
119 + pass
120 + ": cost="
121 + cost
122 + ": best="
123 + bestcost);
124 g.restoreOrder();
125 if (true)
126 for (int i = g.minRank; i <= g.maxRank; ++i)
127 g.ranks[i].valid = false;
128 cost = bestcost;
129 bestcost = g.totalCost();
130 }
131 trying = 0;
132 for (int iter = 0; iter < maxiter && cost > 0; ++iter, ++niter) {
133 cost = minCrossStep(g, iter);
134 if (cost < bestcost) {
135 if (cost < convergence * bestcost)
136 trying = 0;
137 bestcost = cost;
138 g.saveOrder();
139 }
140 if (VERBOSE)
141 msg.println(
142 NAME
143 + ".minCross()"
144 + ": pass="
145 + pass
146 + ": iter="
147 + iter
148 + ": trying="
149 + trying
150 + ": cost="
151 + cost
152 + ": best="
153 + bestcost);
154 if (false) {
155 msg.println("### minCross step result:");
156 g.debugPrintRanks();
157 }
158 if (trying++ > g.minQuit)
159 break;
160 }
161 if (VERBOSE)
162 msg.println(
163 NAME
164 + ".minCross()"
165 + ": seed="
166 + seed
167 + ": pass="
168 + pass
169 + ": cost="
170 + cost
171 + ": best="
172 + bestcost);
173 if (pass >= 3 && bestcost == lastbest)
174 break;
175 }
176 if (cost > bestcost)
177 g.restoreOrder();
178 if (bestcost > 0) {
179 transpose(g, false);
180 for (int i = g.minRank; i <= g.maxRank; ++i)
181 g.ranks[i].valid = false;
182 bestcost = g.totalCost();
183 }
184 } else {
185 transpose(g, false);
186 if (true)
187 for (int i = g.minRank; i <= g.maxRank; ++i)
188 g.ranks[i].valid = false;
189 bestcost = g.totalCost();
190 }
191 if (VERBOSE) {
192 timer.stop();
193 msg.println(
194 NAME
195 + ".minCross()"
196 + ": seed="
197 + seed
198 + ": startpass="
199 + startpass
200 + ": endpass="
201 + endpass
202 + ": iterations="
203 + niter
204 + sprint
205 .f(": elapsed=%.2f: iter/sec=%.2f")
206 .a(timer.elapsed())
207 .a(niter / timer.elapsed())
208 .end()
209 + ": best="
210 + bestcost);
211 }
212 if (CHECK)
213 g.checkOrder(NAME + ".minCross()");
214 return bestcost;
215 }
216
217 ////////////////////////////////////////////////////////////////////////
218
219 private int minCrossStep(VirtualGraph g, int iter) {
220 int dir, first, last, other;
221 boolean hasnoswap;
222 boolean reverse = (iter % 8) < 2;
223 int nsort = 0;
224 int nvts = 0;
225
226 if (iter % 2 == 0) {
227 // Down iter.
228 dir = 1;
229 //DEBUG: first = g.minRank+1;
230 first = g.minRank + 1;
231 //if(g.minRank>Root.minrank) first--;
232 last = g.maxRank;
233 } else {
234 // Up iter.
235 dir = -1;
236 //DEBUG: first = g.maxRank-1;
237 first = g.maxRank - 1;
238 last = g.minRank;
239 //if(g.maxRank<Root.maxrank) first++;
240 }
241
242 //DEBUG: for (int r = first; r != last + dir; r += dir) {
243 for (int r = first; r != last; r += dir) {
244 other = r - dir;
245 hasnoswap = medians(g, r, other);
246 if (reorder(g, r, reverse, hasnoswap)) {
247 nsort++;
248 nvts += g.ranks[r].nVts;
249 }
250 }
251 if (DEBUG)
252 msg.println(
253 NAME
254 + ".minCrossStop(): nsort="
255 + nsort
256 + "/"
257 + (g.maxRank - g.minRank)
258 + " ranks, "
259 + nvts
260 + "/"
261 + g.getVertices().length
262 + " vertices.");
263 transpose(g, !reverse);
264 return g.totalCost();
265 }
266
267 /**
268 * @enter r1==r0-1 for down pass.
269 * r1==r0+1 for up pass.
270 *
271 * @return true if there are flat edges or fixed vertices
272 * (median==-1) in the rank.
273 */
274 private boolean medians(VirtualGraph g, int r0, int r1) {
275 VirtualVertex v;
276 VirtualEdge e;
277 int[] medians = new int[10];
278 int max;
279 boolean hasnoswap = false; // has noswap.
280
281 VirtualGraph.Rank rank0 = g.ranks[r0];
282 for (int i = 0; i < rank0.nVts; ++i) {
283 v = rank0.vts[i];
284 int j = 0;
285 if (r1 > r0) {
286 // Down pass.
287 max = v.outs.length;
288 if (max > medians.length)
289 medians = new int[max];
290 for (; j < max; ++j) {
291 e = v.outs[j];
292 medians[j] =
293 (e.head.order << MCSCALE)
294 + ((e.headPort != null) ? e.headPort.order : 0);
295 }
296 } else {
297 // Up pass.
298 max = v.ins.length;
299 if (max > medians.length)
300 medians = new int[max];
301 for (; j < max; ++j) {
302 e = v.ins[j];
303 medians[j] =
304 (e.tail.order << MCSCALE)
305 + ((e.tailPort != null) ? e.tailPort.order : 0);
306 }
307 }
308 switch (j) {
309 case 0 :
310 v.median = -1;
311 hasnoswap = true;
312 break;
313 case 1 :
314 v.median = medians[0];
315 break;
316 case 2 :
317 v.median = (medians[0] + medians[1]) / 2;
318 break;
319 default :
320 Arrays.sort(medians, 0, j);
321 if (j % 2 == 1)
322 v.median = medians[j / 2];
323 else {
324 //j is even, weighted median.
325 //
326 //FIXME: Not sure this make much sense. Use the
327 //middle or select one of the two may be better.
328 int lm, rm; // left and right middle.
329 rm = j / 2;
330 lm = rm - 1;
331 int lspan, rspan;
332 rspan = medians[j - 1] - medians[rm];
333 lspan = medians[lm] - medians[0];
334 v.median =
335 (medians[lm] * rspan + medians[rm] * lspan) / (lspan + rspan);
336 //v.median=(medians[lm]+medians[rm])/2;
337 }
338 }
339 }
340 for (int i = 0; i < rank0.nVts; ++i) {
341 v = rank0.vts[i];
342 if (v.hasFlat)
343 hasnoswap = true;
344 if (!v.hasIO && v.hasFlat) {
345 flatMedian(v);
346 }
347 }
348 return hasnoswap;
349 }
350
351 /** When given vertex 'v' do not have vertically connections, try
352 * determine its median value from one of its peer 'w' that do.
353 * Such that 'v'->'w' or 'w'->'v' from left to right.
354 *
355 * NOTE:
356 *
357 * . The original code tried to find the rightmost tail and put
358 * 'v' on right of it or the leftmost head and put 'v' on left
359 * of it. Flat connected nodes are not swapped, the flat
360 * order are always preserved. Since we are iterating from left
361 * to right, there is no problem with the using the median
362 * value from the rightmost tail. But there is no guarantee
363 * that the leftmost head have valid median value.
364 *
365 * @enter (v.ins.length==0 && v.outs.length==0)
366 * @return true if v has flat edges.
367 */
368 private boolean flatMedian(VirtualVertex v) {
369 VirtualEdge e;
370 VirtualEdge[] a;
371 VirtualVertex w;
372
373 if (v.flatIns.length > 0) {
374 a = v.flatIns;
375 w = a[0].tail;
376 for (int i = 1; i < a.length; ++i) {
377 e = a[i];
378 if (e.tail.order > w.order)
379 w = e.tail;
380 }
381 v.median = w.median + 1;
382 return true;
383 } else if (v.flatOuts.length > 0) {
384 a = v.flatOuts;
385 w = a[0].head;
386 for (int i = 1; i < a.length; ++i) {
387 e = a[i];
388 if (e.head.order < w.order && (e.head.outs.length != 0 || e.head.ins.length != 0))
389 w = e.head;
390 }
391 v.median = w.median - 1;
392 return true;
393 }
394 return false;
395 }
396
397 /** A special (bubble) sort function on the given rank that
398 * reorder vertices in ascending median value but preserve order
399 * of flat connected (keepOrder) vertices.
400 *
401 * NOTE:
402 * . Since for now, the virtual graph only have the rank leaders
403 * from the clusters, we don't need the sawclust stuff from the
404 * original code that filter out vertices after the leader.
405 */
406 private boolean reorder(VirtualGraph g, int r, boolean reverse, boolean hasnoswap) {
407 boolean muststay;
408 int left, right;
409 VirtualVertex v;
410 //
411 VirtualGraph.Rank rank = g.ranks[r];
412 VirtualVertex[] vts = rank.vts;
413 int end = rank.nVts;
414 boolean changed = false;
415 int nswap = 0;
416
417 if (false) {
418 if (!hasnoswap) {
419 Arrays.sort(rank.vts, 0, rank.nVts, new VirtualVertex.MedianComparator());
420 for (int i = 0; i < rank.nVts; ++i)
421 rank.vts[i].order = i;
422 rank.valid = false;
423 if (r > 0)
424 g.ranks[r - 1].valid = false;
425 if (DEBUG)
426 msg.println(
427 NAME
428 + ".reorder(): niter="
429 + niter
430 + ", r="
431 + r
432 + ", nVts="
433 + rank.nVts);
434 return true;
435 }
436 }
437
438 for (int i = rank.nVts - 1; i >= 0; --i) {
439 left = 0;
440 while (left < end) {
441 /* find leftmost node that can be compared */
442 while ((left < end) && (vts[left].median < 0))
443 left++;
444 if (left >= end)
445 break;
446 /* find the node that can be compared */
447 muststay = false;
448 for (right = left + 1; right < end; right++) {
449 if (rank.keepOrder(vts[left], vts[right])) {
450 muststay = true;
451 break;
452 }
453 //TELME: why not compare with left.median ?
454 if (vts[right].median >= 0)
455 break;
456 }
457 if (right >= end)
458 break;
459 if (!muststay) {
460 int lm = vts[left].median;
461 int rm = vts[right].median;
462 if ((lm > rm) || ((lm == rm) && (reverse))) {
463 changed = true;
464 nswap++;
465 if (false)
466 msg.println(
467 NAME
468 + ".reorder(): i="
469 + i
470 + ": left="
471 + left
472 + ", right="
473 + right);
474 // Exchange left and right.
475 lm = vts[left].order;
476 vts[left].order = vts[right].order;
477 vts[right].order = lm;
478 lm = vts[left].x;
479 vts[left].x = vts[right].x;
480 vts[right].x = lm;
481 v = vts[left];
482 vts[left] = vts[right];
483 vts[right] = v;
484 }
485 }
486 left = right;
487 }
488 }
489 if (DEBUG) {
490 g.checkOrder(NAME + ".reorder()");
491 msg.println(
492 NAME
493 + ".reorder(): niter="
494 + niter
495 + ", r="
496 + r
497 + ", nVts="
498 + rank.nVts
499 + ", swaps="
500 + nswap);
501 if (DEBUG) {
502 StringBuffer buf = new StringBuffer("# medians:\n");
503 for (int k = 0; k < rank.nVts;) {
504 buf.append("\t" + k + "=" + (vts[k].median >> 8));
505 ++k;
506 if (k % 10 == 0)
507 buf.append("\n");
508 }
509 msg.println(buf.toString());
510 }
511 }
512
513 if (changed) {
514 rank.valid = false;
515 if (r > 0)
516 g.ranks[r - 1].valid = false;
517 }
518 return false;
519 }
520
521 ////////////////////////////////////////////////////////////////////////
522
523 public void transpose(VirtualGraph g, boolean reverse) {
524 if (DEBUG)
525 msg.println(NAME + ".transpose(): " + g.totalCost());
526 int delta;
527 for (int r = g.minRank; r <= g.maxRank; r++)
528 g.ranks[r].candidate = true;
529 for (int step = 1; step <= 1; ++step) {
530 do {
531 delta = 0;
532 /*
533 // don't run both the upward and downward passes- they
534 // cancel. i tried making it depend on whether an odd
535 // or even pass, but that didn't help.
536 for(r=maxRank; r>=minRank; r--)
537 if(rank[r].candidate) delta+=transpose_step(r,reverse);
538 */
539 for (int r = g.minRank; r <= g.maxRank; r++) {
540 if (g.ranks[r].candidate)
541 delta += transposeStep(g, r, step, reverse);
542 }
543 if (DEBUG)
544 msg.println(
545 "###\n### "
546 + NAME
547 + ".tranpose(): delta="
548 + delta
549 + ", crosscost="
550 + g.totalCost()
551 + "\n###");
552 //} while (delta > ncross(g)*(1.0 - convergence));*/
553 } while (delta >= 1);
554 }
555 if (false)
556 g.sanityCheck();
557 }
558
559 private int transposeStep(VirtualGraph g, int r, int step, boolean reverse) {
560 int c1, c2, order;
561 VirtualVertex v, w;
562 int ret = 0;
563 VirtualGraph.Rank[] ranks = g.ranks;
564 VirtualGraph.Rank rank = ranks[r];
565 rank.candidate = false;
566 for (int i = 0; i < rank.nVts - step; i++) {
567 v = rank.vts[i];
568 w = rank.vts[i + step];
569 if (rank.keepOrder(v, w))
570 continue;
571 c1 = 0;
572 c2 = 0;
573 if (r > g.minRank) {
574 c1 += inCost(v, w, false, reverse);
575 c2 += inCost(w, v, true, reverse);
576 }
577 if (r < g.maxRank && ranks[r + 1].nVts > 0) {
578 c1 += outCost(v, w, false, reverse);
579 c2 += outCost(w, v, true, reverse);
580 }
581 if ((c1 > c2) || ((c1 == c2) && reverse)) { // Exchange v,w
582 ret += (c1 - c2);
583 rank.vts[i] = w;
584 rank.vts[i + step] = v;
585 order = v.x;
586 v.x = w.x;
587 w.x = order;
588 order = v.order;
589 v.order = w.order;
590 w.order = order;
591 //
592 rank.valid = false;
593 rank.candidate = true;
594 if (r > g.minRank) {
595 ranks[r - 1].valid = false;
596 ranks[r - 1].candidate = true;
597 }
598 if (r < g.maxRank) {
599 ranks[r + 1].valid = false;
600 ranks[r + 1].candidate = true;
601 }
602 if (DEBUG)
603 msg.println(
604 NAME
605 + ".transposeStep(): swap: reverse="
606 + reverse
607 + ", r="
608 + r
609 + ", c1="
610 + c1
611 + ", c2="
612 + c2
613 + ", delta="
614 + (c1 - c2)
615 + ", ret="
616 + ret
617 + "\n\tv="
618 + v.getName()
619 + "\n\tw="
620 + w.getName());
621 }
622 }
623 return ret;
624 }
625
626 ////////////////////////////////////////////////////////////////////////
627
628 /**
629 * For each input to v crossed input to w, cost+=product of
630 * xpenalty of the crossed edges.
631 * For each input to a vertex, cost+=Math.abs(tail.order-v.order).
632 *
633 * @enter v.order<w.order
634 */
635 private int inCost(VirtualVertex v, VirtualVertex w, boolean swap, boolean reverse) {
636 VirtualEdge e1, e2;
637 int c2, order2, cross;
638 int cost = 0;
639 for (int i2 = 0; i2 < w.ins.length; ++i2) {
640 e2 = w.ins[i2];
641 if (!reverse && e2.tail.degree == 1)
642 continue;
643 c2 = e2.xPenalty;
644 order2 = e2.tail.order;
645 for (int i1 = 0; i1 < v.ins.length; ++i1) {
646 e1 = v.ins[i1];
647 if (!reverse && e1.tail.degree == 1)
648 continue;
649 cross = e1.tail.order - order2;
650 if ((cross > 0)
651 || ((cross == 0) && (e1.tailPort != null) && (e1.tailPort.dx > e2.tailPort.dx)))
652 cost += e1.xPenalty * c2;
653 }
654 }
655 // Second pass.
656 // if (v.x != 0) {
657 // if (swap) {
658 // cost += tailDistCost(v, w.x);
659 // cost += tailDistCost(w, v.x);
660 // } else {
661 // cost += tailDistCost(v, v.x);
662 // cost += tailDistCost(w, w.x);
663 // }
664 // }
665 return cost;
666 }
667
668 /** Crossing cost between v and w if v is on left of w. */
669 private int outCost(VirtualVertex v, VirtualVertex w, boolean swap, boolean reverse) {
670 VirtualEdge e1, e2;
671 int c2, order2, cross;
672 int cost = 0;
673 for (int i2 = 0; i2 < w.outs.length; ++i2) {
674 e2 = w.outs[i2];
675 if (!reverse && e2.head.degree == 1)
676 continue;
677 c2 = e2.xPenalty;
678 order2 = e2.head.order;
679 for (int i1 = 0; i1 < v.outs.length; ++i1) {
680 e1 = v.outs[i1];
681 if (!reverse && e1.head.degree == 1)
682 continue;
683 cross = e1.head.order - order2;
684 if ((cross > 0)
685 || ((cross == 0) && (e1.headPort != null) && (e1.headPort.dx > e2.headPort.dx)))
686 cost += e1.xPenalty * c2;
687 }
688 }
689 // if (v.x != 0) {
690 // if (swap) {
691 // cost += headDistCost(v, w.x);
692 // cost += headDistCost(w, v.x);
693 // } else {
694 // cost += headDistCost(v, v.x);
695 // cost += headDistCost(w, w.x);
696 // }
697 // }
698 return cost;
699 }
700
701 /**
702 * Cost of route distance approximated by absolute order distance
703 * of tails to 'v'.
704 */
705 // private int tailDistCost(VirtualVertex v, int vx) {
706 // int cost = 0;
707 // int x;
708 // VirtualEdge e;
709 // for (int i = 0; i < v.ins.length; ++i) {
710 // e = v.ins[i];
711 // while (e.tail.isVirtual() && e.prev != null)
712 // e = e.prev;
713 // x = e.tail.x;
714 // cost += (x - vx) * (x - vx) * e.weight;
715 // // if (x > vx)
716 // // cost += (x - vx) * e.weight;
717 // // else
718 // // cost += (vx - x) * e.weight;
719 // }
720 // return (int) (cost * fDISTCOST);
721 // }
722
723 // private int headDistCost(VirtualVertex v, int vx) {
724 // int cost = 0;
725 // int x;
726 // VirtualEdge e;
727 // for (int i = 0; i < v.outs.length; ++i) {
728 // e = v.outs[i];
729 // x = e.head.x;
730 // while (e.head.isVirtual() && e.next != null)
731 // e = e.next;
732 // cost += (x - vx) * (x - vx) * e.weight;
733 // // if (x > vx)
734 // // cost += (x - vx) * e.weight;
735 // // else
736 // // cost += (vx - x) * e.weight;
737 // }
738 // return (int) (cost * fDISTCOST);
739 // }
740
741 ////////////////////////////////////////////////////////////////////////
742
743 private void permutate(VirtualGraph g, int seed) {
744 VirtualGraph.Rank rank;
745 PseudoRandom rand = new PseudoRandom(PseudoRandom.getTableID(seed));
746 for (int r = g.minRank; r <= g.maxRank; ++r) {
747 rank = g.ranks[r];
748 rand.permutate(rank.vts);
749 for (int i = 0; i < rank.nVts; ++i)
750 rank.vts[i].order = i;
751 }
752 }
753
754 ////////////////////////////////////////////////////////////////////////
755
756 }