Source code: com/port80/graph/dot/impl/DotVertex.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import java.util.*;
8 import com.port80.util.msg;
9 import com.port80.util.Debug;
10 import com.port80.graph.*;
11 import com.port80.graph.impl.*;
12
13 /** Graph vertex with spanning tree for ranking.
14 *
15 * @see com.port80.graph.IVertex
16 */
17 public class DotVertex {
18
19 // Static fields ///////////////////////////////////////////////////////
20 //
21
22 private static final String NAME = "DotVertex";
23 private static final String PACKAGENAME = "com.port80.graph.dot.impl";
24 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
25 private static final int VERSION = 0x0001;
26 private static final String VERSIONNAME = "v0.1";
27 static {
28 Debug.add(CLASSNAME);
29 }
30 private static final boolean DEBUG = false;
31 private static final boolean CHECK = true;
32 private static int anonymousCount = 0;
33
34 public static final int NONE = 0;
35 public static final int TYPEMASK = 0x0f;
36 public static final int VERTEX = 0x00;
37 public static final int GRAPH = 0x01;
38
39 public static final int RANKMASK = 0xf0;
40 // TOPRANK force vertex to top rank if vertex has no input edge.
41 public static final int TOPRANK = 0x10;
42 // SAMERANK force vertices in a subgraph to same rank.
43 public static final int SAMERANK = 0x20;
44 // MINRANK force vertices in a subgraph or a vertex to the min rank.
45 public static final int MINRANK = 0x40;
46 // MAXRANK force vertices in a subgraph or a vertex to the max rank.
47 public static final int MAXRANK = 0x80;
48
49 // Instance fields /////////////////////////////////////////////////////
50 //
51
52 int type;
53 String name;
54 /** The original IVertex/IGraph. */
55 Object original;
56 /**
57 * For efficiency, ins and outs are allowed to be accessed directly.
58 * However, DON'T trust the array length, use inSize() and outSize().
59 */
60 DotEdge[] ins = new DotEdge[2];
61 DotEdge[] outs = new DotEdge[2];
62 private int inSize = 0;
63 private int outSize = 0;
64 int rank;
65 //
66 // Undirected tree overlay used by dotRank().
67 //
68 DotEdge treeParent; /** Tree parent edge. */
69 DotEdge[] treeIos; /** Tree edges include the parent edge. */
70 int nTreeIos = 0; /** Number of tree edges, including the parent edge. */
71 int lower = 0; /** Depth first search index range lower bound for this subtree. */
72 int upper = 0; /** Upper bound. */
73 /** A counter for general use. User should not assume any init. value.*/
74 int counter = 0;
75
76 // Constructors ////////////////////////////////////////////////////////
77 //
78
79 public DotVertex(int type) {
80 this.type = type;
81 this.name = "$" + anonymousCount++;
82 }
83
84 public DotVertex(String name, int type) {
85 this.type = type;
86 this.name = name;
87 }
88
89 public DotVertex(IVertex v) {
90 if (DEBUG)
91 if (v == null || v.getName() == null)
92 msg.err(NAME + ": v=" + v);
93 this.original = v;
94 this.name = v.getName();
95 //
96 String rtype = v.getAttrString("rank");
97 if (rtype != null) {
98 if (rtype.equalsIgnoreCase("top"))
99 type|=TOPRANK;
100 else if (rtype.equalsIgnoreCase("min"))
101 type |= MINRANK;
102 else if (rtype.equalsIgnoreCase("max"))
103 type |= MAXRANK;
104 else {
105 msg.err(NAME + "(IGraph): invalid rank type: " + rtype);
106 }
107 }
108 }
109
110 /** Force subgraph to the specified rank.*/
111 public DotVertex(IGraph g) {
112 this.type = GRAPH;
113 this.original = g;
114 this.name = "$" + anonymousCount++;
115 //
116 String rtype = g.getAttrString("rank");
117 if (rtype != null) {
118 if(rtype.equalsIgnoreCase("same"))
119 type|=SAMERANK;
120 else if (rtype.equalsIgnoreCase("min"))
121 type |= MINRANK;
122 else if (rtype.equalsIgnoreCase("max"))
123 type |= MAXRANK;
124 else {
125 msg.err(NAME + "(IGraph): invalid rank type: " + rtype);
126 }
127 }
128 }
129
130 // Instance methods ////////////////////////////////////////////////////
131 //
132
133 public int getType() {
134 return type;
135 }
136 public boolean isGraph() {
137 return (type & TYPEMASK) == GRAPH;
138 }
139 public boolean isVertex() {
140 return (type & TYPEMASK) == VERTEX;
141 }
142 public boolean isForceTopRank() {
143 return (type & RANKMASK) == TOPRANK;
144 }
145 public boolean isForceSameRank() {
146 return (type & RANKMASK) == SAMERANK;
147 }
148 public boolean isForceMinRank() {
149 return (type & RANKMASK) == MINRANK;
150 }
151 public boolean isForceMaxRank() {
152 return (type & RANKMASK) == MAXRANK;
153 }
154 //
155 public String getName() {
156 return name;
157 }
158 public DotEdge[] getIns() {
159 return ins;
160 }
161 public DotEdge[] getOuts() {
162 return outs;
163 }
164 public int inSize() {
165 return inSize;
166 }
167 public int outSize() {
168 return outSize;
169 }
170 public boolean isDecendent(DotVertex v) {
171 return (v.lower <= upper && upper <= v.upper);
172 }
173 public Object getOriginal() {
174 return original;
175 }
176 public int getRank() {
177 return rank;
178 }
179
180 public void setType(int t) {
181 type = t;
182 }
183 public void setOriginal(Object original) {
184 this.original = original;
185 }
186
187 public String toString() {
188 StringBuffer ret =
189 new StringBuffer(
190 NAME
191 + ": "
192 + name
193 + " (r="
194 + rank
195 + ",n="
196 + nTreeIos
197 + ",l="
198 + lower
199 + ",u="
200 + upper
201 + ",p="
202 + treeParent
203 + ")\n\tI: ");
204 for (int i = 0; i < inSize; ++i)
205 ret.append(ins[i].toString() + " ");
206 ret.append("\n\tO: ");
207 for (int i = 0; i < outSize; ++i)
208 ret.append(outs[i].toString() + " ");
209 ret.append("\n");
210 return ret.toString();
211 }
212
213 ////////////////////////////////////////////////////////////////////////
214
215 public int removeIn(DotEdge e) {
216 if (CHECK && !e.getHead().equals(this)) {
217 msg.err(NAME + ".removeIn(): invalid edge: v=" + this +"\te=" + e);
218 return 0;
219 }
220 for (int i = 0; i < inSize; ++i) {
221 if (ins[i].equals(e)) {
222 --inSize;
223 ins[i] = ins[inSize];
224 ins[inSize] = null;
225 if (DEBUG)
226 msg.println(
227 NAME
228 + ".remove(): new size="
229 + inSize
230 + ", i="
231 + i
232 + ", v="
233 + name
234 + ", e="
235 + e);
236 return 1;
237 }
238 }
239 return 0;
240 }
241
242 public int removeOut(DotEdge e) {
243 if (CHECK && !e.getTail().equals(this)) {
244 msg.err(NAME + ".removeOut(): invalid edge: v=" + this +"\te=" + e);
245 return 0;
246 }
247 for (int i = 0; i < outSize; ++i) {
248 if (outs[i].equals(e)) {
249 --outSize;
250 outs[i] = outs[outSize];
251 outs[outSize] = null;
252 if (DEBUG)
253 msg.println(
254 NAME
255 + ".remove(): new size="
256 + outSize
257 + ", i="
258 + i
259 + ", v="
260 + name
261 + ", e="
262 + e);
263 return 1;
264 }
265 }
266 return 0;
267 }
268
269 public void addIn(DotEdge e) {
270 if (CHECK && !e.getHead().equals(this)) {
271 msg.err(NAME + ".addIn(): invalid edge: v=" + this +"\te=" + e);
272 return;
273 }
274 if (inSize >= ins.length)
275 ins = grow(ins);
276 ins[inSize] = e;
277 ++inSize;
278 }
279
280 public void addOut(DotEdge e) {
281 if (CHECK && !e.getTail().equals(this)) {
282 msg.err(NAME + ".addOut(): invalid edge: v=" + this +"\te=" + e);
283 return;
284 }
285 if (outSize >= outs.length)
286 outs = grow(outs);
287 outs[outSize] = e;
288 ++outSize;
289 }
290
291 private DotEdge[] grow(DotEdge[] a) {
292 DotEdge[] ret = new DotEdge[a.length + (a.length >> 1) + 1];
293 System.arraycopy(a, 0, ret, 0, a.length);
294 return ret;
295 }
296
297 ////////////////////////////////////////////////////////////////////////
298
299 /** Remove e from treeIos. */
300 public void removeTreeEdge(DotEdge e) {
301 // NOTE: if not for checking, we can use i<max. If i==max, we
302 // don't have to do the assignment.
303 int i, max;
304 for (i = 0, max = --nTreeIos; i <= max; ++i) {
305 if (treeIos[i] == e) {
306 treeIos[i] = treeIos[max];
307 break;
308 }
309 }
310 if (DEBUG)
311 if (i > max)
312 msg.err(NAME + ".removeTreeEdge(): i>max" + ": edge not exist: e=" + e);
313 }
314
315 /** Add e to treeIos. */
316 public void addTreeEdge(DotEdge e) {
317 treeIos[nTreeIos++] = e;
318 }
319
320 ////////////////////////////////////////////////////////////////////////
321
322 /** Label each vertices of a tree with the range of DFS index
323 * under its subtree. This provide a quick way to determine if a
324 * given vertex V (with DFS order number Vi) is under the subtree
325 * T (with range Tl,Tu). V is under the subtree if:
326 *
327 * Tl<=Vi<=Tu
328 *
329 * . The DFS index is the index of the vertex in a DFS result
330 * list. The first (ie. the lower-left) vertex index=lower of
331 * the root, given when the method is first invoked.
332 *
333 * . The tree edges are treated as non-directional so search
334 * propagate to both in and out edges.
335 *
336 * @param p Parent edge.
337 * @param low The lower bound propagated from above.
338 * @return treeParent,upper,lower are populated.
339 */
340 public int initRange(DotEdge p, int low) {
341 treeParent = p;
342 lower = low;
343 DotEdge e;
344 for (int i = 0; i < nTreeIos; ++i) {
345 e = treeIos[i];
346 if (e != treeParent)
347 low = e.getOpposite(this).initRange(e, low);
348 }
349 upper = low;
350 if (DEBUG)
351 msg.println(NAME + ".initRange(): this=" + name + " (l=" + lower + ",u=" + upper + ")");
352 return upper + 1;
353 }
354
355 ////////////////////////////////////////////////////////////////////////
356
357 // public int hashcode() {
358 // return name.hashCode();
359 // }
360 // public boolean equals(Object a) {
361 // return (name.equals(((DotVertex) a).getName()));
362 // }
363
364 // Nested classes //////////////////////////////////////////////////////
365 //
366
367 /**
368 * Compare DotVertex by its name (same ordering as String).
369 */
370 public static class NameComparator implements Comparator {
371 public int compare(Object a, Object b) {
372 return ((DotVertex) a).getName().compareTo(((DotVertex) b).getName());
373 }
374 public boolean equals(Object a, Object b) {
375 return ((DotVertex) a).getName().equals(((DotVertex) b).getName());
376 }
377 }
378
379 /**
380 * Compare DotVertex by its rank (lowest rank highest priority).
381 *
382 * Note that this comparator <b>reversed</b> the sense of the compare() output
383 * so that priority heap should dequeue lowest rank first (as highest priority).
384 */
385 public static class RankComparator implements Comparator {
386 public int compare(Object a, Object b) {
387 DotVertex va = (DotVertex) a;
388 DotVertex vb = (DotVertex) b;
389 int ranka = va.getRank();
390 int rankb = vb.getRank();
391 if (ranka > rankb)
392 return -1;
393 if (ranka < rankb)
394 return 1;
395 return 0;
396 }
397 public boolean equals(Object a, Object b) {
398 DotVertex va = (DotVertex) a;
399 DotVertex vb = (DotVertex) b;
400 return va.getRank() == vb.getRank();
401 }
402 }
403
404 ////////////////////////////////////////////////////////////////////////
405
406 }