Line | Hits | Source |
---|---|---|
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 | /* | |
11 | * Created on Dec 11, 2003 | |
12 | */ | |
13 | package edu.uci.ics.jung.graph.impl; | |
14 | ||
15 | import java.util.Collection; | |
16 | import java.util.HashMap; | |
17 | import java.util.HashSet; | |
18 | import java.util.Iterator; | |
19 | import java.util.Map; | |
20 | import java.util.Set; | |
21 | ||
22 | import org.apache.commons.collections.CollectionUtils; | |
23 | import org.apache.commons.collections.Transformer; | |
24 | ||
25 | import edu.uci.ics.jung.graph.ArchetypeEdge; | |
26 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
27 | import edu.uci.ics.jung.graph.ArchetypeVertex; | |
28 | import edu.uci.ics.jung.graph.Hyperedge; | |
29 | import edu.uci.ics.jung.graph.Hypergraph; | |
30 | import edu.uci.ics.jung.graph.Hypervertex; | |
31 | import edu.uci.ics.jung.utils.UserDataContainer; | |
32 | ||
33 | /** | |
34 | * Implements a hypergraph built over an underlying | |
35 | * Bipartite graph, using the equivalence explained in | |
36 | * the FAQ. Fully implements the Hypergraph interface; | |
37 | * its vertices and edges fully implement their interfaces. | |
38 | * | |
39 | * Use and create in the standard way; the underlying graph | |
40 | * is invisible to the user (but can be extracted | |
41 | * with a call to getBipartiteGraphEquivalent() ). | |
42 | * | |
43 | * @author danyelf | |
44 | * @deprecated As of version 1.7, replaced by <code>SetHypergraph</code>. | |
45 | * @see SetHypergraph | |
46 | */ | |
47 | public class HypergraphBPG extends AbstractArchetypeGraph implements Hypergraph { | |
48 | ||
49 | protected BipartiteGraph bpg; | |
50 | ||
51 | 8 | public HypergraphBPG() { |
52 | 8 | initialize(); |
53 | 8 | } |
54 | ||
55 | protected void initialize() | |
56 | { | |
57 | 8 | this.bpg = new BipartiteGraph(); |
58 | 8 | hyperedges = new HashMap(); |
59 | 8 | hypervertices = new HashMap(); |
60 | 8 | vertexToHyperVertex = new XToHyperX(hypervertices); |
61 | 8 | vertexToHyperEdge = new XToHyperX(hyperedges); |
62 | 8 | super.initialize(); |
63 | 8 | } |
64 | ||
65 | /** | |
66 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#newInstance() | |
67 | */ | |
68 | public ArchetypeGraph newInstance() { | |
69 | 1 | return new HypergraphBPG(); |
70 | } | |
71 | ||
72 | 1 | public static final BipartiteGraph.Choice VERTEX = BipartiteGraph.CLASSA; |
73 | 1 | public static final BipartiteGraph.Choice EDGE = BipartiteGraph.CLASSB; |
74 | ||
75 | Map hypervertices, hyperedges; | |
76 | private Transformer vertexToHyperVertex, vertexToHyperEdge; | |
77 | ||
78 | /** | |
79 | * Adds <code>v</code> to this graph. | |
80 | */ | |
81 | public Hypervertex addVertex(Hypervertex v) { | |
82 | 21 | HypervertexBPG hv = (HypervertexBPG) v; |
83 | 21 | this.bpg.addVertex(hv.underlying_vertex(), VERTEX); |
84 | 21 | hypervertices.put(hv.underlying_vertex(), hv); |
85 | 21 | hv.setGraph(this); |
86 | 21 | mGraphListenerHandler.handleAdd(v); |
87 | 21 | return v; |
88 | } | |
89 | ||
90 | /** | |
91 | * Adds a single edge to the graph | |
92 | * | |
93 | * @see edu.uci.ics.jung.graph.Hypergraph#addEdge(edu.uci.ics.jung.graph.Hyperedge) | |
94 | */ | |
95 | public Hyperedge addEdge(Hyperedge e) { | |
96 | 14 | HyperedgeBPG he = (HyperedgeBPG) e; |
97 | 14 | this.bpg.addVertex( he.underlying_vertex(), EDGE ); |
98 | 14 | hyperedges.put( he.underlying_vertex(), he ); |
99 | 14 | he.setGraph( this ); |
100 | 14 | mGraphListenerHandler.handleAdd(e); |
101 | 14 | return e; |
102 | } | |
103 | ||
104 | /** | |
105 | * Returns a set of all the vertices in the graph. | |
106 | * | |
107 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#getVertices() | |
108 | */ | |
109 | public Set getVertices() { | |
110 | 17 | return new HashSet( hypervertices.values()); |
111 | } | |
112 | ||
113 | /** | |
114 | * Returns the set of all edges in the graph. | |
115 | * | |
116 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#getEdges() | |
117 | */ | |
118 | public Set getEdges() { | |
119 | 17 | return new HashSet( hyperedges.values() ); |
120 | } | |
121 | ||
122 | /** | |
123 | * Returns a count of the number of vertices in the graph. | |
124 | * | |
125 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#numVertices() | |
126 | */ | |
127 | public int numVertices() { | |
128 | 0 | return hypervertices.size(); |
129 | } | |
130 | ||
131 | /** | |
132 | * Returns a count of the number of edges in the graph. | |
133 | * | |
134 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#numEdges() | |
135 | */ | |
136 | public int numEdges() { | |
137 | 0 | return hyperedges.size(); |
138 | } | |
139 | ||
140 | public void removeVertex(Hypervertex v) { | |
141 | 0 | HypervertexBPG hv = (HypervertexBPG) v; |
142 | 0 | hypervertices.remove( hv.underlying_vertex() ); |
143 | 0 | bpg.removeVertex( hv.underlying_vertex() ); |
144 | 0 | hv.setGraph(null); |
145 | 0 | mGraphListenerHandler.handleRemove(v); |
146 | 0 | } |
147 | ||
148 | public void removeEdge(Hyperedge e) { | |
149 | 0 | HyperedgeBPG he = (HyperedgeBPG) e; |
150 | 0 | hyperedges.remove( he.underlying_vertex() ); |
151 | 0 | bpg.removeVertex( he.underlying_vertex() ); |
152 | 0 | he.setGraph(null); |
153 | 0 | mGraphListenerHandler.handleRemove(e); |
154 | 0 | } |
155 | ||
156 | public void addVertices(Set vertices) | |
157 | { | |
158 | 0 | for (Iterator iter = vertices.iterator(); iter.hasNext(); ) |
159 | 0 | addVertex((HypervertexBPG)iter.next()); |
160 | 0 | } |
161 | ||
162 | public void addEdges(Set edges) | |
163 | { | |
164 | 0 | for (Iterator iter = edges.iterator(); iter.hasNext(); ) |
165 | 0 | addEdge((HyperedgeBPG)iter.next()); |
166 | 0 | } |
167 | ||
168 | /** | |
169 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeVertices(java.util.Set) | |
170 | */ | |
171 | public void removeVertices(Set vertices) { | |
172 | 0 | for (Iterator iter = vertices.iterator(); iter.hasNext();) { |
173 | 0 | HypervertexBPG v = (HypervertexBPG) iter.next(); |
174 | 0 | removeVertex( v ); |
175 | } | |
176 | 0 | } |
177 | ||
178 | /** | |
179 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeEdges(java.util.Set) | |
180 | */ | |
181 | public void removeEdges(Set edges) { | |
182 | 0 | for (Iterator iter = edges.iterator(); iter.hasNext();) { |
183 | 0 | HyperedgeBPG e = (HyperedgeBPG) iter.next(); |
184 | 0 | removeEdge( e ); |
185 | } | |
186 | 0 | } |
187 | ||
188 | /** | |
189 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeAllEdges() | |
190 | */ | |
191 | public void removeAllEdges() { | |
192 | 0 | removeEdges( new HashSet( hyperedges.values() )); |
193 | 0 | } |
194 | ||
195 | /** | |
196 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#removeAllVertices() | |
197 | */ | |
198 | public void removeAllVertices() { | |
199 | 0 | removeVertices( new HashSet( hypervertices.values()) ); |
200 | 0 | } |
201 | ||
202 | /** | |
203 | * @see edu.uci.ics.jung.graph.ArchetypeGraph#copy() | |
204 | */ | |
205 | public ArchetypeGraph copy() { | |
206 | 1 | HypergraphBPG cln = (HypergraphBPG) this.newInstance(); |
207 | 1 | cln.bpg = (BipartiteGraph) bpg.copy(); |
208 | 1 | cln.updateHyperTable(); |
209 | 1 | return cln; |
210 | } | |
211 | ||
212 | /** | |
213 | * | |
214 | */ | |
215 | private void updateHyperTable() { | |
216 | // creates a HyperEdge and HyperVertex for each Edge and Vertex in the tables | |
217 | 1 | for (Iterator iter = bpg.getAllVertices(VERTEX).iterator(); |
218 | 4 | iter.hasNext(); |
219 | ) { | |
220 | 3 | BipartiteVertex bpv = (BipartiteVertex) iter.next(); |
221 | 3 | hypervertices.put(bpv, new HypervertexBPG(bpv, this)); |
222 | } | |
223 | 1 | for (Iterator iter = bpg.getAllVertices(EDGE).iterator(); |
224 | 3 | iter.hasNext(); |
225 | ) { | |
226 | 2 | BipartiteVertex bpe = (BipartiteVertex) iter.next(); |
227 | 2 | hyperedges.put(bpe, new HyperedgeBPG(bpe, this)); |
228 | } | |
229 | 1 | } |
230 | ||
231 | /** | |
232 | * @see edu.uci.ics.jung.utils.UserDataContainer#addUserDatum(java.lang.Object, java.lang.Object, edu.uci.ics.jung.utils.UserDataContainer.CopyAction) | |
233 | */ | |
234 | public void addUserDatum(Object key, Object datum, CopyAction copyAct) { | |
235 | 0 | bpg.addUserDatum(key, datum, copyAct); |
236 | 0 | } |
237 | ||
238 | /** | |
239 | * @see edu.uci.ics.jung.utils.UserDataContainer#importUserData(edu.uci.ics.jung.utils.UserDataContainer) | |
240 | */ | |
241 | public void importUserData(UserDataContainer udc) { | |
242 | 0 | bpg.importUserData(udc); |
243 | 0 | } |
244 | ||
245 | /** | |
246 | * @see edu.uci.ics.jung.utils.UserDataContainer#getUserDatumKeyIterator() | |
247 | */ | |
248 | public Iterator getUserDatumKeyIterator() { | |
249 | 0 | return bpg.getUserDatumKeyIterator(); |
250 | } | |
251 | ||
252 | /** | |
253 | * @see edu.uci.ics.jung.utils.UserDataContainer#getUserDatumCopyAction(java.lang.Object) | |
254 | */ | |
255 | public CopyAction getUserDatumCopyAction(Object key) { | |
256 | 0 | return bpg.getUserDatumCopyAction(key); |
257 | } | |
258 | ||
259 | /** | |
260 | * @see edu.uci.ics.jung.utils.UserDataContainer#getUserDatum(java.lang.Object) | |
261 | */ | |
262 | public Object getUserDatum(Object key) { | |
263 | 0 | return bpg.getUserDatum(key); |
264 | } | |
265 | ||
266 | /** | |
267 | * @see edu.uci.ics.jung.utils.UserDataContainer#setUserDatum(java.lang.Object, java.lang.Object, edu.uci.ics.jung.utils.UserDataContainer.CopyAction) | |
268 | */ | |
269 | public void setUserDatum(Object key, Object datum, CopyAction copyAct) { | |
270 | 0 | bpg.setUserDatum(key, datum, copyAct); |
271 | ||
272 | 0 | } |
273 | ||
274 | /** | |
275 | * @see edu.uci.ics.jung.utils.UserDataContainer#removeUserDatum(java.lang.Object) | |
276 | */ | |
277 | public Object removeUserDatum(Object key) { | |
278 | 0 | return bpg.removeUserDatum(key); |
279 | } | |
280 | ||
281 | /** | |
282 | * Adds a vertex that is already part of the BPG. Is a part of | |
283 | * the Vertex.copy() system. | |
284 | * @param hv | |
285 | */ | |
286 | void addVertex_without_adding(HypervertexBPG hv) { | |
287 | 0 | hypervertices.put( hv.underlying_vertex(), hv ); |
288 | 0 | hv.setGraph( this ); |
289 | 0 | } |
290 | ||
291 | /** | |
292 | * @param vertex2 | |
293 | * @return the vertex in the hypergraph corresponding to the underlying | |
294 | * bipartite vertex <code>vertex2</code> | |
295 | */ | |
296 | public ArchetypeVertex getVertexCorrespondingTo(BipartiteVertex vertex2) { | |
297 | 3 | return (HypervertexBPG) hypervertices.get(vertex2); |
298 | } | |
299 | ||
300 | /** | |
301 | * @param vertex2 | |
302 | * @return the edge in the hypergraph corresponding to the underlying | |
303 | * bipartite vertex <code>vertex2</code> | |
304 | */ | |
305 | public ArchetypeEdge getEdgeCorrespondingTo(BipartiteVertex vertex2) { | |
306 | 2 | return (HyperedgeBPG) hyperedges.get(vertex2); |
307 | } | |
308 | ||
309 | /** | |
310 | * @param realNeighbors | |
311 | * @return | |
312 | */ | |
313 | Set translateUnderlyingVertices(Set vertices) { | |
314 | 13 | Collection translated = CollectionUtils.collect( vertices, vertexToHyperVertex ); |
315 | 13 | return new HashSet( translated ); |
316 | } | |
317 | ||
318 | /** | |
319 | * @param set | |
320 | * @return | |
321 | */ | |
322 | Set translateUnderlyingEdges(Set vertices) { | |
323 | 6 | Collection translated = CollectionUtils.collect( vertices, vertexToHyperEdge); |
324 | 6 | return new HashSet( translated ); |
325 | } | |
326 | ||
327 | ||
328 | private class XToHyperX implements Transformer { | |
329 | private Map map; | |
330 | XToHyperX( Map m ) { | |
331 | this.map = m; | |
332 | } | |
333 | public Object transform(Object o) { | |
334 | return map.get(o); | |
335 | } | |
336 | } | |
337 | ||
338 | /** | |
339 | * Returns a BipartiteGraph equivalent to this Graph. Each | |
340 | * vertex in the BipartiteGraph will be Equal to a HyperVertex | |
341 | * or a HyperEdge in this graph. | |
342 | * (Note that equals is NOT symmetrical in this case; | |
343 | * <tt>hyperedge.equals( vertex )</tt> | |
344 | * will return true for one of these vertices, but | |
345 | * <tt>vertex.equals( hyperedge )</tt> | |
346 | * will return false. | |
347 | */ | |
348 | public BipartiteGraph getBipartiteGraphEquivalent() { | |
349 | 0 | return (BipartiteGraph) bpg.copy(); |
350 | } | |
351 | ||
352 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |