| Line | Hits | Source |
|---|---|---|
| 1 | /* | |
| 2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University of | |
| 3 | * California All rights reserved. | |
| 4 | * | |
| 5 | * This software is open-source under the BSD license; see either "license.txt" | |
| 6 | * or http://jung.sourceforge.net/license.txt for a description. | |
| 7 | */ | |
| 8 | package edu.uci.ics.jung.graph.impl; | |
| 9 | ||
| 10 | import java.util.Collections; | |
| 11 | import java.util.HashSet; | |
| 12 | import java.util.Set; | |
| 13 | ||
| 14 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
| 15 | import edu.uci.ics.jung.graph.Edge; | |
| 16 | import edu.uci.ics.jung.graph.Graph; | |
| 17 | import edu.uci.ics.jung.graph.Vertex; | |
| 18 | import edu.uci.ics.jung.utils.GraphUtils; | |
| 19 | import edu.uci.ics.jung.utils.Pair; | |
| 20 | import edu.uci.ics.jung.utils.PredicateUtils; | |
| 21 | ||
| 22 | /** | |
| 23 | * This class provides a skeletal implementation of the <code>Graph</code> | |
| 24 | * interface to minimize the effort required to implement this interface. This | |
| 25 | * graph implementation stores vertices and edges in Sets. It is appropriate | |
| 26 | * for sparse graphs (those in which each vertex has only a few neighbors). For | |
| 27 | * dense graphs (those in which each vertex is connected to most other | |
| 28 | * vertices), a different implementation (for example, one which represents a | |
| 29 | * graph via a matrix) may be more appropriate. | |
| 30 | * | |
| 31 | * <P>Currently, the addition and removal methods will notify their arguments that | |
| 32 | * they have been added to or removed from this graph only if they are | |
| 33 | * instances of <code>AbstractSparseVertex</code> or <code>AbstractSparseEdge</code>.</p> | |
| 34 | * | |
| 35 | * <P>This class extends <code>UserData</code>, which provides storage and | |
| 36 | * retrieval mechanisms for user-defined data for each graph instance. This | |
| 37 | * allows users to attach data to graphs without having to extend this class.</p> | |
| 38 | * | |
| 39 | * <p>Constraints imposed by this class: | |
| 40 | * <ul> | |
| 41 | * <li/><b>system</b> (invisible, unmodifiable) constraints: | |
| 42 | * <code>NotInGraphVertexPredicate</code>, <code>NotInGraphEdgePredicate</code> | |
| 43 | * <li/><b>user</b> (visible, modifiable via <code>getEdgeConstraints</code>): none | |
| 44 | * </ul></p> | |
| 45 | ||
| 46 | * @author Scott D. White | |
| 47 | * @author Danyel Fisher | |
| 48 | * @author Joshua O'Madadhain | |
| 49 | */ | |
| 50 | public abstract class AbstractSparseGraph | |
| 51 | extends AbstractArchetypeGraph | |
| 52 | implements Graph, Cloneable { | |
| 53 | ||
| 54 | /** | |
| 55 | * The set of vertices registered with the graph. | |
| 56 | */ | |
| 57 | protected Set mVertices; | |
| 58 | ||
| 59 | /** | |
| 60 | * The set of edges registered with the graph. | |
| 61 | */ | |
| 62 | protected Set mEdges; | |
| 63 | ||
| 64 | ||
| 65 | //------------------------- CONSTRUCTION ----------------- | |
| 66 | ||
| 67 | /** | |
| 68 | * Creates an instance of a sparse graph. Invokes <code>initialize()</code> | |
| 69 | * to set up the local data structures. | |
| 70 | * | |
| 71 | * @see #initialize() | |
| 72 | */ | |
| 73 | 545 | public AbstractSparseGraph() { |
| 74 | 545 | initialize(); |
| 75 | // super(); | |
| 76 | 545 | } |
| 77 | ||
| 78 | protected void initialize() | |
| 79 | { | |
| 80 | 646 | mVertices = new HashSet(); |
| 81 | 646 | mEdges = new HashSet(); |
| 82 | 646 | super.initialize(); |
| 83 | 646 | } |
| 84 | ||
| 85 | /** | |
| 86 | * Returns an unmodifiable set view of the vertices in this graph. Will | |
| 87 | * reflect changes made to the graph after the view is generated. | |
| 88 | * | |
| 89 | * @see ArchetypeGraph#getVertices() | |
| 90 | * @see java.util.Collections#unmodifiableSet(java.util.Set) | |
| 91 | */ | |
| 92 | public Set getVertices() { | |
| 93 | 46164 | return Collections.unmodifiableSet(mVertices); |
| 94 | } | |
| 95 | ||
| 96 | /** | |
| 97 | * Returns an unmodifiable set view of the edges in this graph. Will | |
| 98 | * reflect changes made to the graph after the view is generated. | |
| 99 | * | |
| 100 | * @see ArchetypeGraph#getEdges() | |
| 101 | * @see java.util.Collections#unmodifiableSet(java.util.Set) | |
| 102 | */ | |
| 103 | public Set getEdges() { | |
| 104 | 169628 | return Collections.unmodifiableSet(mEdges); |
| 105 | } | |
| 106 | ||
| 107 | ||
| 108 | ||
| 109 | // --------------------------- ADDERS | |
| 110 | ||
| 111 | /** | |
| 112 | * @see edu.uci.ics.jung.graph.Graph#addEdge(edu.uci.ics.jung.graph.Edge) | |
| 113 | */ | |
| 114 | public Edge addEdge(Edge e) | |
| 115 | { | |
| 116 | // needs to happen before ase.addGraph_internal() so | |
| 117 | // that test for e.getGraph() will be valid | |
| 118 | 148095 | checkConstraints(e, edge_requirements); |
| 119 | ||
| 120 | 148062 | if (e instanceof AbstractElement) |
| 121 | { | |
| 122 | 148062 | AbstractElement ae = (AbstractElement)e; |
| 123 | 148062 | ae.checkIDs(mEdgeIDs); |
| 124 | 148062 | if (ae instanceof AbstractSparseEdge) |
| 125 | 148062 | ((AbstractSparseEdge)ae).addGraph_internal(this); |
| 126 | else | |
| 127 | 0 | ae.addGraph_internal(this); |
| 128 | } | |
| 129 | 148053 | mEdges.add(e); |
| 130 | 148053 | mGraphListenerHandler.handleAdd( e ); |
| 131 | 148053 | return e; |
| 132 | } | |
| 133 | ||
| 134 | /** | |
| 135 | * | |
| 136 | * @see edu.uci.ics.jung.graph.Graph#addVertex(edu.uci.ics.jung.graph.Vertex) | |
| 137 | */ | |
| 138 | public Vertex addVertex(Vertex v) | |
| 139 | { | |
| 140 | // needs to happen before addGraph_internal() so | |
| 141 | // that test for v.getGraph() will be valid | |
| 142 | 32384 | checkConstraints(v, vertex_requirements); |
| 143 | ||
| 144 | 32376 | if (v instanceof AbstractElement) |
| 145 | { | |
| 146 | 32376 | AbstractElement ae = (AbstractElement)v; |
| 147 | 32376 | ae.checkIDs(mVertexIDs); |
| 148 | 32375 | ae.addGraph_internal(this); |
| 149 | } | |
| 150 | 32375 | mVertices.add(v); |
| 151 | 32375 | mGraphListenerHandler.handleAdd( v ); |
| 152 | 32375 | return v; |
| 153 | } | |
| 154 | ||
| 155 | ||
| 156 | // ---------------------------- ACCESSORS --------------------------- | |
| 157 | ||
| 158 | ||
| 159 | ||
| 160 | ||
| 161 | /** | |
| 162 | * Removes all edges adjacent to the specified vertex, removes the vertex, | |
| 163 | * and notifies the vertex that it has been removed. <b>Note</b>: the | |
| 164 | * vertex will not be notified unless it is an instance of <code>AbstractSparseVertex</code>. | |
| 165 | */ | |
| 166 | public void removeVertex(Vertex v) { | |
| 167 | 90 | if (v.getGraph() != this) |
| 168 | 0 | throw new IllegalArgumentException("This vertex is not in this graph"); |
| 169 | 90 | GraphUtils.removeEdges(this, v.getIncidentEdges()); |
| 170 | 90 | mVertices.remove(v); |
| 171 | 90 | if (v instanceof AbstractSparseVertex) { |
| 172 | 90 | AbstractSparseVertex asv = (AbstractSparseVertex) v; |
| 173 | 90 | asv.removeGraph_internal(); |
| 174 | 90 | mVertexIDs.remove(new Integer(asv.getID())); |
| 175 | } | |
| 176 | 90 | mGraphListenerHandler.handleRemove( v ); |
| 177 | 90 | } |
| 178 | ||
| 179 | /** | |
| 180 | * Removes the edge from the graph, and notifies that the edge and its | |
| 181 | * incident vertices that it has been removed. <b>Note</b>: the edge | |
| 182 | * will not be notified unless it is an instance of <code>AbstractSparseEdge</code>, | |
| 183 | * and the incident vertices will not be notified unless they are instances | |
| 184 | * of <code>AbstractSparseVertex</code>. | |
| 185 | */ | |
| 186 | public void removeEdge(Edge e) { | |
| 187 | 109693 | if (e.getGraph() != this) |
| 188 | 2 | throw new IllegalArgumentException("This edge is not in this graph"); |
| 189 | ||
| 190 | 109691 | Pair endpoints = e.getEndpoints(); |
| 191 | 109691 | Vertex from = (Vertex) endpoints.getFirst(); |
| 192 | 109691 | Vertex to = (Vertex) endpoints.getSecond(); |
| 193 | ||
| 194 | 109691 | if (from instanceof AbstractSparseVertex) |
| 195 | 109691 | ((AbstractSparseVertex) from).removeNeighbor_internal(e, to); |
| 196 | 109691 | if (to instanceof AbstractSparseVertex) |
| 197 | 109691 | ((AbstractSparseVertex) to).removeNeighbor_internal(e, from); |
| 198 | ||
| 199 | 109691 | if (e instanceof AbstractSparseEdge) { |
| 200 | 109691 | AbstractSparseEdge ase = (AbstractSparseEdge) e; |
| 201 | 109691 | ase.removeGraph_internal(); |
| 202 | 109691 | mEdgeIDs.remove(new Integer(ase.getID())); |
| 203 | } | |
| 204 | ||
| 205 | 109691 | mEdges.remove(e); |
| 206 | 109691 | mGraphListenerHandler.handleRemove( e ); |
| 207 | 109691 | } |
| 208 | ||
| 209 | /** | |
| 210 | * @see Graph#isDirected() | |
| 211 | * @deprecated As of version 1.4, the semantics of this method have | |
| 212 | * changed; it no longer returns a boolean value that is hardwired into | |
| 213 | * the class definition, but checks to see whether one of the | |
| 214 | * requirements of this graph is that it only accepts directed edges. | |
| 215 | * | |
| 216 | */ | |
| 217 | public boolean isDirected() | |
| 218 | { | |
| 219 | 0 | return PredicateUtils.enforcesDirected(this); |
| 220 | } | |
| 221 | ||
| 222 | /** | |
| 223 | * Removes all vertices in the specified set from <code>g</code>. Syntactic | |
| 224 | * sugar for a loop that calls <code>g.removeVertex</code> on all elements | |
| 225 | * of the set. | |
| 226 | * If any element of <code>vertices</code> is not part of this graph, | |
| 227 | * then throws <code>IllegalArgumentException</code>. If this | |
| 228 | * exception is thrown, any vertices that may have been removed already | |
| 229 | * are not guaranteed to be restored to the graph. | |
| 230 | */ | |
| 231 | public void removeVertices(Set vertices) | |
| 232 | { | |
| 233 | 21 | GraphUtils.removeVertices(this, vertices); |
| 234 | 21 | } |
| 235 | ||
| 236 | /** | |
| 237 | * Removes all vertices in the specified set from <code>g</code>. Syntactic | |
| 238 | * sugar for a loop that calls <code>g.removeVertex</code> on all elements | |
| 239 | * of the set. | |
| 240 | * If any element of <code>edges</code> is not part of this graph, | |
| 241 | * then throws <code>IllegalArgumentException</code>. If this | |
| 242 | * exception is thrown, any edges that may have been removed already | |
| 243 | * are not guaranteed to be restored to the graph. | |
| 244 | */ | |
| 245 | public void removeEdges(Set edges) | |
| 246 | { | |
| 247 | 2 | GraphUtils.removeEdges(this, edges); |
| 248 | 2 | } |
| 249 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |