Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | package edu.uci.ics.jung.graph.impl; | |
11 | ||
12 | ||
13 | import java.util.Collection; | |
14 | import java.util.Collections; | |
15 | import java.util.HashSet; | |
16 | import java.util.Iterator; | |
17 | import java.util.Map; | |
18 | import java.util.Set; | |
19 | ||
20 | import edu.uci.ics.jung.exceptions.FatalException; | |
21 | import edu.uci.ics.jung.graph.DirectedEdge; | |
22 | import edu.uci.ics.jung.graph.Edge; | |
23 | import edu.uci.ics.jung.graph.UndirectedEdge; | |
24 | import edu.uci.ics.jung.graph.Vertex; | |
25 | ||
26 | /** | |
27 | * An implementation of <code>Vertex</code> that resides in a | |
28 | * sparse graph which may contain directed and/or undirected edges, | |
29 | * as well as parallel edges. | |
30 | * <P> | |
31 | * This implementation stores hash tables that map the successors | |
32 | * of this vertex to its outgoing edges, and its predecessors to | |
33 | * its incoming edges. This enables an efficient implementation of | |
34 | * <code>findEdge(Vertex)</code>, but causes the routines that | |
35 | * return the sets of neighbors and of incident edges to require | |
36 | * time proportional to the number of neighbors. | |
37 | * | |
38 | * @author Joshua O'Madadhain | |
39 | * @author Scott White | |
40 | * @author Danyel Fisher | |
41 | * | |
42 | * @see SparseGraph | |
43 | */ | |
44 | public class SparseVertex extends SimpleSparseVertex | |
45 | { | |
46 | /** | |
47 | * Creates a new instance of a vertex for inclusion in a | |
48 | * sparse graph. | |
49 | */ | |
50 | public SparseVertex() | |
51 | { | |
52 | 31462 | super(); |
53 | 31462 | } |
54 | ||
55 | /** | |
56 | * @see Vertex#getInEdges() | |
57 | */ | |
58 | public Set getInEdges() | |
59 | { | |
60 | 11073 | Collection inEdgeSets = getPredsToInEdges().values(); |
61 | 11073 | Collection edgeSets = getNeighborsToEdges().values(); |
62 | 11073 | Set inEdges = new HashSet(); |
63 | ||
64 | 11073 | for (Iterator i_iter = inEdgeSets.iterator(); i_iter.hasNext(); ) |
65 | 1095 | inEdges.addAll((Set)i_iter.next()); |
66 | ||
67 | 11073 | for (Iterator e_iter = edgeSets.iterator(); e_iter.hasNext(); ) |
68 | 493 | inEdges.addAll((Set)e_iter.next()); |
69 | ||
70 | 11073 | return Collections.unmodifiableSet(inEdges); |
71 | } | |
72 | ||
73 | /** | |
74 | * @see Vertex#getOutEdges() | |
75 | */ | |
76 | public Set getOutEdges() { | |
77 | 6597 | Collection outEdgeSets = getSuccsToOutEdges().values(); |
78 | 6597 | Collection edgeSets = getNeighborsToEdges().values(); |
79 | 6597 | Set outEdges = new HashSet(); |
80 | ||
81 | 6597 | for (Iterator o_iter = outEdgeSets.iterator(); o_iter.hasNext(); ) |
82 | 6858 | outEdges.addAll((Set)o_iter.next()); |
83 | ||
84 | 6597 | for (Iterator e_iter = edgeSets.iterator(); e_iter.hasNext(); ) |
85 | 14072 | outEdges.addAll((Set)e_iter.next()); |
86 | ||
87 | 6597 | return Collections.unmodifiableSet(outEdges); |
88 | } | |
89 | ||
90 | ||
91 | /** | |
92 | * Returns the edge that connects this | |
93 | * vertex to the specified vertex <code>v</code>, or | |
94 | * <code>null</code> if there is no such edge. | |
95 | * Implemented using a hash table for a performance | |
96 | * improvement over the implementation in | |
97 | * <code>AbstractSparseVertex</code>. | |
98 | * | |
99 | * Looks for a directed edge first, and then for an | |
100 | * undirected edge if no directed edges are found. | |
101 | * | |
102 | * @see Vertex#findEdge(Vertex) | |
103 | */ | |
104 | public Edge findEdge(Vertex v) | |
105 | { | |
106 | 2107 | Set outEdges = (Set)getSuccsToOutEdges().get(v); |
107 | 2107 | if (outEdges == null) |
108 | 1803 | outEdges = (Set)getNeighborsToEdges().get(v); |
109 | 2107 | if (outEdges == null) |
110 | 44 | return null; |
111 | 2063 | return (Edge)outEdges.iterator().next(); |
112 | } | |
113 | ||
114 | /** | |
115 | * @see Vertex#findEdgeSet(Vertex) | |
116 | */ | |
117 | public Set findEdgeSet(Vertex v) | |
118 | { | |
119 | // v. 1.4: no longer using CollectionUtils.union to combine these sets, | |
120 | // since this method does not accept null arguments | |
121 | 147577 | Set edgeSet = new HashSet(); |
122 | 147577 | Set outEdges = (Set)getSuccsToOutEdges().get(v); |
123 | 147577 | Set edges = (Set)getNeighborsToEdges().get(v); |
124 | 147577 | if (outEdges != null) |
125 | 21 | edgeSet.addAll(outEdges); |
126 | 147577 | if (edges != null) |
127 | 10 | edgeSet.addAll(edges); |
128 | 147577 | return Collections.unmodifiableSet(edgeSet); |
129 | } | |
130 | ||
131 | /** | |
132 | * Returns a list of all incident edges of this vertex. | |
133 | * Requires time proportional to the number of incident edges. | |
134 | * | |
135 | * @see AbstractSparseVertex#getEdges_internal() | |
136 | */ | |
137 | protected Collection getEdges_internal() { | |
138 | 540806 | HashSet edges = new HashSet(); |
139 | ||
140 | 540806 | Collection inEdgeSets = getPredsToInEdges().values(); |
141 | 540806 | Collection outEdgeSets = getSuccsToOutEdges().values(); |
142 | 540806 | Collection edgeSets = getNeighborsToEdges().values(); |
143 | ||
144 | 540806 | for (Iterator e_iter = inEdgeSets.iterator(); e_iter.hasNext(); ) |
145 | 170 | edges.addAll((Set)e_iter.next()); |
146 | ||
147 | 540806 | for (Iterator e_iter = outEdgeSets.iterator(); e_iter.hasNext(); ) |
148 | 200 | edges.addAll((Set)e_iter.next()); |
149 | ||
150 | 540806 | for (Iterator e_iter = edgeSets.iterator(); e_iter.hasNext(); ) |
151 | 4721570 | edges.addAll((Set)e_iter.next()); |
152 | ||
153 | 540806 | return edges; |
154 | } | |
155 | ||
156 | /** | |
157 | * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex) | |
158 | */ | |
159 | protected void addNeighbor_internal(Edge e, Vertex v) | |
160 | { | |
161 | 295684 | if (e instanceof DirectedEdge) |
162 | { | |
163 | 7544 | DirectedEdge de = (DirectedEdge) e; |
164 | 7544 | boolean added = false; |
165 | 7544 | if (this == de.getSource()) |
166 | { | |
167 | 3915 | Map stoe = getSuccsToOutEdges(); |
168 | 3915 | Set outEdges = (Set)stoe.get(v); |
169 | 3915 | if (outEdges == null) |
170 | { | |
171 | 3767 | outEdges = new HashSet(); |
172 | 3767 | stoe.put(v, outEdges); |
173 | } | |
174 | 3915 | outEdges.add(de); |
175 | 3915 | added = true; |
176 | } | |
177 | 7544 | if (this == de.getDest()) |
178 | { | |
179 | 3915 | Map ptie = getPredsToInEdges(); |
180 | 3915 | Set inEdges = (Set)ptie.get(v); |
181 | 3915 | if (inEdges == null) |
182 | { | |
183 | 3767 | inEdges = new HashSet(); |
184 | 3767 | ptie.put(v, inEdges); |
185 | } | |
186 | 3915 | inEdges.add(de); |
187 | 3915 | added = true; |
188 | } | |
189 | 7544 | if (!added) |
190 | 0 | throw new IllegalArgumentException("Internal error: " + |
191 | "this vertex is not incident to " + e); | |
192 | } | |
193 | 288140 | else if (e instanceof UndirectedEdge) |
194 | { | |
195 | 288140 | Map nte = getNeighborsToEdges(); |
196 | 288140 | Set edges = (Set)nte.get(v); |
197 | ||
198 | 288140 | if (edges == null) |
199 | { | |
200 | 287820 | edges = new HashSet(); |
201 | 287820 | nte.put(v, edges); |
202 | } | |
203 | 288140 | edges.add(e); |
204 | } | |
205 | 0 | else throw new IllegalArgumentException("Edge is neither directed" + |
206 | "nor undirected"); | |
207 | 295684 | } |
208 | ||
209 | /** | |
210 | * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex) | |
211 | */ | |
212 | protected void removeNeighbor_internal(Edge e, Vertex v) | |
213 | { | |
214 | 219334 | boolean predecessor = false; |
215 | 219334 | boolean successor = false; |
216 | ||
217 | 219334 | if (e instanceof DirectedEdge) |
218 | { | |
219 | 320 | Map ptie = getPredsToInEdges(); |
220 | 320 | Set inEdges = (Set)ptie.get(v); |
221 | 320 | Map stoe = getSuccsToOutEdges(); |
222 | 320 | Set outEdges = (Set)stoe.get(v); |
223 | 320 | DirectedEdge de = (DirectedEdge)e; |
224 | ||
225 | 320 | if (de.getSource() == v && inEdges != null) |
226 | { // -> v is predecessor and not yet removed | |
227 | 160 | predecessor = inEdges.remove(e); |
228 | 160 | if (inEdges.isEmpty()) // remove entry if it's now obsolete |
229 | 159 | ptie.remove(v); |
230 | } | |
231 | 320 | if (de.getDest() == v && outEdges != null) |
232 | { // -> v is successor and not yet removed | |
233 | 160 | successor = outEdges.remove(e); |
234 | 160 | if (outEdges.isEmpty()) // remove entry if it's now obsolete |
235 | 159 | stoe.remove(v); |
236 | } | |
237 | 320 | if (!predecessor && !successor && !(this == v)) |
238 | 0 | throw new FatalException("Internal error in data structure" + |
239 | " for vertex " + this); | |
240 | } | |
241 | 219014 | else if (e instanceof UndirectedEdge) |
242 | { | |
243 | // if v doesn't point to e, and it's not a self-loop | |
244 | // that's been removed in a previous call to removeNeighbor... | |
245 | 219014 | Map nte = getNeighborsToEdges(); |
246 | 219014 | Set edges = (Set)nte.get(v); |
247 | 219014 | if (edges != null) |
248 | { | |
249 | 218894 | boolean removed = edges.remove(e); |
250 | 218894 | if (edges.isEmpty()) |
251 | 218892 | nte.remove(v); |
252 | 218894 | if (!removed && this != v) |
253 | 0 | throw new FatalException("Internal error in data structure" + |
254 | "for vertex " + this); | |
255 | } | |
256 | 120 | else if (this != v) |
257 | 0 | throw new FatalException("Internal error in data structure" + |
258 | "for vertex " + this); | |
259 | ||
260 | // if it *is* a self-loop, we're already done | |
261 | } | |
262 | ||
263 | else | |
264 | 0 | throw new FatalException("Edge is neither directed nor undirected"); |
265 | 219334 | } |
266 | ||
267 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |