Source code: com/port80/graph/dot/impl/VirtualEdge.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.Comparator;
8
9 import com.port80.graph.IEdge;
10 import com.port80.util.Debug;
11 import com.port80.util.msg;
12
13 /**
14 * VirtualGraph edge.
15 * VirtualEdge should be create through the factory method in the VirtualGraph class.
16 *
17 * FIXME:
18 * . Instead of (head,tail), should use (tail,head) in parameters
19 * which is more natural to use.
20 *
21 * @see com.port80.graph.IEdge
22 */
23 public class VirtualEdge {
24
25 // Static fields ///////////////////////////////////////////////////////
26 //
27
28 private static final String NAME = "VirtualEdge";
29 private static final String PACKAGENAME = "com.port80.graph.dot.impl";
30 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
31 private static final int VERSION = 0x0001;
32 private static final String VERSIONNAME = "0.1";
33 static {
34 Debug.add(CLASSNAME);
35 }
36 private static final boolean DEBUG = false;
37 private static final boolean CHECK = true;
38
39 /** VirtualEdge types.*/
40 private static final int NONE = 0;
41 private static final int STUB = 0x80; /** Critical edges. */
42 private static final int CRITICAL = 0x40; /** Critical edges. */
43 private static final int BUS = 0x20; /** Inter-rank bus edges.*/
44 private static final int NORMAL = 0x10; /** Inter-rank edges.*/
45 private static final int FLAT = 0x08; /** Intra-rank flat edges.*/
46 private static final int SELF = 0x04; /** Self edges.*/
47 private static final int AUX = 0x01;
48 ;
49
50 private int type = NORMAL;
51 protected VirtualVertex head;
52 protected VirtualVertex tail;
53 protected VirtualPort headPort;
54 protected VirtualPort tailPort;
55
56 IEdge[] originals; /** The original IEdge this VirtualEdge represent.*/
57 VirtualEdge next; /** Next edge in the edge chain, towards the head. */
58 VirtualEdge prev; /** Previous edge in the edge chain, towards the tail. */
59 int minLength; /** =2 if edge has label. */
60 int weight;
61 /** Since VirtualEdge merge IEdge in opposite direction together,
62 * isReversed don't really meaningful.*/
63 //boolean isReversed=false;
64 DotSpline spline = null;
65 DotSpline fUnclipped = null;
66 //
67 int xPenalty; /** Cross penalty. */
68 //
69 //DEBUG:
70 boolean isDebug = false;
71
72 // Constructors ////////////////////////////////////////////////////////
73 //
74
75 /** Create a virtual edge as part of an edge chain.
76 *
77 * @param head head node for this edge.
78 * @param tail tail node for this edge.
79 * @param e original edge that this virtual edge represent.
80 * @param ve the neighbouring edge in the chain.
81 */
82 private VirtualEdge(
83 int type,
84 VirtualVertex head,
85 VirtualVertex tail,
86 IEdge e,
87 VirtualEdge ve,
88 VirtualGraph parent) {
89 if (CHECK) {
90 if (head == null || tail == null || parent == null)
91 msg.err(NAME + ": e=" + e + ", parent=" + parent);
92 }
93 //if(e==null) msg.err(NAME+"(): e==null: type="+type+", head="+head+", tail="+tail+", ve="+ve);
94 this.type = type;
95 this.head = head;
96 this.tail = tail;
97 this.minLength = 1;
98 if (type != SELF && ve != null) {
99 if (ve.getHead().equals(tail)) {
100 // ve->tail->head
101 prev = ve;
102 ve.next = this;
103 } else if (ve.getTail().equals(head)) {
104 // tail->head->ve
105 next = ve;
106 ve.prev = this;
107 } else
108 msg.err(NAME + "(): Invalid neighbour edge: " + ve);
109 }
110 if (e != null) {
111 // Virtual edge is part of a real edge.
112 if (e.getAttrBool("critical"))
113 type |= CRITICAL;
114 isDebug = e.getAttrBool("debug");
115 originals = new IEdge[1];
116 originals[0] = e;
117 weight = e.getAttrInt("weight", -1);
118 xPenalty = e.getAttrInt("xpenalty", -1);
119 } else {
120 originals = new IEdge[0];
121 weight = -1;
122 xPenalty = -1;
123 }
124 // If weigth/xpenalty is not specified, determine the default values from edge type.
125 if (weight < 0) {
126 if ((type & STUB) != 0)
127 weight = parent.fWEIGHT_STUB;
128 else if ((type & CRITICAL) != 0)
129 weight = parent.fWEIGHT_CRITICAL;
130 else if ((type & BUS) != 0)
131 weight = parent.fWEIGHT_BUS;
132 else if ((type & AUX) != 0) {
133 weight=parent.fWEIGHT_DEFAULT;
134 } else
135 weight = parent.fWEIGHT_DEFAULT;
136 }
137 if (xPenalty < 0) {
138 if ((type & STUB) != 0)
139 xPenalty = parent.fXPENALTY_STUB;
140 else if ((type & CRITICAL) != 0)
141 xPenalty = parent.fXPENALTY_CRITICAL;
142 else if ((type & BUS) != 0)
143 xPenalty = parent.fXPENALTY_BUS;
144 else if ((type & AUX) != 0)
145 xPenalty = parent.fXPENALTY_AUX;
146 else
147 xPenalty = parent.fXPENALTY_DEFAULT;
148 }
149
150 if (type != SELF) {
151 head.addIn(this);
152 tail.addOut(this);
153 }
154 }
155
156 ////////////////////////////////////////////////////////////////////////
157
158 static VirtualEdge newEdge(
159 VirtualVertex head,
160 VirtualVertex tail,
161 IEdge e,
162 VirtualEdge ve,
163 VirtualGraph parent) {
164 return new VirtualEdge(NORMAL, head, tail, e, ve, parent);
165 }
166
167 static VirtualEdge newSelfEdge(VirtualVertex head, IEdge e, VirtualEdge ve, VirtualGraph parent) {
168 return new VirtualEdge(SELF, head, head, e, ve, parent);
169 }
170
171 static VirtualEdge newBusEdge(
172 VirtualVertex head,
173 VirtualVertex tail,
174 IEdge e,
175 VirtualEdge ve,
176 VirtualGraph parent) {
177 return new VirtualEdge(BUS, head, tail, e, ve, parent);
178 }
179
180 static VirtualEdge newStubEdge(VirtualVertex head, VirtualVertex tail, VirtualEdge ve, VirtualGraph parent) {
181 return new VirtualEdge(STUB, head, tail, null, ve, parent);
182 }
183
184 static VirtualEdge newFlatEdge(VirtualVertex head, VirtualVertex tail, IEdge e, VirtualGraph parent) {
185 return new VirtualEdge(FLAT, head, tail, e, null, parent);
186 }
187
188 /**
189 * Auxillary edges connect Vertex to its in/out bus vertices and
190 * used (by MinCross) to pull bus vertices together.
191 * Auxillary edges should be ignored for routing.
192 */
193 static VirtualEdge newAuxEdge(VirtualVertex head, VirtualVertex tail, VirtualEdge ve, VirtualGraph parent) {
194 return new VirtualEdge(AUX, head, tail, null, ve, parent);
195 }
196
197 /*
198 static VirtualEdge newReversedEdge(VirtualVertex head,VirtualVertex tail,IEdge e,VirtualEdge ve) {
199 VirtualEdge ret=new VirtualEdge(head,tail,e,ve);
200 ret.isReversed=true;
201 return ret;
202 }
203 */
204
205 // Instance methods ////////////////////////////////////////////////////
206 //
207
208 public int getType() {
209 return type;
210 }
211
212 public IEdge[] getOriginals() {
213 return originals;
214 }
215
216 public String getOriginalName() {
217 if (originals.length == 0)
218 return getName();
219 else
220 return originals[0].getName();
221 }
222
223 public boolean isFlat() {
224 return (type & FLAT) != 0;
225 }
226
227 public boolean isSelf() {
228 return (type & SELF) != 0;
229 }
230
231 public boolean isCritical() {
232 return (type & CRITICAL) != 0;
233 }
234
235 public boolean isAux() {
236 return (type & AUX) != 0;
237 }
238
239 public DotSpline getSpline() {
240 return spline;
241 }
242
243 public DotSpline getUnclipped() {
244 return fUnclipped;
245 }
246
247 public void setSpline(DotSpline s, DotSpline unclipped) {
248 spline = s;
249 fUnclipped = unclipped;
250 }
251
252 /** Represent the given edge too. */
253 public void merge(IEdge e) {
254 IEdge[] a = new IEdge[originals.length + 1];
255 for (int i = 0; i < originals.length; ++i)
256 a[i] = originals[i];
257 a[originals.length] = e;
258 originals = a;
259 if (e.getAttrBool("debug"))
260 isDebug = true;
261
262 }
263
264 /** Merge the two virtual edges. */
265 public void merge(VirtualEdge e) {
266 if (type != e.getType())
267 msg.err(NAME + ".merge(): type!=e.type" + ": type=" + type + ": e.type=" + e.getType());
268 IEdge[] a = e.getOriginals();
269 if (a != null)
270 for (int i = 0; i < a.length; ++i)
271 merge(a[i]);
272 xPenalty += e.xPenalty;
273 weight+= e.weight;
274 }
275
276 /**
277 * Merge the specified edge into this edge chain.
278 */
279 public void mergeChain(IEdge e) {
280 if (DEBUG) {
281 msg.println(NAME + ".mergeChain(): this=" + this +"\n\te=" + e);
282 if (e.getAttrBool("debug"))
283 isDebug = true;
284 }
285 VirtualEdge first = this;
286 while (first.prev != null)
287 first = first.prev;
288 while (first != null) {
289 first.merge(e);
290 first = first.next;
291 }
292 }
293
294 /** Reverse the virtual edge. */
295 public void reverse() {
296 head.removeIn(this);
297 tail.removeOut(this);
298 VirtualVertex v = head;
299 head = tail;
300 tail = v;
301 //isReversed=!isReversed;
302 head.addIn(this);
303 tail.addOut(this);
304 }
305
306 // IEdge interface /////////////////////////////////////////////////////
307 //
308 public String getName() {
309 return tail.getName() + "->" + head.getName();
310 }
311 public VirtualVertex getHead() {
312 return head;
313 }
314 public VirtualVertex getTail() {
315 return tail;
316 }
317 public int getHeadPortDx() {
318 if (headPort == null)
319 return 0;
320 return headPort.dx;
321 }
322 public int getTailPortDx() {
323 if (tailPort == null)
324 return 0;
325 return tailPort.dx;
326 }
327
328 public VirtualVertex getOpposite(VirtualVertex v) {
329 if (v.equals(head))
330 return tail;
331 if (v.equals(tail))
332 return head;
333 return null;
334 }
335
336 /** @return vertex at the head end of the chain. */
337 public VirtualVertex getChainHead() {
338 VirtualEdge e = this;
339 while (e.next != null)
340 e = e.next;
341 return e.head;
342 }
343
344 /** @return vertex at the head end of the chain. */
345 public VirtualVertex getChainTail() {
346 VirtualEdge e = this;
347 while (e.prev != null)
348 e = e.prev;
349 return e.tail;
350 }
351
352 public int chainLength() {
353 int ret = 1;
354 VirtualEdge e = this;
355 while (e.prev != null)
356 e = e.prev;
357 while (e.next != null) {
358 e = e.next;
359 ++ret;
360 }
361 return ret;
362 }
363
364 /**
365 * @return First edge in the reverse direction if one exists, otherwise.
366 */
367 public VirtualEdge findReverseEdge() {
368 VirtualEdge e;
369 for (int i = 0; i < head.outs.length; ++i) {
370 e = head.outs[i];
371 if (e.getHead().equals(tail))
372 return e;
373 }
374 return null;
375 }
376
377 public VirtualEdge findReverseFlatEdge() {
378 VirtualEdge ve;
379 for (int i = 0; i < head.flatOuts.length; ++i) {
380 ve = head.flatOuts[i];
381 if (ve.getHead().equals(tail))
382 return ve;
383 }
384 return null;
385 }
386
387 public String toString() {
388 return getName();
389 }
390
391 ////////////////////////////////////////////////////////////////////////
392
393 /** Sort edge in drawing order.
394 *
395 * . Edges are drawn is the following order: STUB,CRITICAL,BUS,NORMAL,FLAT,SELF
396 * . Without each type, long edges are drawn first.
397 */
398 public static final class EdgeChainComparator implements Comparator {
399
400 /** @return 1=a>b, 0=a==b, -1=a<b */
401 public int compare(Object a, Object b) {
402 // Sort by type. STUB,CRITICAL,NORMAL,FLAT,SELF
403 VirtualEdge ve0 = (VirtualEdge) a;
404 VirtualEdge ve1 = (VirtualEdge) b;
405 int type0 = ve0.getType();
406 int type1 = ve1.getType();
407 if (type0 != type1)
408 return (type1 - type0);
409 // Sort by length of edge that the VirtualEdge segment
410 // represent, long first (smallest).
411 VirtualEdge he0, te0, he1, te1;
412 for (te0 = ve0; te0.prev != null; te0 = te0.prev);
413 for (he0 = ve0; he0.next != null; he0 = he0.next);
414 for (te1 = ve1; te1.prev != null; te1 = te1.prev);
415 for (he1 = ve1; he1.next != null; he1 = he1.next);
416 int dx = he0.head.x - te0.tail.x;
417 int dy = he0.head.rank - te0.tail.rank;
418 int dist0 = dx * dx + dy * dy;
419 dx = he1.head.x - te1.tail.x;
420 dy = he1.head.rank - te1.tail.rank;
421 int dist1 = dx * dx + dy * dy;
422 if (dist0 != dist1)
423 return dist0 - dist1;
424 //
425 int w0 =
426 Math.abs(
427 te0.tail.x
428 + ((te0.tailPort == null) ? 0 : te0.tailPort.dx)
429 - (he0.head.x + ((he0.headPort == null) ? 0 : he0.headPort.dx)));
430 int w1 =
431 Math.abs(
432 te1.tail.x
433 + ((te1.tailPort == null) ? 0 : te1.tailPort.dx)
434 - (he1.head.x + ((he1.headPort == null) ? 0 : he1.headPort.dx)));
435 if (w0 != w1)
436 return w0 - w1;
437 // Forward edge first, just to make it more predictable.
438 //if(ve0.isReversed()) return (ve1.isReversed()? 0: 1);
439 //else return (ve1.isReversed()? -1: 0);
440 int ret=ve0.getName().compareTo(ve1.getName());
441 if(ret!=0) return ret;
442 if(ve0==ve1) return 0;
443 return 1;
444 }
445 }
446
447 ////////////////////////////////////////////////////////////////////////
448
449 // public int hascode() {
450 // return getName().hashCode();
451 // }
452 //
453 // public boolean equals(Object a) {
454 // if (!(a instanceof VirtualEdge))
455 // return false;
456 // return getName().equals(((VirtualEdge) a).getName());
457 // }
458
459 ////////////////////////////////////////////////////////////////////////
460
461 }