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