Source code: com/port80/graph/impl/Vertex.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.impl;
6
7 import java.util.ArrayList;
8 import java.util.Comparator;
9 import java.util.HashSet;
10 import java.util.Iterator;
11 import java.util.List;
12 import java.util.Set;
13 import java.util.Stack;
14
15 import com.port80.graph.IEdge;
16 import com.port80.graph.IGraph;
17 import com.port80.graph.IVertex;
18 import com.port80.graph.IVertexPort;
19 import com.port80.util.Debug;
20 import com.port80.util.attr.IAttrRegistry;
21
22 /** Basic graph vertex implementation.
23 *
24 * @see com.port80.graph.IVertex
25 */
26 public class Vertex extends GraphElement implements IVertex {
27
28 // Static fields ///////////////////////////////////////////////////////
29 //
30
31 private static final String NAME = "Vertex";
32 private static final String PACKAGENAME = "com.port80.graph.impl";
33 private static final String CLASSNAME = PACKAGENAME + "." + NAME;
34 private static final int VERSION = 0x0101;
35 private static final String VERSIONNAME = "$Revision: 1.19 $";
36 static {
37 Debug.add(CLASSNAME);
38 }
39 private static boolean DEBUG = false;
40
41 ////////////////////////////////////////////////////////////////////////
42
43 public static class Port implements IVertexPort {
44 String fName;
45 int fDx, fDy; /** x,y offset from vertex center in pixels.*/
46 int fOrder;
47 //FIXME: This is not good enough to specify a port, but for
48 // now, we don't care about ports yet. Remove this when we do.
49 Port(String name) {
50 this.fName = name;
51 }
52 public Port(String name, int order, int dx, int dy) {
53 this.fName = name;
54 this.fOrder = order;
55 this.fDx = dx;
56 this.fDy = dy;
57 }
58 public String getName() {
59 return fName;
60 }
61 public int getDx() {
62 return fDx;
63 }
64 public int getDy() {
65 return fDy;
66 }
67 }
68
69 public static class NameComparator implements Comparator {
70 public int compare(Object a, Object b) {
71 return ((IVertex) a).getName().compareTo(((IVertex) b).getName());
72 }
73 }
74
75 // Instance fields /////////////////////////////////////////////////////
76 //
77
78 protected IGraph parent = null;
79 protected Port[] ports = null;
80 protected int inSize = 0;
81 protected int outSize = 0;
82 private IEdge[] ins = new IEdge[0];
83 private IEdge[] outs = new IEdge[0];
84
85 // Constructors ////////////////////////////////////////////////////////
86 //
87
88 public Vertex(String name, String port, Object data, IGraph parent) {
89 super(parent == null ? null : parent.getVertexAttrTable());
90 fName = name;
91 fData = data;
92 if (port != null) {
93 if (ports == null)
94 ports = new Port[1];
95 ports[0] = new Port(port);
96 }
97 this.parent = parent;
98 setAttr("label", name);
99 }
100
101 // Instance methods ////////////////////////////////////////////////////
102 //
103
104 public String toString() {
105 StringBuffer ret = new StringBuffer(NAME + ": " + fName + "\n\t" + parent.getName() + "\n\tI: ");
106 for (int i = 0; i < inSize; ++i)
107 ret.append(ins[i].getName() + " ");
108 ret.append("\n\tO: ");
109 for (int i = 0; i < outSize; ++i)
110 ret.append(outs[i].getName() + " ");
111 return ret.toString();
112 }
113
114 // IVertex interface ///////////////////////////////////////////////////
115 //
116
117 public IGraph getParent() {
118 return parent;
119 }
120
121 public void setParent(IGraph g) {
122 this.parent = g;
123 if (g != null)
124 this.parentAttrTable = g.getVertexAttrTable();
125 else
126 this.parentAttrTable = null;
127 }
128
129 public void addPort(String portname) {
130 Port[] p;
131 if (ports == null)
132 p = new Port[1];
133 else {
134 p = new Port[ports.length + 1];
135 System.arraycopy(ports, 0, p, 0, ports.length);
136 }
137 ports = p;
138 ports[p.length - 1] = new Port(portname);
139 }
140
141 ////////////////////////////////////////////////////////////////////////
142
143 public void addIn(IEdge e) {
144 if (inSize >= ins.length) {
145 IEdge[] ret = new IEdge[ins.length + 1];
146 System.arraycopy(ins, 0, ret, 0, ins.length);
147 ins = ret;
148 }
149 ins[inSize] = e;
150 ++inSize;
151 }
152
153 public void addIn(IEdge e, int n) {
154 if (inSize >= ins.length) {
155 IEdge[] ret = new IEdge[ins.length + 1];
156 System.arraycopy(ins, 0, ret, 0, n);
157 System.arraycopy(ins, n, ret, n + 1, inSize - n);
158 ins = ret;
159 } else {
160 System.arraycopy(ins, n, ins, n + 1, inSize - n);
161 }
162 ins[n] = e;
163 ++inSize;
164 }
165
166 public void addOut(IEdge e) {
167 IEdge[] ret = new IEdge[outs.length + 1];
168 System.arraycopy(outs, 0, ret, 0, outs.length);
169 ret[outs.length] = e;
170 ++outSize;
171 outs = ret;
172 }
173
174 public void addOut(IEdge e, int n) {
175 if (outSize >= outs.length) {
176 IEdge[] ret = new IEdge[outs.length + 1];
177 System.arraycopy(outs, 0, ret, 0, n);
178 System.arraycopy(outs, n, ret, n + 1, outSize - n);
179 outs = ret;
180 } else {
181 System.arraycopy(outs, n, outs, n + 1, outSize - n);
182 }
183 outs[n] = e;
184 ++outSize;
185 }
186
187 public IEdge removeIn(int n) {
188 IEdge ret = ins[n];
189 --inSize;
190 if (n != inSize)
191 System.arraycopy(ins, n + 1, ins, n, inSize - n);
192 ins[inSize] = null;
193 return ret;
194 }
195
196 public boolean removeIn(IEdge e) {
197 for (int i = 0; i < inSize; ++i) {
198 if (e.equals(ins[i]))
199 return removeIn(i) != null;
200 }
201 return false;
202 }
203
204 /**
205 * Remove all edges coming from given vertex.
206 * @return Number of edges removed.
207 */
208 public int removeInsFrom(IVertex v) {
209 int ret = 0;
210 for (int i = 0; i < inSize; ++i) {
211 if (ins[i].getTail().equals(v)) {
212 removeIn(i);
213 ++ret;
214 }
215 }
216 return ret;
217 }
218
219 public IEdge removeOut(int n) {
220 IEdge ret = outs[n];
221 --outSize;
222 if (n != outSize)
223 System.arraycopy(outs, n + 1, outs, n, outSize - n);
224 outs[outSize] = null;
225 return ret;
226 }
227
228 public boolean removeOut(IEdge e) {
229 for (int i = 0; i < outSize; ++i) {
230 if (e.equals(outs[i]))
231 return removeOut(i) != null;
232 }
233 return false;
234 }
235
236 /**
237 * Remove all edges to given vertex.
238 * @return Number of edges removed.
239 */
240 public int removeOutsTo(IVertex v) {
241 int ret = 0;
242 for (int i = 0; i < outSize; ++i) {
243 if (outs[i].getHead().equals(v)) {
244 removeOut(i);
245 ++ret;
246 }
247 }
248 return ret;
249 }
250
251 ////////////////////////////////////////////////////////////////////////
252
253 public int inSize() {
254 return inSize;
255 }
256
257 public int outSize() {
258 return outSize;
259 }
260
261 public IEdge[] ins() {
262 IEdge[] ret = new IEdge[inSize];
263 System.arraycopy(ins, 0, ret, 0, inSize);
264 return ret;
265 }
266
267 public IEdge[] outs() {
268 IEdge[] ret = new IEdge[outSize];
269 System.arraycopy(outs, 0, ret, 0, outSize);
270 return ret;
271 }
272
273 /** The set of all edges.
274 *
275 * NOTE: The set returned should be considered read only. Add or
276 * remove of edges should use method provided by the Edge class.
277 */
278 public IEdge[] edges() {
279 IEdge[] ret = new IEdge[ins.length + outs.length];
280 System.arraycopy(ins, 0, ret, 0, ins.length);
281 System.arraycopy(outs, 0, ret, ins.length, outs.length);
282 return ret;
283 }
284
285 public List findIns(String attrname, List ret) {
286 for (int i = 0; i < ins.length; i++) {
287 IEdge e = (IEdge) ins[i];
288 if (!e.hasAttr(attrname))
289 continue;
290 if (ret == null)
291 ret = new ArrayList();
292 ret.add(e);
293 }
294 return ret;
295 }
296
297 public List findOuts(String attrname, List ret) {
298 for (int i = 0; i < outs.length; i++) {
299 IEdge e = (IEdge) outs[i];
300 if (!e.hasAttr(attrname))
301 continue;
302 if (ret == null)
303 ret = new ArrayList();
304 ret.add(e);
305 }
306 return ret;
307 }
308
309 /**
310 * @return All edges from this vertex to the given vertex. If 'ret' is null and no edge if found, null is returned.
311 */
312 public List findEdgesTo(IVertex v, List ret) {
313 for (int i = 0; i < outs.length; ++i) {
314 IEdge e = outs[i];
315 if (e.getHead() == v) {
316 if (ret == null)
317 ret = new ArrayList();
318 ret.add(e);
319 }
320 }
321 return ret;
322 }
323
324 /**
325 * @return All edges from the given vertex to this vertex. If 'ret' is null and no edge if found, null is returned.
326 */
327 public List findEdgesFrom(IVertex v, List ret) {
328 for (int i = 0; i < inSize; i++) {
329 IEdge e = ins[i];
330 if (e.getTail() == v) {
331 if (ret == null)
332 ret = new ArrayList();
333 ret.add(e);
334 }
335 }
336 return ret;
337 }
338
339 /**
340 * @return All edges from this vertex to the given vertex with the given attribute defined locally.
341 * If 'ret' is null and no edge if found, null is returned.
342 */
343 public List findEdgesTo(IVertex v, String attrname, List ret) {
344 for (int i = 0; i < outs.length; ++i) {
345 IEdge e = outs[i];
346 if (e.getHead() == v) {
347 if (!e.hasAttr(attrname))
348 continue;
349 if (ret == null)
350 ret = new ArrayList();
351 ret.add(e);
352 }
353 }
354 return ret;
355 }
356
357 /**
358 * @return All edges from the given vertex to this vertex with the given attribute defined locally.
359 * If 'ret' is null and no edge if found, null is returned.
360 */
361 public List findEdgesFrom(IVertex v, String attrname, List ret) {
362 for (int i = 0; i < inSize; i++) {
363 IEdge e = ins[i];
364 if (e.getTail() == v) {
365 if (!e.hasAttr(attrname))
366 continue;
367 if (ret == null)
368 ret = new ArrayList();
369 ret.add(e);
370 }
371 }
372 return ret;
373 }
374
375 public void clearEdges() {
376 for (int i = 0; i < outSize; i++) {
377 IEdge e = outs[i];
378 getParent().removeEdge(e);
379 }
380 for (int i = 0; i < inSize; ++i) {
381 IEdge e = ins[i];
382 getParent().removeEdge(e);
383 }
384 }
385
386 public void clearLayout() {
387 for (Iterator it = new HashSet(attrKeySet()).iterator(); it.hasNext();) {
388 String attr = (String) it.next();
389 if (attr.startsWith("-")||attr.equals("pos"))
390 removeAttr(attr);
391 }
392 for(int i=0; i<outs.length; ++i) {
393 IEdge e=outs[i];
394 e.clearLayout();
395 }
396 }
397
398 public void pack() {
399 ins = ins();
400 outs = outs();
401 }
402
403 /** Set of directly conected vertex.
404 *
405 * NOTE: The set returned should be considered read only. Add or
406 * remove of neighours should be done by add/remove edges.
407 *
408 */
409 public Set neighbours() {
410 Set ret = new HashSet();
411 for (int i = 0; i < outSize; i++) {
412 IEdge e = outs[i];
413 ret.add(e.getHead());
414 }
415 for (int i = 0; i < inSize; i++) {
416 IEdge e = ins[i];
417 ret.add(e.getTail());
418 }
419 return ret;
420 }
421
422 /** @return set of all directly/indirectly connected vertex.
423 */
424 public Set reachable() {
425 Set visited = new HashSet();
426 Stack stack = new Stack();
427 IVertex v;
428 IEdge[] ret;
429 int size = 1;
430 // A depth first transversal.
431 stack.push(this);
432 visited.add(this);
433 while (size != 0) {
434 v = (IVertex) stack.pop();
435 --size;
436 ret = v.outs();
437 for (int i = 0, max = ret.length; i < max; ++i) {
438 v = ret[i].getHead();
439 if (visited.add(v)) {
440 stack.push(v);
441 ++size;
442 }
443 }
444 }
445 return visited;
446 }
447
448 public boolean isReachable(IVertex target) {
449 //
450 if (target == this)
451 return true;
452 //
453 Set visited = new HashSet();
454 Stack stack = new Stack();
455 IVertex v;
456 IEdge[] ret;
457 int size = 1;
458 // A depth first transversal.
459 stack.push(this);
460 visited.add(this);
461 while (size != 0) {
462 v = (IVertex) stack.pop();
463 --size;
464 ret = v.outs();
465 for (int i = 0, max = ret.length; i < max; ++i) {
466 v = ret[i].getHead();
467 if (visited.add(v)) {
468 if (v == target)
469 return true;
470 stack.push(v);
471 ++size;
472 }
473 }
474 }
475 return false;
476 }
477
478 // IGraphElement interface //////////////////////////////////////////////
479 //
480 public String getElementTypeName() {
481 return NAME;
482 }
483
484 public int hashCode() {
485 return fName.hashCode();
486 }
487
488 public boolean equals(Object a) {
489 if (!(a instanceof Vertex))
490 return false;
491 Vertex aa = (Vertex) a;
492 if (parent == null && aa.parent != null)
493 return false;
494 if (!parent.equals(aa.getParent()))
495 return false;
496 return fName.equals(aa.getName());
497 }
498
499 ////////////////////////////////////////////////////////////////////////
500
501 }