Line | Hits | Source |
---|---|---|
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 | { | |
42 | 23 | super(); |
43 | 23 | } |
44 | ||
45 | /** | |
46 | * @see Vertex#getInEdges() | |
47 | */ | |
48 | public Set getInEdges() | |
49 | { | |
50 | 0 | Collection inEdgeSets = getPredsToInEdges().values(); |
51 | 0 | Set inEdges = new HashSet(); |
52 | ||
53 | 0 | for (Iterator i_iter = inEdgeSets.iterator(); i_iter.hasNext(); ) |
54 | 0 | inEdges.addAll((Set)i_iter.next()); |
55 | ||
56 | 0 | return Collections.unmodifiableSet(inEdges); |
57 | } | |
58 | ||
59 | /** | |
60 | * @see Vertex#getOutEdges() | |
61 | */ | |
62 | public Set getOutEdges() { | |
63 | 0 | Collection outEdgeSets = getSuccsToOutEdges().values(); |
64 | 0 | Set outEdges = new HashSet(); |
65 | ||
66 | 0 | for (Iterator o_iter = outEdgeSets.iterator(); o_iter.hasNext(); ) |
67 | 0 | outEdges.addAll((Set)o_iter.next()); |
68 | ||
69 | 0 | 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 | { | |
88 | 0 | Set outEdges = (Set)getSuccsToOutEdges().get(v); |
89 | 0 | if (outEdges == null) |
90 | 0 | return null; |
91 | 0 | return (Edge)outEdges.iterator().next(); |
92 | } | |
93 | ||
94 | /** | |
95 | * @see Vertex#findEdgeSet(Vertex) | |
96 | */ | |
97 | public Set findEdgeSet(Vertex v) | |
98 | { | |
99 | 19 | Set edgeSet = new HashSet(); |
100 | 19 | Set edges = (Set)getSuccsToOutEdges().get(v); |
101 | 19 | if (edges != null) |
102 | 1 | edgeSet.addAll(edges); |
103 | 19 | 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() { | |
113 | 0 | HashSet edges = new HashSet(); |
114 | ||
115 | 0 | Collection inEdgeSets = getPredsToInEdges().values(); |
116 | 0 | Collection outEdgeSets = getSuccsToOutEdges().values(); |
117 | ||
118 | 0 | for (Iterator e_iter = inEdgeSets.iterator(); e_iter.hasNext(); ) |
119 | 0 | edges.addAll((Set)e_iter.next()); |
120 | ||
121 | 0 | for (Iterator e_iter = outEdgeSets.iterator(); e_iter.hasNext(); ) |
122 | 0 | edges.addAll((Set)e_iter.next()); |
123 | ||
124 | 0 | return edges; |
125 | } | |
126 | ||
127 | /** | |
128 | * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex) | |
129 | */ | |
130 | protected void addNeighbor_internal(Edge e, Vertex v) | |
131 | { | |
132 | 59 | if (! (e instanceof DirectedEdge)) |
133 | 1 | throw new IllegalArgumentException("This vertex " + |
134 | "implementation only accepts directed edges"); | |
135 | ||
136 | 58 | DirectedEdge de = (DirectedEdge) e; |
137 | 58 | boolean added = false; |
138 | 58 | if (this == de.getSource()) |
139 | { | |
140 | 34 | Map stoe = getSuccsToOutEdges(); |
141 | 34 | Set outEdges = (Set)stoe.get(v); |
142 | 34 | if (outEdges == null) |
143 | { | |
144 | 27 | outEdges = new HashSet(); |
145 | 27 | stoe.put(v, outEdges); |
146 | } | |
147 | 34 | outEdges.add(de); |
148 | 34 | added = true; |
149 | } | |
150 | 58 | if (this == de.getDest()) |
151 | { | |
152 | 34 | Map ptie = getPredsToInEdges(); |
153 | 34 | Set inEdges = (Set)ptie.get(v); |
154 | 34 | if (inEdges == null) |
155 | { | |
156 | 27 | inEdges = new HashSet(); |
157 | 27 | ptie.put(v, inEdges); |
158 | } | |
159 | 34 | inEdges.add(de); |
160 | 34 | added = true; |
161 | } | |
162 | 58 | if (!added) |
163 | 0 | throw new IllegalArgumentException("Internal error: " + |
164 | "this vertex is not incident to " + e); | |
165 | 58 | } |
166 | ||
167 | /** | |
168 | * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex) | |
169 | */ | |
170 | protected void removeNeighbor_internal(Edge e, Vertex v) | |
171 | { | |
172 | 8 | boolean predecessor = false; |
173 | 8 | boolean successor = false; |
174 | ||
175 | 8 | Map ptie = getPredsToInEdges(); |
176 | 8 | Set inEdges = (Set)ptie.get(v); |
177 | 8 | Map stoe = getSuccsToOutEdges(); |
178 | 8 | Set outEdges = (Set)stoe.get(v); |
179 | 8 | DirectedEdge de = (DirectedEdge)e; |
180 | ||
181 | 8 | if (de.getSource() == v && inEdges != null) |
182 | { // -> v is predecessor and not yet removed | |
183 | 4 | predecessor = inEdges.remove(e); |
184 | 4 | if (inEdges.isEmpty()) // remove entry if it's now obsolete |
185 | 4 | ptie.remove(v); |
186 | } | |
187 | 8 | if (de.getDest() == v && outEdges != null) |
188 | { // -> v is successor and not yet removed | |
189 | 4 | successor = outEdges.remove(e); |
190 | 4 | if (outEdges.isEmpty()) // remove entry if it's now obsolete |
191 | 4 | stoe.remove(v); |
192 | } | |
193 | 8 | if (!predecessor && !successor && !(this == v)) |
194 | 0 | throw new FatalException("Internal error in data structure" + |
195 | " for vertex " + this); | |
196 | 8 | } |
197 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |