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