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 | package edu.uci.ics.jung.algorithms.blockmodel; | |
11 | ||
12 | import java.util.Collection; | |
13 | import java.util.HashMap; | |
14 | import java.util.HashSet; | |
15 | import java.util.Iterator; | |
16 | import java.util.Map; | |
17 | import java.util.Set; | |
18 | ||
19 | import org.apache.commons.collections.MultiHashMap; | |
20 | import org.apache.commons.collections.MultiMap; | |
21 | ||
22 | import edu.uci.ics.jung.graph.DirectedEdge; | |
23 | import edu.uci.ics.jung.graph.Edge; | |
24 | import edu.uci.ics.jung.graph.Graph; | |
25 | import edu.uci.ics.jung.graph.Vertex; | |
26 | import edu.uci.ics.jung.graph.impl.DirectedSparseEdge; | |
27 | import edu.uci.ics.jung.graph.impl.SparseVertex; | |
28 | import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge; | |
29 | import edu.uci.ics.jung.utils.PredicateUtils; | |
30 | ||
31 | /** | |
32 | * This is a skeleton class for collapsing graphs. In particular, it takes in a Graph g | |
33 | * and a set of vertices to be collapsed into one, "rootset". It then returns a variant of | |
34 | * the graph in which the root set has been merged into one vertex (of class | |
35 | * CollapsedVertex). The user has the opportunity to override a number of these functions | |
36 | * (thus, the need for instantiation only exists for overriding). | |
37 | * | |
38 | * There are several issues to be resolved: | |
39 | * <ul> | |
40 | * <li>What sort of Collapsed vertex should be created? | |
41 | * <code>getCollapsedVertex(Set vertices)</code></li> | |
42 | * <li>What userdata goes on the collapsed vertex? | |
43 | * <code>annotateVertex(Vertex collapsedVertex, Set original vertices)</code></li> | |
44 | * <li>Should an edge be connected to a given vertex, given a set of vertices? | |
45 | * <code> protected boolean shouldAddEdge( | |
46 | * Vertex opposite, | |
47 | * Set rootSet, | |
48 | * Collection edges) </code></li> | |
49 | * <li>How do I add, or annotate, an edge from the super vertex to a given vertex? | |
50 | * <code> public void addDirectedEdges( | |
51 | Graph graph, | |
52 | Vertex superVertex, | |
53 | Vertex opposite, | |
54 | Set relevantEdges) | |
55 | protected void addUndirectedEdge(Vertex opposite, Vertex superVertex, Set relevantEdges) { | |
56 | protected boolean shouldAddEdge( | |
57 | Vertex opposite, | |
58 | Set rootSet, | |
59 | Collection edges) { | |
60 | * </code></li> | |
61 | * </ul> | |
62 | * | |
63 | * @author Danyel Fisher | |
64 | */ | |
65 | public class GraphCollapser { | |
66 | ||
67 | 2 | protected static GraphCollapser instance = null; |
68 | ||
69 | public static GraphCollapser getInstance() { | |
70 | 4 | if ( instance == null ) |
71 | 1 | instance = new GraphCollapser(); |
72 | 4 | return instance; |
73 | } | |
74 | ||
75 | 2 | protected GraphCollapser() { |
76 | 2 | } |
77 | ||
78 | /** | |
79 | * This version collects sets of vertices in an equivalence relation into a single CollapsedVertex. | |
80 | * @param equivalence A properly-defined EquivalenceRelation representing DISJOINT sets of vertices from the Graph. | |
81 | * @return a copy of the original graph where vertices are replaced by their collapsed equivalents | |
82 | */ | |
83 | public Graph getCollapsedGraph(EquivalenceRelation equivalence) { | |
84 | 2 | Graph g = equivalence.getGraph(); |
85 | ||
86 | // first, we copy the original graph | |
87 | 2 | Graph copy = (Graph) g.copy(); |
88 | ||
89 | // map FROM set of vertices TO supervertex | |
90 | 2 | Map superVertices = new HashMap(); |
91 | ||
92 | 2 | replaceEquivalencesWithCollapsedVertices( |
93 | equivalence, | |
94 | copy, | |
95 | superVertices); | |
96 | ||
97 | // copy currently has NONE of the edges (ooh!) running from | |
98 | // ANY of the root sets to any other | |
99 | ||
100 | // need to characterise all edges as: | |
101 | // A) from outside to outside | |
102 | // -- already set | |
103 | // B) from CollapsdVertex to CollapsedVertex | |
104 | // -- may summarize several edges into one | |
105 | // C) from CollapsedVertex to outside | |
106 | // -- may summarize several edges into one | |
107 | // we've already taken care of (B); this takes care of (C) | |
108 | ||
109 | // so let's go through each CollapsedVertex and classify each by the next | |
110 | 2 | Set coveredCV = new HashSet(); |
111 | ||
112 | 2 | for (Iterator iter = superVertices.values().iterator(); |
113 | 5 | iter.hasNext(); |
114 | ) { | |
115 | 3 | CollapsedVertex cv = (CollapsedVertex) iter.next(); |
116 | ||
117 | // collect all edges and vertices connected to this SuperVertex | |
118 | 3 | MultiMap vertices_to_edges = |
119 | findEdgesAndVerticesConnectedToRootSet(cv.getRootSet()); | |
120 | ||
121 | // ok, at this point we've got a map from all adjacent vertices to edges | |
122 | 3 | collapseVerticesIntoSuperVertices( |
123 | equivalence, | |
124 | superVertices, | |
125 | vertices_to_edges); | |
126 | ||
127 | // for (Iterator iterator = vertices_to_edges.keySet().iterator(); | |
128 | // iterator.hasNext(); | |
129 | // ) { | |
130 | // Vertex v = (Vertex) iterator.next(); | |
131 | // if (equivalence.getEquivalenceRelationContaining(v) != null) { | |
132 | // System.out.println("Panic " + v); | |
133 | // throw new FatalException("Damn."); | |
134 | // } | |
135 | // } | |
136 | ||
137 | 3 | createEdgesCorrespondingToMap( |
138 | copy, | |
139 | cv, | |
140 | vertices_to_edges, | |
141 | coveredCV); | |
142 | ||
143 | 3 | coveredCV.add(cv); |
144 | ||
145 | } | |
146 | ||
147 | 2 | return copy; |
148 | } | |
149 | ||
150 | /** | |
151 | * INTERNAL METHOD | |
152 | */ | |
153 | protected void createEdgesCorrespondingToMap( | |
154 | Graph copy, | |
155 | CollapsedVertex cv, | |
156 | MultiMap vertices_to_edges, | |
157 | Set coveredCV) { | |
158 | 3 | for (Iterator iter = vertices_to_edges.keySet().iterator(); |
159 | 8 | iter.hasNext(); |
160 | ) { | |
161 | ||
162 | 5 | Vertex edgeDestination = (Vertex) iter.next(); |
163 | ||
164 | // this line does nothing for CVs, but is useful for other vertices | |
165 | // opposite is either a CollapsedVertex, or it's a copy of the origial | |
166 | // if we've already seen it, we should skip it; we've already done those edges | |
167 | 5 | if (coveredCV.contains(edgeDestination)) |
168 | 1 | continue; |
169 | ||
170 | 4 | Set relevantEdges = |
171 | new HashSet( | |
172 | (Collection) vertices_to_edges.get(edgeDestination)); | |
173 | ||
174 | 4 | edgeDestination = |
175 | (Vertex) edgeDestination.getEqualVertex(copy); | |
176 | ||
177 | 4 | if (shouldAddEdge(edgeDestination, |
178 | cv.getRootSet(), | |
179 | relevantEdges)) { | |
180 | ||
181 | 4 | if (PredicateUtils.enforcesEdgeConstraint(copy, Graph.DIRECTED_EDGE)) |
182 | 2 | createDirectedEdges(copy, cv, edgeDestination, relevantEdges); |
183 | 2 | else if (PredicateUtils.enforcesEdgeConstraint(copy, Graph.UNDIRECTED_EDGE)) |
184 | 2 | createUndirectedEdge(copy, cv, edgeDestination, relevantEdges); |
185 | else | |
186 | 0 | throw new IllegalArgumentException("Mixed (directed/undirected) " + |
187 | "graphs not currently supported"); | |
188 | } | |
189 | } | |
190 | ||
191 | 3 | } |
192 | ||
193 | /** | |
194 | * Internal method for collapsing a set of vertexes. | |
195 | * | |
196 | * @param er | |
197 | * @param superVertices | |
198 | * @param vertices_to_edges | |
199 | */ | |
200 | protected void collapseVerticesIntoSuperVertices( | |
201 | EquivalenceRelation er, | |
202 | Map superVertices, | |
203 | MultiMap vertices_to_edges) { | |
204 | ||
205 | 3 | Set vertices = new HashSet(vertices_to_edges.keySet()); |
206 | // some of these vertices may be parts of one or another root set | |
207 | 3 | for (Iterator destinations = vertices.iterator(); |
208 | 10 | destinations.hasNext(); |
209 | ) { | |
210 | 7 | Vertex dest = (Vertex) destinations.next(); |
211 | 7 | Set destSet = er.getEquivalenceRelationContaining(dest); |
212 | 7 | if (destSet != null) { |
213 | 4 | CollapsedVertex superV = |
214 | (CollapsedVertex) superVertices.get(destSet); | |
215 | 4 | replaceWith(vertices_to_edges, dest, superV); |
216 | } | |
217 | } | |
218 | 3 | } |
219 | ||
220 | /** | |
221 | * INTERNAL (undocumented) method | |
222 | * @param m | |
223 | * @param dest | |
224 | * @param superV | |
225 | */ | |
226 | protected void replaceWith(MultiMap m, Vertex dest, CollapsedVertex superV) { | |
227 | 4 | Collection c = (Collection) m.get(dest); |
228 | 4 | for (Iterator iter = c.iterator(); iter.hasNext();) { |
229 | 8 | m.put(superV, iter.next()); |
230 | } | |
231 | 4 | m.remove(dest); |
232 | 4 | } |
233 | ||
234 | /** | |
235 | * INTERNAL (undocumented) method. | |
236 | * @param er | |
237 | * @param copy | |
238 | * @param superVertices | |
239 | */ | |
240 | protected void replaceEquivalencesWithCollapsedVertices( | |
241 | EquivalenceRelation er, | |
242 | Graph copy, | |
243 | Map superVertices) { | |
244 | // and remove our set to merge | |
245 | 2 | for (Iterator iter = er.getAllEquivalences(); iter.hasNext();) { |
246 | 3 | Set rootSet = (Set) iter.next(); |
247 | 3 | CollapsedVertex superVertex = createCollapsedVertex(copy, rootSet); |
248 | 3 | for (Iterator iter2 = rootSet.iterator(); iter2.hasNext();) { |
249 | 8 | Vertex v = (Vertex) iter2.next(); |
250 | 8 | copy.removeVertex((Vertex) v.getEqualVertex(copy)); |
251 | } | |
252 | 3 | annotateVertex(superVertex, rootSet); |
253 | 3 | superVertices.put(rootSet, superVertex); |
254 | } | |
255 | 2 | } |
256 | ||
257 | /** | |
258 | * This function collapses a series of vertices in one | |
259 | * EquivalenceSet into one | |
260 | * CollapsedVertex. | |
261 | * @param g A graph to collapse vertices from | |
262 | * @param rootSet A set of vertice to collapse into one CollapsedVertex | |
263 | * @return A graph with rootset.size()-1 fewer vertices. | |
264 | */ | |
265 | public Graph getCollapsedGraph(Graph g, Set rootSet) { | |
266 | ||
267 | // first, we copy the original graph | |
268 | 3 | Graph copy = (Graph) g.copy(); |
269 | ||
270 | // and remove our set to merge | |
271 | 3 | for (Iterator iter = rootSet.iterator(); iter.hasNext();) { |
272 | 3 | Vertex v = (Vertex) iter.next(); |
273 | 3 | copy.removeVertex((Vertex) v.getEqualVertex(copy)); |
274 | } | |
275 | ||
276 | // and create one new vertex | |
277 | 3 | CollapsedVertex superVertex = createCollapsedVertex(copy, rootSet); |
278 | 3 | annotateVertex(superVertex, rootSet); |
279 | ||
280 | 3 | MultiMap vertices_to_edges = |
281 | findEdgesAndVerticesConnectedToRootSet(superVertex.getRootSet()); | |
282 | ||
283 | 3 | for (Iterator iter = vertices_to_edges.keySet().iterator(); |
284 | 7 | iter.hasNext(); |
285 | ) { | |
286 | 4 | Vertex opposite = (Vertex) iter.next(); |
287 | 4 | opposite = (Vertex) opposite.getEqualVertex(copy); |
288 | 4 | Set relevantEdges = |
289 | new HashSet((Collection) vertices_to_edges.get(opposite)); | |
290 | ||
291 | 4 | if (shouldAddEdge(opposite, |
292 | superVertex.getRootSet(), | |
293 | relevantEdges)) { | |
294 | ||
295 | 4 | if (PredicateUtils.enforcesEdgeConstraint(g, Graph.DIRECTED_EDGE)) { |
296 | 4 | createDirectedEdges( |
297 | copy, | |
298 | superVertex, | |
299 | opposite, | |
300 | relevantEdges); | |
301 | 0 | } else if (PredicateUtils.enforcesEdgeConstraint(g, Graph.UNDIRECTED_EDGE)){ |
302 | 0 | createUndirectedEdge( |
303 | copy, | |
304 | superVertex, | |
305 | opposite, | |
306 | relevantEdges); | |
307 | } | |
308 | else | |
309 | 0 | throw new IllegalArgumentException("Mixed (directed/undirected" + |
310 | " graphs not currently supported"); | |
311 | } | |
312 | } | |
313 | ||
314 | 3 | return copy; |
315 | } | |
316 | ||
317 | /** | |
318 | * Overridable method annotates the new collapsed vertex with userdata | |
319 | * from the rootset. By default, does nothing. | |
320 | * @param superVertex a new CollapsedVertex | |
321 | * @param rootSet a set of Vertexes from the old graph. | |
322 | */ | |
323 | protected void annotateVertex(CollapsedVertex superVertex, Set rootSet) { | |
324 | 6 | } |
325 | ||
326 | /** | |
327 | * Overridable method annotates the new collapsed edge with userdata | |
328 | * from the original set. By default, does nothing. | |
329 | * @param newEdge a new CollapsedEdge | |
330 | * @param edgesFromWhichWeMightDeriveData | |
331 | */ | |
332 | protected void annotateEdge( | |
333 | CollapsedEdge newEdge, | |
334 | Collection edgesFromWhichWeMightDeriveData) { | |
335 | 8 | } |
336 | ||
337 | ||
338 | /** | |
339 | * Overridable method to create a single vertex representing a set of vertices in the | |
340 | * graph. | |
341 | * @param g The input graph | |
342 | * @param rootSet The set of vertices which should be represented by the | |
343 | * new vertex. | |
344 | * @return a new CollapsedVertex | |
345 | */ | |
346 | protected CollapsedVertex createCollapsedVertex(Graph g, Set rootSet) { | |
347 | 5 | return (CollapsedVertex) g.addVertex(new CollapsedSparseVertex(rootSet)); |
348 | } | |
349 | ||
350 | /** | |
351 | * Overridable method to create a single undirected edge that represents the data in its parameters. | |
352 | * Should call annotateEdge with the new edge. | |
353 | * @param g The graph in which this edge should be added | |
354 | * @param opposite The vertex at the far end of this edge | |
355 | * @param superVertex The vertex at the near end of this edge. (For an undirecte | |
356 | * graph, it doesn't really matter). | |
357 | * @param relevantEdges The set of edges that this edge is meant to represent. | |
358 | */ | |
359 | protected void createUndirectedEdge( | |
360 | Graph g, | |
361 | CollapsedVertex superVertex, | |
362 | Vertex opposite, | |
363 | Set relevantEdges) { | |
364 | 0 | CollapsedEdge newEdge = |
365 | (CollapsedEdge) g.addEdge( | |
366 | new UndirectedCollapsedEdge( | |
367 | opposite, | |
368 | superVertex, | |
369 | relevantEdges)); | |
370 | 0 | annotateEdge(newEdge, relevantEdges); |
371 | 0 | } |
372 | ||
373 | /** | |
374 | * Overridable method to create a up to two directed edges that represents the data in its parameters. | |
375 | * This method, by default, creates one edge in each direction that there is an edge in | |
376 | * relevantEdges. | |
377 | * Should call annotateEdge with the new edge. | |
378 | * @param g The graph in which this edge should be added | |
379 | * @param opposite The vertex at the far end of this edge | |
380 | * @param superVertex The vertex at the near end of this edge. (For an undirecte | |
381 | * graph, it doesn't really matter). | |
382 | * @param relevantEdges The set of edges that this edge is meant to represent. | |
383 | */ | |
384 | protected void createDirectedEdges( | |
385 | Graph graph, | |
386 | CollapsedVertex superVertex, | |
387 | Vertex opposite, | |
388 | Set relevantEdges) { | |
389 | ||
390 | // System.out.println("Creating " + superVertex + " " + opposite ); | |
391 | // System.out.println( relevantEdges ); | |
392 | ||
393 | // sort edges by directionality | |
394 | 6 | Set oppositeToSup = new HashSet(), supToOpposite = new HashSet(); |
395 | // from here to there, from there to here, funny things are everyhere! -- Seuss | |
396 | ||
397 | 6 | for (Iterator iterator = relevantEdges.iterator(); |
398 | 18 | iterator.hasNext(); |
399 | ) { | |
400 | 12 | DirectedEdge de = (DirectedEdge) iterator.next(); |
401 | 12 | if (superVertex.getRootSet().contains( de.getSource() )) { |
402 | 12 | supToOpposite.add(de); |
403 | } else { | |
404 | 0 | oppositeToSup.add(de); |
405 | } | |
406 | } | |
407 | ||
408 | ||
409 | // is there an edge from HERE to THERE? | |
410 | 6 | if (oppositeToSup.size() > 0) { |
411 | 0 | CollapsedEdge newEdge = |
412 | (CollapsedEdge) graph.addEdge( | |
413 | new DirectedCollapsedEdge( | |
414 | opposite, | |
415 | superVertex, | |
416 | oppositeToSup)); | |
417 | 0 | annotateEdge(newEdge, oppositeToSup); |
418 | // System.out.println(" [1]" + newEdge); | |
419 | } | |
420 | // is there an edge from THERE to HERE? | |
421 | 6 | if (supToOpposite.size() > 0) { |
422 | 6 | CollapsedEdge newEdge = |
423 | (CollapsedEdge) graph.addEdge( | |
424 | new DirectedCollapsedEdge( | |
425 | superVertex, | |
426 | opposite, | |
427 | supToOpposite)); | |
428 | 6 | annotateEdge(newEdge, supToOpposite); |
429 | // System.out.println(" [2]" + newEdge); | |
430 | } | |
431 | 6 | } |
432 | ||
433 | /** | |
434 | * INTERNAL METHOD. | |
435 | * For a set of vertices, finds all the edges connected to them, indexed (in a MultiMap) | |
436 | * to the vertices to which they connect. Thus, in the graph with edges (A-C, A-D, B-C), | |
437 | * with input (A, B), the result will be ( C {A-C, B-C}; D {A-D} ) | |
438 | * @param rootSet | |
439 | * @return | |
440 | */ | |
441 | protected MultiMap findEdgesAndVerticesConnectedToRootSet(Set rootSet) { | |
442 | // now, let's get a candidate set of edges | |
443 | 6 | MultiMap vertices_to_edges = new MultiHashMap(); |
444 | ||
445 | 6 | for (Iterator iter = rootSet.iterator(); iter.hasNext();) { |
446 | 11 | Vertex v = (Vertex) iter.next(); |
447 | 11 | for (Iterator iterator = v.getIncidentEdges().iterator(); |
448 | 35 | iterator.hasNext(); |
449 | ) { | |
450 | 24 | Edge e = (Edge) iterator.next(); |
451 | 24 | Vertex other = e.getOpposite(v); |
452 | 24 | if (rootSet.contains(other)) |
453 | 0 | continue; |
454 | 24 | vertices_to_edges.put(other, e); |
455 | } | |
456 | } | |
457 | 6 | return vertices_to_edges; |
458 | } | |
459 | ||
460 | ||
461 | /** | |
462 | * Overridable method checks whether an edge representing | |
463 | * the given set of edges should be created. The edge will | |
464 | * run from a new CollapsedVertex representing the rootSet | |
465 | * to opposite; it will replace all the edges in the collection | |
466 | * edges. By default, this method returns true. | |
467 | * @param opposite | |
468 | * @param rootSet a set of vertices that currently are one end | |
469 | * of these edges. | |
470 | * @param edges a non-empty collection of edges that may be | |
471 | * replaced | |
472 | * @return a boolean value. If true, the system will replace | |
473 | * these edges with one new collapsededge; if false, the system | |
474 | * will remove all these edges from the graph. | |
475 | */ | |
476 | protected boolean shouldAddEdge( | |
477 | Vertex opposite, | |
478 | Set rootSet, | |
479 | Collection edges) { | |
480 | 8 | return true; |
481 | } | |
482 | ||
483 | /** | |
484 | * This interface represents a vertex that holds a set of objects in some other graph. | |
485 | */ | |
486 | public interface CollapsedVertex extends Vertex { | |
487 | public Set getRootSet(); | |
488 | } | |
489 | ||
490 | /** | |
491 | * A CollapsedSparseVertex extends CollapsedVertex. | |
492 | */ | |
493 | public static class CollapsedSparseVertex extends SparseVertex implements CollapsedVertex { | |
494 | ||
495 | private Set rootSet; | |
496 | ||
497 | /** | |
498 | * @param rootSet | |
499 | */ | |
500 | public CollapsedSparseVertex (Set rootSet) { | |
501 | this.rootSet = rootSet; | |
502 | } | |
503 | ||
504 | public String toString() { | |
505 | return super.toString() + ":" + rootSet; | |
506 | } | |
507 | ||
508 | public Set getRootSet() { | |
509 | return rootSet; | |
510 | } | |
511 | ||
512 | } | |
513 | ||
514 | /** | |
515 | * The CollapsedEdge interface represents a set of edges | |
516 | * in some other graph. | |
517 | */ | |
518 | public interface CollapsedEdge extends Edge { | |
519 | public Set getRelevantEdges(); | |
520 | } | |
521 | ||
522 | /** | |
523 | * This class represents a Collapsed Undirected edge, | |
524 | * and extends UndirectedSparseEdge. | |
525 | */ | |
526 | public static class UndirectedCollapsedEdge | |
527 | extends UndirectedSparseEdge | |
528 | implements CollapsedEdge { | |
529 | ||
530 | private Set relevantEdges; | |
531 | ||
532 | public UndirectedCollapsedEdge( | |
533 | Vertex opposite, | |
534 | Vertex superVertex, | |
535 | Set relevantEdges) { | |
536 | super(opposite, superVertex); | |
537 | this.relevantEdges = relevantEdges; | |
538 | } | |
539 | ||
540 | public Set getRelevantEdges() { | |
541 | return relevantEdges; | |
542 | } | |
543 | ||
544 | } | |
545 | ||
546 | /** | |
547 | * This class represents a Collapsed Directed edge, | |
548 | * and extends DirectedSparseEdge. | |
549 | */ | |
550 | public static class DirectedCollapsedEdge | |
551 | extends DirectedSparseEdge | |
552 | implements CollapsedEdge { | |
553 | private Set relevantEdges; | |
554 | ||
555 | public DirectedCollapsedEdge( | |
556 | Vertex opposite, | |
557 | Vertex superVertex, | |
558 | Set relevantEdges) { | |
559 | super(opposite, superVertex); | |
560 | this.relevantEdges = relevantEdges; | |
561 | } | |
562 | ||
563 | public Set getRelevantEdges() { | |
564 | return relevantEdges; | |
565 | } | |
566 | ||
567 | } | |
568 | ||
569 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |