Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Created on Apr 2, 2004 | |
3 | * | |
4 | * Copyright (c) 2004, the JUNG Project and the Regents of the University | |
5 | * of California | |
6 | * All rights reserved. | |
7 | * | |
8 | * This software is open-source under the BSD license; see either | |
9 | * "license.txt" or | |
10 | * http://jung.sourceforge.net/license.txt for a description. | |
11 | */ | |
12 | package edu.uci.ics.jung.graph.impl; | |
13 | ||
14 | import java.util.Collection; | |
15 | import java.util.Collections; | |
16 | import java.util.HashMap; | |
17 | import java.util.HashSet; | |
18 | import java.util.Map; | |
19 | import java.util.Set; | |
20 | ||
21 | import org.apache.commons.collections.CollectionUtils; | |
22 | ||
23 | import edu.uci.ics.jung.exceptions.FatalException; | |
24 | import edu.uci.ics.jung.graph.DirectedEdge; | |
25 | import edu.uci.ics.jung.graph.Edge; | |
26 | import edu.uci.ics.jung.graph.UndirectedEdge; | |
27 | import edu.uci.ics.jung.graph.Vertex; | |
28 | import edu.uci.ics.jung.graph.predicates.ParallelEdgePredicate; | |
29 | ||
30 | /** | |
31 | * An implementation of <code>Vertex</code> that resides in a | |
32 | * sparse graph which may contain both directed and undirected edges. | |
33 | * It does not support parallel edges. | |
34 | * | |
35 | * <P> | |
36 | * This implementation stores hash tables that map the successors | |
37 | * of this vertex to its outgoing edges, and its predecessors to | |
38 | * its incoming edges. This enables an efficient implementation of | |
39 | * <code>findEdge(Vertex)</code>, but causes the routines that | |
40 | * return the sets of neighbors and of incident edges to require | |
41 | * time proportional to the number of neighbors. | |
42 | * | |
43 | * @author Joshua O'Madadhain | |
44 | */ | |
45 | public class SimpleSparseVertex extends AbstractSparseVertex | |
46 | { | |
47 | /** | |
48 | * A map of the predecessors of this vertex to the corresponding | |
49 | * sets of incoming edges. | |
50 | * Used to speed up <code>findEdge(Vertex)</code>. | |
51 | */ | |
52 | protected Map mPredsToInEdges; | |
53 | ||
54 | /** | |
55 | * A map of the successors of this vertex to the corresponding | |
56 | * sets of outgoing edges. | |
57 | * Used to speed up <code>findEdge(Vertex)</code>. | |
58 | */ | |
59 | protected Map mSuccsToOutEdges; | |
60 | ||
61 | /** | |
62 | * A map of the vertices connected to this vertex by undirected | |
63 | * edges to the corresponding sets of edges. | |
64 | * Used to speed up <code>findEdge(Vertex)</code>. | |
65 | */ | |
66 | protected Map mNeighborsToEdges; | |
67 | ||
68 | /** | |
69 | * Creates a new instance of a vertex for inclusion in a | |
70 | * sparse graph. | |
71 | */ | |
72 | public SimpleSparseVertex() | |
73 | { | |
74 | 31481 | super(); |
75 | 31481 | } |
76 | ||
77 | /** | |
78 | * @see Vertex#getPredecessors() | |
79 | */ | |
80 | public Set getPredecessors() { | |
81 | 360 | Collection preds = CollectionUtils.union( |
82 | getPredsToInEdges().keySet(), | |
83 | getNeighborsToEdges().keySet()); | |
84 | ||
85 | 360 | return Collections.unmodifiableSet(new HashSet(preds)); |
86 | } | |
87 | ||
88 | /** | |
89 | * @see Vertex#getSuccessors() | |
90 | */ | |
91 | public Set getSuccessors() { | |
92 | 1351 | Collection succs = CollectionUtils.union( |
93 | getSuccsToOutEdges().keySet(), | |
94 | getNeighborsToEdges().keySet()); | |
95 | ||
96 | 1351 | return Collections.unmodifiableSet(new HashSet(succs)); |
97 | } | |
98 | ||
99 | /** | |
100 | * @see Vertex#inDegree() | |
101 | */ | |
102 | public int inDegree() { | |
103 | 10043 | return getInEdges().size(); |
104 | } | |
105 | ||
106 | /** | |
107 | * @see Vertex#outDegree() | |
108 | */ | |
109 | public int outDegree() { | |
110 | 1588 | return getOutEdges().size(); |
111 | } | |
112 | ||
113 | /** | |
114 | * @see Vertex#numPredecessors() | |
115 | */ | |
116 | public int numPredecessors() | |
117 | { | |
118 | 0 | return getPredsToInEdges().size(); |
119 | } | |
120 | ||
121 | /** | |
122 | * @see Vertex#numSuccessors() | |
123 | */ | |
124 | public int numSuccessors() | |
125 | { | |
126 | 0 | return getSuccsToOutEdges().size(); |
127 | } | |
128 | ||
129 | /** | |
130 | * @see Vertex#isSuccessorOf(Vertex) | |
131 | */ | |
132 | public boolean isSuccessorOf(Vertex v) { | |
133 | 133500 | return getPredsToInEdges().containsKey(v) || |
134 | getNeighborsToEdges().containsKey(v); | |
135 | } | |
136 | ||
137 | /** | |
138 | * @see Vertex#isPredecessorOf(Vertex) | |
139 | */ | |
140 | public boolean isPredecessorOf(Vertex v) { | |
141 | 318 | return getSuccsToOutEdges().containsKey(v) || |
142 | getNeighborsToEdges().containsKey(v); | |
143 | } | |
144 | ||
145 | /** | |
146 | * @see Vertex#isSource(Edge) | |
147 | */ | |
148 | public boolean isSource(Edge e) | |
149 | { | |
150 | 11 | if (e instanceof DirectedEdge) |
151 | { | |
152 | 9 | if (e.getGraph() == this.getGraph()) |
153 | 9 | return (this == ((DirectedEdge)e).getSource()); |
154 | else | |
155 | 0 | return false; |
156 | } | |
157 | 2 | else if (e instanceof UndirectedEdge) |
158 | 2 | return isIncident(e); |
159 | else | |
160 | 0 | throw new IllegalArgumentException("Edge is neither directed nor undirected"); |
161 | } | |
162 | ||
163 | /** | |
164 | * @see Vertex#isDest(Edge) | |
165 | */ | |
166 | public boolean isDest(Edge e) | |
167 | { | |
168 | 11 | if (e instanceof DirectedEdge) |
169 | { | |
170 | 9 | if (e.getGraph() == this.getGraph()) |
171 | 9 | return (this == ((DirectedEdge)e).getDest()); |
172 | else | |
173 | 0 | return false; |
174 | } | |
175 | 2 | else if (e instanceof UndirectedEdge) |
176 | 2 | return isIncident(e); |
177 | else | |
178 | 0 | throw new IllegalArgumentException("Edge is neither directed nor undirected"); |
179 | } | |
180 | ||
181 | /** | |
182 | * @see edu.uci.ics.jung.graph.Vertex#getInEdges() | |
183 | */ | |
184 | public Set getInEdges() | |
185 | { | |
186 | 0 | Collection inEdges = getPredsToInEdges().values(); |
187 | 0 | Collection adjacentEdges = getNeighborsToEdges().values(); |
188 | ||
189 | 0 | Set edges = new HashSet(); |
190 | 0 | if (inEdges != null) |
191 | 0 | edges.addAll(inEdges); |
192 | 0 | if (adjacentEdges != null) |
193 | 0 | edges.addAll(adjacentEdges); |
194 | ||
195 | 0 | return Collections.unmodifiableSet(edges); |
196 | } | |
197 | ||
198 | /** | |
199 | * @see edu.uci.ics.jung.graph.Vertex#getOutEdges() | |
200 | */ | |
201 | public Set getOutEdges() | |
202 | { | |
203 | 0 | Collection outEdges = getSuccsToOutEdges().values(); |
204 | 0 | Collection adjacentEdges = getNeighborsToEdges().values(); |
205 | ||
206 | 0 | Set edges = new HashSet(); |
207 | 0 | if (outEdges != null) |
208 | 0 | edges.addAll(outEdges); |
209 | 0 | if (adjacentEdges != null) |
210 | 0 | edges.addAll(adjacentEdges); |
211 | ||
212 | 0 | return Collections.unmodifiableSet(edges); |
213 | } | |
214 | ||
215 | /** | |
216 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#findEdge(Vertex) | |
217 | */ | |
218 | public Edge findEdge(Vertex v) | |
219 | { | |
220 | 0 | Edge e = (Edge)getSuccsToOutEdges().get(v); |
221 | 0 | if (e != null) |
222 | 0 | return e; |
223 | 0 | e = (Edge)getNeighborsToEdges().get(v); |
224 | 0 | return e; |
225 | } | |
226 | ||
227 | /** | |
228 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#findEdgeSet(Vertex) | |
229 | */ | |
230 | public Set findEdgeSet(Vertex v) | |
231 | { | |
232 | 57 | Set s = new HashSet(); |
233 | 57 | Edge d = (Edge)getSuccsToOutEdges().get(v); |
234 | 57 | Edge u = (Edge)getNeighborsToEdges().get(v); |
235 | 57 | if (d != null) |
236 | 16 | s.add(d); |
237 | 57 | if (u != null) |
238 | 14 | s.add(u); |
239 | 57 | return Collections.unmodifiableSet(s); |
240 | } | |
241 | ||
242 | /** | |
243 | * Returns a set of all neighbors attached to this vertex. | |
244 | * Requires time proportional to the number of neighbors. | |
245 | * | |
246 | * @see AbstractSparseVertex#getNeighbors_internal() | |
247 | */ | |
248 | protected Collection getNeighbors_internal() | |
249 | { | |
250 | 1676 | HashSet neighbors = new HashSet(); |
251 | 1676 | neighbors.addAll(getPredsToInEdges().keySet()); |
252 | 1676 | neighbors.addAll(getSuccsToOutEdges().keySet()); |
253 | 1676 | neighbors.addAll(getNeighborsToEdges().keySet()); |
254 | 1676 | return neighbors; |
255 | } | |
256 | ||
257 | ||
258 | /** | |
259 | * Returns a map from the predecessors of this vertex to its incoming | |
260 | * edges. If this map has not yet been created, it creates it. | |
261 | * This map should not be directly accessed by users. | |
262 | */ | |
263 | protected Map getPredsToInEdges() { | |
264 | 691726 | if (mPredsToInEdges == null) { |
265 | 28670 | setPredsToInEdges(new HashMap(5)); |
266 | } | |
267 | 691726 | return mPredsToInEdges; |
268 | } | |
269 | ||
270 | /** | |
271 | * Sets this vertex's internal predecessor -> in-edge map to | |
272 | * the specified map <code>predsToInEdges</code>. | |
273 | * This method should not be directly accessed by users. | |
274 | */ | |
275 | protected void setPredsToInEdges(Map predsToInEdges) { | |
276 | 92367 | this.mPredsToInEdges = predsToInEdges; |
277 | 92367 | } |
278 | ||
279 | /** | |
280 | * Returns a map from the successors of this vertex to its outgoing | |
281 | * edges. If this map has not yet been created, it creates it. | |
282 | * This method should not be directly accessed by users. | |
283 | */ | |
284 | protected Map getSuccsToOutEdges() { | |
285 | 704945 | if (mSuccsToOutEdges == null) { |
286 | 21332 | setSuccsToOutEdges(new HashMap(5)); |
287 | } | |
288 | 704945 | return mSuccsToOutEdges; |
289 | } | |
290 | ||
291 | /** | |
292 | * Sets this vertex's internal successor -> out-edge map to | |
293 | * the specified map <code>succsToOutEdges</code>. | |
294 | * This method should not be directly accessed by users. | |
295 | */ | |
296 | protected void setSuccsToOutEdges(Map succsToOutEdges) { | |
297 | 85029 | this.mSuccsToOutEdges = succsToOutEdges; |
298 | 85029 | } |
299 | ||
300 | /** | |
301 | * Returns a map from the successors of this vertex to its outgoing | |
302 | * edges. If this map has not yet been created, it creates it. | |
303 | * This method should not be directly accessed by users. | |
304 | */ | |
305 | protected Map getNeighborsToEdges() { | |
306 | 1353149 | if (mNeighborsToEdges == null) { |
307 | 31556 | setNeighborsToEdges(new HashMap(5)); |
308 | } | |
309 | 1353149 | return mNeighborsToEdges; |
310 | } | |
311 | ||
312 | /** | |
313 | * Sets this vertex's internal successor -> out-edge map to | |
314 | * the specified map <code>succsToOutEdges</code>. | |
315 | * This method should not be directly accessed by users. | |
316 | */ | |
317 | protected void setNeighborsToEdges(Map neighborsToEdges) { | |
318 | 95253 | this.mNeighborsToEdges = neighborsToEdges; |
319 | 95253 | } |
320 | ||
321 | /** | |
322 | * Initializes the internal data structures of this vertex. | |
323 | * | |
324 | * @see AbstractSparseVertex#initialize() | |
325 | */ | |
326 | protected void initialize() { | |
327 | 63697 | super.initialize(); |
328 | 63697 | setPredsToInEdges(null); |
329 | 63697 | setSuccsToOutEdges(null); |
330 | 63697 | setNeighborsToEdges(null); |
331 | 63697 | } |
332 | ||
333 | /** | |
334 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#getEdges_internal() | |
335 | */ | |
336 | protected Collection getEdges_internal() | |
337 | { | |
338 | 0 | HashSet edges = new HashSet(); |
339 | ||
340 | 0 | Collection inEdges = getPredsToInEdges().values(); |
341 | 0 | Collection outEdges = getSuccsToOutEdges().values(); |
342 | 0 | Collection adjacentEdges = getNeighborsToEdges().values(); |
343 | ||
344 | 0 | if (inEdges != null) |
345 | 0 | edges.addAll(inEdges); |
346 | 0 | if (outEdges != null) |
347 | 0 | edges.addAll(outEdges); |
348 | 0 | if (adjacentEdges != null) |
349 | 0 | edges.addAll(adjacentEdges); |
350 | ||
351 | 0 | return edges; |
352 | } | |
353 | ||
354 | /** | |
355 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#addNeighbor_internal(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.Vertex) | |
356 | */ | |
357 | protected void addNeighbor_internal(Edge e, Vertex v) | |
358 | { | |
359 | 45 | if (ParallelEdgePredicate.getInstance().evaluate(e)) |
360 | 1 | throw new IllegalArgumentException("This vertex " + |
361 | "implementation does not support parallel edges"); | |
362 | ||
363 | 44 | if (e instanceof DirectedEdge) |
364 | { | |
365 | 22 | DirectedEdge de = (DirectedEdge) e; |
366 | 22 | boolean added = false; |
367 | 22 | if (this == de.getSource()) |
368 | { | |
369 | 15 | getSuccsToOutEdges().put(v, e); |
370 | 15 | added = true; |
371 | } | |
372 | 22 | if (this == de.getDest()) |
373 | { | |
374 | 15 | getPredsToInEdges().put(v, e); |
375 | 15 | added = true; |
376 | } | |
377 | 22 | if (!added) |
378 | 0 | throw new IllegalArgumentException("Internal error: " + |
379 | "this vertex is not incident to " + e); | |
380 | } | |
381 | 22 | else if (e instanceof UndirectedEdge) |
382 | { | |
383 | 22 | getNeighborsToEdges().put(v, e); |
384 | } | |
385 | 0 | else throw new IllegalArgumentException("Edge is neither directed" + |
386 | "nor undirected"); | |
387 | 44 | } |
388 | ||
389 | /** | |
390 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#removeNeighbor_internal(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.Vertex) | |
391 | */ | |
392 | protected void removeNeighbor_internal(Edge e, Vertex v) | |
393 | { | |
394 | 16 | String error = "Internal error: " + |
395 | "edge " + e + " not incident to vertex "; | |
396 | 16 | if (e instanceof DirectedEdge) |
397 | { | |
398 | 8 | if (getSuccsToOutEdges().containsKey(v) && v.isDest(e)) |
399 | { // e is an outgoing edge of this vertex -> v is a successor | |
400 | 4 | if (getSuccsToOutEdges().remove(v) == null) |
401 | 0 | throw new FatalException(error + v); |
402 | } | |
403 | 4 | else if (getPredsToInEdges().containsKey(v) && v.isSource(e)) |
404 | { // e is an incoming edge of this vertex -> v is a predecessor | |
405 | 4 | if (getPredsToInEdges().remove(v) == null) |
406 | 0 | throw new FatalException(error + v); |
407 | } | |
408 | else | |
409 | 0 | throw new FatalException(error + this); |
410 | } | |
411 | 8 | else if (e instanceof UndirectedEdge) |
412 | { | |
413 | 8 | Map nte = getNeighborsToEdges(); |
414 | 8 | if (nte.get(v) == e) |
415 | { | |
416 | 6 | nte.remove(v); |
417 | } | |
418 | else | |
419 | { | |
420 | // if this is not a self-loop or a fatal error | |
421 | 2 | if (this != v) |
422 | 0 | throw new FatalException(error + v); |
423 | } | |
424 | } | |
425 | else | |
426 | 0 | throw new IllegalArgumentException("Edge is neither directed" + |
427 | "nor undirected"); | |
428 | 16 | } |
429 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |