Coverage details for edu.uci.ics.jung.graph.impl.AbstractSparseGraph

LineHitsSource
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      */
73545    public AbstractSparseGraph() {
74545        initialize();
75 // super();
76545    }
77  
78     protected void initialize()
79     {
80646        mVertices = new HashSet();
81646        mEdges = new HashSet();
82646        super.initialize();
83646    }
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() {
9346164        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() {
104169628        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
118148095        checkConstraints(e, edge_requirements);
119         
120148062        if (e instanceof AbstractElement)
121         {
122148062            AbstractElement ae = (AbstractElement)e;
123148062            ae.checkIDs(mEdgeIDs);
124148062            if (ae instanceof AbstractSparseEdge)
125148062                ((AbstractSparseEdge)ae).addGraph_internal(this);
126             else
1270                ae.addGraph_internal(this);
128         }
129148053        mEdges.add(e);
130148053        mGraphListenerHandler.handleAdd( e );
131148053        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
14232384        checkConstraints(v, vertex_requirements);
143         
14432376        if (v instanceof AbstractElement)
145         {
14632376            AbstractElement ae = (AbstractElement)v;
14732376            ae.checkIDs(mVertexIDs);
14832375            ae.addGraph_internal(this);
149         }
15032375        mVertices.add(v);
15132375        mGraphListenerHandler.handleAdd( v );
15232375        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) {
16790        if (v.getGraph() != this)
1680            throw new IllegalArgumentException("This vertex is not in this graph");
16990        GraphUtils.removeEdges(this, v.getIncidentEdges());
17090        mVertices.remove(v);
17190        if (v instanceof AbstractSparseVertex) {
17290            AbstractSparseVertex asv = (AbstractSparseVertex) v;
17390            asv.removeGraph_internal();
17490            mVertexIDs.remove(new Integer(asv.getID()));
175         }
17690        mGraphListenerHandler.handleRemove( v );
17790    }
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) {
187109693        if (e.getGraph() != this)
1882            throw new IllegalArgumentException("This edge is not in this graph");
189  
190109691        Pair endpoints = e.getEndpoints();
191109691        Vertex from = (Vertex) endpoints.getFirst();
192109691        Vertex to = (Vertex) endpoints.getSecond();
193  
194109691        if (from instanceof AbstractSparseVertex)
195109691            ((AbstractSparseVertex) from).removeNeighbor_internal(e, to);
196109691        if (to instanceof AbstractSparseVertex)
197109691            ((AbstractSparseVertex) to).removeNeighbor_internal(e, from);
198  
199109691        if (e instanceof AbstractSparseEdge) {
200109691            AbstractSparseEdge ase = (AbstractSparseEdge) e;
201109691            ase.removeGraph_internal();
202109691            mEdgeIDs.remove(new Integer(ase.getID()));
203         }
204  
205109691        mEdges.remove(e);
206109691        mGraphListenerHandler.handleRemove( e );
207109691    }
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     {
2190        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     {
23321        GraphUtils.removeVertices(this, vertices);
23421    }
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     {
2472        GraphUtils.removeEdges(this, edges);
2482    }
249 }

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.