third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/VertexPartitionCollapser.java

   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.transformation;
  11
  12 import java.util.Collection;
  13 import java.util.HashMap;
  14 import java.util.HashSet;
  15 import java.util.Map;
  16 import java.util.Set;
  17
  18 import org.apache.commons.collections15.Factory;
  19 import org.apache.commons.collections15.Transformer;
  20 import org.apache.commons.collections15.functors.MapTransformer;
  21
  22 import edu.uci.ics.jung.algorithms.blockmodel.VertexPartition;
  23 import edu.uci.ics.jung.graph.Graph;
  24
  25 /**
  26  * This class transforms a graph with a known vertex partitioning into a graph whose
  27  * vertices correspond to the input graph's partitions.  Two vertices in the output graph
  28  * are connected if and only if there exists at least one edge between vertices in the
  29  * corresponding partitions of the input graph.  If the output graph permits parallel edges,
  30  * there will be an edge connecting two vertices in the new graph for each such
  31  * edge connecting constituent vertices in the input graph.
  32  *
  33  * <p>Concept based on Danyel Fisher's <code>GraphCollapser</code> in JUNG 1.x.
  34  *
  35  */
  36 public class VertexPartitionCollapser<V,E,CV,CE>
  37 {
  38     protected Factory<Graph<CV,CE>> graph_factory;
  39     protected Factory<CV> vertex_factory;
  40     protected Factory<CE> edge_factory;
  41     protected Map<Set<V>, CV> set_collapsedv;
  42
  43     /**
  44      * Creates an instance with the specified graph and element factories.
  45      * @param vertex_factory used to construct the vertices of the new graph
  46      * @param edge_factory used to construct the edges of the new graph
  47      * @param graph_factory used to construct the new graph
  48      */
  49     public VertexPartitionCollapser(Factory<Graph<CV,CE>> graph_factory,
  50             Factory<CV> vertex_factory, Factory<CE> edge_factory)
  51     {
  52         this.graph_factory = graph_factory;
  53         this.vertex_factory = vertex_factory;
  54         this.edge_factory = edge_factory;
  55         this.set_collapsedv = new HashMap<Set<V>, CV>();
  56     }
  57
  58     /**
  59      * Creates a new graph whose vertices correspond to the partitions of the supplied graph.
  60      * @param partitioning
  61      * @return a new graph whose vertices correspond to the partitions of the supplied graph
  62      */
  63     public Graph<CV,CE> collapseVertexPartitions(VertexPartition<V,E> partitioning)
  64     {
  65         Graph<V,E> original = partitioning.getGraph();
  66         Graph<CV, CE> collapsed = graph_factory.create();
  67
  68         // create vertices in new graph corresponding to equivalence sets in the original graph
  69         for (Set<V> set : partitioning.getVertexPartitions())
  70         {
  71             CV cv = vertex_factory.create();
  72             collapsed.addVertex(vertex_factory.create());
  73             set_collapsedv.put(set, cv);
  74         }
  75
  76         // create edges in new graph corresponding to edges in original graph
  77         for (E e : original.getEdges())
  78         {
  79             Collection<V> incident = original.getIncidentVertices(e);
  80             Collection<CV> collapsed_vertices = new HashSet<CV>();
  81             Map<V, Set<V>> vertex_partitions = partitioning.getVertexToPartitionMap();
  82             // collect the collapsed vertices corresponding to the original incident vertices
  83             for (V v : incident)
  84                 collapsed_vertices.add(set_collapsedv.get(vertex_partitions.get(v)));
  85             // if there's only one collapsed vertex, continue (no edges to create)
  86             if (collapsed_vertices.size() > 1)
  87             {
  88                 CE ce = edge_factory.create();
  89                 collapsed.addEdge(ce, collapsed_vertices);
  90             }
  91         }
  92         return collapsed;
  93     }
  94
  95     /**
  96      * Returns a transformer from vertex sets in the original graph to collapsed vertices
  97      * in the transformed graph.
  98      */
  99     public Transformer<Set<V>, CV> getSetToCollapsedVertexTransformer()
 100     {
 101         return MapTransformer.getInstance(set_collapsedv);
 102     }
 103 }