Source code: com/port80/graph/dot/impl/NetworkSimplex.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.io.*;
8 import java.util.*;
9 import com.port80.util.*;
10 import com.port80.graph.*;
11 import com.port80.graph.impl.ToDotVisitor;
12 import com.port80.graph.dot.parser.*;
13
14 /** Network Simplex Algorithm for ranking an acyclic directed graph.
15 *
16 * . Clusters and same/min/max ranked subgraphs should have been
17 * collapsed into a single vertex for ranking.
18 */
19 public class NetworkSimplex {
20
21 // Static fields ///////////////////////////////////////////////////////
22 //
23
24 private static final String NAME = "NetworkSimplex";
25 private static final String USAGE = "\n" + "usage: java " + NAME + " <file> [ <file>...]\n" + "\n";
26
27 private static final boolean DEBUG = false;
28 private static boolean VERBOSE = Debug.isVerbose();
29 private static final int SEARCHSIZE = 30;
30 private static NetworkSimplex instance = null;
31
32 // Instance fields /////////////////////////////////////////////////////
33 //
34
35 private DotVertex[] grVertices; /** All input graph vertices. */
36 private DotVertex[] treeVts;
37 private DotEdge[] treeEdges;
38 private int nTreeVts;
39 private int nTreeEdges;
40 private int searchSize;
41
42 private List fRoots = new ArrayList();
43 private DotVertex cutChild;
44 private DotEdge bestEnter;
45 private int minSlack;
46 private int searchIndex = 0;
47
48 // Static methods //////////////////////////////////////////////////////
49 //
50
51 public static NetworkSimplex getInstance() {
52 return new NetworkSimplex();
53 }
54
55 /** @param tbmode true=vertical ranking, false=x-position ranking.
56 */
57 public static int dotRank(DotGraph g, double nslimit, boolean tbmode) {
58 return new NetworkSimplex().rank(g, nslimit, tbmode);
59 }
60
61 // Instance methods ////////////////////////////////////////////////////
62 //
63
64 /** @param tbmode true=vertical ranking, false=x-position ranking.
65 */
66 public int rank(DotGraph g, double nslimit, boolean tbmode) {
67 StopWatch timer1 = null;
68 if (VERBOSE)
69 timer1 = new StopWatch().start();
70
71 DotEdge leave, enter;
72 int iter = 0;
73 int cost = Integer.MAX_VALUE;
74 grVertices = g.getVertices();
75 if (grVertices.length > 0) {
76 int maxiter = (int) (grVertices.length * nslimit);
77 treeEdges = new DotEdge[grVertices.length];
78 treeVts = new DotVertex[grVertices.length];
79 nTreeVts = 0;
80 nTreeEdges = 0;
81 //if((searchSize=g.getAttrInt("searchsize"))<0)
82 searchSize = SEARCHSIZE;
83
84 initRank();
85 feasibleTree();
86 while ((leave = leaveEdge()) != null) {
87 enter = enterEdge(leave);
88 update(leave, enter);
89 iter++;
90 if (VERBOSE) {
91 if (iter % 1000 == 1)
92 msg.print(NAME + ": ");
93 if (iter % 10 == 0) {
94 msg.print(".");
95 if (iter % 1000 == 0)
96 msg.println("");
97 }
98 if (iter >= maxiter)
99 break;
100 }
101 }
102 if (VERBOSE)
103 cost = sanityChecks();
104 else
105 cost = checkRanks();
106 if (tbmode)
107 tbBalance();
108 else
109 lrBalance();
110 }
111 if (VERBOSE) {
112 msg.println(
113 sprint
114 .f("\n * %s: %d vertices %d edges %d iter: elapsed=%.2f sec\n")
115 .a(NAME)
116 .a(nTreeVts)
117 .a(nTreeEdges)
118 .a(iter)
119 .a(timer1.stop().elapsed())
120 .end());
121 }
122 if (!DEBUG)
123 cleanup();
124 return cost;
125 }
126
127 /** Assign ranks by breadth first search and init vertices.
128 */
129 private void initRank() {
130 int ctr = 0;
131 DotVertex v;
132 DotEdge e;
133 //
134 List queue = new LinkedList();
135 Set notvisited = new HashSet();
136 // Start with nodes with no fanin (those at top). Since there
137 // are no cycles, there should be one.
138 for (int i = 0; i < grVertices.length; ++i) {
139 v = grVertices[i];
140 v.rank = 0;
141 v.treeIos = new DotEdge[v.inSize() + v.outSize()];
142 v.counter = v.inSize();
143 if (!notvisited.add(v))
144 msg.err(NAME + ".initRank(): Duplicated DotVertex: v=" + v.getName());
145 ;
146 if (v.counter == 0) {
147 fRoots.add(v);
148 queue.add(v);
149 }
150 }
151 if (DEBUG)
152 msg.println(NAME + ".initRank(): " + fRoots.size() + " roots");
153 int rank;
154 while (queue.size() != 0) {
155 v = (DotVertex) queue.remove(0);
156 notvisited.remove(v);
157 ctr++;
158 // Derive rank from parent vertex. rank=max(parents.rank)+1
159 for (int i = 0; i < v.inSize(); ++i) {
160 e = v.ins[i];
161 rank = e.tail.rank + e.minLength;
162 if (rank > v.rank)
163 v.rank = rank;
164 }
165 // Queue child that have all parent ranks determined.
166 for (int i = 0; i < v.outSize(); ++i) {
167 e = v.outs[i];
168 if (e.head.counter == 1)
169 queue.add(e.head);
170 if (e.head.counter > 0)
171 e.head.counter -= 1;
172 }
173 }
174 if (ctr != grVertices.length || queue.size() != 0) {
175 msg.println(NAME + ".initRank(): notvisied=");
176 for (Iterator it = notvisited.iterator(); it.hasNext();) {
177 msg.println("\t" + it.next().toString());
178 }
179 msg.err(
180 NAME
181 + ".initRank(): trouble in initRank:"
182 + ": ctr="
183 + ctr
184 + ": vertices.length="
185 + grVertices.length
186 + ": queue.size="
187 + queue.size()
188 + "\n\t: vertices="
189 + grVertices
190 + "\n\t: queue="
191 + queue);
192 }
193 }
194
195 ////////////////////////////////////////////////////////////////////////
196
197 private void feasibleTree() {
198 int size = grVertices.length;
199 if (size <= 1)
200 return;
201
202 DotVertex v;
203 DotEdge enter, e;
204 int enterslack;
205 int slack;
206
207 while (tightTree() < size) {
208 enter = null;
209 enterslack = Integer.MAX_VALUE;
210 for (int i = 0; i < size; ++i) {
211 v = grVertices[i];
212 for (int nout = 0; nout < v.outSize(); ++nout) {
213 e = v.outs[nout];
214 // Find non-tree edge with minimum slack that have one vertex on the tree.
215 if (e.treeIndex < 0
216 && incident(e) != null
217 && ((slack = e.slack()) < enterslack || enter == null)) {
218 enter = e;
219 enterslack = slack;
220 }
221 }
222 }
223 if (enter == null)
224 msg.err(
225 NAME
226 + ": no tight tree"
227 + ": nVertices="
228 + size
229 + ": nTreeVts="
230 + nTreeVts
231 + ": nTreeEdges="
232 + nTreeEdges
233 + ": treeVts="
234 + sprintTreeVts());
235 else if (DEBUG)
236 msg
237 .println(
238 NAME
239 + ".feasibleTree(): enter="
240 + enter
241 + ": nVertices="
242 + size
243 + ": nTreeVts="
244 + nTreeVts
245 + ": nTreeEdges="
246 + nTreeEdges
247 //+": treeVts="+sprintTreeVts()
248 //+"\ngraph="+graph.toString()
249 );
250
251 // Tighten enter.
252 if (enterslack != 0) {
253 if (incident(enter) == enter.head)
254 enterslack = -enterslack;
255 for (int i = 0; i < nTreeVts; ++i) {
256 treeVts[i].rank += enterslack;
257 }
258 }
259 }
260 initCutValues();
261 }
262
263 /** Find all edges with slack==0 into treeVts and treeEdges.
264 */
265 private int tightTree() {
266 for (int i = 0; i < nTreeVts; ++i)
267 treeVts[i].nTreeIos = 0;
268 for (int i = 0; i < nTreeEdges; ++i)
269 treeEdges[i].treeIndex = -1;
270 nTreeVts = 0;
271 nTreeEdges = 0;
272 //NOTE: Stop on nTreeEdges!=0 since we want connected edges
273 // only.
274 DotVertex v;
275 //for(int i=0; i<grVertices.length && nTreeEdges==0; ++i) {
276 //int index=i+95;
277 //if(index>=grVertices.length) index-=grVertices.length;
278 //v=grVertices[i];
279 //
280 // Since initRank() assign ranks from roots outward, the roots
281 // should always be in the most connected net.
282 for (int i = 0; i < fRoots.size() && nTreeEdges == 0; ++i) {
283 v = (DotVertex) fRoots.get(i);
284 treeSearch(v);
285 }
286 return nTreeVts;
287 }
288
289 /** Find tree edges started from v outward that have slack==0. */
290 private boolean treeSearch(DotVertex v) {
291 DotEdge e;
292
293 for (int i = 0; i < v.outSize(); ++i) {
294 e = v.outs[i];
295 if ((e.head.nTreeIos == 0) && (e.slack() == 0)) {
296 addTreeEdge(e);
297 if (nTreeEdges == grVertices.length - 1)
298 return true; // terminate.
299 if (treeSearch(e.head))
300 return true;
301 }
302 }
303 for (int i = 0; i < v.inSize(); ++i) {
304 e = v.ins[i];
305 if (e.tail.nTreeIos == 0 && e.slack() == 0) {
306 addTreeEdge(e);
307 if (nTreeEdges == grVertices.length - 1)
308 return true;
309 if (treeSearch(e.tail))
310 return true;
311 }
312 }
313 return false;
314 }
315
316 /** @return the vertex of an edge that is in the tree while the other vertex is not.
317 * null if both ends are in or not in the tree.
318 */
319 private DotVertex incident(DotEdge e) {
320 boolean tail = (e.tail.nTreeIos > 0);
321 boolean head = (e.head.nTreeIos > 0);
322 if (tail && !head)
323 return e.tail;
324 if (head && !tail)
325 return e.head;
326 return null;
327 }
328
329 private void addTreeEdge(DotEdge e) {
330 DotVertex v;
331
332 if (e.treeIndex >= 0) {
333 msg.err(NAME + ".addTreeEdge(): already a tree edge" + ": e=" + e);
334 return;
335 }
336 e.treeIndex = nTreeEdges;
337 treeEdges[nTreeEdges++] = e;
338 v = e.tail;
339 if (v.nTreeIos == 0)
340 treeVts[nTreeVts++] = v;
341 v.treeIos[v.nTreeIos++] = e;
342 v = e.head;
343 if (v.nTreeIos == 0)
344 treeVts[nTreeVts++] = v;
345 v.treeIos[v.nTreeIos++] = e;
346 }
347
348 ////////////////////////////////////////////////////////////////////////
349
350 private void initCutValues() {
351 if (DEBUG)
352 msg.println(NAME + ".initCutValues()");
353 // Since the tree is indirectional, any vertex on the tree can
354 // be treated as root. dot use graph->u.nlist.
355 //
356 DotVertex root = grVertices[0];
357 //DotVertex root=(DotVertex)roots.get(0);
358 root.initRange(null, 1);
359 dfCutValue(root, null);
360 }
361
362 /** Calculate cut value of edges in a tree from bottom up.
363 *
364 * @param parent Edge who cut value is to be determined.
365 */
366 private void dfCutValue(DotVertex v, DotEdge parent) {
367 if (DEBUG)
368 msg.println(NAME + ".dfCutValue(): parent=" + parent);
369 DotEdge e;
370 for (int i = 0; i < v.nTreeIos; ++i) {
371 e = v.treeIos[i];
372 if (e != parent)
373 dfCutValue(e.getOpposite(v), e);
374 }
375 if (parent != null)
376 parent.initCutValue();
377
378 }
379
380 ////////////////////////////////////////////////////////////////////////
381
382 /** Find edge with minimum cutValue starting from the last leave
383 * edge in round-robin.
384 */
385 private DotEdge leaveEdge() {
386 DotEdge e;
387 DotEdge rv = null;
388 int limit = 0;
389 for (int i = 0; i < nTreeEdges; ++i) {
390 e = treeEdges[searchIndex];
391 if (e.cutValue < 0) {
392 if (rv == null || rv.cutValue > e.cutValue)
393 rv = e;
394 if (++limit >= searchSize)
395 return rv;
396 }
397 if (++searchIndex >= nTreeEdges)
398 searchIndex = 0;
399 }
400 if (DEBUG)
401 msg.println(NAME + ".leaveEdge(): rv=" + rv);
402 return rv;
403 }
404
405 ////////////////////////////////////////////////////////////////////////
406
407 /** Find an non-tree edge with minimum slack going from head
408 * component to the tail component.
409 *
410 * @param v Vertex on the child side of the broken tree and head
411 * side of the broken edge.
412 *
413 * (ancestors)-- cut -->(v)--e--(v,decendents)
414 */
415 private void dfEnterOutEdge(DotVertex v) {
416 DotEdge e;
417
418 // Since v is on head side, look among out-edges of v and all
419 // vertices under v.
420 for (int i = 0; i < v.outSize(); ++i) { //TELLME: why not stop on Slack<=0
421 e = v.outs[i];
422 // non-tree edge going to tail component.
423 if (e.treeIndex < 0 && !e.head.isDecendent(cutChild)) {
424 if (e.slack() < minSlack) {
425 bestEnter = e;
426 minSlack = e.slack();
427 }
428 }
429 }
430 // If Slack==0, then we are done, since there would not be
431 // edge with slack<0.
432 for (int i = 0, max = v.nTreeIos; i < max && minSlack > 0; ++i) {
433 e = v.treeIos[i];
434 if (e != v.treeParent)
435 dfEnterOutEdge(e.getOpposite(v));
436 }
437 }
438
439 /** Find an non-tree edge with minimum slack going from head
440 * component to the tail component.
441 *
442 * @param v Vertex on the child side of the broken tree and tail
443 * side of the broken edge.
444 *
445 * (ancestors)<-- cut --(v)--e--(v,decendents)
446 */
447 private void dfEnterInEdge(DotVertex v) {
448 DotEdge e;
449
450 // v is on the child side, look among the in-edges of v and
451 // all child vertices of v.
452 for (int i = 0; i < v.inSize(); ++i) {
453 e = v.ins[i];
454 if (e.treeIndex < 0 && !e.tail.isDecendent(cutChild)) {
455 if (e.slack() < minSlack) {
456 bestEnter = e;
457 minSlack = e.slack();
458 }
459 }
460 }
461 for (int i = 0, max = v.nTreeIos; i < max && minSlack > 0; ++i) {
462 e = v.treeIos[i];
463 if (e != v.treeParent)
464 dfEnterInEdge(e.getOpposite(v));
465 }
466 }
467
468 /** Find an non-tree edge with minimum slack going from head
469 * component to the tail component.
470 */
471 private DotEdge enterEdge(DotEdge e) {
472 // Search in the child side.
473 minSlack = Integer.MAX_VALUE;
474 bestEnter = null;
475 if (e.tail.upper < e.head.upper) {
476 cutChild = e.tail;
477 dfEnterInEdge(cutChild);
478 } else {
479 cutChild = e.head;
480 dfEnterOutEdge(cutChild);
481 }
482 if (DEBUG)
483 msg.println(NAME + ".enterEdge(): bestEnter=" + bestEnter);
484 return bestEnter;
485 }
486
487 ////////////////////////////////////////////////////////////////////////
488
489 /** Swap non-tree edge 'leave' with tree edge 'enter'.
490 */
491 private void exchangeTreeEdges(DotEdge leave, DotEdge enter) {
492 enter.treeIndex = leave.treeIndex;
493 treeEdges[leave.treeIndex] = enter;
494 leave.treeIndex = -1;
495 // Delete 'leave' from treeIos of tail.
496 leave.tail.removeTreeEdge(leave);
497 leave.head.removeTreeEdge(leave);
498 // Insert enter to tree.
499 enter.tail.addTreeEdge(enter);
500 enter.head.addTreeEdge(enter);
501 }
502
503 /** Walk up from v to LCA(v,w), setting new cut values.
504 *
505 * @param v One vertex on the enter edge.
506 * @param w The other vertex on the enter edge.
507 * @param cutvalue cutValue of the leave edge.
508 * @param fromtail v is tail.
509 */
510 private DotVertex treeUpdate(DotVertex v, DotVertex w, int cutvalue, boolean fromtail) {
511 DotEdge e;
512 boolean dir; // v is tail of e.
513
514 while (!w.isDecendent(v)) {
515 e = v.treeParent;
516 if (v == e.tail)
517 dir = fromtail;
518 else
519 dir = !fromtail;
520 if (dir)
521 e.cutValue += cutvalue;
522 else
523 e.cutValue -= cutvalue;
524 if (e.tail.upper > e.head.upper)
525 v = e.tail;
526 else
527 v = e.head;
528 }
529 return v;
530 }
531
532 /** Compute new cut values, ranks, and exchange leave and enter.
533 *
534 * @param leave is the tree edge that is leave.
535 * @param enter is the nontree edge that is enter.
536 */
537 private void update(DotEdge leave, DotEdge enter) {
538 int delta = enter.slack();
539 /* "for (v = in nodes in tail side of leave) do v.rank -= delta;" */
540 if (delta > 0) {
541 //TELLME: why do we need s==1 cases.
542 /*
543 int s;
544 s=leave.tail.treeInList.size + leave.tail.treeOutList.size;
545 // tail is a leaf.
546 if(s==1) rerank(leave.tail,delta);
547 else {
548 s=leave.head.treeInList.size + leave.head.treeOutList.size;
549 // head is a leaf
550 if(s==1) rerank(leave.head,-delta);
551 else {
552 */
553 // tail is below head.
554 if (leave.tail.upper < leave.head.upper)
555 rerank(leave.tail, delta);
556 // head is below tail.
557 else
558 rerank(leave.head, -delta);
559 //}
560 //}
561 }
562
563 DotVertex lca; // Least common ancestor.
564 int cutvalue = leave.cutValue;
565 lca = treeUpdate(enter.tail, enter.head, cutvalue, true);
566 if (treeUpdate(enter.head, enter.tail, cutvalue, false) != lca)
567 msg.err(
568 NAME
569 + ".update(): lca for enter edge head and tail not match"
570 + ": enter="
571 + enter
572 + ": leave="
573 + leave);
574 enter.cutValue = -cutvalue;
575 leave.cutValue = 0;
576 exchangeTreeEdges(leave, enter);
577 lca.initRange(lca.treeParent, lca.lower);
578 if (DEBUG)
579 msg.println(NAME + ".update(): leave=" + leave + ", enter=" + enter + ", lca=" + lca);
580 }
581
582 /** Adjust ranks of subtree at v by -delta.
583 */
584 private void rerank(DotVertex v, int delta) {
585 DotEdge e;
586
587 if (false)
588 msg.println(NAME + ".rerank(): v=" + v.getName() + ", delta=" + delta);
589 v.rank -= delta;
590 for (int i = 0, max = v.nTreeIos; i < max; ++i) {
591 e = v.treeIos[i];
592 if (e != v.treeParent)
593 rerank(e.getOpposite(v), delta);
594 }
595 }
596
597 ////////////////////////////////////////////////////////////////////////
598
599 private void lrBalance() {
600 int delta;
601 DotVertex v;
602 DotEdge e, enter;
603
604 if (DEBUG)
605 msg.println(NAME + ".lrBalance()");
606 for (int i = 0; i < nTreeEdges; ++i) {
607 e = treeEdges[i];
608 if (e.cutValue == 0) {
609 enter = enterEdge(e);
610 if (enter == null)
611 continue;
612 delta = enter.slack();
613 if (delta <= 1)
614 continue;
615 if (e.tail.upper < e.head.upper)
616 rerank(e.tail, delta / 2);
617 else
618 rerank(e.head, -delta / 2);
619 }
620 }
621 for (int i = 0; i < grVertices.length; ++i) {
622 v = grVertices[i];
623 v.treeIos = null;
624 }
625
626 int min = Integer.MAX_VALUE;
627 int max = Integer.MIN_VALUE;
628 for (int i = 0; i < grVertices.length; ++i) {
629 v = grVertices[i];
630 //if(v.type==v.NORMAL) {
631 if (v.rank < min)
632 min = v.rank;
633 if (v.rank > max)
634 max = v.rank;
635 //}
636 }
637 if (min != 0) {
638 for (int i = 0; i < grVertices.length; ++i)
639 grVertices[i].rank -= min;
640 max -= min;
641 min = 0;
642 }
643 }
644
645 /**
646 * Move vertex that don't care (with same inweight and outweight) to less populated rank.
647 */
648 private void tbBalance() {
649 DotVertex v;
650 int min = Integer.MAX_VALUE;
651 int max = Integer.MIN_VALUE;
652
653 for (int i = 0; i < grVertices.length; ++i) {
654 v = grVertices[i];
655 //if(v.type==v.NORMAL) {
656 if (v.rank < min)
657 min = v.rank;
658 if (v.rank > max)
659 max = v.rank;
660 //}
661 }
662 if (min != 0) {
663 for (int i = 0; i < grVertices.length; ++i)
664 grVertices[i].rank -= min;
665 max -= min;
666 min = 0;
667 }
668
669 /* find nodes that are not tight and move to less populated ranks */
670
671 DotEdge e;
672 int low, high, choice;
673 int inweight, outweight;
674 int[] ranks = new int[max + 1]; // Java init. int[] to all 0.
675
676 for (int i = 0; i < grVertices.length; ++i) {
677 v = grVertices[i];
678 //if(v.type==NORMAL)
679 ranks[v.rank]++;
680 }
681 for (int vn = 0; vn < grVertices.length; ++vn) {
682 v = grVertices[vn];
683 //if(v.type!=NORMAL) continue;
684 inweight = 0;
685 outweight = 0;
686 low = 0;
687 high = max;
688 for (int i = 0; i < v.inSize(); ++i) {
689 e = v.ins[i];
690 inweight += e.weight;
691 low = Math.max(low, e.tail.rank + e.minLength);
692 }
693 for (int i = 0; i < v.outSize(); ++i) {
694 e = v.outs[i];
695 outweight += e.weight;
696 high = Math.min(high, e.head.rank - e.minLength);
697 }
698 if (low < 0)
699 low = 0; /* vnodes can have ranks < 0 */
700 if (inweight == outweight) {
701 choice = low;
702 for (int i = low + 1; i <= high; ++i) {
703 if (ranks[i] < ranks[choice])
704 choice = i;
705 }
706 if (DEBUG)
707 msg.println(NAME + ".tbBalance(): choice=" + choice + ",v=" + v);
708 ranks[v.rank]--;
709 ranks[choice]++;
710 v.rank = choice;
711 }
712 }
713 }
714
715 private void cleanup() {
716 for (int i = 0; i < grVertices.length; ++i) {
717 grVertices[i].treeIos = null;
718 }
719 }
720
721 // Debugging checks ////////////////////////////////////////////////////
722 //
723
724 /** Check that vertices have a valid tight tree. */
725 private void checkTight() {
726 DotVertex v;
727
728 int nv = 0;
729 int ne = 0;
730 for (nv = 0; nv < grVertices.length; ++nv) {
731 v = grVertices[nv];
732 ne += v.nTreeIos;
733 for (int i = 0, max = v.nTreeIos; i < max; ++i) {
734 if (v.treeIos[i].slack() > 0)
735 msg.err(NAME + ".checkTight(): not a tight tree: " + v.treeIos[i]);
736 }
737 }
738 if (nv != nTreeVts || ne != nTreeEdges * 2)
739 msg.err(
740 NAME
741 + ".checkTight(): sizes not match"
742 + ": nv="
743 + nv
744 + ": nTreeVts="
745 + nTreeVts
746 + ": ne="
747 + ne
748 + ": nTreeEdges="
749 + nTreeEdges);
750 }
751
752 /** Check that cut values are correct by recalculating all the cut vaules. */
753 private void checkCutValues() {
754 DotVertex v;
755 DotEdge e;
756 int save;
757
758 for (int nv = 0; nv < grVertices.length; ++nv) {
759 v = grVertices[nv];
760 for (int i = 0; i < v.nTreeIos; ++i) {
761 e = v.treeIos[i];
762 save = e.cutValue;
763 e.initCutValue();
764 if (e.cutValue != save)
765 msg.err(
766 NAME
767 + ".checkCutValues(): mismatch"
768 + ": save="
769 + save
770 + ": new="
771 + e.cutValue);
772 }
773 }
774 }
775
776 /** Check that ranks do not violate minLength of edges. */
777 private int checkRanks() {
778 int cost = 0;
779 DotVertex v;
780 DotEdge e;
781
782 for (int nv = 0; nv < grVertices.length; ++nv) {
783 v = grVertices[nv];
784 for (int i = 0; i < v.outSize(); ++i) {
785 e = v.outs[i];
786 cost += (e.weight) * Math.abs(e.length());
787 if (e.slack() < 0)
788 msg.err(
789 NAME
790 + ".checkRanks(): slack<0"
791 + ": e.slack()="
792 + e.slack()
793 + ":e="
794 + e);
795 }
796 }
797 if (VERBOSE)
798 msg.println("rank cost=" + cost);
799 return cost;
800 }
801
802 /** Check number of tree edges match treeEdges size. */
803 private void checkTree() {
804 int ne = 0;
805
806 for (int i = 0; i < grVertices.length; ++i) {
807 ne += grVertices[i].nTreeIos;
808 }
809 if (ne != nTreeEdges * 2)
810 msg.err(NAME + ".checkTree(): ne==nTreeEdges" + ": ne=" + ne + ": nTreeEdges=" + nTreeEdges);
811 }
812
813 private int sanityChecks() {
814 checkTree();
815 int cost = checkRanks();
816 checkCutValues();
817 checkTight();
818 return cost;
819 }
820
821 private String sprintTreeVts() {
822 StringBuffer ret = new StringBuffer("\n");
823 for (int i = 0; i < nTreeVts; ++i)
824 ret.append(treeVts[i].toString());
825 return ret.toString();
826 }
827
828 ////////////////////////////////////////////////////////////////////////
829
830 }