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

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.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     {
6144        super();
6244    }
63  
64     /**
65      * @see Vertex#getPredecessors()
66      */
67     public Set getPredecessors() {
680        return Collections.unmodifiableSet(getPredsToInEdges().keySet());
69     }
70  
71     /**
72      *
73      * @see edu.uci.ics.jung.graph.Vertex#numPredecessors()
74      */
75     public int numPredecessors()
76     {
770        return getPredecessors().size();
78     }
79     
80     /**
81      * @see Vertex#getSuccessors()
82      */
83     public Set getSuccessors() {
840        return Collections.unmodifiableSet(getSuccsToOutEdges().keySet());
85     }
86  
87     /**
88      * @see edu.uci.ics.jung.graph.Vertex#numSuccessors()
89      */
90     public int numSuccessors()
91     {
920        return getSuccessors().size();
93     }
94     
95     /**
96      * @see Vertex#getInEdges()
97      */
98     public Set getInEdges() {
990        return Collections.unmodifiableSet(new HashSet(getPredsToInEdges().values()));
100     }
101  
102     /**
103      * @see Vertex#getOutEdges()
104      */
105     public Set getOutEdges() {
1060        return Collections.unmodifiableSet(new HashSet(getSuccsToOutEdges().values()));
107     }
108  
109     /**
110      * @see Vertex#inDegree()
111      */
112     public int inDegree() {
1130        return getInEdges().size();
114     }
115  
116     /**
117      * @see Vertex#outDegree()
118      */
119     public int outDegree() {
1200        return getOutEdges().size();
121     }
122  
123     /**
124      * @see Vertex#isSuccessorOf(Vertex)
125      */
126     public boolean isSuccessorOf(Vertex v) {
12721        return getPredsToInEdges().containsKey(v);
128     }
129  
130     /**
131      * @see Vertex#isPredecessorOf(Vertex)
132      */
133     public boolean isPredecessorOf(Vertex v) {
13460        return getSuccsToOutEdges().containsKey(v);
135     }
136  
137     /**
138      * @see Vertex#isSource(Edge)
139      */
140     public boolean isSource(Edge e)
141     {
1424        if (e.getGraph() == this.getGraph())
1434            return equals(((DirectedEdge)e).getSource());
144         else
1450            return false;
146     }
147  
148     /**
149      * @see Vertex#isDest(Edge)
150      */
151     public boolean isDest(Edge e)
152     {
1534        if (e.getGraph() == this.getGraph())
1544            return equals(((DirectedEdge)e).getDest());
155         else
1560            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     {
17148        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     {
18539        Set s = new HashSet();
18639        Edge e = findEdge(v);
18739        if (e != null)
18817            s.add(e);
18939        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     {
20047        HashSet neighbors = new HashSet();
20147        neighbors.addAll(getPredsToInEdges().keySet());
20247        neighbors.addAll(getSuccsToOutEdges().keySet());
20347        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() {
2130        HashSet edges = new HashSet();
2140        edges.addAll(getPredsToInEdges().values());
2150        edges.addAll(getSuccsToOutEdges().values());
2160        return edges;
217     }
218  
219     /**
220      * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex)
221      */
222     protected void addNeighbor_internal(Edge e, Vertex v)
223     {
22432        if (! (e instanceof DirectedEdge))
2251            throw new IllegalArgumentException("This vertex " +
226                     "implementation only accepts directed edges");
227         
22831        if (ParallelEdgePredicate.getInstance().evaluate(e))
2291            throw new IllegalArgumentException("This vertex " +
230                     "implementation does not support parallel edges");
231         
23230        DirectedEdge edge = (DirectedEdge) e;
23330        boolean added = false;
23430        if (this == edge.getSource())
235         {
23620            getSuccsToOutEdges().put(v, e);
23720            added = true;
238         }
23930        if (this == edge.getDest())
240         {
24120            getPredsToInEdges().put(v, e);
24220            added = true;
243         }
24430        if (!added)
2450            throw new IllegalArgumentException("Internal error: " +
246                 "this vertex is not incident to " + e);
24730    }
248  
249     /**
250      * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex)
251      */
252     protected void removeNeighbor_internal(Edge e, Vertex v)
253     {
2548        String error = "Internal error: " +
255             "edge " + e + " not incident to vertex ";
2568        if (getSuccsToOutEdges().containsKey(v) && v.isDest(e))
257         { // e is an outgoing edge of this vertex -> v is a successor
2584            if (getSuccsToOutEdges().remove(v) == null)
2590                throw new FatalException(error + v);
260         }
2614        else if (getPredsToInEdges().containsKey(v) && v.isSource(e))
262         { // e is an incoming edge of this vertex -> v is a predecessor
2634            if (getPredsToInEdges().remove(v) == null)
2640                throw new FatalException(error + v);
265         }
266         else
2670            throw new FatalException(error + this);
2688    }
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() {
276138        if (mPredsToInEdges == null) {
27729            setPredsToInEdges(new HashMap(5));
278         }
279138        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) {
288120        this.mPredsToInEdges = predsToInEdges;
289120    }
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() {
297248        if (mSuccsToOutEdges == null) {
29826            setSuccsToOutEdges(new HashMap(5));
299         }
300248        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) {
309117        this.mSuccsToOutEdges = succsToOutEdges;
310117    }
311  
312     /**
313      * Initializes the internal data structures of this vertex.
314      *
315      * @see AbstractSparseVertex#initialize()
316      */
317     protected void initialize() {
31891        super.initialize();
31991        setPredsToInEdges(null);
32091        setSuccsToOutEdges(null);
32191    }
322  
323 }

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.