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

LineHitsSource
1 /*
2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
3 * of California
4 * All rights reserved.
5 *
6 * This software is open-source under the BSD license; see either
7 * "license.txt" or
8 * http://jung.sourceforge.net/license.txt for a description.
9 */
10 package edu.uci.ics.jung.graph.impl;
11  
12  
13 import java.util.Collection;
14 import java.util.Collections;
15 import java.util.HashSet;
16 import java.util.Iterator;
17 import java.util.Map;
18 import java.util.Set;
19  
20 import edu.uci.ics.jung.exceptions.FatalException;
21 import edu.uci.ics.jung.graph.DirectedEdge;
22 import edu.uci.ics.jung.graph.Edge;
23 import edu.uci.ics.jung.graph.UndirectedEdge;
24 import edu.uci.ics.jung.graph.Vertex;
25  
26 /**
27  * An implementation of <code>Vertex</code> that resides in a
28  * sparse graph which may contain directed and/or undirected edges,
29  * as well as parallel edges.
30  * <P>
31  * This implementation stores hash tables that map the successors
32  * of this vertex to its outgoing edges, and its predecessors to
33  * its incoming edges. This enables an efficient implementation of
34  * <code>findEdge(Vertex)</code>, but causes the routines that
35  * return the sets of neighbors and of incident edges to require
36  * time proportional to the number of neighbors.
37  *
38  * @author Joshua O'Madadhain
39  * @author Scott White
40  * @author Danyel Fisher
41  *
42  * @see SparseGraph
43  */
44 public class SparseVertex extends SimpleSparseVertex
45 {
46     /**
47      * Creates a new instance of a vertex for inclusion in a
48      * sparse graph.
49      */
50     public SparseVertex()
51     {
5231462        super();
5331462    }
54  
55     /**
56      * @see Vertex#getInEdges()
57      */
58     public Set getInEdges()
59     {
6011073        Collection inEdgeSets = getPredsToInEdges().values();
6111073        Collection edgeSets = getNeighborsToEdges().values();
6211073        Set inEdges = new HashSet();
63         
6411073        for (Iterator i_iter = inEdgeSets.iterator(); i_iter.hasNext(); )
651095            inEdges.addAll((Set)i_iter.next());
66             
6711073        for (Iterator e_iter = edgeSets.iterator(); e_iter.hasNext(); )
68493            inEdges.addAll((Set)e_iter.next());
69             
7011073        return Collections.unmodifiableSet(inEdges);
71     }
72  
73     /**
74      * @see Vertex#getOutEdges()
75      */
76     public Set getOutEdges() {
776597        Collection outEdgeSets = getSuccsToOutEdges().values();
786597        Collection edgeSets = getNeighborsToEdges().values();
796597        Set outEdges = new HashSet();
80         
816597        for (Iterator o_iter = outEdgeSets.iterator(); o_iter.hasNext(); )
826858            outEdges.addAll((Set)o_iter.next());
83  
846597        for (Iterator e_iter = edgeSets.iterator(); e_iter.hasNext(); )
8514072            outEdges.addAll((Set)e_iter.next());
86             
876597        return Collections.unmodifiableSet(outEdges);
88     }
89  
90  
91     /**
92      * Returns the edge that connects this
93      * vertex to the specified vertex <code>v</code>, or
94      * <code>null</code> if there is no such edge.
95      * Implemented using a hash table for a performance
96      * improvement over the implementation in
97      * <code>AbstractSparseVertex</code>.
98      *
99      * Looks for a directed edge first, and then for an
100      * undirected edge if no directed edges are found.
101      *
102      * @see Vertex#findEdge(Vertex)
103      */
104     public Edge findEdge(Vertex v)
105     {
1062107        Set outEdges = (Set)getSuccsToOutEdges().get(v);
1072107        if (outEdges == null)
1081803            outEdges = (Set)getNeighborsToEdges().get(v);
1092107        if (outEdges == null)
11044            return null;
1112063        return (Edge)outEdges.iterator().next();
112     }
113  
114     /**
115      * @see Vertex#findEdgeSet(Vertex)
116      */
117     public Set findEdgeSet(Vertex v)
118     {
119         // v. 1.4: no longer using CollectionUtils.union to combine these sets,
120         // since this method does not accept null arguments
121147577        Set edgeSet = new HashSet();
122147577        Set outEdges = (Set)getSuccsToOutEdges().get(v);
123147577        Set edges = (Set)getNeighborsToEdges().get(v);
124147577        if (outEdges != null)
12521            edgeSet.addAll(outEdges);
126147577        if (edges != null)
12710            edgeSet.addAll(edges);
128147577        return Collections.unmodifiableSet(edgeSet);
129     }
130  
131     /**
132      * Returns a list of all incident edges of this vertex.
133      * Requires time proportional to the number of incident edges.
134      *
135      * @see AbstractSparseVertex#getEdges_internal()
136      */
137     protected Collection getEdges_internal() {
138540806        HashSet edges = new HashSet();
139  
140540806        Collection inEdgeSets = getPredsToInEdges().values();
141540806        Collection outEdgeSets = getSuccsToOutEdges().values();
142540806        Collection edgeSets = getNeighborsToEdges().values();
143         
144540806        for (Iterator e_iter = inEdgeSets.iterator(); e_iter.hasNext(); )
145170            edges.addAll((Set)e_iter.next());
146  
147540806        for (Iterator e_iter = outEdgeSets.iterator(); e_iter.hasNext(); )
148200            edges.addAll((Set)e_iter.next());
149  
150540806        for (Iterator e_iter = edgeSets.iterator(); e_iter.hasNext(); )
1514721570            edges.addAll((Set)e_iter.next());
152         
153540806        return edges;
154     }
155  
156     /**
157      * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex)
158      */
159     protected void addNeighbor_internal(Edge e, Vertex v)
160     {
161295684        if (e instanceof DirectedEdge)
162         {
1637544            DirectedEdge de = (DirectedEdge) e;
1647544            boolean added = false;
1657544            if (this == de.getSource())
166             {
1673915                Map stoe = getSuccsToOutEdges();
1683915                Set outEdges = (Set)stoe.get(v);
1693915                if (outEdges == null)
170                 {
1713767                    outEdges = new HashSet();
1723767                    stoe.put(v, outEdges);
173                 }
1743915                outEdges.add(de);
1753915                added = true;
176             }
1777544            if (this == de.getDest())
178             {
1793915                Map ptie = getPredsToInEdges();
1803915                Set inEdges = (Set)ptie.get(v);
1813915                if (inEdges == null)
182                 {
1833767                    inEdges = new HashSet();
1843767                    ptie.put(v, inEdges);
185                 }
1863915                inEdges.add(de);
1873915                added = true;
188             }
1897544            if (!added)
1900                throw new IllegalArgumentException("Internal error: " +
191                     "this vertex is not incident to " + e);
192         }
193288140        else if (e instanceof UndirectedEdge)
194         {
195288140            Map nte = getNeighborsToEdges();
196288140            Set edges = (Set)nte.get(v);
197  
198288140            if (edges == null)
199             {
200287820                edges = new HashSet();
201287820                nte.put(v, edges);
202             }
203288140            edges.add(e);
204         }
2050        else throw new IllegalArgumentException("Edge is neither directed" +
206             "nor undirected");
207295684    }
208  
209     /**
210      * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex)
211      */
212     protected void removeNeighbor_internal(Edge e, Vertex v)
213     {
214219334        boolean predecessor = false;
215219334        boolean successor = false;
216  
217219334        if (e instanceof DirectedEdge)
218         {
219320            Map ptie = getPredsToInEdges();
220320            Set inEdges = (Set)ptie.get(v);
221320            Map stoe = getSuccsToOutEdges();
222320            Set outEdges = (Set)stoe.get(v);
223320            DirectedEdge de = (DirectedEdge)e;
224  
225320            if (de.getSource() == v && inEdges != null)
226             { // -> v is predecessor and not yet removed
227160                predecessor = inEdges.remove(e);
228160                if (inEdges.isEmpty()) // remove entry if it's now obsolete
229159                    ptie.remove(v);
230             }
231320            if (de.getDest() == v && outEdges != null)
232             { // -> v is successor and not yet removed
233160                successor = outEdges.remove(e);
234160                if (outEdges.isEmpty()) // remove entry if it's now obsolete
235159                    stoe.remove(v);
236             }
237320            if (!predecessor && !successor && !(this == v))
2380                throw new FatalException("Internal error in data structure" +
239                     " for vertex " + this);
240         }
241219014        else if (e instanceof UndirectedEdge)
242         {
243             // if v doesn't point to e, and it's not a self-loop
244             // that's been removed in a previous call to removeNeighbor...
245219014            Map nte = getNeighborsToEdges();
246219014            Set edges = (Set)nte.get(v);
247219014            if (edges != null)
248             {
249218894                boolean removed = edges.remove(e);
250218894                if (edges.isEmpty())
251218892                    nte.remove(v);
252218894                if (!removed && this != v)
2530                    throw new FatalException("Internal error in data structure" +
254                         "for vertex " + this);
255             }
256120            else if (this != v)
2570                throw new FatalException("Internal error in data structure" +
258                     "for vertex " + this);
259  
260             // if it *is* a self-loop, we're already done
261         }
262         
263         else
2640            throw new FatalException("Edge is neither directed nor undirected");
265219334    }
266  
267 }

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.