Coverage details for edu.uci.ics.jung.algorithms.blockmodel.GraphCollapser

LineHitsSource
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  
672    protected static GraphCollapser instance = null;
68     
69     public static GraphCollapser getInstance() {
704        if ( instance == null )
711            instance = new GraphCollapser();
724        return instance;
73     }
74     
752    protected GraphCollapser() {
762    }
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) {
842        Graph g = equivalence.getGraph();
85  
86         // first, we copy the original graph
872        Graph copy = (Graph) g.copy();
88  
89         // map FROM set of vertices TO supervertex
902        Map superVertices = new HashMap();
91  
922        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
1102        Set coveredCV = new HashSet();
111  
1122        for (Iterator iter = superVertices.values().iterator();
1135            iter.hasNext();
114             ) {
1153            CollapsedVertex cv = (CollapsedVertex) iter.next();
116  
117             // collect all edges and vertices connected to this SuperVertex
1183            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
1223            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  
1373            createEdgesCorrespondingToMap(
138                 copy,
139                 cv,
140                 vertices_to_edges,
141                 coveredCV);
142  
1433            coveredCV.add(cv);
144  
145         }
146  
1472        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) {
1583        for (Iterator iter = vertices_to_edges.keySet().iterator();
1598            iter.hasNext();
160             ) {
161  
1625            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
1675            if (coveredCV.contains(edgeDestination))
1681                continue;
169  
1704            Set relevantEdges =
171                 new HashSet(
172                     (Collection) vertices_to_edges.get(edgeDestination));
173  
1744            edgeDestination =
175                 (Vertex) edgeDestination.getEqualVertex(copy);
176  
1774            if (shouldAddEdge(edgeDestination,
178                 cv.getRootSet(),
179                 relevantEdges)) {
180  
1814                if (PredicateUtils.enforcesEdgeConstraint(copy, Graph.DIRECTED_EDGE))
1822                    createDirectedEdges(copy, cv, edgeDestination, relevantEdges);
1832                else if (PredicateUtils.enforcesEdgeConstraint(copy, Graph.UNDIRECTED_EDGE))
1842                    createUndirectedEdge(copy, cv, edgeDestination, relevantEdges);
185                 else
1860                    throw new IllegalArgumentException("Mixed (directed/undirected) " +
187                         "graphs not currently supported");
188             }
189         }
190  
1913    }
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  
2053        Set vertices = new HashSet(vertices_to_edges.keySet());
206         // some of these vertices may be parts of one or another root set
2073        for (Iterator destinations = vertices.iterator();
20810            destinations.hasNext();
209             ) {
2107            Vertex dest = (Vertex) destinations.next();
2117            Set destSet = er.getEquivalenceRelationContaining(dest);
2127            if (destSet != null) {
2134                CollapsedVertex superV =
214                     (CollapsedVertex) superVertices.get(destSet);
2154                replaceWith(vertices_to_edges, dest, superV);
216             }
217         }
2183    }
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) {
2274        Collection c = (Collection) m.get(dest);
2284        for (Iterator iter = c.iterator(); iter.hasNext();) {
2298            m.put(superV, iter.next());
230         }
2314        m.remove(dest);
2324    }
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
2452        for (Iterator iter = er.getAllEquivalences(); iter.hasNext();) {
2463            Set rootSet = (Set) iter.next();
2473            CollapsedVertex superVertex = createCollapsedVertex(copy, rootSet);
2483            for (Iterator iter2 = rootSet.iterator(); iter2.hasNext();) {
2498                Vertex v = (Vertex) iter2.next();
2508                copy.removeVertex((Vertex) v.getEqualVertex(copy));
251             }
2523            annotateVertex(superVertex, rootSet);
2533            superVertices.put(rootSet, superVertex);
254         }
2552    }
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
2683        Graph copy = (Graph) g.copy();
269  
270         // and remove our set to merge
2713        for (Iterator iter = rootSet.iterator(); iter.hasNext();) {
2723            Vertex v = (Vertex) iter.next();
2733            copy.removeVertex((Vertex) v.getEqualVertex(copy));
274         }
275  
276         // and create one new vertex
2773        CollapsedVertex superVertex = createCollapsedVertex(copy, rootSet);
2783        annotateVertex(superVertex, rootSet);
279  
2803        MultiMap vertices_to_edges =
281             findEdgesAndVerticesConnectedToRootSet(superVertex.getRootSet());
282  
2833        for (Iterator iter = vertices_to_edges.keySet().iterator();
2847            iter.hasNext();
285             ) {
2864            Vertex opposite = (Vertex) iter.next();
2874            opposite = (Vertex) opposite.getEqualVertex(copy);
2884            Set relevantEdges =
289                 new HashSet((Collection) vertices_to_edges.get(opposite));
290  
2914            if (shouldAddEdge(opposite,
292                 superVertex.getRootSet(),
293                 relevantEdges)) {
294  
2954                if (PredicateUtils.enforcesEdgeConstraint(g, Graph.DIRECTED_EDGE)) {
2964                    createDirectedEdges(
297                         copy,
298                         superVertex,
299                         opposite,
300                         relevantEdges);
3010                } else if (PredicateUtils.enforcesEdgeConstraint(g, Graph.UNDIRECTED_EDGE)){
3020                    createUndirectedEdge(
303                         copy,
304                         superVertex,
305                         opposite,
306                         relevantEdges);
307                 }
308                 else
3090                    throw new IllegalArgumentException("Mixed (directed/undirected" +
310                         " graphs not currently supported");
311             }
312         }
313  
3143        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) {
3246    }
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) {
3358    }
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) {
3475        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) {
3640        CollapsedEdge newEdge =
365             (CollapsedEdge) g.addEdge(
366                 new UndirectedCollapsedEdge(
367                     opposite,
368                     superVertex,
369                     relevantEdges));
3700            annotateEdge(newEdge, relevantEdges);
3710    }
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
3946        Set oppositeToSup = new HashSet(), supToOpposite = new HashSet();
395         // from here to there, from there to here, funny things are everyhere! -- Seuss
396  
3976        for (Iterator iterator = relevantEdges.iterator();
39818            iterator.hasNext();
399             ) {
40012            DirectedEdge de = (DirectedEdge) iterator.next();
40112            if (superVertex.getRootSet().contains( de.getSource() )) {
40212                supToOpposite.add(de);
403             } else {
4040                oppositeToSup.add(de);
405             }
406         }
407  
408  
409         // is there an edge from HERE to THERE?
4106        if (oppositeToSup.size() > 0) {
4110            CollapsedEdge newEdge =
412                 (CollapsedEdge) graph.addEdge(
413                     new DirectedCollapsedEdge(
414                         opposite,
415                         superVertex,
416                         oppositeToSup));
4170            annotateEdge(newEdge, oppositeToSup);
418 // System.out.println(" [1]" + newEdge);
419         }
420         // is there an edge from THERE to HERE?
4216        if (supToOpposite.size() > 0) {
4226            CollapsedEdge newEdge =
423                 (CollapsedEdge) graph.addEdge(
424                     new DirectedCollapsedEdge(
425                         superVertex,
426                         opposite,
427                         supToOpposite));
4286            annotateEdge(newEdge, supToOpposite);
429 // System.out.println(" [2]" + newEdge);
430         }
4316    }
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
4436        MultiMap vertices_to_edges = new MultiHashMap();
444  
4456        for (Iterator iter = rootSet.iterator(); iter.hasNext();) {
44611            Vertex v = (Vertex) iter.next();
44711            for (Iterator iterator = v.getIncidentEdges().iterator();
44835                iterator.hasNext();
449                 ) {
45024                Edge e = (Edge) iterator.next();
45124                Vertex other = e.getOpposite(v);
45224                if (rootSet.contains(other))
4530                    continue;
45424                vertices_to_edges.put(other, e);
455             }
456         }
4576        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) {
4808        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.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.