Source code: com/port80/graph/dot/impl/VirtualVertex.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.awt.geom.Rectangle2D;
8 import java.util.Comparator;
9
10 import com.port80.graph.IEdge;
11 import com.port80.graph.IGraphShape;
12 import com.port80.graph.IVertex;
13 import com.port80.util.Debug;
14 import com.port80.util.msg;
15
16 /** Graph vertex with layout information.
17 *
18 * @enter IVertex dimension, as well as the dimensions of all its
19 * edges label, should have been determined before layout
20 * (to get correct x,y positions).
21 *
22 * @see com.port80.graph.IVertex
23 */
24 public class VirtualVertex {
25
26 // Static fields ///////////////////////////////////////////////////////
27 //
28
29 private static final String NAME = "VirtualVertex";
30 private static final String PACKAGENAME = "com.port80.graph.dot.impl";
31 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
32 private static final int VERSION = 0x0001;
33 private static final String VERSIONNAME = "v0.1";
34 static {
35 Debug.add(CLASSNAME);
36 }
37
38 private static final boolean DEBUG = false;
39 private static final boolean CHECK = true;
40
41 private static int anonymousCount = 0;
42
43 private static final int NONE = 0;
44 private static final int VERTEX = 0; /** VirtualVertex for an IVertex.*/
45 private static final int GRAPH = 1; /** VirtualVertex for a subgrpah/cluster.*/
46 private static final int EDGELABEL = 2; /** VirtualVertex for an edge label.*/
47 private static final int EDGE = 3; /** VirtualVertex for an edge segment.*/
48 private static final int BUS = 4; /** VirtualVertex for an input/output bus. */
49 private static final int AUX = 5; /** Used by Mincross, removed before Posiition.*/
50
51 // Instance fields /////////////////////////////////////////////////////
52 //
53
54 private int type = 0; /** NONE,LEADER...etc.*/
55 String name;
56 Object original; /** The original IVertex/IEdge.*/
57 VirtualGraph parent;
58 IGraphShape shape;
59 //
60 VirtualEdge[] ins = new VirtualEdge[0]; /** InterRank in edges.*/
61 VirtualEdge[] outs = new VirtualEdge[0]; /** InterRank out edges.*/
62 VirtualEdge[] selves = new VirtualEdge[0]; /** Self edges.*/
63 VirtualEdge[] flatIns = new VirtualEdge[0]; /** Flat in edges.*/
64 VirtualEdge[] flatOuts = new VirtualEdge[0]; /** Flat out edges.*/
65 int[] adjacencyList = new int[0]; /** Adjacent flatindex list.*/
66 //
67 VirtualVertex inBus;
68 VirtualVertex outBus;
69 boolean hasPort; /** true=has port.*/
70 boolean hasIO; /** true=has in/out edge.*/
71 boolean hasFlat; /** true=has flat edge.*/
72 int rank; /** Vertex rank.*/
73 int flatIndex; /** Index within the rank.*/
74 int median; /** Median value. */
75 int leftWidth;
76 int rightWidth;
77 int inthreshold;
78 int outthreshold;
79 /**
80 * Extra spacing from neighbour vertices for expansion of merged edges.
81 * The padding is to be added as reserved space at the neighbours (instead of this vertex)
82 * so as to prevent routing of the virtual edge get too close to the neighbour vertex.
83 */
84 int padding;
85 int top;
86 int bottom;
87 int x;
88 int y;
89 /**
90 * Since in/out edges may have been merged,
91 * fan in/out may not be same as number of in/out edges.
92 */
93 int fanIn;
94 int fanOut;
95 /** degree=ins.length+outs.length. */
96 int degree;
97 //
98 int order;
99 int savedOrder;
100 int savex;
101 int[] crossCost;
102 int[] savedCrossCost;
103 boolean isErased;
104
105 // Static constructor //////////////////////////////////////////////////
106 //
107
108 /** Represent a connection on the buses.*/
109 public static VirtualVertex newBusVertex(IVertex v, int rank, VirtualGraph parent) {
110 VirtualVertex ret = new VirtualVertex();
111 ret.type = BUS;
112 ret.original = v;
113 ret.rank = rank;
114 ret.parent = parent;
115 //
116 ret.name = "#" + v.getName() + "." + anonymousCount++;
117 ret.initBounds(parent);
118 if (DEBUG)
119 ret.checkInit();
120 return ret;
121 }
122
123 /** Represent a connection from IVertex to its in/out bus replicates.*/
124 public static VirtualVertex newAuxVertex(String name, int rank, VirtualGraph parent) {
125 VirtualVertex ret = new VirtualVertex();
126 ret.type = AUX;
127 ret.original = null;
128 ret.rank = rank;
129 ret.parent = parent;
130 //
131 ret.name = "!" + name + "." + anonymousCount++;
132 ret.initBounds(parent);
133 if (DEBUG)
134 ret.checkInit();
135 return ret;
136 }
137
138 // /** Represent a connection on the buses.*/
139 // public static VirtualVertex newAuxVertex(int rank, VirtualGraph parent) {
140 // VirtualVertex ret = new VirtualVertex();
141 // ret.type = AUX;
142 // ret.rank = rank;
143 // ret.parent = parent;
144 // //
145 // ret.name = "##" + rank + "." + anonymousCount++;
146 // ret.initBounds(parent);
147 // if (DEBUG)
148 // ret.checkInit();
149 // return ret;
150 // }
151
152 // Constructors ////////////////////////////////////////////////////////
153 //
154
155 //FIXME: subgraph and clusters.
156
157 private VirtualVertex() {}
158
159 /** Represent an IVertex.
160 */
161 public VirtualVertex(IVertex v, VirtualGraph parent) {
162 this.type = VERTEX;
163 this.original = v;
164 this.parent = parent;
165 //
166 this.name = v.getName();
167 this.rank = v.getAttrInt("-rank", 0);
168 initBounds((Rectangle2D) v.getAttr("-bounds"));
169 this.shape = (IGraphShape) v.getAttr("-shape");
170 this.inthreshold= v.getAttrInt("inthreshold");
171 this.outthreshold= v.getAttrInt("outthreshold");
172 if (DEBUG)
173 checkInit();
174 }
175
176 /** VirtualVertex represent an IEdge label.
177 */
178 public VirtualVertex(int rank, String label, IEdge e, VirtualGraph parent) {
179 this.type = EDGELABEL;
180 this.name = "$$" + label + "." + rank + "." + anonymousCount++;
181 this.rank = rank;
182 this.parent = parent;
183 this.original = e;
184 //
185 if (e.getAttrString("label") != null)
186 initBounds((Rectangle2D) e.getAttr("-bounds"));
187 else
188 initBounds(parent);
189 if (DEBUG)
190 checkInit();
191 }
192
193 /** VirtualVertex created between ends of an edge chain.
194 */
195 public VirtualVertex(int rank, IEdge e, VirtualGraph parent) {
196 this.type = EDGE;
197 this.name = "$" + rank + "." + anonymousCount++;
198 this.rank = rank;
199 this.parent = parent;
200 this.original = e;
201 //
202 initBounds(parent);
203 if (DEBUG)
204 checkInit();
205 }
206
207 ////////////////////////////////////////
208
209 /** Pixel dimensions from given Rectangle2D. */
210 private void initBounds(Rectangle2D bounds) {
211 int hw = ((int) (bounds.getWidth() / 2)) + 1;
212 //int defaultwidth=parent.getDefaultHalfWidth();
213 //this.leftWidth=Math.max(hw,defaultwidth);
214 //this.rightWidth=Math.max(hw,defaultwidth);
215 this.leftWidth = hw;
216 this.rightWidth = hw;
217 int hh = ((int) (bounds.getHeight() / 2)) + 1;
218 this.top = hh;
219 this.bottom = hh;
220 }
221
222 /** Default bounds for interrank virtual vertex. */
223 private void initBounds(VirtualGraph parent) {
224 //int w=e.getAttrInt("-linewidth");
225 int hw = parent.getDefaultHalfWidth() / parent.fXDIV_EDGES / 2;
226 this.leftWidth = hw;
227 this.rightWidth = hw;
228 this.top = parent.fHALFHEIGHT_VIRTUALVERTEX;
229 this.bottom = this.top;
230 }
231
232 /** Check initialization values are valid. */
233 private void checkInit() {
234 if (leftWidth == 0 || rightWidth == 0 || top == 0 || bottom == 0)
235 msg.err(
236 NAME
237 + "(): invalid dimension"
238 + ": leftWidth="
239 + leftWidth
240 + ": rightWidth="
241 + rightWidth
242 + ": top="
243 + top
244 + ": bottom="
245 + bottom);
246 if (parent != null) {
247 int minrank = parent.getOriginal().getAttrInt("-minrank");
248 int maxrank = parent.getOriginal().getAttrInt("-maxrank");
249 if (!(minrank <= rank && rank <= maxrank))
250 msg.err(
251 NAME
252 + "(): rank out of bound"
253 + ": minrank="
254 + minrank
255 + ": maxrank="
256 + maxrank
257 + ": rank="
258 + rank);
259 }
260 }
261
262 // Instance methods ////////////////////////////////////////////////////
263 //
264
265 public int getType() {
266 return type;
267 }
268 public String getName() {
269 return name;
270 }
271 public VirtualEdge[] getIns() {
272 return ins;
273 }
274 public VirtualEdge[] getOuts() {
275 return outs;
276 }
277 /**
278 * @return True if this vertex represent a real IVertex which has no in/out edges.
279 */
280 public boolean isUnconnected() {
281 if (type != VERTEX)
282 return false;
283 IVertex v = (IVertex) original;
284 return (v.inSize() + v.outSize() == 0);
285 }
286 /**
287 * @return True if this vertex represent a real IVertex which has only one edge.
288 */
289 public boolean isSingleConnected() {
290 if (type != VERTEX)
291 return false;
292 IVertex v = (IVertex) original;
293 return (v.inSize() + v.outSize() == 1);
294 }
295 /** Any vertex not represent a real IVertex is virtual. */
296 public boolean isVirtual() {
297 return type != VERTEX && type != GRAPH;
298 }
299 public boolean isReal() {
300 return (type == VERTEX || type == GRAPH);
301 }
302 public boolean isEdge() {
303 return type == EDGE || type == EDGELABEL;
304 }
305 public boolean isLabel() {
306 return type == EDGELABEL;
307 }
308 public boolean isBus() {
309 return type == BUS;
310 }
311 public boolean isAux() {
312 return type == AUX;
313 }
314 public boolean hasFlat() {
315 return hasFlat;
316 }
317 public boolean hasSelf() {
318 return selves.length > 0;
319 }
320 public Object getOriginal() {
321 return original;
322 }
323 public int getRank() {
324 return rank;
325 }
326 public int getLeftWidth() {
327 return leftWidth;
328 }
329 public int getRightWidth() {
330 return rightWidth;
331 }
332 public int getTop() {
333 return top;
334 }
335 public int getBottom() {
336 return bottom;
337 }
338
339 public String toString() {
340 return (name + " (r=" + rank + ",x=" + x +",order=" + order + ",t=" + type + ")");
341 }
342
343 public String dump() {
344 StringBuffer ret = new StringBuffer(toString());
345 ret.append(
346 ": #i="
347 + ins.length
348 + ",#o="
349 + outs.length
350 + ",#FlatIns="
351 + flatIns.length
352 + ",#FlatOuts="
353 + flatOuts.length
354 + ",#selves="
355 + selves.length);
356 ret.append("\n\tI: ");
357 for (int i = 0; i < ins.length; ++i)
358 ret.append(ins[i].toString() + " ");
359 ret.append("\n\tO: ");
360 for (int i = 0; i < outs.length; ++i)
361 ret.append(outs[i].toString() + " ");
362 ret.append("\n");
363 return ret.toString();
364 }
365
366 /** Compute position of an edge label from its virtual node. Edge
367 * label is placed with its lower-left corner at the center of
368 * the VirtualVertex.
369 *
370 * @enter original must be an IEdge.
371 *
372 * @return Edge label position is saved to IEdge as the 'lp' attribute.
373 */
374 public void placeLabel() {
375 IEdge e = (IEdge) getOriginal();
376 if (parent != null && parent.isLeftToRight) {
377 //FIXME:
378 msg.warn(NAME + ".placeLabel(): FIXME: isLeftToRight.");
379 } else {
380 //FIXME: What if spline is curved away from the
381 //VirtualVertex center.
382 //
383 //FIXME: Check that "lp" attribute specify center
384 //coordinate, not the lower-left corner of the label.
385 e.setAttr("lp", (x + leftWidth) + "," + (y + bottom));
386 }
387 }
388
389 ////////////////////////////////////////////////////////////////////////
390
391 public int removeIn(VirtualEdge e) {
392 if (!equals(e.getHead())) {
393 msg.err(NAME + ".removeIn(): invalid edge: v=" + this +"\te=" + e);
394 return 0;
395 }
396 int ret = 0;
397 VirtualEdge[] a = e.isFlat() ? flatIns : ins;
398 for (int i = 0, max = a.length; i < max; ++i) {
399 if (a[i].equals(e)) {
400 ++ret;
401 if (e.isFlat())
402 flatIns = shrink(flatIns, i);
403 else {
404 ins = shrink(ins, i);
405 --degree;
406 }
407 if (DEBUG)
408 msg.println(
409 NAME
410 + ".remove(): i="
411 + i
412 + ", max="
413 + max
414 + ", v="
415 + name
416 + ", e="
417 + e
418 + ", a.length="
419 + a.length);
420 break;
421 }
422 }
423 return ret;
424 }
425
426 public int removeOut(VirtualEdge e) {
427 if (!e.getTail().equals(this)) {
428 msg.err(NAME + ".removeOut(): invalid edge: v=" + this +"\te=" + e);
429 return 0;
430 }
431 int ret = 0;
432 VirtualEdge[] a = e.isFlat() ? flatOuts : outs;
433 for (int i = 0, max = a.length; i < max; ++i) {
434 if (a[i].equals(e)) {
435 ++ret;
436 if (e.isFlat())
437 flatOuts = shrink(flatOuts, i);
438 else {
439 outs = shrink(outs, i);
440 --degree;
441 }
442 if (DEBUG)
443 msg.println(
444 NAME
445 + ".remove(): i="
446 + i
447 + ", max="
448 + max
449 + ", v="
450 + name
451 + ", e="
452 + e
453 + ", a.length="
454 + a.length);
455 break;
456 }
457 }
458 return ret;
459 }
460
461 public void addSelfEdge(VirtualEdge e) {
462 if (!equals(e.getHead()) || !equals(e.getTail())) {
463 msg.err(NAME + ".addSelfEdge(): invalid edge: v=" + this +"\te=" + e);
464 return;
465 }
466 selves = grow(selves, e);
467 }
468
469 public void addIn(VirtualEdge e) {
470 if (!equals(e.getHead())) {
471 msg.err(NAME + ".addIn(): invalid edge: v=" + this +"\te=" + e);
472 return;
473 }
474 IEdge[] originals = e.getOriginals();
475 if (originals != null)
476 fanIn += originals.length;
477 if (e.isFlat())
478 flatIns = grow(flatIns, e);
479 else {
480 ins = grow(ins, e);
481 ++degree;
482 }
483 }
484
485 public void addOut(VirtualEdge e) {
486 if (!equals(e.getTail())) {
487 msg.err(NAME + ".addOut(): invalid edge: v=" + this +"\te=" + e);
488 return;
489 }
490 IEdge[] originals = e.getOriginals();
491 if (originals != null)
492 fanOut += originals.length;
493 if (e.isFlat())
494 flatOuts = grow(flatOuts, e);
495 else {
496 outs = grow(outs, e);
497 ++degree;
498 }
499 }
500
501 /**
502 * Find edge chain that terminate with the given head and has no
503 * label.
504 */
505 public VirtualEdge findOutChain(VirtualVertex head) {
506 IEdge a[];
507 String vlabel;
508 VirtualEdge e;
509 for (int i = 0; i < outs.length; ++i) {
510 e = outs[i];
511 if (e.isAux())
512 continue;
513 if (!head.equals(e.getChainHead()))
514 continue;
515 a = e.getOriginals();
516 if (a == null)
517 continue;
518 vlabel = a[0].getAttrString("label");
519 // Since only edge without label can be merged, checking
520 // the first edge is sufficient.
521 if (vlabel == null)
522 return e;
523 }
524 return null;
525 }
526
527 ////////////////////////////////////////////////////////////////////////
528
529 // public int hascode() {
530 // return name.hashCode();
531 // }
532 //
533 // public boolean equals(Object a) {
534 // if (!(a instanceof VirtualVertex))
535 // return false;
536 // return name.equals(((VirtualVertex) a).name);
537 // }
538
539 // Comparable interface /////////////////////////////////////////////////
540 //
541
542 /*
543 public int compareTo(Object v) {
544 return name.compareTo(((VirtualVertex)v).getName());
545 }
546 */
547
548 ////////////////////////////////////////////////////////////////////////
549
550 private VirtualEdge[] grow(VirtualEdge[] a, VirtualEdge e) {
551 VirtualEdge[] ret = new VirtualEdge[a.length + 1];
552 System.arraycopy(a, 0, ret, 0, a.length);
553 ret[a.length] = e;
554 return ret;
555 }
556
557 private VirtualEdge[] shrink(VirtualEdge[] a, int i) {
558 int len = a.length - 1;
559 a[i] = a[len];
560 VirtualEdge[] ret = new VirtualEdge[len];
561 System.arraycopy(a, 0, ret, 0, len);
562 return ret;
563 }
564
565 // For Anneal //////////////////////////////////////////////////////////
566
567 public void erase() {
568 isErased = true;
569 }
570
571 public void restore() {
572 isErased = false;
573 }
574
575 public boolean isErased() {
576 return isErased;
577 }
578
579 public void saveCrossCost() {
580 if (savedCrossCost == null || savedCrossCost.length < crossCost.length) {
581 savedCrossCost = new int[crossCost.length];
582 }
583 System.arraycopy(crossCost, 0, savedCrossCost, 0, crossCost.length);
584 }
585
586 public void restoreCrossCost() {
587 System.arraycopy(savedCrossCost, 0, crossCost, 0, crossCost.length);
588 if (CHECK)
589 savedCrossCost = null;
590 }
591
592 public boolean checkSavedCrossCost() {
593 boolean ok = true;
594 for (int i = 0; i < crossCost.length; ++i) {
595 if (savedCrossCost[i] == crossCost[i])
596 continue;
597 msg.err(
598 NAME
599 + ".checkSavedCrossCost(): "+": mismatch: vertex="
600 + getName()
601 + ", i="
602 + i
603 + ", saved="
604 + savedCrossCost[i]
605 + ", current="
606 + crossCost[i]);
607 ok = false;
608 }
609 return ok;
610 }
611
612 // Nested Classes /////////////////////////////////////////////////////////////
613 //
614
615 static class NameComparator implements Comparator {
616 public int compare(Object a, Object b) {
617 return ((VirtualVertex) a).getName().compareTo(((VirtualVertex) b).getName());
618 }
619 }
620
621 static class OrderComparator implements Comparator {
622 public int compare(Object a, Object b) {
623 int oa = ((VirtualVertex) a).order;
624 int ob = ((VirtualVertex) b).order;
625 if (oa > ob)
626 return 1;
627 if (oa < ob)
628 return -1;
629 return 0;
630 }
631 }
632
633 static class MedianComparator implements Comparator {
634 public int compare(Object a, Object b) {
635 int oa = ((VirtualVertex) a).median;
636 int ob = ((VirtualVertex) b).median;
637 if (oa > ob)
638 return 1;
639 if (oa < ob)
640 return -1;
641 return 0;
642 }
643 }
644
645 ////////////////////////////////////////////////////////////////////////
646
647 }