Source code: com/port80/graph/dot/impl/DotGraph.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.HashMap;
10 import java.util.HashSet;
11 import java.util.Iterator;
12 import java.util.LinkedList;
13 import java.util.List;
14 import java.util.Map;
15 import java.util.Set;
16
17 import com.port80.graph.IEdge;
18 import com.port80.graph.IGraph;
19 import com.port80.graph.IVertex;
20 import com.port80.util.Debug;
21 import com.port80.util.StopWatch;
22 import com.port80.util.msg;
23 import com.port80.util.sprint;
24 import com.port80.util.struct.Heap;
25 import com.port80.util.struct.IHeap;
26
27 /**
28 * DotGraph is an intermediate graph created for layout using the
29 * 'dot' layout algorithms. DotGraph is created from an IGraph
30 * with additional V/E added or removed to be used by the
31 * NetworkSimplex.dotRank().
32 *
33 * . DotGraph is created by extracting the topology
34 * information from an input IGraph. Instead of overlay onto the
35 * original graph, DotDirectGraph build an independent copy of the
36 * original graph.
37 *
38 * . Layout result are patched back to the original graph attribute
39 * table ('pos','-rank') and the DotGraph can be released
40 * after each layout.
41 *
42 * . DotGraph is read only since neither the vertex nor the
43 * edges from the original IGraph can be changed.
44 *
45 * @see com.port80.graph.IGraph
46 */
47 public class DotGraph {
48
49 // Static fields ///////////////////////////////////////////////////////
50 //
51
52 private static final String NAME = "DotGraph";
53 private static final String PACKAGENAME = "com.port80.graph.dot.impl";
54 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
55 private static final int VERSION = 0x0101;
56 private static final String VERSIONNAME = "v0.1";
57 static {
58 Debug.add(CLASSNAME);
59 }
60 private static final boolean DEBUG = false;
61 private static boolean VERBOSE = Debug.isVerbose();
62
63 private static final int NONE = 0;
64 private static final int ROOTGRAPH = 0;
65 private static final int CLUSTER = 1;
66 private static final int SUBGRAPH = 2;
67
68 // Instance fields /////////////////////////////////////////////////////
69 //
70
71 protected String fName = null;
72 protected int fType = 0;
73 /** The original IGraph. */
74 protected IGraph fOriginal = null;
75 protected int fMinRank = 0;
76 protected int fMaxRank = 0;
77 /** IVertex,IGraph->DotVertex mapping. */
78 protected Map fVertexMap = new HashMap();
79
80 // IEdge->DotEdge mapping.
81 private Map fEdgeMap = new HashMap();
82 // The vertices used for ranking.
83 private DotVertex[] fVertices = null;
84 // Temp. variables for acyclic().
85 private final class AcyclicData {
86 boolean fDoReverse = false;
87 int fNMerged = 0;
88 int fNReversed = 0;
89 int fNCritical = 0;
90 List fCritical = new LinkedList();
91 public AcyclicData(boolean doreverse) {
92 fDoReverse = doreverse;
93 }
94 public int cost() {
95 return fNCritical * 100 + fNReversed - fNMerged;
96 }
97 public String toString() {
98 return "critical="
99 + fNCritical
100 + ", reverse="
101 + fNReversed
102 + ", merge="
103 + fNMerged
104 + ", cost="
105 + cost();
106 }
107 }
108
109 // Constructors ////////////////////////////////////////////////////////
110 //
111
112 public DotGraph(String name, DotVertex[] vlist) {
113 this.fName = name;
114 this.fVertices = vlist;
115 }
116
117 public DotGraph(IGraph g) {
118
119 this.fName = g.getName();
120 this.fOriginal = g;
121
122 StopWatch timer = null;
123 if (VERBOSE)
124 timer = new StopWatch().start();
125
126 // Add vertices.
127 List vertexList = new ArrayList();
128 importGraphVertex(g, vertexList);
129 fVertices = new DotVertex[vertexList.size()];
130 for (int i = 0, max = vertexList.size(); i < max; ++i) {
131 fVertices[i] = (DotVertex) vertexList.get(i);
132 }
133 //NOTE: Sort vertices to a defined order to reduce dependency
134 // on order in the graph description and make result layout
135 // more stable.
136 Arrays.sort(fVertices, new DotVertex.NameComparator());
137 if (VERBOSE)
138 msg.println(NAME + "(): nVertices=" + fVertices.length);
139
140 // Add edges.
141 IVertex v, head, tail;
142 DotVertex dotv, dothead, dottail;
143 DotEdge dote;
144 IEdge e;
145 List in = null;
146 List out = null;
147 for (int nv = 0; nv < fVertices.length; ++nv) {
148 dotv = fVertices[nv];
149 in = new ArrayList();
150 out = new ArrayList();
151 if (dotv.isGraph())
152 importGraphEdge((IGraph) dotv.getOriginal(), in, out);
153 else
154 importVertexEdge((IVertex) dotv.getOriginal(), in, out);
155 initEdges(dotv, in, out);
156 }
157 //edgelabel_ranks(g);
158 //collapse_sets(g);
159 /*collapse_leaves(g);*/
160 //class1(g);
161 //minmax_edges(g);
162 minMaxRanked(fVertices);
163 if (DEBUG) {
164 List islands = decompose();
165 msg.println(NAME + ": " + islands.size() + " islands");
166 }
167 acyclic(fVertices);
168
169 //
170 // Add an invisible root with edge to every top vertex to make sure vertices are on a single island.
171 // Add an invisible edge from all unconnected vertices to root to make sure they are at a separate top rank.
172 //
173 DotVertex root = new DotVertex("", DotVertex.VERTEX);
174 int ndummy = 0;
175 for (int i = 0; i < fVertices.length; ++i) {
176 dotv = fVertices[i];
177 if (dotv.inSize() == 0) {
178 if (dotv.outSize() == 0) {
179 dote = new DotEdge(root, dotv, 1, 0);
180 root.addIn(dote);
181 dotv.addOut(dote);
182 } else {
183 dote = new DotEdge(dotv, root, 1, (dotv.isForceTopRank()? 1024: 0));
184 root.addOut(dote);
185 dotv.addIn(dote);
186 }
187 ++ndummy;
188 if (VERBOSE)
189 msg.println(NAME + ".initGraph(): dummy virtual edge: " + dote);
190 }
191 }
192 DotVertex[] a = new DotVertex[fVertices.length + 1];
193 System.arraycopy(fVertices, 0, a, 1, fVertices.length);
194 a[0] = root;
195 fVertices = a;
196
197 if (VERBOSE) {
198 timer.stop();
199 msg.println(
200 sprint
201 .f(" * %s(IGraph): %d vertices %d edges mapped, %d DotVertex %d DotEdges: elapsed=%.2f sec\n")
202 .a(NAME)
203 .a(fVertexMap.size())
204 .a(fEdgeMap.size())
205 .a(fVertices.length)
206 .a(fEdgeMap.size() + ndummy)
207 .a(timer.elapsed())
208 .end());
209 }
210 fEdgeMap = null;
211 }
212
213 private void initEdges(DotVertex dotv, List in, List out) {
214 DotVertex dothead;
215 DotVertex dottail;
216 DotEdge dote;
217 IEdge e;
218 // Add edges.
219 for (int i = 0, max = in.size(); i < max; ++i) {
220 e = (IEdge) in.get(i);
221 dote = (DotEdge) fEdgeMap.get(e);
222 if (dote == null) {
223 dottail = (DotVertex) fVertexMap.get(e.getTail());
224 dote = new DotEdge(dotv, dottail, e);
225 dote.setCritical(e.getAttrBool("critical"));
226 fEdgeMap.put(e, dote);
227 }
228 dotv.addIn(dote);
229 }
230 //
231 for (int i = 0, max = out.size(); i < max; ++i) {
232 e = (IEdge) out.get(i);
233 dote = (DotEdge) fEdgeMap.get(e);
234 if (dote == null) {
235 dothead = (DotVertex) fVertexMap.get(e.getHead());
236 dote = new DotEdge(dothead, dotv, e);
237 dote.setCritical(e.getAttrBool("critical"));
238 fEdgeMap.put(e, dote);
239 }
240 dotv.addOut(dote);
241 }
242 }
243
244 private void importVertexEdge(IVertex v, List in, List out) {
245 IEdge[] a = v.ins();
246 for (int i = 0; i < v.inSize(); ++i) {
247 // We don't need self edges for ranking.
248 if (a[i].getTail().equals(v))
249 continue;
250 in.add(a[i]);
251 }
252 a = v.outs();
253 for (int i = 0; i < v.outSize(); ++i) {
254 // We don't need self edges for ranking.
255 if (a[i].getHead().equals(v))
256 continue;
257 out.add(a[i]);
258 }
259 }
260
261 /**
262 * Only edges going from graph g to vertex external to g are used.
263 * External vertex that conected to an internal vertex of g would connect to
264 * the vertex that represent g instead. The fVertexMap of IVertex->DotVertex is built
265 * for such purpose.
266 */
267 private void importGraphEdge(IGraph g, List in, List out) {
268 IVertex v;
269 IVertex head;
270 IEdge e;
271 // Construct the I/O list from vertices (including
272 // those from nested subgraphs).
273 Set vset = g.allVertices();
274 IEdge[] a;
275 for (Iterator iv = vset.iterator(); iv.hasNext();) {
276 v = (IVertex) iv.next();
277 a = v.outs();
278 for (int i = 0, max = v.outSize(); i < max; ++i) {
279 e = a[i];
280 head = e.getHead();
281 if (vset.contains(head))
282 continue;
283 if (fVertexMap.get(head) == null)
284 msg.err(NAME + "(IGraph): head not exists in DotGraph: e=" + e);
285 out.add(e);
286 }
287 a = v.ins();
288 for (int i = 0, max = v.inSize(); i < max; ++i) {
289 e = a[i];
290 if (vset.contains(e.getTail()))
291 continue;
292 if (fVertexMap.get(e.getTail()) == null)
293 msg.err(NAME + "(IGraph): tail not exists in DotGraph: e=" + e);
294 in.add(e);
295 }
296 }
297 }
298
299 /** Add subgraph, collapse cluster to single node for ranking. */
300 private void importGraphVertex(IGraph g, List ret) {
301 IVertex v;
302 DotVertex dotv;
303 Set vset;
304 if (g.isCluster()) {
305 // Cluster is ranked internally and (includes any subgraph
306 // under it) is represented by a single DotVertex.
307 //
308 //FIXME:
309 /*
310 if(vertexMap.get(g)==null) {
311 v=new DotVertex(g);
312 vertexMap.put(g,v);
313 }
314 */
315 return;
316 } else if (g.getAttrString("rank") != null) {
317 // Same ranked subgraph including any graph below it would
318 // be represented by a single DotVertex.
319 if (fVertexMap.get(g) == null) {
320 dotv = new DotVertex(g);
321 if (fVertexMap.put(g, dotv) != null)
322 msg.err(NAME + ".addGraph(): duplicated graph: " + g.getName());
323 else
324 ret.add(dotv);
325 vset = g.allVertices();
326 // Map all IVertex to this DotVertex.
327 for (Iterator it = vset.iterator(); it.hasNext();) {
328 if (fVertexMap.put(it.next(), dotv) != null)
329 msg.err(
330 NAME
331 + ".addGraph(): duplicated vertex: dotv="
332 + dotv.getName());
333 }
334 }
335 return;
336 }
337 // Add vertices.
338 vset = g.getVertexSet();
339 for (Iterator it = vset.iterator(); it.hasNext();) {
340 v = (IVertex) it.next();
341 dotv = new DotVertex(v);
342 if (fVertexMap.put(v, dotv) != null)
343 msg.err(NAME + ".addGraph(): duplicated vertex: " + v.getName());
344 else
345 ret.add(dotv);
346 }
347 // Recursively add subgraph.
348 List subs = g.getSubGraphs();
349 for (int i = 0, max = subs.size(); i < max; ++i) {
350 g = (IGraph) subs.get(i);
351 importGraphVertex(g, ret);
352 }
353 }
354
355 ////////////////////////////////////////////////////////////////////////
356
357 /**
358 * Reverse edges for min/max ranked vertex so ranking would put
359 * them into the right rank.
360 */
361 private void minMaxRanked(DotVertex[] vts) {
362 DotVertex v;
363 for (int i = 0; i < vts.length; ++i) {
364 v = vts[i];
365 if (v.isForceMinRank()) {
366 for (int j = 0; j < v.inSize(); ++j)
367 v.ins[j].reverse();
368 } else if (v.isForceMaxRank()) {
369 for (int j = 0; j < v.outSize(); ++j)
370 v.outs[j].reverse();
371 }
372 }
373 }
374
375 /**
376 * Decompose graph into islands.
377 * @return List of island (each island is a List of DotVertex).
378 */
379 private List decompose() {
380 final String METHOD = NAME + ".decompose(): ";
381 DotVertex v;
382 List island;
383 List islands = new ArrayList();
384 Set visited = new HashSet();
385 for (int i = 0; i < fVertices.length; ++i) {
386 v = fVertices[i];
387 if (visited.add(v)) {
388 island = decompose(v, visited, new ArrayList());
389 islands.add(island);
390 if (VERBOSE)
391 msg.println(METHOD + "island " + islands.size() + ",size=" + island.size());
392 }
393 }
394 if (VERBOSE)
395 msg.println(METHOD + "nIsland=" + islands.size());
396 return islands;
397 }
398
399 /**
400 * Perform a bidirectional depth first search from the starting vertex to all vertices
401 * connected on the same island.
402 *
403 * @return The list of vertex on the island.
404 * @param start The starting vertex.
405 * @param visited The visited vertex set.
406 * @param ret List to hold the return vertices.
407 */
408 private List decompose(DotVertex start, Set visited, List ret) {
409 final String METHOD = NAME + "decompose(): ";
410 DotVertex v;
411 DotEdge[] a;
412 a = start.getOuts();
413 for (int i = 0, max = start.outSize(); i < max; ++i) {
414 v = a[i].getHead();
415 if (v == null)
416 msg.err(METHOD + "e.head==null: e=" + a[i]);
417 if (visited.add(v))
418 decompose(v, visited, ret);
419 }
420 a = start.getIns();
421 for (int i = 0, max = start.inSize(); i < max; ++i) {
422 v = a[i].getTail();
423 if (v == null)
424 msg.err(METHOD + "e.tail==null: e=" + a[i]);
425 if (visited.add(v))
426 decompose(v, visited, ret);
427 }
428 ret.add(start);
429 return ret;
430 }
431
432 ////////////////////////////////////////////////////////////////////////
433
434 /** Make graph acyclic by reversing edges that points back to an
435 * ancestor in a depth first search.
436 *
437 * . Which edge got reversed very much depends on where the
438 * search is started. We try all starting points and find the
439 * one with least reversals. This reduce distortion of the
440 * original topology and also make the layout result more stable
441 * (ie. we comes up with same result for same graph topology).
442 */
443 private int acyclic(DotVertex[] vts) {
444 int cost;
445 int beststart = 0;
446 int worststart = 0;
447 int bestcost = Integer.MAX_VALUE;
448 int worstcost = Integer.MIN_VALUE;
449 for (int start = 0; start < vts.length; ++start) {
450 cost = acyclic(vts, start, false);
451 if (cost < bestcost) {
452 bestcost = cost;
453 beststart = start;
454 }
455 if (cost > worstcost) {
456 worstcost = cost;
457 worststart = start;
458 }
459 }
460 if (VERBOSE)
461 msg.println(
462 NAME
463 + ".acyclic(): worst start="
464 + worststart
465 + "(cost="
466 + worstcost
467 + "), best start="
468 + beststart
469 + "(cost="
470 + bestcost
471 + ")");
472 // Move the best starting vertex to the front.
473 // DotVertex[] a = new DotVertex[fVertices.length];
474 // for (int i = 0; i < fVertices.length; ++i) {
475 // if (i + beststart >= fVertices.length)
476 // a[i] = fVertices[i + beststart - fVertices.length];
477 // else
478 // a[i] = fVertices[i + beststart];
479 // }
480 // fVertices = a;
481 return acyclic(vts, beststart, true);
482 }
483
484 private int acyclic(DotVertex[] vts, int start, boolean doreverse) {
485 DotVertex v;
486 Set visited = new HashSet();
487 Set ancestors = new HashSet();
488 Set reversed = new HashSet();
489 AcyclicData data = new AcyclicData(doreverse);
490 int index;
491 for (int i = 0, len = vts.length; i < len; ++i) {
492 index = start + i;
493 if (index >= len)
494 index -= len;
495 v = vts[index];
496 if (visited.add(v))
497 acyclic(v, visited, ancestors, reversed, data);
498 }
499 if (doreverse && data.fNCritical > 0)
500 anneal(data);
501 if (VERBOSE)
502 msg.println(NAME + ".acyclic(): start=" + start + ", " + data);
503 return data.cost();
504 }
505
506 /**
507 * @enter DotGraph must not have any self edges.
508 */
509 private void acyclic(DotVertex start, Set visited, Set ancestors, Set reversed, AcyclicData data) {
510 if (DEBUG)
511 msg.println(NAME + ".acyclic(): start=" + start.getName());
512 DotVertex v;
513 DotEdge e, rev;
514 ancestors.add(start);
515 for (int i = 0, max = start.outSize(); i < max; ++i) {
516 e = start.outs[i];
517 v = e.getHead();
518 if (ancestors.contains(v)) {
519 if (DEBUG)
520 msg.println("\treverse=" + e);
521 if (e.isCritical()) {
522 // Don't merge critical edges.
523 if (reversed.remove(e)) {
524 msg.err("reversing an reversed edge: e=" + e);
525 data.fNCritical--;
526 } else {
527 reversed.add(e);
528 data.fNCritical++;
529 }
530 if (data.fDoReverse) {
531 if(!DEBUG && VERBOSE) msg.println("\treverse critical=" + e);
532 data.fCritical.add(e);
533 e.reverse();
534 }
535 } else {
536 if (reversed.remove(e)) {
537 msg.err(NAME + ".acyclic(): reversing an reversed edge: e=" + e);
538 data.fNReversed--;
539 } else {
540 data.fNReversed++;
541 reversed.add(e);
542 }
543 rev = e.findReverseEdge();
544 if (data.fDoReverse) {
545 if (rev != null) {
546 rev.merge(e);
547 data.fNMerged++;
548 if (DEBUG||VERBOSE)
549 msg.println("\tmerge:\trev=" + rev + "\n\t\te=" + e);
550 } else {
551 if(!DEBUG && VERBOSE) msg.println("\treverse=" + e);
552 e.reverse();
553 }
554 } else {
555 if (reversed.contains(rev))
556 rev = null;
557 if (rev != null) {
558 // FIXME: merge edge may need to be reversed again by anneal.
559 // If there is already an edge in the reverse
560 // direction, merge the two edges. In both case the
561 // outedge is removed (possibly with an inedge added).
562 if (DEBUG)
563 msg.println("\tmerge:\trev=" + rev + "\n\t\te=" + e);
564 data.fNMerged++;
565 }
566 }
567 }
568 if (data.fDoReverse) {
569 --i;
570 --max;
571 }
572 } else if (visited.add(v))
573 acyclic(v, visited, ancestors, reversed, data);
574 }
575 ancestors.remove(start);
576 }
577
578 /** Fix reversed critical edges.
579 */
580 private void anneal(AcyclicData data) {
581 Set fixed = new HashSet();
582 boolean abort = false;
583 for (int iter = 0, max = data.fCritical.size() * 4;
584 !abort && iter < max && data.fCritical.size() > 0;
585 ++iter) {
586 DotEdge e = (DotEdge) data.fCritical.remove(0);
587 --data.fNCritical;
588 int mark = data.fCritical.size();
589 if (!e.reversed)
590 continue;
591 e.reverse();
592 fixed.add(e);
593 if (VERBOSE)
594 msg.println(NAME + ".anneal(): e=" + e);
595 Set visited = new HashSet();
596 visited.add(e.tail);
597 acyclic(e.tail, visited, new HashSet(), new HashSet(), data);
598 // for(int i=mark; i<data.fCritical.size(); ++i) {
599 // if(fixed.contains(data.fCritical.get(i))) {
600 // msg.warn(NAME+".anneal(): critical edge loops found: e="+e);
601 // abort=true;
602 // }
603 // break;
604 // }
605 }
606 if (VERBOSE)
607 msg.println(NAME + ".anneal(): " + data);
608 }
609
610 // Instance methods ////////////////////////////////////////////////////
611 //
612
613 public String getName() {
614 return fName;
615 }
616 public IGraph getOriginal() {
617 return fOriginal;
618 }
619 public DotVertex[] getVertices() {
620 return fVertices;
621 }
622
623 /**
624 * Adjust ranks to eliminate empty ranks and save ranks to IGraph.
625 */
626 public void saveRanks() {
627 IHeap heap = new Heap(new DotVertex.RankComparator(), fVertices.length);
628 for (int i = 0; i < fVertices.length; ++i) {
629 // Skip root.
630 if (fVertices[i].getName().length() == 0)
631 continue;
632 heap.enqueue(fVertices[i]);
633 }
634 DotVertex v;
635 int rank = -1;
636 int prev = -1;
637 // Adjust ranks to sequential order.
638 for (int i = 0; i < fVertices.length - 1; ++i) {
639 v = (DotVertex) heap.dequeue(); // Lowest rank first.
640 if (v.getRank() != prev) {
641 ++rank;
642 prev = v.getRank();
643 }
644 v.rank = rank;
645 }
646 IVertex original;
647 Set vset;
648 for (int i = 0; i < fVertices.length; ++i) {
649 v = fVertices[i];
650 if (v.getName().length() == 0)
651 continue;
652 rank = v.getRank();
653 if (rank < fMinRank)
654 fMinRank = rank;
655 if (rank > fMaxRank)
656 fMaxRank = rank;
657 if (v.isGraph()) {
658 vset = ((IGraph) v.getOriginal()).allVertices();
659 //FIXME: For now, just assume all vertices in graph is same rank.
660 for (Iterator it = vset.iterator(); it.hasNext();) {
661 ((IVertex) it.next()).setAttr("-rank", rank);
662 }
663 } else {
664 original = (IVertex) v.getOriginal();
665 if (original != null)
666 original.setAttr("-rank", rank);
667 }
668 }
669 fOriginal.setAttr("-minrank", fMinRank);
670 fOriginal.setAttr("-maxrank", fMaxRank);
671 if (DEBUG)
672 msg.println(NAME + ".saveRanks()" + ": minrank=" + fMinRank + ": maxrank=" + fMaxRank);
673 }
674
675 public void clear() {
676 fOriginal = null;
677 fVertexMap = null;
678 fVertices = null;
679 }
680
681 public String toString() {
682 StringBuffer ret = new StringBuffer("### DotGraph: " + fName + " {\n");
683 DotVertex v;
684 DotEdge e;
685 for (int i = 0; i < fVertices.length; ++i) {
686 v = fVertices[i];
687 ret.append(" " + v + "\n");
688 }
689 ret.append("\n");
690 for (int i = 0; i < fVertices.length; ++i) {
691 v = fVertices[i];
692 for (int en = 0; en < v.outSize(); ++en) {
693 e = v.outs[en];
694 ret.append(" " + e + "\n");
695 }
696 }
697 ret.append("\n");
698 return ret.toString();
699 }
700
701 // Debugging methods ///////////////////////////////////////////////////
702 //
703
704 /** Check that graph is acyclic. */
705 private boolean checkAcyclic(DotVertex v, Set visited, Set ancestors) {
706 if (!visited.add(v))
707 return false;
708 DotEdge e;
709 DotVertex w;
710 ancestors.add(v);
711 for (int i = 0; i < v.outSize(); ++i) {
712 e = v.outs[i];
713 w = e.head;
714 if (ancestors.contains(w)) {
715 msg.err(NAME + ".checkAcyclic(): cycle involving: " + v + ", " + w);
716 return false;
717 }
718 if (!visited.contains(w)) {
719 if (!checkAcyclic(w, visited, ancestors))
720 return false;
721 }
722 }
723 ancestors.remove(v);
724 return true;
725 }
726
727 public boolean checkAcyclic() {
728 HashSet visited = new HashSet();
729 HashSet ancestors = new HashSet();
730 for (int i = 0; i < fVertices.length; ++i) {
731 if (visited.contains(fVertices[i]))
732 continue;
733 if (!checkAcyclic(fVertices[i], visited, ancestors))
734 return false;
735 }
736 return true;
737 }
738
739 ////////////////////////////////////////////////////////////////////////
740
741 /** Print rank result graph for debugging. */
742 public String sprintRankDebugGraph() {
743 StringBuffer ret = new StringBuffer("digraph " + fName + "DebugRank {\n");
744 DotVertex v;
745 DotEdge e;
746 for (int i = 0; i < fVertices.length; ++i) {
747 v = fVertices[i];
748 ret.append(" \"" + v.getName() + "\" [label=\"" + v.getName() + "(" + v.rank + ")\"];\n");
749 }
750 ret.append("\n");
751 for (int i = 0; i < fVertices.length; ++i) {
752 v = fVertices[i];
753 for (int en = 0; en < v.outSize(); ++en) {
754 e = v.outs[en];
755 sprintRankDebugEdge(ret, e);
756 while ((e = e.next) != null)
757 sprintRankDebugEdge(ret, e);
758 }
759 }
760 ret.append("}\n");
761 return ret.toString();
762 }
763
764 private void sprintRankDebugEdge(StringBuffer ret, DotEdge e) {
765 DotVertex head, tail;
766 //if(e.isReversed()) {
767 //head=e.tail;
768 //tail=e.head;
769 //} else {
770 head = e.head;
771 tail = e.tail;
772 //}
773 ret.append(" \""
774 //+tail.getName()+"(r="+tail.rank+")\"->\""
775 //+head.getName()+"(r="+head.rank+")\" [label="+e.cutValue
776 +tail.getName() + "\"->\"" + head.getName() + "\" [label=" + e.cutValue);
777 if (e.isReversed())
778 ret.append(",color=red");
779 if (e.treeIndex < 0)
780 ret.append(",style=dotted");
781 ret.append("];\n");
782 }
783
784 ////////////////////////////////////////////////////////////////////////
785
786 }