|
1
19
20 package edu.umd.cs.findbugs.graph;
21
22 import java.util.ArrayList  ;
23 import java.util.Iterator ;
24 import java.util.NoSuchElementException ;
25
26
39 public abstract class AbstractGraph
40 <
41 EdgeType extends AbstractEdge<EdgeType, VertexType>,
42 VertexType extends AbstractVertex<EdgeType, VertexType>
43 > implements Graph<EdgeType, VertexType> {
44
45
48
49
52 private static class OutgoingEdgeIterator
53 <
54 EdgeType extends AbstractEdge<EdgeType, VertexType>,
55 VertexType extends AbstractVertex<EdgeType, VertexType>
56 > implements Iterator <EdgeType> {
57
58 private EdgeType edge;
59
60 public OutgoingEdgeIterator(VertexType source) {
61 this.edge = source.getFirstOutgoingEdge();
62 }
63
64 public boolean hasNext() {
65 return edge != null;
66 }
67
68 public EdgeType next() {
69 if (!hasNext())
70 throw new NoSuchElementException ();
71 EdgeType result = edge;
72 edge = edge.getNextOutgoingEdge();
73 return result;
74 }
75
76 public void remove() {
77 throw new UnsupportedOperationException ();
78 }
79 }
80
81
84 private static class IncomingEdgeIterator
85 <
86 EdgeType extends AbstractEdge<EdgeType, VertexType>,
87 VertexType extends AbstractVertex<EdgeType, VertexType>
88 > implements Iterator <EdgeType> {
89
90 private EdgeType edge;
91
92 public IncomingEdgeIterator(VertexType target) {
93 this.edge = target.getFirstIncomingEdge();
94 }
95
96 public boolean hasNext() {
97 return edge != null;
98 }
99
100 public EdgeType next() {
101 if (!hasNext())
102 throw new NoSuchElementException ();
103 EdgeType result = edge;
104 edge = edge.getNextIncomingEdge();
105 return result;
106 }
107
108 public void remove() {
109 throw new UnsupportedOperationException ();
110 }
111 }
112
113
116
117 private ArrayList <VertexType> vertexList;
118 private ArrayList <EdgeType> edgeList;
119 private int maxVertexLabel;
120 private int nextVertexId;
121 private int maxEdgeLabel;
122
123
126
127 public AbstractGraph() {
128 this.vertexList = new ArrayList <VertexType>();
129 this.edgeList = new ArrayList <EdgeType>();
130 this.maxVertexLabel = 0;
131 this.nextVertexId = 0;
132 this.maxEdgeLabel = 0;
133 }
134
135 public int getNumEdges() {
136 return edgeList.size();
137 }
138
139 public int getNumVertices() {
140 return vertexList.size();
141 }
142
143 public Iterator <EdgeType> edgeIterator() {
144 return edgeList.iterator();
145 }
146
147 public Iterator <VertexType> vertexIterator() {
148 return vertexList.iterator();
149 }
150
151 public void addVertex(VertexType v) {
152 vertexList.add(v);
153 v.setId(nextVertexId++);
154 v.setLabel(maxVertexLabel++);
155 }
156
157 public boolean containsVertex(VertexType v) {
158 for (VertexType existingVertex : vertexList) {
159 if (v == existingVertex)
160 return true;
161 }
162 return false;
163 }
164
165 public EdgeType createEdge(VertexType source, VertexType target) {
166 EdgeType edge = allocateEdge(source, target);
167 edgeList.add(edge);
168 source.addOutgoingEdge(edge);
169 target.addIncomingEdge(edge);
170 edge.setLabel(maxEdgeLabel++);
171 return edge;
172 }
173
174 public EdgeType lookupEdge(VertexType source, VertexType target) {
175 Iterator <EdgeType> i = outgoingEdgeIterator(source);
176 while (i.hasNext()) {
177 EdgeType edge = i.next();
178 if (edge.getTarget() == target)
179 return edge;
180 }
181 return null;
182 }
183
184 public int getNumVertexLabels() {
185 return maxVertexLabel;
186 }
187
188 public void setNumVertexLabels(int numLabels) {
189 this.maxVertexLabel = numLabels;
190 }
191
192 public int getNumEdgeLabels() {
193 return maxEdgeLabel;
194 }
195
196 public void setNumEdgeLabels(int numLabels) {
197 maxEdgeLabel = numLabels;
198 }
199
200 public void removeEdge(EdgeType edge) {
201 if (!edgeList.remove(edge))
202 throw new IllegalArgumentException ("removing nonexistent edge!");
203 edge.getSource().removeOutgoingEdge(edge);
204 edge.getTarget().removeIncomingEdge(edge);
205 }
206
207 public void removeVertex(VertexType v) {
208 if (!vertexList.remove(v))
209 throw new IllegalArgumentException ("removing nonexistent vertex!");
210
211 for (Iterator <EdgeType> i = incomingEdgeIterator(v); i.hasNext();)
212 removeEdge(i.next());
213
214 for (Iterator <EdgeType> i = outgoingEdgeIterator(v); i.hasNext();)
215 removeEdge(i.next());
216 }
217
218 public Iterator <EdgeType> outgoingEdgeIterator(VertexType source) {
219 return new OutgoingEdgeIterator<EdgeType, VertexType>(source);
220 }
221
222 public Iterator <EdgeType> incomingEdgeIterator(VertexType target) {
223 return new IncomingEdgeIterator<EdgeType, VertexType>(target);
224 }
225
226 public int getNumIncomingEdges(VertexType vertex) {
227 int count = 0;
228 EdgeType e = vertex.firstIncomingEdge;
229 while (e != null) {
230 ++count;
231 e = e.getNextIncomingEdge();
232 }
233 return count;
234 }
235
236 public int getNumOutgoingEdges(VertexType vertex) {
237 int count = 0;
238 EdgeType e = vertex.firstOutgoingEdge;
239 while (e != null) {
240 ++count;
241 e = e.getNextOutgoingEdge();
242 }
243 return count;
244 }
245
246 public Iterator <VertexType> successorIterator(final VertexType source) {
247 return new Iterator <VertexType>() {
248 private Iterator <EdgeType> iter = outgoingEdgeIterator(source);
249
250 public boolean hasNext() {
251 return iter.hasNext();
252 }
253
254 public VertexType next() {
255 return iter.next().getTarget();
256 }
257
258 public void remove() {
259 iter.remove();
260 }
261 };
262 }
263
264 public Iterator <VertexType> predecessorIterator(final VertexType target) {
265 return new Iterator <VertexType>() {
266 private Iterator <EdgeType> iter = incomingEdgeIterator(target);
267
268 public boolean hasNext() {
269 return iter.hasNext();
270 }
271
272 public VertexType next() {
273 return iter.next().getSource();
274 }
275
276 public void remove() {
277 iter.remove();
278 }
279 };
280 }
281
282
285
286 protected abstract EdgeType allocateEdge(VertexType source, VertexType target);
287
288 }
289
290 |
Popular Tags |
Java API By Example, From Geeks To Geeks.