1
2
3
4
5
6
7
8
9
10
11
12 package edu.uci.ics.jung.graph;
13
14 import java.util.ArrayList;
15 import java.util.Collection;
16 import java.util.Collections;
17 import java.util.HashMap;
18 import java.util.HashSet;
19 import java.util.Map;
20
21 import org.apache.commons.collections15.Factory;
22
23 import edu.uci.ics.jung.graph.util.EdgeType;
24 import edu.uci.ics.jung.graph.util.Pair;
25
26
27
28
29 @SuppressWarnings("serial")
30 public class DirectedSparseGraph<V,E> extends AbstractTypedGraph<V, E> implements
31 DirectedGraph<V, E>
32 {
33
34
35
36
37
38 public static final <V,E> Factory<DirectedGraph<V,E>> getFactory() {
39 return new Factory<DirectedGraph<V,E>> () {
40 public DirectedGraph<V,E> create() {
41 return new DirectedSparseGraph<V,E>();
42 }
43 };
44 }
45
46 protected Map<V, Pair<Map<V,E>>> vertices;
47
48 protected Map<E, Pair<V>> edges;
49
50
51
52
53 public DirectedSparseGraph()
54 {
55 super(EdgeType.DIRECTED);
56 vertices = new HashMap<V, Pair<Map<V,E>>>();
57 edges = new HashMap<E, Pair<V>>();
58 }
59
60 @Override
61 public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType)
62 {
63 this.validateEdgeType(edgeType);
64 Pair<V> new_endpoints = getValidatedEndpoints(edge, endpoints);
65 if (new_endpoints == null)
66 return false;
67
68 V source = new_endpoints.getFirst();
69 V dest = new_endpoints.getSecond();
70
71 if (findEdge(source, dest) != null)
72 return false;
73
74 edges.put(edge, new_endpoints);
75
76 if (!vertices.containsKey(source))
77 this.addVertex(source);
78
79 if (!vertices.containsKey(dest))
80 this.addVertex(dest);
81
82
83 vertices.get(source).getSecond().put(dest, edge);
84 vertices.get(dest).getFirst().put(source, edge);
85
86 return true;
87 }
88
89 @Override
90 public E findEdge(V v1, V v2)
91 {
92 if (!containsVertex(v1) || !containsVertex(v2))
93 return null;
94 return vertices.get(v1).getSecond().get(v2);
95 }
96
97 @Override
98 public Collection<E> findEdgeSet(V v1, V v2)
99 {
100 if (!containsVertex(v1) || !containsVertex(v2))
101 return null;
102 ArrayList<E> edge_collection = new ArrayList<E>(1);
103 E e = findEdge(v1, v2);
104 if (e == null)
105 return edge_collection;
106 edge_collection.add(e);
107 return edge_collection;
108 }
109
110 protected Collection<E> getIncoming_internal(V vertex)
111 {
112 return vertices.get(vertex).getFirst().values();
113 }
114
115 protected Collection<E> getOutgoing_internal(V vertex)
116 {
117 return vertices.get(vertex).getSecond().values();
118 }
119
120 protected Collection<V> getPreds_internal(V vertex)
121 {
122 return vertices.get(vertex).getFirst().keySet();
123 }
124
125 protected Collection<V> getSuccs_internal(V vertex)
126 {
127 return vertices.get(vertex).getSecond().keySet();
128 }
129
130 public Collection<E> getInEdges(V vertex)
131 {
132 if (!containsVertex(vertex))
133 return null;
134 return Collections.unmodifiableCollection(getIncoming_internal(vertex));
135 }
136
137 public Collection<E> getOutEdges(V vertex)
138 {
139 if (!containsVertex(vertex))
140 return null;
141 return Collections.unmodifiableCollection(getOutgoing_internal(vertex));
142 }
143
144 public Collection<V> getPredecessors(V vertex)
145 {
146 if (!containsVertex(vertex))
147 return null;
148 return Collections.unmodifiableCollection(getPreds_internal(vertex));
149 }
150
151 public Collection<V> getSuccessors(V vertex)
152 {
153 if (!containsVertex(vertex))
154 return null;
155 return Collections.unmodifiableCollection(getSuccs_internal(vertex));
156 }
157
158 public Pair<V> getEndpoints(E edge)
159 {
160 if (!containsEdge(edge))
161 return null;
162 return edges.get(edge);
163 }
164
165 public V getSource(E directed_edge)
166 {
167 if (!containsEdge(directed_edge))
168 return null;
169 return edges.get(directed_edge).getFirst();
170 }
171
172 public V getDest(E directed_edge)
173 {
174 if (!containsEdge(directed_edge))
175 return null;
176 return edges.get(directed_edge).getSecond();
177 }
178
179 public boolean isSource(V vertex, E edge)
180 {
181 if (!containsEdge(edge) || !containsVertex(vertex))
182 return false;
183 return vertex.equals(this.getEndpoints(edge).getFirst());
184 }
185
186 public boolean isDest(V vertex, E edge)
187 {
188 if (!containsEdge(edge) || !containsVertex(vertex))
189 return false;
190 return vertex.equals(this.getEndpoints(edge).getSecond());
191 }
192
193 public Collection<E> getEdges()
194 {
195 return Collections.unmodifiableCollection(edges.keySet());
196 }
197
198 public Collection<V> getVertices()
199 {
200 return Collections.unmodifiableCollection(vertices.keySet());
201 }
202
203 public boolean containsVertex(V vertex)
204 {
205 return vertices.containsKey(vertex);
206 }
207
208 public boolean containsEdge(E edge)
209 {
210 return edges.containsKey(edge);
211 }
212
213 public int getEdgeCount()
214 {
215 return edges.size();
216 }
217
218 public int getVertexCount()
219 {
220 return vertices.size();
221 }
222
223 public Collection<V> getNeighbors(V vertex)
224 {
225 if (!containsVertex(vertex))
226 return null;
227
228 Collection<V> neighbors = new HashSet<V>();
229 neighbors.addAll(getPreds_internal(vertex));
230 neighbors.addAll(getSuccs_internal(vertex));
231 return Collections.unmodifiableCollection(neighbors);
232 }
233
234 public Collection<E> getIncidentEdges(V vertex)
235 {
236 if (!containsVertex(vertex))
237 return null;
238
239 Collection<E> incident_edges = new HashSet<E>();
240 incident_edges.addAll(getIncoming_internal(vertex));
241 incident_edges.addAll(getOutgoing_internal(vertex));
242 return Collections.unmodifiableCollection(incident_edges);
243 }
244
245 public boolean addVertex(V vertex)
246 {
247 if(vertex == null) {
248 throw new IllegalArgumentException("vertex may not be null");
249 }
250 if (!containsVertex(vertex)) {
251 vertices.put(vertex, new Pair<Map<V,E>>(new HashMap<V,E>(), new HashMap<V,E>()));
252 return true;
253 } else {
254 return false;
255 }
256 }
257
258 public boolean removeVertex(V vertex) {
259 if (!containsVertex(vertex))
260 return false;
261
262
263 ArrayList<E> incident = new ArrayList<E>(getIncoming_internal(vertex));
264 incident.addAll(getOutgoing_internal(vertex));
265
266 for (E edge : incident)
267 removeEdge(edge);
268
269 vertices.remove(vertex);
270
271 return true;
272 }
273
274 public boolean removeEdge(E edge) {
275 if (!containsEdge(edge))
276 return false;
277
278 Pair<V> endpoints = this.getEndpoints(edge);
279 V source = endpoints.getFirst();
280 V dest = endpoints.getSecond();
281
282
283 vertices.get(source).getSecond().remove(dest);
284 vertices.get(dest).getFirst().remove(source);
285
286 edges.remove(edge);
287 return true;
288 }
289 }