Source code: com/port80/graph/dot/impl/Position.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.awt.geom.Point2D;
8 import java.awt.geom.Rectangle2D;
9 import java.util.Arrays;
10 import java.util.HashMap;
11 import java.util.Iterator;
12 import java.util.Map;
13
14 import com.port80.graph.IEdge;
15 import com.port80.graph.IVertex;
16 import com.port80.util.Debug;
17 import com.port80.util.StopWatch;
18 import com.port80.util.msg;
19 import com.port80.util.sprint;
20
21 /**
22 * position(g): set n.coord (x and y) for all nodes n of g, using g.rank.
23 * (the graph may be modified by merging certain edges with a common endpoint.)
24 * the coordinates are computed by constructing and ranking an auxiliary graph.
25 * then leaf nodes are inserted in the fast graph. cluster boundary nodes are
26 * created and correctly separated.
27 */
28 public class Position {
29
30 // Static fields ///////////////////////////////////////////////////////
31 //
32
33 private static final String NAME = "Position";
34 private static final boolean DEBUG = false;
35 private static final boolean VERBOSE = Debug.isVerbose();
36
37 // Instance fields /////////////////////////////////////////////////////
38 //
39
40 // private int scaleCritical = 8; /** vertex-bus/bus-vertex edge weigth scaling factor.*/
41 // private int scaleBusVertex = 8; /** vertex-bus/bus-vertex edge weigth scaling factor.*/
42 // private int scaleBus = 8; /** bus-x/x-bus edge.*/
43 // private int scaleVirtual = 8; /** x-virtual edge. */
44 // private int scaleOther = 1; /** other edge.*/
45 private int fXMargin;
46 private int fYMargin;
47 private VirtualEdge fDummy = null;
48
49 Map fVertexMap = null;
50
51 //
52 // Layout parameters.
53 //
54 private int fXDIV_EDGES;
55 private int fXDIV_XEDGE;
56 private int fYSPACING_BUSBUS;
57 private int fYSPACING_XBUS;
58 private int fWEIGHT_VIRTUALFACTOR;
59
60 // Static methods //////////////////////////////////////////////////////
61 //
62
63 public static int dotPosition(VirtualGraph g) {
64 return new Position().position(g);
65 }
66
67 public static void saveResult(VirtualGraph g) {
68 VirtualVertex[] vertices = g.getVertices();
69 VirtualVertex v;
70 IVertex iv;
71 for (int i = 0; i < vertices.length; ++i) {
72 v = vertices[i];
73 if (v.isReal()) {
74 iv = (IVertex) v.getOriginal();
75 iv.setAttr("pos", new Point2D.Double(v.x, v.y));
76 }
77 //FIXME: GRAPH
78 }
79 }
80
81 /** Print Position() result for viewing with ide.plugins.plotGraph. */
82 public static void printPositionGraph(VirtualGraph g) {
83 int scale = 2;
84 StringBuffer ret = new StringBuffer("digraph " + g.getName() + "_xposition {\n");
85 int w = g.getWidth() * scale;
86 int h = g.getHeight() * scale;
87 ret.append(" graph [ bb=\"0,0," + w + "," + h + "\"];\n");
88 String name;
89 VirtualVertex v;
90 VirtualVertex[] vertices = g.getVertices();
91 for (int i = 0; i < vertices.length; ++i) {
92 v = vertices[i];
93 name = v.getName();
94 ret.append(" \"" + name + "\" [label=\"" + name + "\"");
95 if (name.startsWith("$"))
96 ret.append(",style=dotted");
97 else
98 ret.append(",style=filled,fillcolor=yellow");
99 ret.append(
100 ",pos=\""
101 + (v.x * scale)
102 + ","
103 + (h - v.y * scale)
104 + "\",width=\""
105 + ((double) (v.leftWidth + v.rightWidth) / 80.0)
106 + "\",height=\""
107 + ((double) (v.top + v.bottom) / 80.0)
108 + "\"");
109 ret.append("];\n");
110
111 }
112 ret.append("}\n");
113 msg.println(ret.toString());
114 }
115
116 // Instance methods ////////////////////////////////////////////////////
117 //
118
119 public int position(VirtualGraph g) {
120 int nvts = g.getVertices().length;
121 if (nvts == 0)
122 return 0;
123 //
124 fYSPACING_XBUS = g.fYSPACING_XBUS;
125 fYSPACING_BUSBUS = g.fYSPACING_BUSBUS;
126 fXDIV_EDGES = g.fXDIV_EDGES;
127 fXDIV_XEDGE = g.fXDIV_XEDGE;
128 fWEIGHT_VIRTUALFACTOR = g.fWEIGHT_VIRTUALFACTOR;
129 //
130 int xspacing = g.vertexSpacing;
131 int yspacing = g.getRankSpacing();
132 int margin = g.getMargin();
133 fXMargin = xspacing * margin;
134 fYMargin = yspacing * margin;
135 if (VERBOSE)
136 msg.println(
137 NAME
138 + ".position(): "
139 + "xspacing="
140 + xspacing
141 + ", yspacing="
142 + yspacing
143 + ", margin="
144 + margin
145 + ", xmargin="
146 + fXMargin
147 + ", ymargin="
148 + fYMargin);
149
150 expandGraph(g);
151 yPosition(g);
152 int cost = xPosition(g);
153 cleanupGraph(g);
154 aspectRatio(g);
155 return cost;
156 }
157
158 ////////////////////////////////////////////////////////////////////////
159
160 /** Expand subgraph and clusters to vertices. */
161 private void expandGraph(VirtualGraph g) {}
162
163 /** Determine y coordinates for each vertex. */
164 private void yPosition(VirtualGraph g) {
165
166 VirtualVertex v;
167 VirtualGraph.Rank rank;
168
169 // scan ranks for tallest nodes.
170 int maxheight = 0;
171 for (int max, r = g.minRank; r <= g.maxRank; ++r) {
172 rank = g.ranks[r];
173 for (int iv = 0; iv < rank.nVts; ++iv) {
174 v = rank.vts[iv];
175 if (v.top > rank.top)
176 rank.top = v.top;
177 if (v.bottom > rank.bottom)
178 rank.bottom = v.bottom;
179 //FIXME: Update nearest enclosing cluster rank ht.
180 }
181 max = rank.top + rank.bottom;
182 if (max > maxheight)
183 maxheight = max;
184 }
185 // Scan sub-clusters.
186 //clust_ht(g);
187
188 // Make the initial assignment of ycoords to leftmost nodes by
189 // ranks.
190 int y = fYMargin;
191 int rankspacing = g.getRankSpacing(); // Spacing between rank.
192 int bus = 0; // bit 0=last level is bus. bit1=this level is bus.
193 int halfmaxheight = maxheight / 2;
194 rank = g.ranks[g.minRank];
195 for (int r = g.minRank; r <= g.maxRank; ++r) {
196 if (r != g.minRank) {
197 //TODO: Increase spacing for row with many horizontal
198 // routes.
199 if (rankspacing == 0) {
200 y += maxheight; //half for bottom, half for spacing.
201 rank = g.ranks[r];
202 } else {
203 y += rank.bottom;
204 rank = g.ranks[r];
205 bus >>= 1;
206 for (int i = 0; i < rank.nVts; ++i)
207 if (rank.vts[i].isBus()) {
208 bus |= 2;
209 break;
210 }
211 switch (bus) {
212 case 1 :
213 case 2 :
214 y += fYSPACING_XBUS;
215 break; // x bus
216 case 3 :
217 y += fYSPACING_BUSBUS;
218 break; // bus bus
219 default :
220 y += rankspacing;
221 }
222 }
223 }
224 if (rankspacing == 0) {
225 rank.top = halfmaxheight;
226 rank.bottom = halfmaxheight;
227 }
228 y += rank.top;
229 for (int i = 0; i < rank.nVts; ++i) {
230 rank.vts[i].y = y;
231 }
232 }
233 y += rank.bottom + fYMargin;
234 g.setHeight(y);
235 if (VERBOSE)
236 msg.println(NAME + ".yPosition(): graph yMargin=" + fYMargin + ", height=" + y);
237 if (DEBUG) {
238 // Print rank heights.
239 msg.println(NAME + ".yPosition(): rank heights:");
240 for (int r = g.minRank; r <= g.maxRank; ++r) {
241 rank = g.ranks[r];
242 msg.println(
243 sprint.f("\tr=%2d, top=%8d, bottom=%9d").a(r).a(rank.top).a(rank.bottom).end());
244 }
245 }
246 }
247
248 /** Determine x coordinates of each vertex. */
249 private int xPosition(VirtualGraph g) {
250 DotGraph dotgraph = initGraph(g);
251 double nslimit = g.getOriginal().getAttrDouble("nslimit", 1.0);
252 int cost = NetworkSimplex.dotRank(dotgraph, nslimit, false);
253 if (DEBUG)
254 printXPositionGraph(dotgraph);
255 //
256 if (fDummy != null) {
257 fDummy.tail.removeOut(fDummy);
258 fDummy.head.removeIn(fDummy);
259 }
260 DotVertex[] vts = dotgraph.getVertices();
261 DotVertex v;
262 VirtualVertex vv;
263 int minx = Integer.MAX_VALUE;
264 int maxx = 0;
265 int nv = 0;
266 int nvv = 0;
267 for (int min, max, i = 0; i < vts.length; ++i) {
268 v = vts[i];
269 vv = (VirtualVertex) v.getOriginal();
270 if (vv == null)
271 continue;
272 nv++;
273 // v.rank==x coord. of left edge of v.
274 vv.x = v.rank; //-vv.leftWidth;
275 if (vv.ins.length == 0 && vv.outs.length == 0)
276 continue;
277 ++nvv;
278 min = vv.x - vv.leftWidth;
279 max = vv.x + vv.rightWidth;
280 if (min < minx)
281 minx = min;
282 if (max > maxx)
283 maxx = max;
284 }
285 if (minx > maxx)
286 minx = maxx;
287 VirtualVertex[] vvts = g.getVertices();
288 if (nv != vvts.length)
289 msg.err(NAME + ".xPosition(): nv!=vvts.length: vvts.length=" + vvts.length+", nv=" + nv);
290 //
291 // Center the top unconnected rank between minx and maxx.
292 //
293 VirtualGraph.Rank rank = g.ranks[g.minRank];
294 vv = rank.vts[0];
295 if (vv.ins.length == 0 && vv.outs.length == 0) {
296 nvv += rank.nVts;
297 int leftmargin = vv.x - vv.leftWidth - minx;
298 vv = rank.vts[rank.nVts - 1];
299 int rightmargin = maxx - vv.x - vv.rightWidth;
300 int offset = (leftmargin + rightmargin) / 2 - leftmargin;
301 if (offset != 0) {
302 for (int i = 0; i < rank.nVts; ++i)
303 rank.vts[i].x += offset;
304 }
305 if (vv.x + vv.rightWidth > maxx)
306 maxx = vv.x + vv.rightWidth;
307 vv = rank.vts[0];
308 if (vv.x - vv.leftWidth < minx)
309 minx = vv.x - vv.leftWidth;
310 }
311 if (nvv != vvts.length) {
312 msg.err(
313 NAME
314 + ".xPosition(): number of vertices counted for margin, nvv!=vvts.length: vvts.length="
315 + vvts.length
316 + ", nvv="
317 + nvv);
318 for(int i=0; i<rank.nVts; ++i) {
319 vv=rank.vts[i];
320 msg.println("\t"+vv.ins.length+","+vv.outs.length+": "+rank.vts[i]);
321 }
322 }
323 for (int i = 0; i < vvts.length; ++i)
324 vvts[i].x -= (minx - fXMargin);
325 maxx -= (minx - fXMargin);
326 g.setWidth(maxx + fXMargin);
327 if (VERBOSE)
328 msg.println(
329 NAME
330 + ".xPosition(): graph width,height="
331 + g.getWidth()
332 + ","
333 + g.getHeight()
334 + ", cost="
335 + cost);
336 return cost;
337 }
338
339 /**
340 * Remove auxillary vertices and edges added for x-ranking,
341 * ... etc.
342 */
343 private void cleanupGraph(VirtualGraph g) {
344 }
345
346 /** Adjust for desired aspect ration. */
347 private void aspectRatio(VirtualGraph g) {}
348
349 ////////////////////////////////////////////////////////////////////////
350
351 /** Create a DotGraph for x-position ranking.
352 *
353 * . x coordinates are determined by running the network simplex
354 * algorithm on the x-axis just like ranking for the y-axis.
355 *
356 * . To account for the port displacements, each edge is broken
357 * into two with one of them using the difference in the port
358 * displacements as its minimium length (ie. x distance)
359 * while the other is 0. Thus when the modified graph has
360 * optimal ranking (ie. with minimium lengths), the ports would
361 * be aligned.
362 *
363 * . Auxillary flat edges are also added between vertices with
364 * same rank that are not flat connected to ensure there are
365 * proper separation between them. The minimium length of
366 * auxillary edge is the minimium vertex separation
367 * (v1.width+v2.width)/2+xspacing
368 *
369 * . Weight of edges (real,virtual/auxillary) are adjusted
370 * according to their type. 'dot' assigned 1,2,8 to
371 * real-real,real-virtual and virtual-virtual edges which give
372 * priority to align long edges that pass through several
373 * levels.
374 *
375 * . Since NetworkSimplex.dotRank() would reinit. all the ranks
376 * anyway, there is no need to init. vertex.rank here. Only
377 * need to make sure edge.minLength and edge.weight is correct.
378 *
379 * . Spacings:
380 *
381 * |v|-vs-|v|-
382 */
383 private DotGraph initGraph(VirtualGraph g) {
384
385 final String METHOD = NAME + ".initGraph(): ";
386 StopWatch timer = null;
387 if (VERBOSE)
388 timer = new StopWatch().start();
389
390 VirtualVertex[] vvts = g.getVertices();
391
392 VirtualGraph.Rank rank;
393 VirtualVertex v, left, right;
394 VirtualEdge e;
395 DotVertex dotv, head, tail;
396 IEdge se;
397 Rectangle2D bound;
398
399 // Spacings.
400 int xspacing = g.vertexSpacing;
401 int yspacing = g.getRankSpacing();
402 int espacing = xspacing / fXDIV_EDGES; // Edge spacing.
403 int xespacing = xspacing / fXDIV_XEDGE;
404
405 // Create vertices.
406 fVertexMap = new HashMap();
407 rank = g.ranks[g.minRank];
408 v = rank.vts[rank.nVts / 2];
409 if (g.maxRank > g.minRank && v.ins.length == 0 && v.outs.length == 0) {
410 Arrays.sort(rank.vts, new VirtualVertex.NameComparator());
411 for (int i = 0; i < rank.nVts; ++i) {
412 rank.vts[i].order = i;
413 }
414 // Make an edge from middle vertex of the unconnected rank
415 // to the middle vertex of top connected rank to make the whole graph connected
416 // required by NetworkSimplex.dotRank().
417 rank = g.ranks[g.minRank + 1];
418 left = rank.vts[rank.nVts / 2];
419 fDummy = VirtualEdge.newStubEdge(left, v, null, g);
420 }
421 for (int width, lw, rw, r = g.minRank; r <= g.maxRank; ++r) {
422 rank = g.ranks[r];
423 if (rank.nVts < 0) {
424 msg.err(METHOD + "rank.nVts<=0: r=" + r);
425 continue;
426 }
427 int xpos = 0; // Start x position next vertex (left edge).
428 int rankheight = rank.top + rank.bottom;
429 left = rank.vts[0];
430 tail = createDotVertex(left);
431 //FIXME: Should use VirtualGraph.MinimiumSpacingIterator instead.
432 for (int vi = 1; vi < rank.nVts; ++vi) {
433 right = rank.vts[vi];
434 if (left.isVirtual() && right.isVirtual()) {
435 width = left.rightWidth + right.leftWidth;
436 width = Math.max(width, espacing);
437 } else if (left.isVirtual()) {
438 //width = right.leftWidth + Math.max(left.rightWidth, xespacing);
439 width = right.leftWidth + left.rightWidth + espacing;
440 } else if (right.isVirtual()) {
441 width = left.rightWidth + right.leftWidth +espacing;
442 } else {
443 width = left.rightWidth + right.leftWidth + xspacing;
444 }
445 // Extra padding for expansion of merged edges.
446 width+=left.padding+right.padding;
447 // Self edges, ensure extra spacing.
448 for (int i = 0; i < left.selves.length; ++i) {
449 se = (left.selves[i].getOriginals())[0];
450 lw = 0;
451 rw = 0;
452 bound = (Rectangle2D) se.getAttr("-bounds");
453 if (bound != null) {
454 lw = (int) (bound.getWidth() / 2); // Width==0 if no label.
455 rw = lw;
456 }
457 width += Math.max(g.selfEdgeSize + rw, xspacing + lw + rw);
458 }
459 if (DEBUG)
460 msg.println(
461 METHOD
462 + "left="
463 + left.getName()
464 + "("
465 + left.leftWidth
466 + ","
467 + left.rightWidth
468 + ")"
469 + ", right="
470 + right.getName()
471 + "("
472 + right.leftWidth
473 + ","
474 + right.rightWidth
475 + ")"
476 + ", width="
477 + width);
478 // Auxillary edge to ensure min. vertex spacing with
479 // non-flat connected neighbour and MinCross()
480 // determined order.
481 head = createDotVertex(right);
482 createDotEdge(head, tail, width, 0);
483 //
484 // Flat edges between adjacent vertices with label
485 // require extra spacing for label. Flat edges fly
486 // over other vertices or there is edge in reverse
487 // direction, label are placed in separate rank and do
488 // not require extra spacing in this rank.
489 if (left.hasFlat()) {
490 for (int i = 0; i < left.flatIns.length; ++i) {
491 e = left.flatIns[i];
492 if (e.tail.equals(left)) {
493 // If there are multiple flat edges
494 // between the two, a DotEdge is created
495 // for each of them and thus reserve
496 // spacing to accomodate widest label.
497 IEdge[] a = e.getOriginals();
498 //FIXME: Assume the first merged flat edge would be draw straight.
499 // left--xspacing/2--lw,rw--xspacing/2-->right
500 se = a[0];
501 lw = 0;
502 rw = 0;
503 bound = (Rectangle2D) se.getAttr("-bounds");
504 if (bound != null) {
505 lw = (int) (bound.getWidth() / 2);
506 // Width==0 if no label.
507 rw = lw;
508 }
509 createDotEdge(
510 head,
511 tail,
512 width + lw + rw,
513 //se.getAttrInt("-weight", 1));
514 e.weight);
515 } else {
516 dotv = (DotVertex) fVertexMap.get(e.tail);
517 if (dotv == null)
518 msg.err(METHOD + "dotv==null: e.tail=" + e.tail);
519 createDotEdge(tail, dotv, 0, e.weight);
520 }
521 }
522 }
523 xpos += width;
524 left = right;
525 tail = head;
526 }
527 }
528
529 // Create inter-rank edges.
530 //
531 // Edge weight is scaled to shorted long edges that involves VirtualVertex:
532 // IVertex->IVertex=1
533 // VirtualVertex->IVertex=1
534 // IVertex->VirtualVertex=4
535 // VirtualVertex->VirtualVertex=4
536
537 for (int vi = 0, offset, x; vi < vvts.length; ++vi) {
538 v = vvts[vi];
539 tail = (DotVertex) fVertexMap.get(v);
540 //left = (VirtualVertex) tail.getOriginal();
541 for (int weight, ei = 0; ei < v.outs.length; ++ei) {
542 e = v.outs[ei];
543 // right = (VirtualVertex) head.getOriginal();
544 // if (left.type == VirtualVertex.BUS || right.type == VirtualVertex.BUS)
545 // if (left.isReal() || right.isReal())
546 // scale = scaleBusVertex;
547 // else
548 // scale = scaleBus;
549 // else if (right.isVirtual())
550 // scale = scaleVirtual;
551 // else
552 // scale = scaleOther;
553 //left = right;
554 weight = e.weight;
555 if (e.head.isVirtual() && e.tail.isVirtual())
556 //if (e.head.isEdge() && e.tail.isEdge())
557 weight *= fWEIGHT_VIRTUALFACTOR;
558 // Edges to aux. vertex.
559 offset = (e.getHeadPortDx() - e.getTailPortDx());
560 //if(offset!=0) {//FIXME:
561 dotv = createDotVertex(e);
562 // Q: Why does it matter to have auxillary vertex?
563 // A: Original code put auxillary vertex at min x of
564 // the two vertices to produce an initially feasible
565 // graph, however, since we rebuild an init. graph
566 // anyway, so it doesn't matter. at the min. x side.
567 if (offset > 0)
568 x = 0;
569 else {
570 x = -offset;
571 offset = 0;
572 }
573 head = (DotVertex) fVertexMap.get(e.head);
574 // Q: Why add 1 to both minLength ?
575 // A: Original code add 1 to minLenghts, which
576 // produce same output.
577 createDotEdge(tail, dotv, offset + 1, weight);
578 createDotEdge(head, dotv, x + 1, weight);
579 //} else {
580 //createDotEdge(head,tail,0,weight);
581 //}
582 }
583 }
584 DotVertex[] vts = new DotVertex[fVertexMap.size()];
585 int nvts = 0;
586 for (Iterator it = fVertexMap.values().iterator(); it.hasNext();) {
587 vts[nvts++] = (DotVertex) it.next();
588 }
589 fVertexMap = null;
590 if (VERBOSE) {
591 timer.stop();
592 msg.println(METHOD + nvts + " DotVertex: elapsed=" + timer.toString());
593 }
594 return new DotGraph(g.getName(), vts);
595 }
596
597 // More intelligent spacing here to allow for more space if the passing edge
598 // has a gentle slope.
599 // private int xespacing(VirtualVertex v, int rankheight, int defaultspacing) {
600 // if(!v.isEdge()||v.x==0) return defaultspacing;
601 // VirtualVertex tail=v.ins[0].tail;
602 // VirtualVertex head=v.ins[0].head;
603 // double topslope=0;
604 // if(head.x-tail.x!=0) topslope=(head.y-tail.y)/(head.x-tail.x);
605 // tail=v.outs[0].tail;
606 // head=v.outs[0].head;
607 // double bottomslope=0;
608 // if(head.x-tail.x!=0) bottomslope=(head.y-tail.y)/(head.x-tail.x);
609 // if(topslope+bottomslope==0) return defaultspacing;
610 // int x=(int) (rankheight/(topslope+bottomslope)/2);
611 // if(x<defaultspacing) return defaultspacing;
612 // if(true) msg.println(NAME+".xespacing(): v="+v.getName()+", default="+defaultspacing+", x="+x);
613 // return x;
614 // }
615
616 private DotVertex createDotVertex(VirtualVertex v) {
617 DotVertex ret = new DotVertex(v.getName(), 0);
618 ret.setOriginal(v);
619 DotVertex old;
620 if ((old = (DotVertex) fVertexMap.put(v, ret)) != null)
621 msg.err(
622 NAME
623 + ".createDotVertex(VirtualVertex): duplicated mapping"
624 + ": v=\n\t"
625 + v
626 + "\n, old=\n\t"
627 + old
628 + ", new=\n\t"
629 + ret);
630 return ret;
631 }
632
633 /** Auxillary vertex that split the given VirtualEdge. */
634 private DotVertex createDotVertex(VirtualEdge e) {
635 DotVertex ret = new DotVertex(0);
636 DotVertex old;
637 if ((old = (DotVertex) fVertexMap.put(e, ret)) != null)
638 msg.err(
639 NAME
640 + ".createDotVertex(VirtualEdge): duplicated mapping"
641 + ": e=\n\t"
642 + e
643 + "+\n, old=\n\t"
644 + old
645 + ", new=\n\t"
646 + ret);
647 return ret;
648 }
649
650 private DotEdge createDotEdge(DotVertex head, DotVertex tail, int minlen, int weight) {
651 DotEdge ret = new DotEdge(head, tail, minlen, weight);
652 head.addIn(ret);
653 tail.addOut(ret);
654 return ret;
655 }
656
657 ////////////////////////////////////////////////////////////////////////
658
659 /** Print x-position rank result graph for debugging. */
660 private void printXPositionGraph(DotGraph g) {
661 StringBuffer ret = new StringBuffer("digraph " + g.getName() + "_xposition {\n");
662 DotVertex v;
663 VirtualVertex vv;
664 DotEdge e;
665 String name;
666 DotVertex[] vertices = g.getVertices();
667 for (int i = 0; i < vertices.length; ++i) {
668 v = vertices[i];
669 name = v.getName();
670 vv = (VirtualVertex) v.getOriginal();
671 ret.append(" \"" + name + "\" [label=\"" + name + "(" + v.rank);
672 if (vv != null)
673 ret.append(",r=" + vv.rank + ",o=" + vv.order);
674 if (name.startsWith("$"))
675 ret.append(")\",style=dotted];\n");
676 else
677 ret.append(")\",style=filled,fillcolor=gray");
678 ret.append("];\n");
679 }
680 ret.append("\n");
681 for (int i = 0; i < vertices.length; ++i) {
682 v = vertices[i];
683 for (int en = 0; en < v.outSize(); ++en) {
684 e = v.outs[en];
685 sprintXPositionEdge(ret, e);
686 while ((e = e.next) != null)
687 sprintXPositionEdge(ret, e);
688 }
689 }
690 ret.append("}\n");
691 msg.println(ret.toString());
692 }
693
694 private void sprintXPositionEdge(StringBuffer ret, DotEdge e) {
695 DotVertex head, tail;
696 //if(e.isReversed()) {
697 //head=e.tail;
698 //tail=e.head;
699 //} else {
700 head = e.head;
701 tail = e.tail;
702 //}
703 ret.append(" \""
704 //+tail.getName()+"(r="+tail.rank+")\"->\""
705 //+head.getName()+"(r="+head.rank+")\" [label="+e.cutValue
706 +tail.getName()
707 + "\"->\""
708 + head.getName()
709 + "\" [label=\""
710 + e.cutValue
711 + ",l="
712 + e.minLength
713 + ",w="
714 + e.weight
715 + "\"");
716 if (e.isReversed())
717 ret.append(",color=red");
718 if (e.treeIndex < 0)
719 ret.append(",style=dotted");
720 ret.append("];\n");
721 }
722
723 private void appendAttr(StringBuffer ret, IVertex v, String name) {
724 String s = v.getAttrAsString(name);
725 if (s != null)
726 ret.append(", \"" + name + "\"=\"" + s + "\"");
727 }
728
729 private void appendAttr(StringBuffer ret, IEdge e, String name) {
730 String s = e.getAttrAsString(name);
731 if (s != null)
732 ret.append(", \"" + name + "\"=\"" + s + "\"");
733 }
734
735 ////////////////////////////////////////////////////////////////////////
736
737 }