Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Created on Apr 3, 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 edu.uci.ics.jung.exceptions.FatalException; | |
22 | import edu.uci.ics.jung.graph.DirectedEdge; | |
23 | import edu.uci.ics.jung.graph.Edge; | |
24 | import edu.uci.ics.jung.graph.Vertex; | |
25 | import edu.uci.ics.jung.graph.predicates.ParallelEdgePredicate; | |
26 | ||
27 | /** | |
28 | * An implementation of <code>Vertex</code> that resides in a | |
29 | * directed graph; none of its adjoining edges may be parallel. | |
30 | * <P> | |
31 | * This implementation stores hash tables that map the neighbors | |
32 | * of this vertex to its incident edges. This enables an | |
33 | * efficient implementation of <code>findEdge(Vertex)</code>. | |
34 | * Optimally, this is to be used with DirectedSparseEdge. | |
35 | * | |
36 | * @author Joshua O'Madadhain | |
37 | * | |
38 | * @see DirectedSparseGraph | |
39 | * @see DirectedSparseEdge | |
40 | */ | |
41 | public class SimpleDirectedSparseVertex extends AbstractSparseVertex | |
42 | { | |
43 | /** | |
44 | * A map of the predecessors of this vertex to its incoming edges. | |
45 | * Used to speed up <code>findEdge(Vertex)</code>. | |
46 | */ | |
47 | private Map mPredsToInEdges; | |
48 | ||
49 | /** | |
50 | * A map of the successors of this vertex to its outgoing edges. | |
51 | * Used to speed up <code>findEdge(Vertex)</code>. | |
52 | */ | |
53 | private Map mSuccsToOutEdges; | |
54 | ||
55 | /** | |
56 | * Creates a new instance of a vertex for inclusion in a | |
57 | * sparse directed graph. | |
58 | */ | |
59 | public SimpleDirectedSparseVertex() | |
60 | { | |
61 | 44 | super(); |
62 | 44 | } |
63 | ||
64 | /** | |
65 | * @see Vertex#getPredecessors() | |
66 | */ | |
67 | public Set getPredecessors() { | |
68 | 0 | return Collections.unmodifiableSet(getPredsToInEdges().keySet()); |
69 | } | |
70 | ||
71 | /** | |
72 | * | |
73 | * @see edu.uci.ics.jung.graph.Vertex#numPredecessors() | |
74 | */ | |
75 | public int numPredecessors() | |
76 | { | |
77 | 0 | return getPredecessors().size(); |
78 | } | |
79 | ||
80 | /** | |
81 | * @see Vertex#getSuccessors() | |
82 | */ | |
83 | public Set getSuccessors() { | |
84 | 0 | return Collections.unmodifiableSet(getSuccsToOutEdges().keySet()); |
85 | } | |
86 | ||
87 | /** | |
88 | * @see edu.uci.ics.jung.graph.Vertex#numSuccessors() | |
89 | */ | |
90 | public int numSuccessors() | |
91 | { | |
92 | 0 | return getSuccessors().size(); |
93 | } | |
94 | ||
95 | /** | |
96 | * @see Vertex#getInEdges() | |
97 | */ | |
98 | public Set getInEdges() { | |
99 | 0 | return Collections.unmodifiableSet(new HashSet(getPredsToInEdges().values())); |
100 | } | |
101 | ||
102 | /** | |
103 | * @see Vertex#getOutEdges() | |
104 | */ | |
105 | public Set getOutEdges() { | |
106 | 0 | return Collections.unmodifiableSet(new HashSet(getSuccsToOutEdges().values())); |
107 | } | |
108 | ||
109 | /** | |
110 | * @see Vertex#inDegree() | |
111 | */ | |
112 | public int inDegree() { | |
113 | 0 | return getInEdges().size(); |
114 | } | |
115 | ||
116 | /** | |
117 | * @see Vertex#outDegree() | |
118 | */ | |
119 | public int outDegree() { | |
120 | 0 | return getOutEdges().size(); |
121 | } | |
122 | ||
123 | /** | |
124 | * @see Vertex#isSuccessorOf(Vertex) | |
125 | */ | |
126 | public boolean isSuccessorOf(Vertex v) { | |
127 | 21 | return getPredsToInEdges().containsKey(v); |
128 | } | |
129 | ||
130 | /** | |
131 | * @see Vertex#isPredecessorOf(Vertex) | |
132 | */ | |
133 | public boolean isPredecessorOf(Vertex v) { | |
134 | 60 | return getSuccsToOutEdges().containsKey(v); |
135 | } | |
136 | ||
137 | /** | |
138 | * @see Vertex#isSource(Edge) | |
139 | */ | |
140 | public boolean isSource(Edge e) | |
141 | { | |
142 | 4 | if (e.getGraph() == this.getGraph()) |
143 | 4 | return equals(((DirectedEdge)e).getSource()); |
144 | else | |
145 | 0 | return false; |
146 | } | |
147 | ||
148 | /** | |
149 | * @see Vertex#isDest(Edge) | |
150 | */ | |
151 | public boolean isDest(Edge e) | |
152 | { | |
153 | 4 | if (e.getGraph() == this.getGraph()) |
154 | 4 | return equals(((DirectedEdge)e).getDest()); |
155 | else | |
156 | 0 | return false; |
157 | } | |
158 | ||
159 | /** | |
160 | * Returns the edge that connects this | |
161 | * vertex to the specified vertex <code>v</code>, or | |
162 | * <code>null</code> if there is no such edge. | |
163 | * Implemented using a hash table for a performance | |
164 | * improvement over the implementation in | |
165 | * <code>AbstractSparseVertex</code>. | |
166 | * | |
167 | * @see Vertex#findEdge(Vertex) | |
168 | */ | |
169 | public Edge findEdge(Vertex v) | |
170 | { | |
171 | 48 | return (Edge)getSuccsToOutEdges().get(v); |
172 | } | |
173 | ||
174 | /** | |
175 | * Returns the set of edges that connect this vertex to the | |
176 | * specified vertex. Since this implementation does not allow | |
177 | * for parallel edges, this implementation simply returns a | |
178 | * set whose contents consist of the return value from | |
179 | * <code>findEdge(v)</code>. | |
180 | * | |
181 | * @see Vertex#findEdgeSet(Vertex) | |
182 | */ | |
183 | public Set findEdgeSet(Vertex v) | |
184 | { | |
185 | 39 | Set s = new HashSet(); |
186 | 39 | Edge e = findEdge(v); |
187 | 39 | if (e != null) |
188 | 17 | s.add(e); |
189 | 39 | return Collections.unmodifiableSet(s); |
190 | } | |
191 | ||
192 | /** | |
193 | * Returns a set of all neighbors attached to this vertex. | |
194 | * Requires time proportional to the number of neighbors. | |
195 | * | |
196 | * @see AbstractSparseVertex#getNeighbors_internal() | |
197 | */ | |
198 | protected Collection getNeighbors_internal() | |
199 | { | |
200 | 47 | HashSet neighbors = new HashSet(); |
201 | 47 | neighbors.addAll(getPredsToInEdges().keySet()); |
202 | 47 | neighbors.addAll(getSuccsToOutEdges().keySet()); |
203 | 47 | return neighbors; |
204 | } | |
205 | ||
206 | /** | |
207 | * Returns a list of all incident edges of this vertex. | |
208 | * Requires time proportional to the number of incident edges. | |
209 | * | |
210 | * @see AbstractSparseVertex#getEdges_internal() | |
211 | */ | |
212 | protected Collection getEdges_internal() { | |
213 | 0 | HashSet edges = new HashSet(); |
214 | 0 | edges.addAll(getPredsToInEdges().values()); |
215 | 0 | edges.addAll(getSuccsToOutEdges().values()); |
216 | 0 | return edges; |
217 | } | |
218 | ||
219 | /** | |
220 | * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex) | |
221 | */ | |
222 | protected void addNeighbor_internal(Edge e, Vertex v) | |
223 | { | |
224 | 32 | if (! (e instanceof DirectedEdge)) |
225 | 1 | throw new IllegalArgumentException("This vertex " + |
226 | "implementation only accepts directed edges"); | |
227 | ||
228 | 31 | if (ParallelEdgePredicate.getInstance().evaluate(e)) |
229 | 1 | throw new IllegalArgumentException("This vertex " + |
230 | "implementation does not support parallel edges"); | |
231 | ||
232 | 30 | DirectedEdge edge = (DirectedEdge) e; |
233 | 30 | boolean added = false; |
234 | 30 | if (this == edge.getSource()) |
235 | { | |
236 | 20 | getSuccsToOutEdges().put(v, e); |
237 | 20 | added = true; |
238 | } | |
239 | 30 | if (this == edge.getDest()) |
240 | { | |
241 | 20 | getPredsToInEdges().put(v, e); |
242 | 20 | added = true; |
243 | } | |
244 | 30 | if (!added) |
245 | 0 | throw new IllegalArgumentException("Internal error: " + |
246 | "this vertex is not incident to " + e); | |
247 | 30 | } |
248 | ||
249 | /** | |
250 | * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex) | |
251 | */ | |
252 | protected void removeNeighbor_internal(Edge e, Vertex v) | |
253 | { | |
254 | 8 | String error = "Internal error: " + |
255 | "edge " + e + " not incident to vertex "; | |
256 | 8 | if (getSuccsToOutEdges().containsKey(v) && v.isDest(e)) |
257 | { // e is an outgoing edge of this vertex -> v is a successor | |
258 | 4 | if (getSuccsToOutEdges().remove(v) == null) |
259 | 0 | throw new FatalException(error + v); |
260 | } | |
261 | 4 | else if (getPredsToInEdges().containsKey(v) && v.isSource(e)) |
262 | { // e is an incoming edge of this vertex -> v is a predecessor | |
263 | 4 | if (getPredsToInEdges().remove(v) == null) |
264 | 0 | throw new FatalException(error + v); |
265 | } | |
266 | else | |
267 | 0 | throw new FatalException(error + this); |
268 | 8 | } |
269 | ||
270 | /** | |
271 | * Returns a map from the predecessors of this vertex to its incoming | |
272 | * edges. If this map has not yet been created, it creates it. | |
273 | * This map should not be directly accessed by users. | |
274 | */ | |
275 | protected Map getPredsToInEdges() { | |
276 | 138 | if (mPredsToInEdges == null) { |
277 | 29 | setPredsToInEdges(new HashMap(5)); |
278 | } | |
279 | 138 | return mPredsToInEdges; |
280 | } | |
281 | ||
282 | /** | |
283 | * Sets this vertex's internal predecessor -> in-edge map to | |
284 | * the specified map <code>predsToInEdges</code>. | |
285 | * This method should not be directly accessed by users. | |
286 | */ | |
287 | protected void setPredsToInEdges(Map predsToInEdges) { | |
288 | 120 | this.mPredsToInEdges = predsToInEdges; |
289 | 120 | } |
290 | ||
291 | /** | |
292 | * Returns a map from the successors of this vertex to its outgoing | |
293 | * edges. If this map has not yet been created, it creates it. | |
294 | * This method should not be directly accessed by users. | |
295 | */ | |
296 | protected Map getSuccsToOutEdges() { | |
297 | 248 | if (mSuccsToOutEdges == null) { |
298 | 26 | setSuccsToOutEdges(new HashMap(5)); |
299 | } | |
300 | 248 | return mSuccsToOutEdges; |
301 | } | |
302 | ||
303 | /** | |
304 | * Sets this vertex's internal successor -> out-edge map to | |
305 | * the specified map <code>succsToOutEdges</code>. | |
306 | * This method should not be directly accessed by users. | |
307 | */ | |
308 | protected void setSuccsToOutEdges(Map succsToOutEdges) { | |
309 | 117 | this.mSuccsToOutEdges = succsToOutEdges; |
310 | 117 | } |
311 | ||
312 | /** | |
313 | * Initializes the internal data structures of this vertex. | |
314 | * | |
315 | * @see AbstractSparseVertex#initialize() | |
316 | */ | |
317 | protected void initialize() { | |
318 | 91 | super.initialize(); |
319 | 91 | setPredsToInEdges(null); |
320 | 91 | setSuccsToOutEdges(null); |
321 | 91 | } |
322 | ||
323 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |