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.Edge; | |
23 | import edu.uci.ics.jung.graph.UndirectedEdge; | |
24 | import edu.uci.ics.jung.graph.UndirectedGraph; | |
25 | import edu.uci.ics.jung.graph.Vertex; | |
26 | import edu.uci.ics.jung.graph.predicates.ParallelEdgePredicate; | |
27 | ||
28 | /** | |
29 | * An implementation of <code>Vertex</code> that resides in a | |
30 | * undirected graph; none of its adjoining edges may be parallel. | |
31 | * <P> | |
32 | * This implementation stores hash tables that map the neighbors | |
33 | * of this vertex to its incident edges. This enables an | |
34 | * efficient implementation of <code>findEdge(Vertex)</code>. | |
35 | * | |
36 | * @author Joshua O'Madadhain | |
37 | * | |
38 | * @see UndirectedGraph | |
39 | * @see UndirectedEdge | |
40 | */ | |
41 | ||
42 | public class SimpleUndirectedSparseVertex extends AbstractSparseVertex | |
43 | { | |
44 | /** | |
45 | * A map of the neighbors of this vertex to its incident edges. | |
46 | * Used to speed up <code>findEdge(Vertex)</code>. | |
47 | */ | |
48 | private Map mNeighborsToEdges; | |
49 | ||
50 | public SimpleUndirectedSparseVertex() | |
51 | { | |
52 | 151 | super(); |
53 | 151 | } |
54 | ||
55 | /** | |
56 | * | |
57 | * @see Vertex#getPredecessors() | |
58 | */ | |
59 | public Set getPredecessors() | |
60 | { | |
61 | 0 | return Collections.unmodifiableSet(getNeighborsToEdges().keySet()); |
62 | } | |
63 | ||
64 | /** | |
65 | * | |
66 | * @see edu.uci.ics.jung.graph.Vertex#numPredecessors() | |
67 | */ | |
68 | public int numPredecessors() | |
69 | { | |
70 | 0 | return getPredecessors().size(); |
71 | } | |
72 | ||
73 | /** | |
74 | * | |
75 | * @see Vertex#getSuccessors() | |
76 | */ | |
77 | public Set getSuccessors() | |
78 | { | |
79 | 0 | return Collections.unmodifiableSet(getNeighborsToEdges().keySet()); |
80 | } | |
81 | ||
82 | /** | |
83 | * | |
84 | * @see edu.uci.ics.jung.graph.Vertex#numPredecessors() | |
85 | */ | |
86 | public int numSuccessors() | |
87 | { | |
88 | 0 | return getSuccessors().size(); |
89 | } | |
90 | ||
91 | /** | |
92 | * | |
93 | * @see Vertex#getInEdges() | |
94 | */ | |
95 | public Set getInEdges() | |
96 | { | |
97 | 0 | return Collections.unmodifiableSet(new HashSet(getEdges_internal())); |
98 | } | |
99 | ||
100 | /** | |
101 | * | |
102 | * @see Vertex#getOutEdges() | |
103 | */ | |
104 | public Set getOutEdges() | |
105 | { | |
106 | 0 | return Collections.unmodifiableSet(new HashSet(getEdges_internal())); |
107 | } | |
108 | ||
109 | /** | |
110 | * | |
111 | * @see Vertex#inDegree() | |
112 | */ | |
113 | public int inDegree() | |
114 | { | |
115 | 0 | return getNeighborsToEdges().values().size(); |
116 | } | |
117 | ||
118 | /** | |
119 | * | |
120 | * @see Vertex#outDegree() | |
121 | */ | |
122 | public int outDegree() | |
123 | { | |
124 | 0 | return getNeighborsToEdges().values().size(); |
125 | } | |
126 | ||
127 | /** | |
128 | * @see Vertex#isSuccessorOf(Vertex) | |
129 | */ | |
130 | public boolean isSuccessorOf(Vertex v) | |
131 | { | |
132 | 0 | return getNeighborsToEdges().containsKey(v); |
133 | } | |
134 | ||
135 | /** | |
136 | * @see Vertex#isPredecessorOf(Vertex) | |
137 | */ | |
138 | public boolean isPredecessorOf(Vertex v) | |
139 | { | |
140 | 0 | return getNeighborsToEdges().containsKey(v); |
141 | } | |
142 | ||
143 | /** | |
144 | * @see Vertex#isSource(Edge) | |
145 | */ | |
146 | public boolean isSource(Edge e) | |
147 | { | |
148 | 0 | return isIncident(e); |
149 | } | |
150 | ||
151 | /** | |
152 | * @see Vertex#isDest(Edge) | |
153 | */ | |
154 | public boolean isDest(Edge e) | |
155 | { | |
156 | 0 | return isIncident(e); |
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 | */ | |
170 | public Edge findEdge(Vertex v) | |
171 | { | |
172 | 105 | return (Edge) getNeighborsToEdges().get(v); |
173 | } | |
174 | ||
175 | /** | |
176 | * Returns the set of edges that connect this vertex to the | |
177 | * specified vertex. Since this implementation does not allow | |
178 | * for parallel edges, this implementation simply returns a | |
179 | * set whose contents consist of the return value from | |
180 | * <code>findEdge(v)</code>. | |
181 | * | |
182 | * @see Vertex#findEdgeSet(Vertex) | |
183 | */ | |
184 | public Set findEdgeSet(Vertex v) | |
185 | { | |
186 | 83 | Set s = new HashSet(); |
187 | 83 | Edge e = findEdge(v); |
188 | 83 | if (e != null) |
189 | 32 | s.add(e); |
190 | 83 | return Collections.unmodifiableSet(s); |
191 | } | |
192 | ||
193 | /** | |
194 | * @see AbstractSparseVertex#initialize() | |
195 | */ | |
196 | protected void initialize() | |
197 | { | |
198 | 306 | super.initialize(); |
199 | 306 | setNeighborsToEdges(null); |
200 | 306 | } |
201 | ||
202 | /** | |
203 | * @see AbstractSparseVertex#getNeighbors_internal() | |
204 | */ | |
205 | protected Collection getNeighbors_internal() | |
206 | { | |
207 | 17 | return getNeighborsToEdges().keySet(); |
208 | } | |
209 | ||
210 | /** | |
211 | * @see AbstractSparseVertex#getEdges_internal() | |
212 | */ | |
213 | protected Collection getEdges_internal() | |
214 | { | |
215 | 0 | return getNeighborsToEdges().values(); |
216 | } | |
217 | ||
218 | /** | |
219 | * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex) | |
220 | */ | |
221 | protected void addNeighbor_internal(Edge e, Vertex v) | |
222 | { | |
223 | 60 | if (ParallelEdgePredicate.getInstance().evaluate(e)) |
224 | 1 | throw new IllegalArgumentException("This vertex " + |
225 | "implementation does not support parallel edges"); | |
226 | ||
227 | 59 | if (! (e instanceof UndirectedEdge)) |
228 | 1 | throw new IllegalArgumentException("This vertex " + |
229 | "implementation only accepts undirected edges"); | |
230 | 58 | getNeighborsToEdges().put(v, e); |
231 | 58 | } |
232 | ||
233 | /** | |
234 | * Removes the neighbor from this vertex's internal map. | |
235 | * | |
236 | * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex) | |
237 | */ | |
238 | protected void removeNeighbor_internal(Edge connectingEdge, Vertex neighbor) | |
239 | { | |
240 | // does connectingEdge connect us to neighbor? | |
241 | 8 | if (connectingEdge == getNeighborsToEdges().get(neighbor)) |
242 | { | |
243 | 6 | getNeighborsToEdges().remove(neighbor); |
244 | } | |
245 | else | |
246 | { | |
247 | // self-loop; already removed this node | |
248 | // in a previous call to removeNeighbor_internal() | |
249 | 2 | if (this == neighbor) |
250 | 2 | return; |
251 | ||
252 | 0 | throw new FatalException("Internal error: " + "edge " |
253 | + connectingEdge + " not incident to vertex " + neighbor); | |
254 | } | |
255 | 6 | } |
256 | ||
257 | /** | |
258 | * Returns a map from the successors of this vertex to its outgoing | |
259 | * edges. If this map has not yet been created, it creates it. | |
260 | * This method should not be directly accessed by users. | |
261 | */ | |
262 | protected Map getNeighborsToEdges() | |
263 | { | |
264 | 3708 | if (mNeighborsToEdges == null) |
265 | { | |
266 | 146 | setNeighborsToEdges(new HashMap(5)); |
267 | } | |
268 | 3708 | return mNeighborsToEdges; |
269 | } | |
270 | ||
271 | /** | |
272 | * Sets this vertex's internal successor -> out-edge map to | |
273 | * the specified map <code>succsToOutEdges</code>. | |
274 | * This method should not be directly accessed by users. | |
275 | */ | |
276 | protected void setNeighborsToEdges(Map neighborsToEdges) | |
277 | { | |
278 | 452 | this.mNeighborsToEdges = neighborsToEdges; |
279 | 452 | } |
280 | ||
281 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |