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

LineHitsSource
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     {
52151        super();
53151    }
54  
55     /**
56      *
57      * @see Vertex#getPredecessors()
58      */
59     public Set getPredecessors()
60     {
610        return Collections.unmodifiableSet(getNeighborsToEdges().keySet());
62     }
63  
64     /**
65      *
66      * @see edu.uci.ics.jung.graph.Vertex#numPredecessors()
67      */
68     public int numPredecessors()
69     {
700        return getPredecessors().size();
71     }
72  
73     /**
74      *
75      * @see Vertex#getSuccessors()
76      */
77     public Set getSuccessors()
78     {
790        return Collections.unmodifiableSet(getNeighborsToEdges().keySet());
80     }
81  
82     /**
83      *
84      * @see edu.uci.ics.jung.graph.Vertex#numPredecessors()
85      */
86     public int numSuccessors()
87     {
880        return getSuccessors().size();
89     }
90  
91     /**
92      *
93      * @see Vertex#getInEdges()
94      */
95     public Set getInEdges()
96     {
970        return Collections.unmodifiableSet(new HashSet(getEdges_internal()));
98     }
99  
100     /**
101      *
102      * @see Vertex#getOutEdges()
103      */
104     public Set getOutEdges()
105     {
1060        return Collections.unmodifiableSet(new HashSet(getEdges_internal()));
107     }
108  
109     /**
110      *
111      * @see Vertex#inDegree()
112      */
113     public int inDegree()
114     {
1150        return getNeighborsToEdges().values().size();
116     }
117  
118     /**
119      *
120      * @see Vertex#outDegree()
121      */
122     public int outDegree()
123     {
1240        return getNeighborsToEdges().values().size();
125     }
126  
127     /**
128      * @see Vertex#isSuccessorOf(Vertex)
129      */
130     public boolean isSuccessorOf(Vertex v)
131     {
1320        return getNeighborsToEdges().containsKey(v);
133     }
134  
135     /**
136      * @see Vertex#isPredecessorOf(Vertex)
137      */
138     public boolean isPredecessorOf(Vertex v)
139     {
1400        return getNeighborsToEdges().containsKey(v);
141     }
142  
143     /**
144      * @see Vertex#isSource(Edge)
145      */
146     public boolean isSource(Edge e)
147     {
1480        return isIncident(e);
149     }
150  
151     /**
152      * @see Vertex#isDest(Edge)
153      */
154     public boolean isDest(Edge e)
155     {
1560        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     {
172105        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     {
18683        Set s = new HashSet();
18783        Edge e = findEdge(v);
18883        if (e != null)
18932            s.add(e);
19083        return Collections.unmodifiableSet(s);
191     }
192  
193     /**
194      * @see AbstractSparseVertex#initialize()
195      */
196     protected void initialize()
197     {
198306        super.initialize();
199306        setNeighborsToEdges(null);
200306    }
201  
202     /**
203      * @see AbstractSparseVertex#getNeighbors_internal()
204      */
205     protected Collection getNeighbors_internal()
206     {
20717        return getNeighborsToEdges().keySet();
208     }
209  
210     /**
211      * @see AbstractSparseVertex#getEdges_internal()
212      */
213     protected Collection getEdges_internal()
214     {
2150        return getNeighborsToEdges().values();
216     }
217  
218     /**
219      * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex)
220      */
221     protected void addNeighbor_internal(Edge e, Vertex v)
222     {
22360        if (ParallelEdgePredicate.getInstance().evaluate(e))
2241            throw new IllegalArgumentException("This vertex " +
225                     "implementation does not support parallel edges");
226         
22759        if (! (e instanceof UndirectedEdge))
2281            throw new IllegalArgumentException("This vertex " +
229                     "implementation only accepts undirected edges");
23058        getNeighborsToEdges().put(v, e);
23158    }
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?
2418        if (connectingEdge == getNeighborsToEdges().get(neighbor))
242         {
2436            getNeighborsToEdges().remove(neighbor);
244         }
245         else
246         {
247             // self-loop; already removed this node
248             // in a previous call to removeNeighbor_internal()
2492            if (this == neighbor)
2502                return;
251  
2520            throw new FatalException("Internal error: " + "edge "
253                     + connectingEdge + " not incident to vertex " + neighbor);
254         }
2556    }
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     {
2643708        if (mNeighborsToEdges == null)
265         {
266146            setNeighborsToEdges(new HashMap(5));
267         }
2683708        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     {
278452        this.mNeighborsToEdges = neighborsToEdges;
279452    }
280  
281 }

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.