1 pnkfelix 1.1.2.1 // Graph.java, created Wed Jan 13 15:51:26 1999 by pnkfelix
2 cananian 1.1.2.5 // Copyright (C) 1998 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // 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.1 import java.util.Enumeration;
9 pnkfelix 1.1.2.1
10 pnkfelix 1.1.2.1 /**
11 pnkfelix 1.1.2.3 * <code>GraphImpl</code> is an abstract class containing the framework
12 pnkfelix 1.1.2.1 * for implementing a graph object.
13 pnkfelix 1.1.2.1 *
14 pnkfelix 1.1.2.3 * @deprecated replaced by <code>Graph</code> interface.
15 cananian 1.1.2.5 * @author Felix S. Klock II <pnkfelix@mit.edu>
16 cananian 1.3 * @version $Id: GraphImpl.java,v 1.3 2004/02/08 01:52:03 cananian Exp $
17 pnkfelix 1.1.2.1 */
18 pnkfelix 1.1.2.1
19 pnkfelix 1.1.2.4 abstract class GraphImpl extends AbstractGraph {
20 pnkfelix 1.1.2.1
21 pnkfelix 1.1.2.3 protected UniqueVector nodes;
22 pnkfelix 1.1.2.1
23 pnkfelix 1.1.2.1 /** Creates a <code>Graph</code>. */
24 pnkfelix 1.1.2.1 public GraphImpl() {
25 pnkfelix 1.1.2.1 nodes = new UniqueVector();
26 pnkfelix 1.1.2.1 }
27 pnkfelix 1.1.2.1
28 pnkfelix 1.1.2.1 /** Adds <code>node</code> to <code>this</code>.
29 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <OL>
30 pnkfelix 1.1.2.1 <LI> <code>this</code> is modifiable,
31 pnkfelix 1.1.2.1 <LI> <code>node</code> is of the correct type
32 pnkfelix 1.1.2.1 for the graph type implemented by
33 pnkfelix 1.1.2.1 <code>this</code>.
34 pnkfelix 1.1.2.1 </OL>
35 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>
36 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Adds <code>node</code> to
37 pnkfelix 1.1.2.1 <code>this</code>, if <code>node</code>
38 pnkfelix 1.1.2.1 is not already a member of
39 pnkfelix 1.1.2.1 <code>this</code>.
40 pnkfelix 1.1.2.1 Else does nothing.
41 pnkfelix 1.1.2.1 */
42 pnkfelix 1.1.2.1 public void addNode( Node node )
43 pnkfelix 1.1.2.1 throws WrongNodeTypeException, ObjectNotModifiableException {
44 pnkfelix 1.1.2.1 // modifies: this.nodes
45 pnkfelix 1.1.2.1 if (this.isModifiable()) {
46 pnkfelix 1.1.2.1 checkNode( node );
47 pnkfelix 1.1.2.1 nodes.addElement( node );
48 pnkfelix 1.1.2.1 } else {
49 pnkfelix 1.1.2.1 throw new ObjectNotModifiableException
50 pnkfelix 1.1.2.1 (node + " can not be added to " +
51 pnkfelix 1.1.2.1 this + "; it is not modifiable.");
52 pnkfelix 1.1.2.1 }
53 pnkfelix 1.1.2.1 }
54 pnkfelix 1.1.2.3
55 pnkfelix 1.1.2.1 /** Node type-checking method for subclasses to implement.
56 pnkfelix 1.1.2.1 <BR> <B>effects:</B> If <code>node</code> is of the wrong type
57 pnkfelix 1.1.2.1 for the graph implementation being used,
58 pnkfelix 1.1.2.1 throws
59 pnkfelix 1.1.2.1 <code>WrongNodeTypeException</code>.
60 pnkfelix 1.1.2.1 Else does nothing.
61 pnkfelix 1.1.2.1 */
62 pnkfelix 1.1.2.1 protected abstract void checkNode( Node node );
63 pnkfelix 1.1.2.1
64 pnkfelix 1.1.2.1 /** Generates an edge from <code>from</code> to <code>to</code>.
65 pnkfelix 1.1.2.1 Subclasses should implement this method to match their
66 pnkfelix 1.1.2.1 internal representation of a graph.
67 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>from</code> and <code>to</code>
68 pnkfelix 1.1.2.1 are present in <code>this</code> and are
69 pnkfelix 1.1.2.1 valid targets for a new edge.
70 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>, <code>from</code>,
71 pnkfelix 1.1.2.1 <code>to</code>.
72 pnkfelix 1.1.2.1 */
73 pnkfelix 1.1.2.1 protected abstract void makeEdge( Node from, Node to );
74 pnkfelix 1.1.2.1
75 pnkfelix 1.1.2.1 /** Adds an edge from <code>from</code> to <code>to</code>.
76 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>from</code> and <code>to</code>
77 pnkfelix 1.1.2.1 are present in <code>this</code> and are
78 pnkfelix 1.1.2.1 valid targets for a new edge.
79 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>.
80 pnkfelix 1.1.2.1 */
81 pnkfelix 1.1.2.1 public void addEdge( Node from, Node to ) {
82 pnkfelix 1.1.2.1 if (this.isModifiable()) {
83 pnkfelix 1.1.2.1 makeEdge( from, to );
84 pnkfelix 1.1.2.1 } else {
85 pnkfelix 1.1.2.1 throw new ObjectNotModifiableException
86 pnkfelix 1.1.2.1 ("Edge can not be added to " +
87 pnkfelix 1.1.2.1 this + "; it is not modifiable.");
88 pnkfelix 1.1.2.1 }
89 pnkfelix 1.1.2.1
90 pnkfelix 1.1.2.1 }
91 pnkfelix 1.1.2.1
92 pnkfelix 1.1.2.1 /** Returns the degree of <code>node</code>.
93 pnkfelix 1.1.2.1 <BR> <B>requires:</B>: <code>node</code> is present in
94 pnkfelix 1.1.2.1 <code>this</code>
95 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns the number of other
96 pnkfelix 1.1.2.1 <code>ColorableNode</code>s that
97 pnkfelix 1.1.2.1 <code>node</code> is connected to.
98 pnkfelix 1.1.2.1 */
99 pnkfelix 1.1.2.1 public abstract int getDegree( Node node )
100 pnkfelix 1.1.2.1 throws NodeNotPresentInGraphException;
101 pnkfelix 1.1.2.1
102 pnkfelix 1.1.2.1 /** Constructs an enumeration for all the nodes.
103 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
104 pnkfelix 1.1.2.1 the <code>Node</code>s that have been
105 pnkfelix 1.1.2.1 successfully added to <code>this</code>.
106 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>this</code> is not modified while
107 pnkfelix 1.1.2.1 the <code>Enumeration</code> returned is
108 pnkfelix 1.1.2.1 still in use.
109 pnkfelix 1.1.2.1 */
110 pnkfelix 1.1.2.1 public Enumeration getNodes() {
111 pnkfelix 1.1.2.1 return nodes.elements();
112 pnkfelix 1.1.2.1 }
113 pnkfelix 1.1.2.1
114 pnkfelix 1.1.2.1 /** Constructs an enumeration for the children of a specific node.
115 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
116 pnkfelix 1.1.2.1 <code>Node</code>s that have an edge from
117 pnkfelix 1.1.2.1 <code>node</code> to them.
118 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>this</code> is not modified while
119 pnkfelix 1.1.2.1 the <code>Enumeration</code> returned is
120 pnkfelix 1.1.2.1 still in use.
121 pnkfelix 1.1.2.1 */
122 pnkfelix 1.1.2.1 public abstract Enumeration getChildrenOf( Node node )
123 pnkfelix 1.1.2.1 throws NodeNotPresentInGraphException;
124 pnkfelix 1.1.2.1
125 pnkfelix 1.1.2.1 /** Constructs an enumeration for the parents of a specific node.
126 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
127 pnkfelix 1.1.2.1 <code>Node</code>s that have an edge from
128 pnkfelix 1.1.2.1 them to <code>node</code>.
129 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>this</code> is not modified while
130 pnkfelix 1.1.2.1 the <code>Enumeration</code> returned is
131 pnkfelix 1.1.2.1 still in use.
132 pnkfelix 1.1.2.1 */
133 pnkfelix 1.1.2.1 public abstract Enumeration getParentsOf( Node node )
134 pnkfelix 1.1.2.1 throws NodeNotPresentInGraphException;
135 pnkfelix 1.1.2.1
136 pnkfelix 1.1.2.1 /** Constructs an enumeration for the parents of a specific node.
137 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns an <code>Enumeration</code> of
138 pnkfelix 1.1.2.1 <code>Node</code>s that have an edge
139 pnkfelix 1.1.2.1 between <code>node</code> and them.
140 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>this</code> is not modified while
141 pnkfelix 1.1.2.1 the <code>Enumeration</code> returned is
142 pnkfelix 1.1.2.1 still in use.
143 pnkfelix 1.1.2.1 */
144 pnkfelix 1.1.2.1 public abstract Enumeration getNeighborsOf( Node node )
145 pnkfelix 1.1.2.1 throws NodeNotPresentInGraphException;
146 pnkfelix 1.1.2.1
147 pnkfelix 1.1.2.1 /** Nodes accessor method for subclass use.
148 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns the <code>UniqueVector</code> of the
149 pnkfelix 1.1.2.1 <code>Node</code>s that have been
150 pnkfelix 1.1.2.1 successfully added to <code>this</code>.
151 pnkfelix 1.1.2.1 */
152 pnkfelix 1.1.2.1 protected UniqueVector getNodeVector() {
153 pnkfelix 1.1.2.1 return nodes;
154 pnkfelix 1.1.2.1 }
155 pnkfelix 1.1.2.1
156 pnkfelix 1.1.2.1 /** Modifiability check.
157 pnkfelix 1.1.2.1 Subclasses should override this method to incorporate
158 pnkfelix 1.1.2.1 consistency checks
159 pnkfelix 1.1.2.1 <BR> <B>effects:</B> If <code>this</code> is allowed to be modified,
160 pnkfelix 1.1.2.1 returns true. Else returns false.
161 pnkfelix 1.1.2.1 */
162 pnkfelix 1.1.2.1 public boolean isModifiable() {
163 pnkfelix 1.1.2.1 return true;
164 pnkfelix 1.1.2.1 }
165 pnkfelix 1.1.2.1
166 pnkfelix 1.1.2.1 }
167 pnkfelix 1.1.2.1
168 pnkfelix 1.1.2.1
169 cananian 1.2