# Coverage details for edu.uci.ics.jung.graph.impl.SparseVertex

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. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.