Source code: com/phoenixst/plexus/Graph.java
1 /*
2 * $Id: Graph.java,v 1.17 2003/10/29 22:47:31 rconner Exp $
3 *
4 * Copyright (C) 1994-2003 by Phoenix Software Technologists,
5 * Inc. and others. All rights reserved.
6 *
7 * THIS PROGRAM AND DOCUMENTATION IS PROVIDED UNDER THE TERMS OF THE
8 * COMMON PUBLIC LICENSE ("AGREEMENT") WHICH ACCOMPANIES IT. ANY
9 * USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM CONSTITUTES
10 * RECIPIENT'S ACCEPTANCE OF THE AGREEMENT.
11 *
12 * The license text can also be found at
13 * http://opensource.org/licenses/cpl.php
14 */
15
16 package com.phoenixst.plexus;
17
18 import java.util.*;
19
20
21 /**
22 * The root interface of the graph hierarchy.
23 *
24 * <P>See the <a href="{@docRoot}/overview-summary.html">Overview
25 * Summary</a> for details not included here.
26 *
27 * <P>Nodes must contain unique (using {@link Object#equals
28 * Object.equals()}) user-provided objects. This requirement allows
29 * nodes to be referenced unambiguously (when creating edges, for
30 * example). The user-defined objects contained in {@link Edge}
31 * objects, however, are not subject to this requirement in the
32 * general case, although <code>Object.equals()</code> will be used
33 * for edge comparisons.
34 *
35 * <P>Nothing in this interface prohibits a {@link Edge} from also
36 * being a node in the same <code>Graph</code>. In other words,
37 * <code>Edges</code> can point to other <code>Edges</code>. If a
38 * particular <code>Graph</code> implementation allows this, these
39 * two aspects of any particular <code>Edge</code> are independent.
40 * Adding or removing an <code>Edge</code> as a node has no impact
41 * upon the object's existence as an <code>Edge</code>, and vice
42 * versa.
43 *
44 * <P>All general-purpose implementations of this interface should
45 * provide two "standard" constructors: a void (no arguments)
46 * constructor, which creates an empty graph, and a constructor with
47 * a single argument of type <code>Graph</code>, which creates a new
48 * graph with the same elements as its argument.
49 *
50 * @version $Revision: 1.17 $
51 * @author Ray A. Conner
52 *
53 * @since 1.0
54 */
55 public interface Graph
56 {
57
58 /**
59 * Returns whether or not this <code>Graph</code> is directed.
60 *
61 * @return whether or not this <code>Graph</code> is directed.
62 */
63 public boolean isDirected();
64
65
66 /**
67 * Returns whether or not this <code>Graph</code> is simple.
68 *
69 * @return whether or not this <code>Graph</code> is simple.
70 */
71 public boolean isSimple();
72
73
74 /**
75 * Returns <code>true</code> if this <code>Graph</code> contains
76 * no edges, it may contain nodes.
77 *
78 * @return <code>true</code> if this <code>Graph</code> contains
79 * no edges, it may contain nodes.
80 */
81 public boolean isEmpty();
82
83
84 /**
85 * Returns the number of nodes in this <code>Graph</code>. If
86 * this <code>Graph</code> contains more than
87 * <code>Integer.MAX_VALUE</code> nodes, returns
88 * <code>Integer.MAX_VALUE</code>.
89 *
90 * @return the number of nodes in this <code>Graph</code>.
91 */
92 public int nodeSize();
93
94
95 /**
96 * Returns the number of edges in this <code>Graph</code>. If
97 * this <code>Graph</code> contains more than
98 * <code>Integer.MAX_VALUE</code> edges, returns
99 * <code>Integer.MAX_VALUE</code>.
100 *
101 * @return the number of edges in this <code>Graph</code>.
102 */
103 public int edgeSize();
104
105
106 /**
107 * Returns the degree of <code>node</code>, defined as the number
108 * of edges incident on <code>node</code>, with self-loops
109 * counted twice. If this node has more than
110 * <code>Integer.MAX_VALUE</code> incident edges, returns
111 * <code>Integer.MAX_VALUE</code>.
112 *
113 * @param node return the degree of this node.
114 *
115 * @return the degree of <code>node</code>.
116 *
117 * @throws ClassCastException if the class of <code>node</code>
118 * is of an inappropriate class for this <code>Graph</code>.
119 *
120 * @throws IllegalArgumentException if some aspect of
121 * <code>node</code> is inappropriate for this
122 * <code>Graph</code>.
123 *
124 * @throws NoSuchNodeException if <code>node</code> is not
125 * present in this <code>Graph</code>.
126 *
127 * @throws NullPointerException if <code>node</code> is
128 * <code>null</code> and this <code>Graph</code> does not not
129 * permit <code>null</code> nodes.
130 */
131 public int degree( Object node );
132
133
134 /**
135 * If this is a directed graph, returns the out degree of
136 * <code>node</code>, defined as the number of edges leaving
137 * <code>node</code>. If this is not a directed graph, throws
138 * <code>UnsupportedOperationException</code>. If this node has
139 * more than <code>Integer.MAX_VALUE</code> edges leaving it,
140 * returns <code>Integer.MAX_VALUE</code>.
141 *
142 * @param node return the out degree of this node.
143 *
144 * @return the out degree of <code>node</code>.
145 *
146 * @throws ClassCastException if the class of <code>node</code>
147 * is of an inappropriate class for this <code>Graph</code>.
148 *
149 * @throws IllegalArgumentException if some aspect of
150 * <code>node</code> is inappropriate for this
151 * <code>Graph</code>.
152 *
153 * @throws NoSuchNodeException if <code>node</code> is not
154 * present in this <code>Graph</code>.
155 *
156 * @throws NullPointerException if <code>node</code> is
157 * <code>null</code> and this <code>Graph</code> does not not
158 * permit <code>null</code> nodes.
159 *
160 * @throws UnsupportedOperationException if this method is not
161 * supported by this <code>Graph</code>.
162 */
163 public int outDegree( Object node );
164
165
166 /**
167 * If this is a directed graph, returns the in degree of
168 * <code>node</code>, defined as the number of edges entering
169 * <code>node</code>. If this is not a directed graph, throws
170 * <code>UnsupportedOperationException</code>. If this node has
171 * more than <code>Integer.MAX_VALUE</code> edges entering it,
172 * returns <code>Integer.MAX_VALUE</code>.
173 *
174 * @param node return the in degree of this node.
175 *
176 * @return the in degree of <code>node</code>.
177 *
178 * @throws ClassCastException if the class of <code>node</code>
179 * is of an inappropriate class for this <code>Graph</code>.
180 *
181 * @throws IllegalArgumentException if some aspect of
182 * <code>node</code> is inappropriate for this
183 * <code>Graph</code>.
184 *
185 * @throws NoSuchNodeException if <code>node</code> is not
186 * present in this <code>Graph</code>.
187 *
188 * @throws NullPointerException if <code>node</code> is
189 * <code>null</code> and this <code>Graph</code> does not not
190 * permit <code>null</code> nodes.
191 *
192 * @throws UnsupportedOperationException if this method is not
193 * supported by this <code>Graph</code>.
194 */
195 public int inDegree( Object node );
196
197
198 /**
199 * Adds <code>node</code> to this <code>Graph</code> (optional
200 * operation). Returns <code>true</code> if this
201 * <code>Graph</code> changed as a result of the call. Returns
202 * <code>false</code> if this <code>Graph</code> already contains
203 * <code>node</code>.
204 *
205 * <P>If a <code>Graph</code> refuses to add a particular node
206 * for any reason other than that it already contains the node,
207 * it <i>must</i> throw an exception (rather than returning
208 * <code>false</code>). This preserves the invariant that a
209 * <code>Graph</code> always contains the specified node after
210 * this call returns. <Code>Graph</Code> classes should clearly
211 * specify in their documentation any other restrictions on what
212 * nodes may be added.
213 *
214 * @param node the node to be added to this <code>Graph</code>.
215 *
216 * @return <code>true</code> if this <code>Graph</code> changed
217 * as a result of the call, <code>false</code> if this
218 * <code>Graph</code> already contains the specified node.
219 *
220 * @throws ClassCastException if the class of <code>node</code>
221 * is of an inappropriate class for this <code>Graph</code>.
222 *
223 * @throws IllegalArgumentException if some aspect of
224 * <code>node</code> is inappropriate for this
225 * <code>Graph</code>.
226 *
227 * @throws NullPointerException if <code>node</code> is
228 * <code>null</code> and this <code>Graph</code> does not not
229 * permit <code>null</code> nodes.
230 *
231 * @throws UnsupportedOperationException if this method is not
232 * supported by this <code>Graph</code>.
233 */
234 public boolean addNode( Object node );
235
236
237 /**
238 * Removes <code>node</code> from this <code>Graph</code>
239 * (optional operation). This method will also remove all edges
240 * incident upon <code>node</code>.
241 *
242 * @param node the node to be removed from this
243 * <code>Graph</code>.
244 *
245 * @return <code>true</code> if this <code>Graph</code> contained
246 * <code>node</code>.
247 *
248 * @throws UnsupportedOperationException if this method is not
249 * supported by this <code>Graph</code>.
250 */
251 public boolean removeNode( Object node );
252
253
254 /**
255 * Returns <code>true</code> if this <code>Graph</code> contains
256 * the specified node.
257 *
258 * @param node the node whose presence in this <code>Graph</code>
259 * is to be tested.
260 *
261 * @return <code>true</code> if this <code>Graph</code> contains
262 * the specified node.
263 */
264 public boolean containsNode( Object node );
265
266
267 /**
268 * Adds the specified edge to the <code>Graph</code> (optional
269 * operation). Returns the newly created <code>Edge</code> if
270 * this <code>Graph</code> changed as a result of the call.
271 * Returns <code>null</code> if this <code>Graph</code> does not
272 * allow duplicate edges and already contains the specified edge.
273 *
274 * <P>If a <code>Graph</code> refuses to add a particular edge
275 * for any reason other than that it already contains the edge,
276 * it <i>must</i> throw an exception (rather than returning
277 * <code>null</code>). This preserves the invariant that a
278 * <code>Graph</code> always contains the specified edge after
279 * this call returns. <Code>Graph</Code> classes should clearly
280 * specify in their documentation any other restrictions on what
281 * edges may be added.
282 *
283 * @param object the user-defined object to be contained in the
284 * new edge.
285 *
286 * @param tail the first endpoint of the new edge.
287 *
288 * @param head the second endpoint of the new edge.
289 *
290 * @return the newly created <code>Edge</code> if this
291 * <code>Graph</code> changed as a result of the call,
292 * <code>null</code> if this <code>Graph</code> does not allow
293 * duplicate edges and already contains the specified edge.
294 *
295 * @throws ClassCastException if the class of
296 * <code>object</code>, <code>tail</code>, or <code>head</code>
297 * is of an inappropriate class for this <code>Graph</code>.
298 *
299 * @throws IllegalArgumentException if some aspect of
300 * <code>object</code>, <code>tail</code>, or <code>head</code>
301 * is inappropriate for this <code>Graph</code>.
302 *
303 * @throws NoSuchNodeException if <code>tail</code> or
304 * <code>head</code> is not present in this <code>Graph</code>.
305 *
306 * @throws NullPointerException if <code>object</code>,
307 * <code>tail</code>, or <code>head</code> is <code>null</code>
308 * and this <code>Graph</code> does not not permit
309 * <code>null</code> edges and/or nodes.
310 *
311 * @throws UnsupportedOperationException if this method is not
312 * supported by this <code>Graph</code>.
313 */
314 public Edge addEdge( Object object, Object tail, Object head );
315
316
317 /**
318 * Removes the specified <code>Edge</code> from this
319 * <code>Graph</code> (optional operation).
320 *
321 * @param edge the <code>Edge</code> to be removed from this
322 * <code>Graph</code>.
323 *
324 * @return <code>true</code> if this <code>Graph</code> contained
325 * the specified <code>Edge</code>.
326 *
327 * @throws UnsupportedOperationException if this method is not
328 * supported by this <code>Graph</code>.
329 */
330 public boolean removeEdge( Edge edge );
331
332
333 /**
334 * Returns <code>true</code> if this <code>Graph</code> contains
335 * the specified <code>Edge</code>.
336 *
337 * @param edge the <code>Edge</code> whose presence in this
338 * <code>Graph</code> is to be tested.
339 *
340 * @return <code>true</code> if this <code>Graph</code> contains
341 * the specified <code>Edge</code>.
342 */
343 public boolean containsEdge( Edge edge );
344
345
346 /**
347 * Returns an <code>Edge</code> from this <code>Graph</code> with
348 * the specified tail and head, or <code>null</code> if it does
349 * not exist.
350 *
351 * @param tail the first endpoint of the edge whose presence in
352 * this <code>Graph</code> is to be tested.
353 *
354 * @param head the second endpoint of the edge whose presence in
355 * this <code>Graph</code> is to be tested.
356 *
357 * @return an <code>Edge</code> from this <code>Graph</code> with
358 * the specified tail and head, or <code>null</code> if it does
359 * not exist.
360 *
361 * @throws ClassCastException if the class of <code>tail</code>
362 * or <code>head</code> is of an inappropriate class for this
363 * <code>Graph</code>.
364 *
365 * @throws IllegalArgumentException if some aspect of
366 * <code>tail</code> or <code>head</code> is inappropriate for
367 * this <code>Graph</code>.
368 *
369 * @throws NoSuchNodeException if <code>tail</code> or
370 * <code>head</code> is not present in this <code>Graph</code>.
371 *
372 * @throws NullPointerException if <code>tail</code> or
373 * <code>head</code> is <code>null</code> and this
374 * <code>Graph</code> does not not permit <code>null</code>
375 * nodes.
376 */
377 public Edge getEdge( Object tail, Object head );
378
379
380 /**
381 * Removes all nodes and edges from this <code>Graph</code>
382 * (optional operation).
383 *
384 * @throws UnsupportedOperationException if this method is not
385 * supported by this <code>Graph</code>.
386 */
387 public void clear();
388
389
390 /**
391 * Returns an <code>Iterator</code> over all the nodes in this
392 * <code>Graph</code>. Calling {@link Iterator#remove} removes
393 * the last node returned by the <code>Iterator</code>, and all
394 * edges incident upon that node, from this <code>Graph</code>.
395 * There are no guarantees concerning the order in which the
396 * nodes are returned (unless this <code>Graph</code> is an
397 * instance of some class that provides a guarantee).
398 *
399 * @return an <code>Iterator</code> over all the nodes in this
400 * <code>Graph</code>.
401 */
402 public Iterator nodeIterator();
403
404
405 /**
406 * Returns an <code>Iterator</code> over all the
407 * <code>Edges</code> in this <code>Graph</code>. There are no
408 * guarantees concerning the order in which the edges are
409 * returned (unless this <code>Graph</code> is an instance of
410 * some class that provides a guarantee).
411 *
412 * @return an <code>Iterator</code> over all the
413 * <code>Edges</code> in this <code>Graph</code>.
414 */
415 public Iterator edgeIterator();
416
417
418 /**
419 * Returns an <code>Iterator</code> over all <code>Edges</code>
420 * from this <code>Graph</code> with the specified tail and head.
421 *
422 * @param tail the first endpoint of edges to be iterated over.
423 *
424 * @param head the second endpoint of edges to be iterated over.
425 *
426 * @return an <code>Iterator</code> over all <code>Edges</code>
427 * from this <code>Graph</code> with the specified tail and head.
428 *
429 * @throws ClassCastException if the class of <code>tail</code>
430 * or <code>head</code> is of an inappropriate class for this
431 * <code>Graph</code>.
432 *
433 * @throws IllegalArgumentException if some aspect of
434 * <code>tail</code> or <code>head</code> is inappropriate for
435 * this <code>Graph</code>.
436 *
437 * @throws NoSuchNodeException if <code>tail</code> or
438 * <code>head</code> is not present in this <code>Graph</code>.
439 *
440 * @throws NullPointerException if <code>tail</code> or
441 * <code>head</code> is <code>null</code> and this
442 * <code>Graph</code> does not not permit <code>null</code>
443 * nodes.
444 */
445 public Iterator edgeIterator( Object tail, Object head );
446
447
448 /**
449 * Returns a <code>Traverser</code> from <code>node</code> to all
450 * adjacent nodes. If the implementation is a multigraph, the
451 * nodes returned by {@link Traverser#next} are not necessarily
452 * distinct. Self-loops are only traversed once. There are no
453 * guarantees concerning the order in which the nodes are
454 * returned (unless this <code>Graph</code> is an instance of
455 * some class that provides a guarantee).
456 *
457 * @param node traverse over all nodes adjacent to this node.
458 *
459 * @return a <code>Traverser</code> from <code>node</code> to all
460 * adjacent nodes.
461 *
462 * @throws ClassCastException if the class of <code>node</code>
463 * is of an inappropriate class for this <code>Graph</code>.
464 *
465 * @throws IllegalArgumentException if some aspect of
466 * <code>node</code> is inappropriate for this
467 * <code>Graph</code>.
468 *
469 * @throws NoSuchNodeException if <code>node</code> is not
470 * present in this <code>Graph</code>.
471 *
472 * @throws NullPointerException if <code>node</code> is
473 * <code>null</code> and this <code>Graph</code> does not not
474 * permit <code>null</code> nodes.
475 */
476 public Traverser traverser( Object node );
477
478
479 /**
480 * If this is a directed graph, returns a <code>Traverser</code>
481 * from <code>node</code> to all adjacent nodes reachable through
482 * edges whose tail is the given node. If this is not a directed
483 * graph, throws <code>UnsupportedOperationException</code>. If
484 * the implementation is a multigraph, the nodes returned by
485 * {@link Traverser#next} are not necessarily distinct. There
486 * are no guarantees concerning the order in which the nodes are
487 * returned (unless this <code>Graph</code> is an instance of
488 * some class that provides a guarantee).
489 *
490 * @param node traverse over all adjacent nodes reachable by
491 * traversing edges leaving this node.
492 *
493 * @return a <code>Traverser</code> from <code>node</code> to all
494 * adjacent nodes reachable through edges whose tail is the given
495 * node.
496 *
497 * @throws ClassCastException if the class of <code>node</code>
498 * is of an inappropriate class for this <code>Graph</code>.
499 *
500 * @throws IllegalArgumentException if some aspect of
501 * <code>node</code> is inappropriate for this
502 * <code>Graph</code>.
503 *
504 * @throws NoSuchNodeException if <code>node</code> is not
505 * present in this <code>Graph</code>.
506 *
507 * @throws NullPointerException if <code>node</code> is
508 * <code>null</code> and this <code>Graph</code> does not not
509 * permit <code>null</code> nodes.
510 *
511 * @throws UnsupportedOperationException if this method is not
512 * supported by this <code>Graph</code>.
513 */
514 public Traverser outTraverser( Object node );
515
516
517 /**
518 * If this is a directed graph, returns a <code>Traverser</code>
519 * from <code>node</code> to all adjacent nodes reachable through
520 * edges whose head is the given node. If this is not a directed
521 * graph, throws <code>UnsupportedOperationException</code>. If
522 * the implementation is a multigraph, the nodes returned by
523 * {@link Traverser#next} are not necessarily distinct. There
524 * are no guarantees concerning the order in which the nodes are
525 * returned (unless this <code>Graph</code> is an instance of
526 * some class that provides a guarantee).
527 *
528 * @param node traverse over all adjacent nodes reachable by
529 * traversing edges entering this node.
530 *
531 * @return a <code>Traverser</code> from <code>node</code> to all
532 * adjacent nodes reachable through edges whose head is the given
533 * node.
534 *
535 * @throws ClassCastException if the class of <code>node</code>
536 * is of an inappropriate class for this <code>Graph</code>.
537 *
538 * @throws IllegalArgumentException if some aspect of
539 * <code>node</code> is inappropriate for this
540 * <code>Graph</code>.
541 *
542 * @throws NoSuchNodeException if <code>node</code> is not
543 * present in this <code>Graph</code>.
544 *
545 * @throws NullPointerException if <code>node</code> is
546 * <code>null</code> and this <code>Graph</code> does not not
547 * permit <code>null</code> nodes.
548 *
549 * @throws UnsupportedOperationException if this method is not
550 * supported by this <code>Graph</code>.
551 */
552 public Traverser inTraverser( Object node );
553
554
555 /**
556 * An interface describing an edge in a {@link Graph}. Please
557 * see {@link #equals(Object) equals( Object )} for important
558 * information on implementing this interface.
559 */
560 public interface Edge
561 {
562
563 /**
564 * Returns whether or not this <code>Edge</code> is directed.
565 *
566 * @return whether or not this <code>Edge</code> is directed.
567 */
568 public boolean isDirected();
569
570
571 /**
572 * Returns the user object contained in this <code>Edge</code>.
573 *
574 * @return the user object contained in this <code>Edge</code>.
575 */
576 public Object getUserObject();
577
578
579 /**
580 * Sets the user object contained in this <code>Edge</code>.
581 *
582 * @param object the user object to replace the one in this
583 * <code>Edge</code>.
584 *
585 * @throws ClassCastException if the class of <code>object</code>
586 * prevents it from being added to the {@link Graph} containing
587 * this <code>Edge</code>.
588 *
589 * @throws IllegalArgumentException if some aspect of
590 * <code>object</code> prevents it from being added to the {@link
591 * Graph} containing this <code>Edge</code>.
592 *
593 * @throws NullPointerException if <code>object</code> is
594 * <code>null</code> and the {@link Graph} containing this
595 * <code>Edge</code> does not not permit <code>null</code> edges.
596 *
597 * @throws UnsupportedOperationException if this method is not
598 * supported by this <code>Edge</code>.
599 */
600 public void setUserObject( Object object );
601
602
603 /**
604 * Returns the node which is the tail of this <code>Edge</code>.
605 *
606 * @return the node which is the tail of this <code>Edge</code>.
607 */
608 public Object getTail();
609
610
611 /**
612 * Returns the node which is the head of this <code>Edge</code>.
613 *
614 * @return the node which is the head of this <code>Edge</code>.
615 */
616 public Object getHead();
617
618
619 /**
620 * Returns the node which is at the other end of this
621 * <code>Edge</code> than the specified node.
622 *
623 * @param node the node which is the endpoint of this
624 * <code>Edge</code> not to return.
625 *
626 * @return the node which is at the other end of this
627 * <code>Edge</code> than the specified node.
628 *
629 * @throws IllegalArgumentException if this <code>Edge</code> is
630 * not incident on the specified node.
631 */
632 public Object getOtherEndpoint( Object node );
633
634
635 /**
636 * Returns whether or not some other object is equal to this
637 * one. It is vitally important that two <code>Edges</code>
638 * only be <code>.equals()</code> when they refer to the same
639 * actual edge in the graph. Which edge this is does not
640 * change when the contained user-defined object changes. In
641 * a multigraph, the endpoints and contained user-defined
642 * object are generally not sufficiently distinguishing
643 * characteristics. Accepting the default implementation
644 * from <code>Object</code>, which uses reference equality,
645 * should be preferred unless <code>Edges</code> are lazily
646 * created on demand.
647 *
648 * <P><b>Description copied from class: {@link Object}</b><br>
649 * {@inheritDoc}
650 */
651 public boolean equals( Object object );
652
653
654 /**
655 * Returns the hash code for this <code>Edge</code>. Since
656 * it is mutable, the contained user-defined object should
657 * not be used when computing the hash code.
658 *
659 * <P><b>Description copied from class: {@link Object}</b><br>
660 * {@inheritDoc}
661 */
662 public int hashCode();
663
664 }
665
666 }