Source code: com/port80/graph/dot/impl/VirtualGraph.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.awt.Rectangle;
8 import java.awt.geom.Rectangle2D;
9 import java.util.ArrayList;
10 import java.util.Arrays;
11 import java.util.HashMap;
12 import java.util.HashSet;
13 import java.util.Iterator;
14 import java.util.LinkedList;
15 import java.util.List;
16 import java.util.Map;
17 import java.util.Set;
18 import java.util.SortedSet;
19 import java.util.TreeSet;
20
21 import com.port80.graph.IEdge;
22 import com.port80.graph.IGraph;
23 import com.port80.graph.IVertex;
24 import com.port80.graph.impl.Vertex;
25 import com.port80.util.Debug;
26 import com.port80.util.msg;
27
28 /** Virtual graph constructed for routing from a IGraph.
29 *
30 * . VirtualGraph is created by extracting the topology information
31 * from an input IGraph for routing.
32 *
33 * . Routing information are patched back to the original graph attribute
34 * table ('pos') and the VirtualGraph can be released after each
35 * layout.
36 *
37 * @see com.port80.graph.IGraph
38 */
39 public class VirtualGraph {
40
41 // Static fields ///////////////////////////////////////////////////////
42 //
43
44 private static final String NAME = "VirtualGraph";
45 private static final String PACKAGENAME = "com.port80.graph.dot.impl";
46 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
47 private static final int VERSION = 0x0101;
48 private static final String VERSIONNAME = "v0.1";
49 static {
50 Debug.add(CLASSNAME);
51 }
52 private static final boolean DEBUG = false;
53 private static final boolean TERSE = false;
54 private static boolean VERBOSE = Debug.isVerbose();
55 private static boolean CHECK = Debug.isCheck();
56
57 private static final boolean USE_MERGE = true;
58
59 // Instance fields /////////////////////////////////////////////////////
60 //
61
62 private VirtualVertex[] vertices; /** Working vertex list, fast graph nlist in dot. */
63
64 private String name;
65 private IGraph original;
66 private Map iedgeMap = new HashMap(); /** IEdge->VirtualEdge map.*/
67 private Map ivertexMap = new HashMap(); /** IVertex->VirtualVertex map.*/
68 private List fVertexList = new ArrayList(); /** List of all VirtualVertex.*/
69 private Map fVertexMap = new HashMap();
70 int minRank;
71 int maxRank;
72 //
73 boolean isLeftToRight = false; /** Layout graph in left->right orientation.*/
74 boolean hasFlatEdges = false; /** Graph has flat edges.*/
75 boolean hasLabel = false; /** Graph has edge labels.*/
76 boolean hasHeadTailLabel = false; /** Graph has edge head label or edge tail label.*/
77 //
78 int minQuit = 8;
79 int maxIter = 32;
80 Rectangle bounds = new Rectangle(0, 0, 0, 0); /** Graph bounds in pixel.*/
81
82 int rankSpacing; /** Min. spacing between ranks.*/
83 int vertexSpacing; /** Min. spacing between vertices. */
84 int fESpacing;
85 int fXESpacing;
86 int selfEdgeSize;
87 //
88 Rank[] ranks;
89 //
90 // Layout parameters from IGraph.
91 //
92 double rankSep; /** Scaling factor for rank dimensions.*/
93 double vertexSep; /** Scaling factor for vertex (sideway) dimensions.*/
94 int margin; /** Scaling factor (*vertexspacing) for graph margin.*/
95 int defaultHalfWidth; /** Default half width in pixels. */
96 int defaultHalfHeight; /** Default half height in pixels. */
97 //
98 int fYSPACING_XBUS;
99 int fYSPACING_BUSBUS;
100 int fHALFHEIGHT_VIRTUALVERTEX;
101 //
102 int fXDIV_EDGES;
103 int fXDIV_XEDGE;
104 //
105 int fXPENALTY_DEFAULT;
106 int fXPENALTY_BUS;
107 int fXPENALTY_CRITICAL;
108 int fXPENALTY_STUB;
109 int fXPENALTY_AUX;
110 double fDISTCOST;
111 //
112 int fWEIGHT_DEFAULT;
113 int fWEIGHT_BUS;
114 int fWEIGHT_CRITICAL;
115 int fWEIGHT_STUB;
116 int fWEIGHT_VIRTUALFACTOR;
117 //
118 int fCELL_XDIV;
119 int fCELL_BASICFACTOR;
120 int fCELL_DISTFACTOR;
121 int fCELL_TURNFACTOR;
122 int fPTP_PERCENT;
123 //
124 int fBOX_MINOVERLAP;
125 int fMERGE_OFFSET;
126 //
127 boolean fCriticalUseInBus;
128 boolean fCriticalUseOutBus;
129 boolean fBidirectionalUseBus;
130
131 //
132 //
133 //
134 /** Scratch path for rankCost(). */
135 int[] fCrossCounts = new int[100];
136
137 // Constructors ////////////////////////////////////////////////////////
138 //
139
140 /** Construct virtual graph for 'dot' mincross, using given ranked IGraph.
141 *
142 * . The VirtualGraph contains VirtualVertex created to represent
143 * the top level vertices and clusters of the input graph.
144 * Clusters are represented by VirtualVertex called 'rank
145 * leaders', one for each rank in the cluster.
146 *
147 * . Also for each edges that connects two vertices in different
148 * rank, a VirtualVertex is created as place holder along the
149 * route in each rank between the two vertices. The original
150 * edges are replaced by a VirtualEdge chain and the
151 * placeholder VirtualVertex along the route. If the edge has
152 * label, it would be represented by the VirtualVertex in the
153 * middle of the chain.
154 *
155 * . Flat edges (edge between vertex on the same rank),
156 * intra-cluster edges are ignored. Parallel edges between
157 * same pair of vertices and have same label (or no labels) are
158 * merged into one to make sure they would route together.
159 *
160 * . Bus vertices are added for each real vertex (say 'v') that
161 * have lots of input or output edges and new ranks for the bus
162 * vertices are inserted before and after 'v'. Ranks for
163 * vertices below 'v' are incremented accordingly.
164 *
165 * r-1 r-1
166 * . r --- new input bus rank ---
167 * r v -> r+1 v
168 * . r+2 --- new output bus rank ---
169 * r+1 r+3
170 *
171 * A VirtualVertex is created for each edge 'e' to 'v' in
172 * addition to a VirtualVertex for the connection from the bus
173 * to 'v'. Each edge 'e' is then terminated at the bus vertex
174 * instead of at 'v' and thus allow them to be rearranged
175 * independently.
176 *
177 * | |
178 * v v
179 * --'iv0'--'iv1'--'iv2'--
180 * |
181 * v
182 * 'v'
183 * |
184 * v
185 * --'ov0'--'ov1'--'ov2'--
186 * | |
187 * v v
188 *
189 */
190 public VirtualGraph(IGraph g) {
191
192 this.original = g;
193 this.name = g.getName();
194 //
195 // Layout parameters
196 //
197 this.margin = g.getAttrInt("margin");
198 this.rankSep = g.getAttrDouble("ranksep");
199 this.vertexSep = g.getAttrDouble("nodesep");
200 //
201 fYSPACING_BUSBUS = g.getAttrInt("yspacing_busbus");
202 fYSPACING_XBUS = (int) (g.getAttrInt("yspacing_xbus") * rankSep);
203 fHALFHEIGHT_VIRTUALVERTEX = (int) (g.getAttrInt("halfheight_virtualvertex") * rankSep);
204 //
205 fXDIV_EDGES = g.getAttrInt("xdiv_edges");
206 fXDIV_XEDGE = g.getAttrInt("xdiv_xedge");
207 //
208 fXPENALTY_DEFAULT = g.getAttrInt("xpenalty_default");
209 fXPENALTY_BUS = g.getAttrInt("xpenalty_bus");
210 fXPENALTY_CRITICAL = g.getAttrInt("xpenalty_critical");
211 fXPENALTY_STUB = g.getAttrInt("xpenalty_stub");
212 fXPENALTY_AUX = g.getAttrInt("xpenalty_aux");
213 fDISTCOST = g.getAttrDouble("xpenalty_dist");
214 //
215 // Position
216 fWEIGHT_DEFAULT = g.getAttrInt("virtual_weight_default");
217 fWEIGHT_BUS = g.getAttrInt("virtual_weight_bus");
218 fWEIGHT_CRITICAL = g.getAttrInt("virtual_weight_critical");
219 fWEIGHT_STUB = g.getAttrInt("virtual_weight_stub");
220 fWEIGHT_VIRTUALFACTOR = g.getAttrInt("virtual_weightfactor");
221 //
222 fCELL_XDIV = g.getAttrInt("cell_xdiv");
223 fCELL_BASICFACTOR = g.getAttrInt("cell_basicfactor");
224 fCELL_DISTFACTOR = g.getAttrInt("cell_distfactor");
225 fCELL_TURNFACTOR = g.getAttrInt("cell_turnfactor");
226 fPTP_PERCENT = g.getAttrInt("ptp_percent");
227 //
228 fBOX_MINOVERLAP = g.getAttrInt("box_minoverlap");
229 fMERGE_OFFSET = g.getAttrInt("merge_offset");
230 //
231 fCriticalUseInBus = g.getAttrBool("criticaluseinbus");
232 fCriticalUseOutBus = g.getAttrBool("criticaluseoutbus");
233 fBidirectionalUseBus = g.getAttrBool("bidirectionalusebus");
234 //
235 this.isLeftToRight = (g.getAttrString("rankdir").equals("LR"));
236 double mclimit = g.getAttrDouble("mclimit");
237 if (mclimit > 0) {
238 minQuit = (int) Math.max(1.0, minQuit * mclimit);
239 maxIter = (int) Math.max(1.0, maxIter * mclimit);
240 }
241 //
242 //
243 //
244 this.minRank = g.getAttrInt("-minrank");
245 this.maxRank = g.getAttrInt("-maxrank");
246 //
247 int hw = g.getAttrInt("default_halfwidth");
248 int hh = g.getAttrInt("default_halfheight");
249 this.defaultHalfWidth = (int) (vertexSep * hw); //FIXME:
250 this.defaultHalfHeight = (int) (rankSep * hh); //FIXME:
251 this.selfEdgeSize = defaultHalfWidth;
252 this.rankSpacing = defaultHalfHeight * 2;
253 this.vertexSpacing = defaultHalfWidth;
254 fESpacing = vertexSpacing / fXDIV_EDGES;
255 fXESpacing = vertexSpacing / fXDIV_XEDGE;
256 // * (Const.XPENALTY * Const.XPENALTY) / (vertexSpacing * vertexSpacing);
257
258 IVertex u;
259 VirtualVertex vv;
260
261 // Add vertices and clusters from IGraph.
262 addGraph(g);
263
264 // Populate vertices, ranks[r].vts and make edges. Sort
265 // IVertex for stability of output layout.
266 SortedSet sorted = new TreeSet(new Vertex.NameComparator());
267 sorted.addAll(ivertexMap.keySet());
268 SortedSet vvset = new TreeSet(new VirtualVertex.NameComparator());
269 vvset.addAll(ivertexMap.values());
270 adjustRanks(vvset);
271 // Construct edge chain for new created vertex-bus VirtualEdges.
272 for (Iterator it = vvset.iterator(); it.hasNext();) {
273 vv = (VirtualVertex) it.next();
274 if (vv.inBus != null)
275 //FIXME: Should check that vv actually connected to a BUS vertex
276 // the bus may not be used at all.
277 createStubChain(vv.inBus, vv);
278 if (vv.outBus != null)
279 createStubChain(vv, vv.outBus);
280 }
281 // Construct edge chain for original vertex-vertex IEdge(s).
282 IEdge[] a;
283 for (Iterator it = sorted.iterator(); it.hasNext();) {
284 u = (IVertex) it.next();
285 vv = (VirtualVertex) ivertexMap.get(u);
286 // Add edges.
287 a = u.outs();
288 for (int i = 0, max = a.length; i < max; ++i) {
289 createEdgeChain(vv, a[i]);
290 }
291 }
292 this.vertices = new VirtualVertex[fVertexList.size()];
293 this.ranks = new Rank[maxRank + 1];
294 for (int i = 0; i <= maxRank; ++i)
295 ranks[i] = new Rank();
296 for (int i = 0; i < fVertexList.size(); ++i) {
297 vv = (VirtualVertex) fVertexList.get(i);
298 this.vertices[i] = vv;
299 fVertexMap.put(vv.getName(), vv);
300 ranks[vv.rank].nVts++;
301 if (vv.isBus())
302 ranks[vv.rank].isBus = true;
303 if (DEBUG)
304 msg.println("vv=" + vv);
305 }
306 for (int r = minRank; r <= maxRank; ++r) {
307 if (DEBUG)
308 msg.println("r=" + r + ", nVts=" + ranks[r].nVts);
309 ranks[r].vts = new VirtualVertex[ranks[r].nVts];
310 }
311 Arrays.sort(vertices, new VirtualVertex.NameComparator());
312 // Dispose data structures no longer needed.
313 iedgeMap = null;
314 ivertexMap = null;
315 fVertexList.clear();
316 }
317
318 ////////////////////////////////////////
319
320 /**
321 * Install nodes in ranks (init_rank()).
322 *
323 * The initial ordering ensure that series-parallel graphs such
324 * as trees are drawn with no crossings. It tries searching in-
325 * and out-edges and takes the better of the two initial
326 * orderings.
327 */
328 public void buildRanks(int pass) {
329 if (DEBUG)
330 msg.println(NAME + ".buildRanks()");
331 VirtualVertex v;
332 List queue = new LinkedList();
333 Set visited = new HashSet();
334
335 for (int r = minRank; r <= maxRank; r++) {
336 ranks[r].valid = false;
337 ranks[r].nVts = 0;
338 }
339 for (int i = 0; i < vertices.length; ++i) {
340 v = vertices[i];
341 if (pass % 2 == 0 && v.ins.length != 0)
342 continue; // Down pass, roots have no in edges.
343 if (pass % 2 == 1 && v.outs.length != 0)
344 continue; // Up pass, start at leaves.
345 if (visited.add(v)) {
346 queue.add(v);
347 while (queue.size() > 0) {
348 v = (VirtualVertex) queue.remove(0);
349 if (DEBUG)
350 msg.println(NAME + ".buildRanks(): v=" + v.getName());
351 //if(v.cluster==null) {
352 buildVertex(v);
353 queueNeighbours(v, visited, queue, pass);
354 //} else {
355 // Install cluster rank leaders.
356 //install_cluster(g,n0,pass,q);
357 //}
358 }
359 }
360 }
361 if (queue.size() != 0 || visited.size() != vertices.length)
362 msg.err(
363 NAME
364 + ".buildRanks(): queue.size()!=0 || visited.size()!=vertices.length"
365 + ": pass="
366 + pass
367 + ": size="
368 + queue.size()
369 + ", visited.size()="
370 + visited.size()
371 + ", vertices.length="
372 + vertices.length);
373 // Turn this on when there are size mismatch to find out which vertex is not visited.
374 if (CHECK) {
375 for (int i = 0; i < vertices.length; ++i) {
376 if (!visited.remove(vertices[i]))
377 visited.add(vertices[i]);
378 }
379 for (Iterator it = visited.iterator(); it.hasNext();) {
380 msg.println(NAME + ".buildRanks(): !visited: " + it.next());
381 }
382 }
383 Rank rank;
384 for (int r = minRank; r <= maxRank; r++) {
385 rank = ranks[r];
386 rank.valid = false;
387 //NOTE: In Java coordinate system with origin at
388 // upper-left corner, we don't need to reverse the vertex
389 // list.
390 // @see initFlatOrder(VirtualVertex,Set,List)
391 /*
392 VirtualVertex[] vts;
393 int n,order;
394 if(isLeftToRight && (rank.nVts>0)) {
395 vts=rank.vts;
396 n=rank.nVts;
397 for(int i=0; i<=n/2; i++) {
398 // Reverse vertex list.
399 v=vts[i];
400 vts[i]=vts[n-i];
401 vts[n-i]=v;
402 order=v.order;
403 v.order=vts[n-i].order;
404 vts[n-i].order=order;
405 }
406 }
407 */
408 }
409 if (false)
410 sanityCheck();
411 }
412
413 /** Install a node at the current right end of its rank */
414 private void buildVertex(VirtualVertex v) {
415 Rank rank = ranks[v.rank];
416 if (DEBUG)
417 msg.println(
418 NAME + ".buildVertex(): r=" + v.rank + ", nVts=" + rank.nVts + ", v=" + v.getName());
419 int order = rank.nVts++;
420 rank.vts[order] = v;
421 v.order = order;
422 }
423
424 /** Queue decendents/ancestors from v.
425 */
426 private void queueNeighbours(VirtualVertex v, Set visited, List queue, int pass) {
427 VirtualEdge e;
428
429 if (pass % 2 == 0) {
430 for (int i = 0; i < v.outs.length; i++) {
431 e = v.outs[i];
432 if (visited.add(e.head))
433 queue.add(e.head);
434 }
435 } else {
436 for (int i = 0; i < v.ins.length; i++) {
437 e = v.ins[i];
438 if (visited.add(e.tail))
439 queue.add(e.tail);
440 }
441 }
442 }
443
444 ////////////////////////////////////////
445
446 /** Add vertices, cluster rank leaders. Only top level clusters
447 * (g.parent.parent==null) would be added. All vertices in the
448 * top level cluster and its sub-clusters should be collapsed into
449 * its rank leaders.
450 */
451 private void addGraph(IGraph g) {
452 if (g.isCluster()) {
453 // Clusters are ranked internally and represented by its leader.
454 //FIXME:
455 /*
456 if(g.getParent()!=null && g.getParent().getParent()==null) {
457 // Top level cluster.
458 if(vertexMap.get(g)==null) {
459 for(int r=g.getMinRank(); r<=g.getMaxRank(); r++) {
460 v=new VirutalVertex(g,r);
461 vertexMap.put(g,v);
462 }
463 }
464 }
465 */
466 } else {
467 // Add vertices.
468 Set vset = g.getVertexSet();
469 IVertex v;
470 VirtualVertex vv;
471 int rank;
472 for (Iterator it = vset.iterator(); it.hasNext();) {
473 v = (IVertex) it.next();
474 if (ivertexMap.get(v) == null) {
475 vv = new VirtualVertex(v, this);
476 ivertexMap.put(v, vv);
477 fVertexList.add(vv);
478 if (v.inSize() > v.getAttrInt("inthreshold", Integer.MAX_VALUE)) {
479 rank = v.getAttrInt("-rank", 0);
480 vv.inBus = VirtualVertex.newBusVertex(v, rank, this);
481 fVertexList.add(vv.inBus);
482 }
483 if (v.outSize() > v.getAttrInt("outthreshold", Integer.MAX_VALUE)) {
484 rank = v.getAttrInt("-rank", 0);
485 vv.outBus = VirtualVertex.newBusVertex(v, rank, this);
486 fVertexList.add(vv.outBus);
487 }
488 }
489 }
490 }
491 // Recursively add subgraph.
492 List subs = g.getSubGraphs();
493 for (int i = 0, max = subs.size(); i < max; ++i) {
494 g = (IGraph) subs.get(i);
495 addGraph(g);
496 }
497 }
498
499 /** For now, we ignore all the cluster stuff first. */
500 private void initCluster() {}
501
502 ////////////////////////////////////////
503
504 /**
505 * Create an VirtualEdge chain for the given IEdge.
506 * @param tail.
507 * @param e an out edge from tail.
508 */
509 private void createEdgeChain(VirtualVertex tail, IEdge e) {
510
511 VirtualEdge ve = (VirtualEdge) iedgeMap.get(e);
512 if (ve != null)
513 msg.err(NAME + ".createEdgeChain(): ve==null" + ": e=" + e + ": ve=" + ve);
514
515 // IVertex under a cluster should have been mapped to its
516 // cluster's rank leader.
517 VirtualVertex head = (VirtualVertex) ivertexMap.get(e.getHead());
518 if (head.equals(tail)) {
519 // Self edge.
520 head.addSelfEdge(VirtualEdge.newSelfEdge(head, e, null, this));
521 return;
522 }
523
524 // Create a new bus vertex for each bus connection end points.
525 // . There is option to not use buses for bidirectional edges since that make
526 // it hard to determine if there is a reverse edge.
527 // . There is also option to disable critical edges to use buses.
528 // . An aux. chain is created from the real vertex to the bus vertices to make
529 // sure Mincross group the vertices together.
530 VirtualVertex headv = head;
531 VirtualVertex tailv = tail;
532 boolean auxstub = false;
533 if (head.inBus != null) {
534 if (fBidirectionalUseBus || e.findReverseEdges(null) == null) {
535 if (fCriticalUseInBus || !e.getAttrBool("critical")) {
536 headv = head;
537 head =
538 VirtualVertex.newBusVertex(
539 (IVertex) head.getOriginal(),
540 head.inBus.rank,
541 this);
542 fVertexList.add(head);
543 createAuxChain(head, headv, headv.getName());
544 }
545 } else {
546 auxstub = true;
547 headv = head.inBus;
548 }
549 }
550 if (tail.outBus != null) {
551 if (fBidirectionalUseBus || e.findReverseEdges(null) == null) {
552 if (fCriticalUseOutBus || !e.getAttrBool("critical")) {
553 tailv = tail;
554 tail =
555 VirtualVertex.newBusVertex(
556 (IVertex) tail.getOriginal(),
557 tail.outBus.rank,
558 this);
559 fVertexList.add(tail);
560 createAuxChain(tailv, tail, tailv.getName());
561 }
562 } else {
563 auxstub = true;
564 tailv = tail.outBus;
565 }
566 }
567 // . An aux. chain from the stub vertex to any vertices the real vertex is
568 // connected to directly to make sure Mincross move the stub and real
569 // vertex close to the vertices that the real vertex is directly connected to.
570 if (auxstub) {
571 createAuxChain(tailv, headv, headv.getName());
572 }
573
574 int headrank = head.getRank();
575 int tailrank = tail.getRank();
576
577 if (headrank == tailrank) {
578 // Flat edge. Flat edge labels are ignored till
579 // dotPosition().
580 ve = VirtualEdge.newFlatEdge(head, tail, e, this);
581 iedgeMap.put(e, ve);
582 return;
583 }
584
585 String label = e.getAttrString("label");
586 int labelrank = -1;
587 if (label != null) {
588 labelrank = (headrank + tailrank) / 2;
589 hasLabel = true;
590 }
591
592 // New chain.
593 boolean isbus = (tail.isBus() || head.isBus());
594 boolean critical = e.getAttrBool("critical");
595 if (headrank > tailrank) {
596 // Forward edge.
597 // tail(r0)->v->v->head(rn)
598 ve = tail.findOutChain(head);
599 if (USE_MERGE) {
600 if ((label == null && Math.abs(headrank - tailrank) == 1)
601 || (!critical && !(fBidirectionalUseBus && isbus))) {
602 if (ve != null) { // Multi edge.
603 ve.mergeChain(e);
604 expandMergedChainWidth(ve);
605 iedgeMap.put(e, ve);
606 return;
607 }
608 }
609 }
610 tailv = tail;
611 for (int r = tailrank + 1; r <= headrank; ++r) {
612 if (r == headrank)
613 headv = head;
614 else if (r == labelrank)
615 headv = new VirtualVertex(r, label, e, this);
616 else
617 headv = new VirtualVertex(r, e, this);
618 if (r != headrank)
619 fVertexList.add(headv);
620 ve =
621 isbus
622 ? VirtualEdge.newBusEdge(headv, tailv, e, ve, this)
623 : VirtualEdge.newEdge(headv, tailv, e, ve, this);
624 if (tailv.equals(tail))
625 iedgeMap.put(e, ve);
626 tailv = headv;
627 }
628 } else {
629 // Backward edge.
630 // head<-e-tail
631 if (USE_MERGE) {
632 if ((label == null && Math.abs(headrank - tailrank) == 1)
633 || (!critical && !(fBidirectionalUseBus && isbus))) {
634 ve = head.findOutChain(tail);
635 if (ve != null) { // Merge to the reverse chain.
636 ve.mergeChain(e);
637 expandMergedChainWidth(ve);
638 iedgeMap.put(e, ve);
639 return;
640 }
641 }
642 }
643 // Create a reverse chain. head(r0)->v->v->tail(rn)
644 tailv = head;
645 for (int r = headrank + 1; r <= tailrank; ++r) {
646 if (r == tailrank)
647 headv = tail;
648 else if (r == labelrank)
649 headv = new VirtualVertex(r, label, e, this);
650 else
651 headv = new VirtualVertex(r, e, this);
652 if (r != tailrank)
653 fVertexList.add(headv);
654 ve =
655 isbus
656 ? VirtualEdge.newBusEdge(headv, tailv, e, ve, this)
657 : VirtualEdge.newEdge(headv, tailv, e, ve, this);
658 if (tailv.equals(head))
659 iedgeMap.put(e, ve);
660 tailv = headv;
661 }
662 }
663 }
664
665 private void expandMergedChainWidth(VirtualEdge e) {
666 while (e.prev != null)
667 e = e.prev;
668 while (e.next != null) {
669 e.head.padding += fMERGE_OFFSET;
670 e = e.next;
671 }
672 }
673
674 /**
675 * Create an edge chain for connections between a vertex
676 * and its inBus and outBus.
677 */
678 private void createStubChain(VirtualVertex tail, VirtualVertex head) {
679 VirtualVertex v;
680 VirtualEdge ve = null;
681 for (int r = tail.rank + 1; r <= head.rank; ++r) {
682 if (r == head.rank)
683 v = head;
684 else {
685 v = new VirtualVertex(r, null, this);
686 fVertexList.add(v);
687 }
688 ve = VirtualEdge.newStubEdge(v, tail, ve, this);
689 tail = v;
690 }
691 }
692
693 /**
694 * Create an edge chain for connections between a vertex
695 * and its inBus and outBus duplicates.
696 */
697 private void createAuxChain(VirtualVertex tail, VirtualVertex head, String name) {
698 VirtualVertex v;
699 VirtualEdge ve = null;
700 for (int r = tail.rank + 1; r <= head.rank; ++r) {
701 if (r == head.rank)
702 v = head;
703 else {
704 v = VirtualVertex.newAuxVertex(name, r, this);
705 fVertexList.add(v);
706 }
707 ve = VirtualEdge.newAuxEdge(v, tail, ve, this);
708 tail = v;
709 }
710 }
711
712 public void removeAux() {
713 Rank rank;
714 VirtualVertex v;
715 VirtualEdge e;
716 fVertexList.clear();
717 fVertexMap.clear();
718 int ne = 0;
719 int nv = 0;
720 //
721 // Remove aux. edges and vertices
722 //
723 for (int r = minRank; r <= maxRank; ++r) {
724 rank = ranks[r];
725 rank.valid = false;
726 if (false)
727 msg.println(NAME + ".removeAux(): start: r=" + r + ", nVts=" + rank.nVts);
728 for (int i = 0, max = rank.nVts; i >= 0 && i < max; ++i) {
729 v = rank.vts[i];
730 for (int k = 0, maxe = v.outs.length; k < maxe; ++k) {
731 e = v.outs[k];
732 if (e.isAux()) {
733 e.tail.removeOut(e);
734 e.head.removeIn(e);
735 if (DEBUG)
736 msg.println(
737 NAME
738 + ".removeAux(): removed out edge: e="
739 + e.getName());
740 --k;
741 --maxe;
742 ++ne;
743 }
744 }
745 for (int k = 0, maxe = v.ins.length; k < maxe; ++k) {
746 e = v.ins[k];
747 if (e.isAux()) {
748 e.tail.removeOut(e);
749 e.head.removeIn(e);
750 if (DEBUG)
751 msg.println(
752 NAME
753 + ".removeAux(): removed in edge: e="
754 + e.getName());
755 --k;
756 --maxe;
757 ++ne;
758 }
759 }
760 // Remove aux. vertex.
761 if (v.isAux()) {
762 if (DEBUG)
763 msg.println(NAME + ".removeAux(): removed vertex: v=" + v.getName());
764 rank.remove(i);
765 --i;
766 --max;
767 ++nv;
768 } else {
769 fVertexList.add(v);
770 }
771
772 }
773 if (false) {
774 msg.println(NAME + ".removeAux(): r=" + r + ", nVts=" + rank.nVts);
775 for (int i = 0; i < rank.nVts; ++i)
776 msg.println(
777 NAME
778 + ".removeAux(): "
779 + rank.vts[i].getName()
780 + ", order="
781 + rank.vts[i].order);
782 }
783 }
784 if (VERBOSE)
785 msg.println(NAME + ".removeAux(): removed " + ne + " edges, " + nv + " vertices");
786 //
787 // Rebuild the vertex list and vertex map.
788 //
789 vertices = new VirtualVertex[fVertexList.size()];
790 for (int i = 0; i < fVertexList.size(); ++i) {
791 v = (VirtualVertex) fVertexList.get(i);
792 vertices[i] = v;
793 fVertexMap.put(v.getName(), v);
794 }
795 Arrays.sort(vertices, new VirtualVertex.NameComparator());
796 }
797
798 /**
799 * @return A List of VirtualChain for all the inter-rank edge chains in the graph.
800 */
801 public List getChainList() {
802 VirtualEdge[] outs;
803 VirtualEdge e;
804 List ret = new ArrayList(vertices.length);
805 for (int i = 0; i < vertices.length; ++i) {
806 outs = vertices[i].outs;
807 for (int k = 0; k < outs.length; ++k) {
808 e = outs[k];
809 if (e.prev == null)
810 ret.add(new VirtualChain(e));
811 }
812 }
813 return ret;
814 }
815
816 ////////////////////////////////////////////////////////////////////////
817
818 /** Adjust VirtualVertex ranks to account for new created buses.*/
819 private void adjustRanks(SortedSet sorted) {
820 VirtualVertex v;
821 for (Iterator it = sorted.iterator(); it.hasNext();) {
822 v = (VirtualVertex) it.next(); // This increment rank of v and v.outBus too.
823 if (v.inBus != null) {
824 incrRank(v.rank);
825 --v.inBus.rank;
826 }
827 if (v.outBus != null) {
828 incrRank(v.rank + 1);
829 ++v.outBus.rank;
830 }
831 }
832 }
833
834 /** Increment rank of all VirtualVertex whose rank>=v.rank except v itself.*/
835 private void incrRank(int rank) {
836 VirtualVertex v;
837 for (int i = 0, max = fVertexList.size(); i < max; ++i) {
838 v = (VirtualVertex) fVertexList.get(i);
839 if (v.rank >= rank) {
840 ++v.rank;
841 if (v.rank > maxRank)
842 maxRank = v.rank;
843 }
844 }
845 }
846
847 // Instance methods ////////////////////////////////////////////////////
848 //
849 public String getName() {
850 return name;
851 }
852 public IGraph getOriginal() {
853 return original;
854 }
855 public VirtualVertex getVertex(String name) {
856 return (VirtualVertex) fVertexMap.get(name);
857 }
858 public VirtualVertex[] getVertices() {
859 return vertices;
860 }
861 //public int numOfEdges() { return edgeMap.size();}
862 public void setMinRank(int min) {
863 minRank = min;
864 }
865 public void setMaxRank(int max) {
866 maxRank = max;
867 }
868 public int getHeight() {
869 return bounds.height;
870 }
871 public int getWidth() {
872 return bounds.width;
873 }
874 public Rectangle getBounds() {
875 return bounds;
876 }
877 public double getRankSep() {
878 return rankSep;
879 }
880 public double getVertexSep() {
881 return vertexSep;
882 }
883 public int getMargin() {
884 return margin;
885 }
886 public int getDefaultHalfWidth() {
887 return defaultHalfWidth;
888 }
889 public int getDefaultHalfHeight() {
890 return defaultHalfHeight;
891 }
892 public int getRankSpacing() {
893 return rankSpacing;
894 }
895 public int getVertexSpacing() {
896 return vertexSpacing;
897 }
898 public int getESpacing() {
899 return fESpacing;
900 }
901 public int getXESpacing() {
902 return fXESpacing;
903 }
904 public int getSelfEdgeSize() {
905 return selfEdgeSize;
906 }
907 public boolean hasLabel() {
908 return hasLabel;
909 }
910 public boolean hasHeadTailLabel() {
911 return hasHeadTailLabel();
912 }
913
914 public void setWidth(int w) {
915 bounds.width = w;
916 }
917 public void setHeight(int h) {
918 bounds.height = h;
919 }
920
921 public void clear() {
922 original = null;
923 vertices = null;
924 }
925
926 public String toString() {
927 StringBuffer ret = new StringBuffer("### VirtualGraph: " + name + " {\n");
928 VirtualVertex v;
929 VirtualEdge e;
930 for (int i = 0; i < vertices.length; ++i) {
931 v = vertices[i];
932 ret.append(" " + v + "\n");
933 }
934 ret.append("\n");
935 for (int i = 0; i < vertices.length; ++i) {
936 v = vertices[i];
937 for (int en = 0; en < v.outs.length; ++en) {
938 e = v.outs[en];
939 ret.append(" " + e + "\n");
940 }
941 }
942 ret.append("\n");
943 return ret.toString();
944 }
945
946 public void updateBoundBox(int x, int y, int w, int h) {
947 if (x < bounds.x)
948 bounds.x = x;
949 if (y < bounds.y)
950 bounds.y = y;
951 if (x + w > bounds.x + bounds.width)
952 bounds.width = x + w - bounds.x;
953 if (y + h > bounds.y + bounds.height)
954 bounds.height = y + h - bounds.y;
955 if (bounds.x < 0 || bounds.y < 0)
956 msg.warn(
957 NAME
958 + ".updateBoundBox(): negative bound: x="
959 + bounds.x
960 + ", y"
961 + bounds.y
962 + ", width="
963 + bounds.width
964 + ", height="
965 + bounds.height);
966 }
967 public void updateBoundBox(Rectangle r) {
968 updateBoundBox(r.x, r.y, r.width, r.height);
969 }
970
971 // Algorithm methods ///////////////////////////////////////////////////
972 //
973
974 /** Save current ordering.
975 */
976 public void saveOrder() {
977 Rank rank;
978 VirtualVertex v;
979 for (int r = minRank; r <= maxRank; ++r) {
980 rank = ranks[r];
981 for (int i = 0; i < rank.nVts; ++i) {
982 v = rank.vts[i];
983 v.savedOrder = v.order;
984 v.savex = v.x;
985 }
986 }
987 if (false)
988 sanityCheck();
989 }
990
991 /** Restore saved ordering.
992 */
993 public void restoreOrder() {
994 VirtualVertex v;
995 Rank rank;
996 for (int r = minRank; r <= maxRank; ++r) {
997 rank = ranks[r];
998 for (int i = 0; i < rank.nVts; ++i) {
999 v = rank.vts[i];
1000 v.order = v.savedOrder;
1001 v.x = v.savex;
1002 }
1003 rank.valid = false;
1004 Arrays.sort(rank.vts, 0, rank.nVts, new VirtualVertex.OrderComparator());
1005 }
1006 if (false)
1007 sanityCheck();
1008 }
1009
1010 public void resetCost() {
1011 Rank rank;
1012 for (int r = minRank; r <= maxRank; ++r) {
1013 rank = ranks[r];
1014 rank.valid = false;
1015 }
1016 }
1017
1018 ////////////////////////////////////////
1019
1020 /** Determine crossing cost if vertex has port. */
1021 private int localCost(VirtualVertex v, boolean tobottom) {
1022 VirtualEdge e, f;
1023 int cost = 0;
1024 VirtualEdge[] a;
1025 if (tobottom)
1026 a = v.outs;
1027 else
1028 a = v.ins;
1029 for (int i = 0; i < a.length; ++i) {
1030 e = a[i];
1031 for (int j = i + 1; j < a.length; ++j) {
1032 f = a[j];
1033 if (tobottom) {
1034 if ((f.head.order - e.head.order) * (f.tailPort.dx - e.tailPort.dx) < 0)
1035 cost += e.xPenalty * f.xPenalty;
1036 } else {
1037 if ((f.tail.order - e.tail.order) * (f.headPort.dx - e.headPort.dx) < 0)
1038 cost += e.xPenalty * f.xPenalty;
1039 }
1040 }
1041 }
1042 if (DEBUG)
1043 msg.println(NAME + ".localCost(): cost=" + cost);
1044 return cost;
1045 }
1046
1047 /**
1048 * Determine total real crossing cost between the specified rank (r)
1049 * and the one below (r+1).
1050 *
1051 * cost=sum(e.xPenalty*f.xPenalty) for every edges e & f that
1052 * crossed.
1053 *
1054 * Used by Mincross.
1055 */
1056 private int rankCost(int r) {
1057 VirtualVertex v;
1058 VirtualEdge e;
1059 int order;
1060 Rank rank = ranks[r];
1061 VirtualVertex[] vts = rank.vts;
1062 int[] counts = new int[ranks[r + 1].nVts];
1063 int cost = 0;
1064 int max = 0;
1065 for (int vn = 0; vn < rank.nVts; ++vn) {
1066 v = vts[vn];
1067 if (max > 0) {
1068 for (int i = 0; i < v.outs.length; ++i) {
1069 e = v.outs[i];
1070 for (order = e.head.order + 1; order <= max; order++) {
1071 // Any edge going to <=max crossed some edges.
1072 cost += counts[order] * e.xPenalty;
1073 if (false)
1074 msg.println(
1075 NAME
1076 + ".rankCost(): v="
1077 + v.getName()
1078 + ", head="
1079 + e.head.getName()
1080 + ", order="
1081 + order
1082 + ", counts="
1083 + counts[order]
1084 + ", cost="
1085 + cost);
1086 }
1087 }
1088 } // Crossing between edges from same node don't count. So
1089 // we have to do this after determing of the cost.
1090 for (int i = 0; i < v.outs.length; ++i) {
1091 e = v.outs[i];
1092 order = e.head.order;
1093 if (order > max)
1094 max = order;
1095 if (false)
1096 msg.println(
1097 "\t# rank="
1098 + r
1099 + ", counts.length="
1100 + counts.length
1101 + ", e="
1102 + e
1103 + ", tailrank="
1104 + e.tail.rank
1105 + ", headrank="
1106 + e.head.rank
1107 + ", i="
1108 + i
1109 + ", len="
1110 + v.outs.length
1111 + ", order="
1112 + order);
1113 counts[order] += e.xPenalty;
1114 }
1115 if (false)
1116 msg.println(
1117 NAME + ".rankCost(): r=" + r + ", v=" + v.getName() + ", v.order=" + v.order);
1118 if (false)
1119 print(counts);
1120 }
1121 rank.crossCost = cost; //
1122 for (int i = 0; i < rank.nVts; ++i) {
1123 v = vts[i];
1124 if (v.hasPort)
1125 cost += localCost(v, true);
1126 // if (v.x != 0) {
1127 // cost += headDistCost(v, v.x); // Second pass.
1128 // cost += tailDistCost(v, v.x);
1129 // }
1130 }
1131 for (int i = 0; i < counts.length; ++i) {
1132 v = ranks[r + 1].vts[i];
1133 if (v.hasPort)
1134 cost += localCost(v, false);
1135 }
1136 rank.totalCost = cost;
1137 rank.valid = true;
1138 if (DEBUG) {
1139 msg.println(
1140 NAME + ".rankCost(): r=" + r + ", crosscost=" + rank.crossCost + ", totalcost=" + cost);
1141 //print(counts);
1142 }
1143 return cost;
1144 }
1145
1146 private void print(int[] counts) {
1147 for (int i = 0; i < counts.length; ++i)
1148 msg.print(" " + i + "=" + counts[i]);
1149 msg.println("");
1150 }
1151
1152 /** Determine the crossing cost for current ordering. */
1153 public int totalCost() {
1154 Rank rank;
1155 int crosscost = 0;
1156 int totalcost = 0;
1157 if (false)
1158 sanityCheck();
1159 for (int r = minRank; r < maxRank; r++) {
1160 rank = ranks[r];
1161 if (!rank.valid)
1162 rankCost(r);
1163 crosscost += rank.crossCost;
1164 totalcost += rank.totalCost;
1165 }
1166 if (DEBUG)
1167 msg.println(NAME + ".totalCost(): crosscost=" + crosscost + ", totalcost=" + totalcost);
1168 return totalcost;
1169 }
1170
1171 ////////////////////////////////////////
1172
1173 public void breakFlatCycles() {
1174 if (DEBUG)
1175 msg.println(NAME + ".breakFlatCycles()");
1176 boolean hasFlat;
1177 Rank rank;
1178 VirtualVertex v;
1179 for (int r = minRank; r <= maxRank; r++) {
1180 hasFlat = false;
1181 rank = ranks[r];
1182 for (int i = 0; i < rank.nVts; i++) {
1183 v = rank.vts[i];
1184 if ((v.flatOuts.length > 0) && (!hasFlat)) {
1185 rank.flatMatrix = new AdjacencyMatrix(rank.nVts, rank.nVts);
1186 hasFlat = true;
1187 }
1188 }
1189 if (hasFlat) {
1190 hasFlatEdges = true;
1191 Set visited = new HashSet();
1192 Set ancestors = new HashSet();
1193 for (int i = 0; i < rank.nVts; i++) {
1194 v = rank.vts[i];
1195 if (visited.add(v) && v.flatOuts.length > 0) {
1196 breakFlatCycles(v, visited, ancestors, rank.flatMatrix);
1197 }
1198 }
1199 }
1200 }
1201 }
1202
1203 /** Look for cycles starting from given vertex 'v'. */
1204 private void breakFlatCycles(VirtualVertex v, Set visited, Set ancestors, AdjacencyMatrix matrix) {
1205 VirtualEdge e, rev;
1206 int headindex, tailindex;
1207 ancestors.add(v);
1208 for (int i = 0, max = v.flatOuts.length; i < max; ++i) {
1209 e = v.flatOuts[i];
1210 //if(e.weight==0) continue;
1211 headindex = e.head.flatIndex;
1212 tailindex = e.tail.flatIndex;
1213 if (headindex >= matrix.nRows)
1214 msg.err(NAME + ".breakFlatCycles(VirtualVertex): headindex>=matrix.nRows" + ": e=" + e);
1215 if (tailindex >= matrix.nCols)
1216 msg.err(NAME + ".breakFlatCycles(VirtualVertex): tailindex>=matrix.nCols" + ": e=" + e);
1217 if (ancestors.contains(e.head)) {
1218 matrix.set(headindex, tailindex, 1);
1219 // Reversed head->tail.
1220 rev = e.findReverseFlatEdge();
1221 if (USE_MERGE && rev != null) {
1222 rev.merge(e);
1223 } else {
1224 e.reverse();
1225 } // In both case, edge 'e' would be removed from v.flatOuts.
1226 i--;
1227 max--;
1228 } else {
1229 matrix.set(tailindex, headindex, 1); // tail->head
1230 if (visited.add(e.head))
1231 breakFlatCycles(e.head, visited, ancestors, matrix);
1232 }
1233 }
1234 ancestors.remove(v);
1235 }
1236
1237 ////////////////////////////////////////////////////////////////////////
1238
1239 /** Init. order of the nodes in each rank.
1240 *
1241 * This may be done by a depth-first or breadth-first search
1242 * starting with vertices of minimum rank. Vertices are assigned
1243 * positions in their ranks in left-to-right order as the search
1244 * progresses. This strategy ensures that the initial ordering of
1245 * a tree has no crossings.
1246 */
1247 public void initFlatOrder() {
1248 if (DEBUG)
1249 msg.println(NAME + ".initFlatOrder()");
1250 if (!hasFlatEdges)
1251 return;
1252 Rank rank;
1253 VirtualVertex v;
1254 for (int r = minRank; r <= maxRank; ++r) {
1255 rank = ranks[r];
1256 Set visited = new HashSet();
1257 List tmp = new ArrayList();
1258 for (int i = 0; i < rank.nVts; ++i) {
1259 v = rank.vts[i];
1260 if (v.flatIns.length == 0 && v.flatOuts.length == 0) {
1261 tmp.add(v);
1262 continue;
1263 } // Since cycles are broken, there should be a root
1264 // with no in edges.
1265 if (v.flatIns.length == 0 && visited.add(v)) {
1266 initFlatOrder(v, visited, tmp);
1267 }
1268 }
1269 if (tmp.size() != rank.nVts)
1270 msg.err(
1271 NAME
1272 + ".initFlatOrder(): tmp.size()!=rank.nVts"
1273 + ": rank="
1274 + r
1275 + ": tmp.size()="
1276 + tmp.size()
1277 + ": rank.nVts="
1278 + rank.nVts);
1279 for (int i = 0; i < rank.nVts; ++i) {
1280 v = (VirtualVertex) tmp.get(i);
1281 rank.vts[i] = v;
1282 v.order = i;
1283 v.flatIndex = v.order;
1284 }
1285 }
1286 }
1287
1288 /**
1289 * Construct reachable vertex from 'v' in post-order.
1290 * This is the same as doing a topological sort in reverse order.
1291 *
1292 * NOTE: In original code, order is left-to-right from tail->head
1293 * if rankdir=top-to-bottom and reversed otherwise. Probably
1294 * because 'dot' coordinate system have origin at the lower left
1295 * corner instead of upper-left corner as in Java. In Java
1296 * coordinate system, we don't have to reverse.
1297 */
1298 private void initFlatOrder(VirtualVertex v, Set visited, List ret) {
1299 VirtualEdge e;
1300 ret.add(v);
1301 for (int i = 0; i < v.flatOuts.length; ++i) {
1302 e = v.flatOuts[i];
1303 if (visited.add(e.getHead()))
1304 initFlatOrder(e.getHead(), visited, ret);
1305 }
1306 }
1307
1308 // Debugging methods ///////////////////////////////////////////////////
1309 //
1310 public void debugPrintRanks() {
1311 Rank rank;
1312 VirtualVertex v;
1313 StringBuffer buf = new StringBuffer();
1314 for (int r = minRank; r <= maxRank; ++r) {
1315 rank = ranks[r];
1316 buf.append("# r=" + r);
1317 for (int i = 0; i < rank.nVts; ++i) {
1318 v = rank.vts[i];
1319 buf.append("\n\t" + v.toString());
1320 }
1321 buf.append("\n");
1322 }
1323 msg.print(buf.toString());
1324 }
1325
1326 public void plotMinCross() {
1327 VirtualVertex v;
1328 VirtualEdge e;
1329 Rank rank;
1330 StringBuffer ret = new StringBuffer("\ndigraph mincross {\n");
1331 for (int r = minRank; r <= maxRank; r++) {
1332 rank = ranks[r];
1333 ret.append(" subgraph cluster_" + r + " { style=invis; rank=same;\n");
1334 for (int i = rank.nVts - 1; i >= 0; --i) {
1335 v = rank.vts[i];
1336 ret.append("\t\"" + v.getName() + "\" [ label=\"" + v.getName() + "(o=" + v.order
1337 //+",m="+(v.median>>8)
1338 +")\"");
1339 if (v.getName().startsWith("$"))
1340 ret.append("];\n");
1341 else
1342 ret.append(",style=filled,fillcolor=gray75];\n");
1343 }
1344 ret.append(" }\n");
1345 }
1346 for (int i = 0; i < vertices.length; ++i) {
1347 v = vertices[i];
1348 for (int j = 0; j < v.outs.length; ++j) {
1349 e = v.outs[j];
1350 ret.append("\t\"" + e.tail.getName() + "\"->\"" + e.head.getName() + "\"");
1351 ret.append(" [xpenalty=" + e.xPenalty + "]");
1352 ret.append(";\n");
1353 }
1354 for (int j = 0; j < v.flatOuts.length; ++j) {
1355 e = v.flatOuts[j];
1356 ret.append("\t\"" + e.tail.getName() + "\"->\"" + e.head.getName() + "\";\n");
1357 }
1358 }
1359 ret.append("}\n");
1360 msg.println(ret.toString());
1361 }
1362
1363 // For Anneal /////////////////////////////////////////////////////////
1364 //
1365
1366 /**
1367 * Pre-calculate static costs for each possible path segments.
1368 */
1369 public int staticCost() {
1370 int total = 0;
1371 for (int r = minRank; r < maxRank; ++r) {
1372 total += staticRankCost(r);
1373 ranks[r].valid = true;
1374 }
1375 if (DEBUG)
1376 msg.println(NAME + ".staticCost(): total=" + total);
1377 return total;
1378 }
1379
1380 /**
1381 * Cross cost for imaginary edge from every vertices on top to
1382 * every vertices at bottom.
1383 *
1384 * v.crossCost[i] is the sum of all xPenalty that the edge v->rank1.vts[i] would crossed.
1385 *
1386 * @usedby Anneal and AnnealWithCell.
1387 *
1388 * @param r The rank whose cost is to be calculated.
1389 */
1390 public int staticRankCost(int r) {
1391 //
1392 int ranktotal = 0;
1393 //
1394 VirtualVertex v;
1395 VirtualEdge e;
1396 int order;
1397 int cost;
1398 //
1399 VirtualGraph.Rank rank = ranks[r];
1400 VirtualGraph.Rank rank1 = ranks[r + 1];
1401 if (fCrossCounts.length < rank1.nVts)
1402 fCrossCounts = new int[rank1.nVts];
1403 else
1404 Arrays.fill(fCrossCounts, 0);
1405 //