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