| 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. |