1 pnkfelix 1.1.2.1 // Graph.java, created Wed Jan 13 15:51:26 1999 by pnkfelix
2 cananian 1.1.2.12 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.6 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.GraphColoring;
5 pnkfelix 1.1.2.1
6 cananian 1.3 import net.cscott.jutil.UniqueVector;
7 pnkfelix 1.1.2.1
8 pnkfelix 1.1.2.8 import java.util.Set;
9 pnkfelix 1.1.2.8 import java.util.Collection;
10 pnkfelix 1.1.2.1
11 pnkfelix 1.1.2.1 /**
12 pnkfelix 1.1.2.9 * Abstractly, a <code>Graph</code> is a pair (V, E), where V is a set
13 pnkfelix 1.1.2.9 * of nodes and E is collection of edges between those nodes.
14 pnkfelix 1.1.2.9 *
15 pnkfelix 1.1.2.9 * (E is a collection instead of a set to allow for <i>multigraphs</i>
16 pnkfelix 1.1.2.9 * which allow multiple edges to exist between the same two nodes)
17 pnkfelix 1.1.2.9 *
18 pnkfelix 1.1.2.9 * The <code>Graph</code> interface provides a number of <i>collection
19 pnkfelix 1.1.2.9 * views</i> of the data maintained by a graph. In addition to being
20 pnkfelix 1.1.2.9 * able to view the nodes and their neighbors, one can also view the
21 pnkfelix 1.1.2.9 * edges between the nodes themselves. Note that since some graphs
22 pnkfelix 1.1.2.9 * may not concretely maintain edge objects in their internal
23 pnkfelix 1.1.2.10 * representation, the edges may have to be constructed on demand
24 pnkfelix 1.1.2.10 * (a performance drain).
25 pnkfelix 1.1.2.1 *
26 cananian 1.1.2.12 * @author Felix S. Klock II <pnkfelix@mit.edu>
27 cananian 1.3 * @version $Id: Graph.java,v 1.3 2004/02/08 01:52:03 cananian Exp $
28 pnkfelix 1.1.2.1 */
29 pnkfelix 1.1.2.1
30 pnkfelix 1.1.2.8 public interface Graph {
31 pnkfelix 1.1.2.1
32 pnkfelix 1.1.2.10 /** Ensures that this graph contains <code>node</code> (optional operation).
33 pnkfelix 1.1.2.4 <BR> <B>modifies:</B> <code>this</code>
34 pnkfelix 1.1.2.9 <BR> <B>effects:</B> If this method returns normally,
35 pnkfelix 1.1.2.9 <code>node</code> will be present in the node-set for
36 pnkfelix 1.1.2.9 <code>this</code>. Returns <tt>true</tt> if this graph
37 pnkfelix 1.1.2.9 changed as a result of the call, <tt>false</tt>
38 pnkfelix 1.1.2.9 otherwise.
39 pnkfelix 1.1.2.9 @throws UnsupportedOperationException addNode is not supported
40 pnkfelix 1.1.2.9 by this graph.
41 pnkfelix 1.1.2.9 @throws ClassCastException class of specified element prevents
42 pnkfelix 1.1.2.9 it from being added to this graph.
43 pnkfelix 1.1.2.9 @throws IllegalArgumentException some aspect of
44 pnkfelix 1.1.2.9 <code>node</code> prevents it from being added to the
45 pnkfelix 1.1.2.9 node-set for this graph.
46 pnkfelix 1.1.2.1 */
47 pnkfelix 1.1.2.9 boolean addNode( Object node );
48 pnkfelix 1.1.2.4
49 pnkfelix 1.1.2.10 /** Ensures that this graph contains an edge between
50 pnkfelix 1.1.2.10 <code>m</code> and <code>n</code> (optional operation).
51 pnkfelix 1.1.2.4 <BR> <B>modifies:</B> <code>this</code>.
52 pnkfelix 1.1.2.9 <BR> <B>effects:</B> If this method returns normally, an edge
53 pnkfelix 1.1.2.10 between <code>m</code> and <code>n</code> will be in
54 pnkfelix 1.1.2.9 <code>this</code>. Returns <tt>true</tt> if
55 pnkfelix 1.1.2.9 <code>this</code> changed as a result of the call.
56 pnkfelix 1.1.2.10 @throws IllegalArgumentException <code>m</code> or
57 pnkfelix 1.1.2.10 <code>n</code> is not present in the node set for
58 pnkfelix 1.1.2.9 <code>this</code>.
59 pnkfelix 1.1.2.9 @throws UnsupportedOperationException addEdge is not supported
60 pnkfelix 1.1.2.9 by this graph.
61 pnkfelix 1.1.2.1 */
62 pnkfelix 1.1.2.10 boolean addEdge( Object m, Object n );
63 pnkfelix 1.1.2.2
64 pnkfelix 1.1.2.1 /** Returns the degree of <code>node</code>.
65 pnkfelix 1.1.2.4 <BR> <B>effects:</B> Returns the number of other
66 pnkfelix 1.1.2.10 <code>Object</code>s that <code>node</code> is joined
67 pnkfelix 1.1.2.10 with.
68 pnkfelix 1.1.2.9 @throws IllegalArgumentException If <code>node</code> is not
69 pnkfelix 1.1.2.9 present in the node set for <code>this</code>.
70 pnkfelix 1.1.2.1 */
71 pnkfelix 1.1.2.8 int getDegree( Object node );
72 pnkfelix 1.1.2.8
73 pnkfelix 1.1.2.9 /** Returns a set view of the nodes in <code>this</code>.
74 pnkfelix 1.1.2.8 <BR> <B>effects:</B> Returns an <code>Set</code> of
75 pnkfelix 1.1.2.10 the <code>Object</code>s that have been successfully
76 pnkfelix 1.1.2.10 added to <code>this</code>.
77 pnkfelix 1.1.2.1 */
78 pnkfelix 1.1.2.9 Set nodeSet();
79 pnkfelix 1.1.2.1
80 pnkfelix 1.1.2.9 /** Returns a collection view for the neighbors of a specific node.
81 pnkfelix 1.1.2.9 <BR> <B>effects:</B> Returns an <code>Collection</code> of
82 pnkfelix 1.1.2.10 <code>Object</code>s that have an edge between
83 pnkfelix 1.1.2.10 <code>node</code> and them.
84 pnkfelix 1.1.2.10 <BR> <B>mandates:</B> <code>node</code> is not removed from
85 pnkfelix 1.1.2.10 <code>this</code> while the returned
86 pnkfelix 1.1.2.10 <code>Collection</code> is in use.
87 pnkfelix 1.1.2.11 @throws IllegalArgumentException If <code>node</code> is not
88 pnkfelix 1.1.2.11 present in the node set for <code>this</code>.
89 pnkfelix 1.1.2.1 */
90 pnkfelix 1.1.2.9 Collection neighborsOf( Object node );
91 pnkfelix 1.1.2.9
92 pnkfelix 1.1.2.9 /** Returns a collection view of the edges contained in this graph.
93 pnkfelix 1.1.2.9 <BR> <B>effects:</B> Returns a <code>Collection</code> of
94 pnkfelix 1.1.2.10 two-element <code>Collection</code>s (known as
95 pnkfelix 1.1.2.10 <i>pairs</i>) where each pair corresponds to an edge
96 pnkfelix 1.1.2.10 { n1, n2 } in this. If the graph is modified while an
97 pnkfelix 1.1.2.10 iteration over the collection is in progress, the results
98 pnkfelix 1.1.2.10 of the iteration are undefined. Order may or
99 pnkfelix 1.1.2.10 may not be significant in the pairs returned.
100 pnkfelix 1.1.2.9 */
101 pnkfelix 1.1.2.9 Collection edges();
102 pnkfelix 1.1.2.9
103 pnkfelix 1.1.2.9 /** Returns a collection view of the edges joining
104 pnkfelix 1.1.2.9 <code>node</code> to nodes in the graph.
105 pnkfelix 1.1.2.9 <BR> <B>effects:</B> Returns a <code>Collection</code> of
106 pnkfelix 1.1.2.10 two-element <code>Collection</code>s (known as
107 pnkfelix 1.1.2.10 <i>pairs</i>) where each pair corresponds to an edge
108 pnkfelix 1.1.2.10 { node, n } in this. If the graph is modified while an
109 pnkfelix 1.1.2.9 iteration over the collection is in progress, the results
110 pnkfelix 1.1.2.10 of the iteration are undefined. Order may or may not be
111 pnkfelix 1.1.2.10 significant in the pairs returned.
112 pnkfelix 1.1.2.10 @throws IllegalArgumentException If <code>node</code> is not
113 pnkfelix 1.1.2.10 present in the node set for <code>this</code>.
114 pnkfelix 1.1.2.9 */
115 pnkfelix 1.1.2.9 Collection edgesFor( Object node );
116 pnkfelix 1.1.2.1
117 pnkfelix 1.1.2.1 }
118 pnkfelix 1.1.2.1
119 pnkfelix 1.1.2.1
120 cananian 1.2