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

LineHitsSource
1 /*
2  * Created on Apr 2, 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 org.apache.commons.collections.CollectionUtils;
22  
23 import edu.uci.ics.jung.exceptions.FatalException;
24 import edu.uci.ics.jung.graph.DirectedEdge;
25 import edu.uci.ics.jung.graph.Edge;
26 import edu.uci.ics.jung.graph.UndirectedEdge;
27 import edu.uci.ics.jung.graph.Vertex;
28 import edu.uci.ics.jung.graph.predicates.ParallelEdgePredicate;
29  
30 /**
31  * An implementation of <code>Vertex</code> that resides in a
32  * sparse graph which may contain both directed and undirected edges.
33  * It does not support parallel edges.
34  *
35  * <P>
36  * This implementation stores hash tables that map the successors
37  * of this vertex to its outgoing edges, and its predecessors to
38  * its incoming edges. This enables an efficient implementation of
39  * <code>findEdge(Vertex)</code>, but causes the routines that
40  * return the sets of neighbors and of incident edges to require
41  * time proportional to the number of neighbors.
42  *
43  * @author Joshua O'Madadhain
44  */
45 public class SimpleSparseVertex extends AbstractSparseVertex
46 {
47     /**
48      * A map of the predecessors of this vertex to the corresponding
49      * sets of incoming edges.
50      * Used to speed up <code>findEdge(Vertex)</code>.
51      */
52     protected Map mPredsToInEdges;
53  
54     /**
55      * A map of the successors of this vertex to the corresponding
56      * sets of outgoing edges.
57      * Used to speed up <code>findEdge(Vertex)</code>.
58      */
59     protected Map mSuccsToOutEdges;
60  
61     /**
62      * A map of the vertices connected to this vertex by undirected
63      * edges to the corresponding sets of edges.
64      * Used to speed up <code>findEdge(Vertex)</code>.
65      */
66     protected Map mNeighborsToEdges;
67  
68     /**
69      * Creates a new instance of a vertex for inclusion in a
70      * sparse graph.
71      */
72     public SimpleSparseVertex()
73     {
7431481        super();
7531481    }
76  
77     /**
78      * @see Vertex#getPredecessors()
79      */
80     public Set getPredecessors() {
81360        Collection preds = CollectionUtils.union(
82             getPredsToInEdges().keySet(),
83             getNeighborsToEdges().keySet());
84         
85360        return Collections.unmodifiableSet(new HashSet(preds));
86     }
87  
88     /**
89      * @see Vertex#getSuccessors()
90      */
91     public Set getSuccessors() {
921351        Collection succs = CollectionUtils.union(
93             getSuccsToOutEdges().keySet(),
94             getNeighborsToEdges().keySet());
95         
961351        return Collections.unmodifiableSet(new HashSet(succs));
97     }
98  
99     /**
100      * @see Vertex#inDegree()
101      */
102     public int inDegree() {
10310043        return getInEdges().size();
104     }
105  
106     /**
107      * @see Vertex#outDegree()
108      */
109     public int outDegree() {
1101588        return getOutEdges().size();
111     }
112  
113     /**
114      * @see Vertex#numPredecessors()
115      */
116     public int numPredecessors()
117     {
1180        return getPredsToInEdges().size();
119     }
120  
121     /**
122      * @see Vertex#numSuccessors()
123      */
124     public int numSuccessors()
125     {
1260        return getSuccsToOutEdges().size();
127     }
128  
129     /**
130      * @see Vertex#isSuccessorOf(Vertex)
131      */
132     public boolean isSuccessorOf(Vertex v) {
133133500        return getPredsToInEdges().containsKey(v) ||
134             getNeighborsToEdges().containsKey(v);
135     }
136  
137     /**
138      * @see Vertex#isPredecessorOf(Vertex)
139      */
140     public boolean isPredecessorOf(Vertex v) {
141318        return getSuccsToOutEdges().containsKey(v) ||
142             getNeighborsToEdges().containsKey(v);
143     }
144  
145     /**
146      * @see Vertex#isSource(Edge)
147      */
148     public boolean isSource(Edge e)
149     {
15011        if (e instanceof DirectedEdge)
151         {
1529            if (e.getGraph() == this.getGraph())
1539                return (this == ((DirectedEdge)e).getSource());
154             else
1550                return false;
156         }
1572        else if (e instanceof UndirectedEdge)
1582            return isIncident(e);
159         else
1600            throw new IllegalArgumentException("Edge is neither directed nor undirected");
161     }
162  
163     /**
164      * @see Vertex#isDest(Edge)
165      */
166     public boolean isDest(Edge e)
167     {
16811        if (e instanceof DirectedEdge)
169         {
1709            if (e.getGraph() == this.getGraph())
1719                return (this == ((DirectedEdge)e).getDest());
172             else
1730                return false;
174         }
1752        else if (e instanceof UndirectedEdge)
1762            return isIncident(e);
177         else
1780            throw new IllegalArgumentException("Edge is neither directed nor undirected");
179     }
180  
181     /**
182      * @see edu.uci.ics.jung.graph.Vertex#getInEdges()
183      */
184     public Set getInEdges()
185     {
1860        Collection inEdges = getPredsToInEdges().values();
1870        Collection adjacentEdges = getNeighborsToEdges().values();
188         
1890        Set edges = new HashSet();
1900        if (inEdges != null)
1910            edges.addAll(inEdges);
1920        if (adjacentEdges != null)
1930            edges.addAll(adjacentEdges);
194         
1950        return Collections.unmodifiableSet(edges);
196     }
197  
198     /**
199      * @see edu.uci.ics.jung.graph.Vertex#getOutEdges()
200      */
201     public Set getOutEdges()
202     {
2030        Collection outEdges = getSuccsToOutEdges().values();
2040        Collection adjacentEdges = getNeighborsToEdges().values();
205         
2060        Set edges = new HashSet();
2070        if (outEdges != null)
2080            edges.addAll(outEdges);
2090        if (adjacentEdges != null)
2100            edges.addAll(adjacentEdges);
211         
2120        return Collections.unmodifiableSet(edges);
213     }
214  
215     /**
216      * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#findEdge(Vertex)
217      */
218     public Edge findEdge(Vertex v)
219     {
2200        Edge e = (Edge)getSuccsToOutEdges().get(v);
2210        if (e != null)
2220            return e;
2230        e = (Edge)getNeighborsToEdges().get(v);
2240        return e;
225     }
226     
227     /**
228      * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#findEdgeSet(Vertex)
229      */
230     public Set findEdgeSet(Vertex v)
231     {
23257        Set s = new HashSet();
23357        Edge d = (Edge)getSuccsToOutEdges().get(v);
23457        Edge u = (Edge)getNeighborsToEdges().get(v);
23557        if (d != null)
23616            s.add(d);
23757        if (u != null)
23814            s.add(u);
23957        return Collections.unmodifiableSet(s);
240     }
241     
242     /**
243      * Returns a set of all neighbors attached to this vertex.
244      * Requires time proportional to the number of neighbors.
245      *
246      * @see AbstractSparseVertex#getNeighbors_internal()
247      */
248     protected Collection getNeighbors_internal()
249     {
2501676        HashSet neighbors = new HashSet();
2511676        neighbors.addAll(getPredsToInEdges().keySet());
2521676        neighbors.addAll(getSuccsToOutEdges().keySet());
2531676        neighbors.addAll(getNeighborsToEdges().keySet());
2541676        return neighbors;
255     }
256  
257  
258     /**
259      * Returns a map from the predecessors of this vertex to its incoming
260      * edges. If this map has not yet been created, it creates it.
261      * This map should not be directly accessed by users.
262      */
263     protected Map getPredsToInEdges() {
264691726        if (mPredsToInEdges == null) {
26528670            setPredsToInEdges(new HashMap(5));
266         }
267691726        return mPredsToInEdges;
268     }
269  
270     /**
271      * Sets this vertex's internal predecessor -> in-edge map to
272      * the specified map <code>predsToInEdges</code>.
273      * This method should not be directly accessed by users.
274      */
275     protected void setPredsToInEdges(Map predsToInEdges) {
27692367        this.mPredsToInEdges = predsToInEdges;
27792367    }
278  
279     /**
280      * Returns a map from the successors of this vertex to its outgoing
281      * edges. If this map has not yet been created, it creates it.
282      * This method should not be directly accessed by users.
283      */
284     protected Map getSuccsToOutEdges() {
285704945        if (mSuccsToOutEdges == null) {
28621332            setSuccsToOutEdges(new HashMap(5));
287         }
288704945        return mSuccsToOutEdges;
289     }
290  
291     /**
292      * Sets this vertex's internal successor -> out-edge map to
293      * the specified map <code>succsToOutEdges</code>.
294      * This method should not be directly accessed by users.
295      */
296     protected void setSuccsToOutEdges(Map succsToOutEdges) {
29785029        this.mSuccsToOutEdges = succsToOutEdges;
29885029    }
299  
300     /**
301      * Returns a map from the successors of this vertex to its outgoing
302      * edges. If this map has not yet been created, it creates it.
303      * This method should not be directly accessed by users.
304      */
305     protected Map getNeighborsToEdges() {
3061353149        if (mNeighborsToEdges == null) {
30731556            setNeighborsToEdges(new HashMap(5));
308         }
3091353149        return mNeighborsToEdges;
310     }
311  
312     /**
313      * Sets this vertex's internal successor -> out-edge map to
314      * the specified map <code>succsToOutEdges</code>.
315      * This method should not be directly accessed by users.
316      */
317     protected void setNeighborsToEdges(Map neighborsToEdges) {
31895253        this.mNeighborsToEdges = neighborsToEdges;
31995253    }
320  
321     /**
322      * Initializes the internal data structures of this vertex.
323      *
324      * @see AbstractSparseVertex#initialize()
325      */
326     protected void initialize() {
32763697        super.initialize();
32863697        setPredsToInEdges(null);
32963697        setSuccsToOutEdges(null);
33063697        setNeighborsToEdges(null);
33163697    }
332  
333     /**
334      * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#getEdges_internal()
335      */
336     protected Collection getEdges_internal()
337     {
3380        HashSet edges = new HashSet();
339  
3400        Collection inEdges = getPredsToInEdges().values();
3410        Collection outEdges = getSuccsToOutEdges().values();
3420        Collection adjacentEdges = getNeighborsToEdges().values();
343         
3440        if (inEdges != null)
3450            edges.addAll(inEdges);
3460        if (outEdges != null)
3470            edges.addAll(outEdges);
3480        if (adjacentEdges != null)
3490            edges.addAll(adjacentEdges);
350         
3510        return edges;
352     }
353  
354     /**
355      * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#addNeighbor_internal(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.Vertex)
356      */
357     protected void addNeighbor_internal(Edge e, Vertex v)
358     {
35945        if (ParallelEdgePredicate.getInstance().evaluate(e))
3601            throw new IllegalArgumentException("This vertex " +
361                     "implementation does not support parallel edges");
362  
36344        if (e instanceof DirectedEdge)
364         {
36522            DirectedEdge de = (DirectedEdge) e;
36622            boolean added = false;
36722            if (this == de.getSource())
368             {
36915                getSuccsToOutEdges().put(v, e);
37015                added = true;
371             }
37222            if (this == de.getDest())
373             {
37415                getPredsToInEdges().put(v, e);
37515                added = true;
376             }
37722            if (!added)
3780                throw new IllegalArgumentException("Internal error: " +
379                     "this vertex is not incident to " + e);
380         }
38122        else if (e instanceof UndirectedEdge)
382         {
38322            getNeighborsToEdges().put(v, e);
384         }
3850        else throw new IllegalArgumentException("Edge is neither directed" +
386             "nor undirected");
38744    }
388  
389     /**
390      * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#removeNeighbor_internal(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.Vertex)
391      */
392     protected void removeNeighbor_internal(Edge e, Vertex v)
393     {
39416        String error = "Internal error: " +
395         "edge " + e + " not incident to vertex ";
39616        if (e instanceof DirectedEdge)
397         {
3988            if (getSuccsToOutEdges().containsKey(v) && v.isDest(e))
399             { // e is an outgoing edge of this vertex -> v is a successor
4004                if (getSuccsToOutEdges().remove(v) == null)
4010                    throw new FatalException(error + v);
402             }
4034            else if (getPredsToInEdges().containsKey(v) && v.isSource(e))
404             { // e is an incoming edge of this vertex -> v is a predecessor
4054                if (getPredsToInEdges().remove(v) == null)
4060                    throw new FatalException(error + v);
407             }
408             else
4090                throw new FatalException(error + this);
410         }
4118        else if (e instanceof UndirectedEdge)
412         {
4138            Map nte = getNeighborsToEdges();
4148            if (nte.get(v) == e)
415             {
4166                nte.remove(v);
417             }
418             else
419             {
420                 // if this is not a self-loop or a fatal error
4212                if (this != v)
4220                    throw new FatalException(error + v);
423             }
424         }
425         else
4260            throw new IllegalArgumentException("Edge is neither directed" +
427                 "nor undirected");
42816    }
429 }

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.