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

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.HashSet;
17 import java.util.Iterator;
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  
26  
27 /**
28  * A vertex class that supports directed edges (but not
29  * undirected edges) and allows parallel edges.
30  *
31  * {@link edu.uci.ics.jung.graph.UndirectedGraph}
32  * @author Joshua O'Madadhain
33  */
34 public class DirectedSparseVertex extends SimpleDirectedSparseVertex
35 {
36     /**
37      * Creates a new instance of a vertex for inclusion in a
38      * sparse graph.
39      */
40     public DirectedSparseVertex()
41     {
4223        super();
4323    }
44  
45     /**
46      * @see Vertex#getInEdges()
47      */
48     public Set getInEdges()
49     {
500        Collection inEdgeSets = getPredsToInEdges().values();
510        Set inEdges = new HashSet();
52         
530        for (Iterator i_iter = inEdgeSets.iterator(); i_iter.hasNext(); )
540            inEdges.addAll((Set)i_iter.next());
55             
560        return Collections.unmodifiableSet(inEdges);
57     }
58  
59     /**
60      * @see Vertex#getOutEdges()
61      */
62     public Set getOutEdges() {
630        Collection outEdgeSets = getSuccsToOutEdges().values();
640        Set outEdges = new HashSet();
65         
660        for (Iterator o_iter = outEdgeSets.iterator(); o_iter.hasNext(); )
670            outEdges.addAll((Set)o_iter.next());
68  
690        return Collections.unmodifiableSet(outEdges);
70     }
71  
72  
73     /**
74      * Returns the edge that connects this
75      * vertex to the specified vertex <code>v</code>, or
76      * <code>null</code> if there is no such edge.
77      * Implemented using a hash table for a performance
78      * improvement over the implementation in
79      * <code>AbstractSparseVertex</code>.
80      *
81      * Looks for a directed edge first, and then for an
82      * undirected edge if no directed edges are found.
83      *
84      * @see Vertex#findEdge(Vertex)
85      */
86     public Edge findEdge(Vertex v)
87     {
880        Set outEdges = (Set)getSuccsToOutEdges().get(v);
890        if (outEdges == null)
900            return null;
910        return (Edge)outEdges.iterator().next();
92     }
93  
94     /**
95      * @see Vertex#findEdgeSet(Vertex)
96      */
97     public Set findEdgeSet(Vertex v)
98     {
9919        Set edgeSet = new HashSet();
10019        Set edges = (Set)getSuccsToOutEdges().get(v);
10119        if (edges != null)
1021            edgeSet.addAll(edges);
10319        return Collections.unmodifiableSet(edgeSet);
104     }
105  
106     /**
107      * Returns a list of all incident edges of this vertex.
108      * Requires time proportional to the number of incident edges.
109      *
110      * @see AbstractSparseVertex#getEdges_internal()
111      */
112     protected Collection getEdges_internal() {
1130        HashSet edges = new HashSet();
114  
1150        Collection inEdgeSets = getPredsToInEdges().values();
1160        Collection outEdgeSets = getSuccsToOutEdges().values();
117         
1180        for (Iterator e_iter = inEdgeSets.iterator(); e_iter.hasNext(); )
1190            edges.addAll((Set)e_iter.next());
120  
1210        for (Iterator e_iter = outEdgeSets.iterator(); e_iter.hasNext(); )
1220            edges.addAll((Set)e_iter.next());
123  
1240        return edges;
125     }
126  
127     /**
128      * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex)
129      */
130     protected void addNeighbor_internal(Edge e, Vertex v)
131     {
13259        if (! (e instanceof DirectedEdge))
1331            throw new IllegalArgumentException("This vertex " +
134                     "implementation only accepts directed edges");
135  
13658        DirectedEdge de = (DirectedEdge) e;
13758        boolean added = false;
13858        if (this == de.getSource())
139         {
14034            Map stoe = getSuccsToOutEdges();
14134            Set outEdges = (Set)stoe.get(v);
14234            if (outEdges == null)
143             {
14427                outEdges = new HashSet();
14527                stoe.put(v, outEdges);
146             }
14734            outEdges.add(de);
14834            added = true;
149         }
15058        if (this == de.getDest())
151         {
15234            Map ptie = getPredsToInEdges();
15334            Set inEdges = (Set)ptie.get(v);
15434            if (inEdges == null)
155             {
15627                inEdges = new HashSet();
15727                ptie.put(v, inEdges);
158             }
15934            inEdges.add(de);
16034            added = true;
161         }
16258        if (!added)
1630            throw new IllegalArgumentException("Internal error: " +
164                 "this vertex is not incident to " + e);
16558    }
166  
167     /**
168      * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex)
169      */
170     protected void removeNeighbor_internal(Edge e, Vertex v)
171     {
1728        boolean predecessor = false;
1738        boolean successor = false;
174  
1758        Map ptie = getPredsToInEdges();
1768        Set inEdges = (Set)ptie.get(v);
1778        Map stoe = getSuccsToOutEdges();
1788        Set outEdges = (Set)stoe.get(v);
1798        DirectedEdge de = (DirectedEdge)e;
180  
1818        if (de.getSource() == v && inEdges != null)
182         { // -> v is predecessor and not yet removed
1834            predecessor = inEdges.remove(e);
1844            if (inEdges.isEmpty()) // remove entry if it's now obsolete
1854                ptie.remove(v);
186         }
1878        if (de.getDest() == v && outEdges != null)
188         { // -> v is successor and not yet removed
1894            successor = outEdges.remove(e);
1904            if (outEdges.isEmpty()) // remove entry if it's now obsolete
1914                stoe.remove(v);
192         }
1938        if (!predecessor && !successor && !(this == v))
1940            throw new FatalException("Internal error in data structure" +
195                 " for vertex " + this);
1968    }
197 }

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.