third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/VertexPartition.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 /*
  11  * Created on Feb 3, 2004
  12  */
  13 package edu.uci.ics.jung.algorithms.blockmodel;
  14
  15 import java.util.*;
  16
  17 import edu.uci.ics.jung.graph.Graph;
  18
  19
  20 /**
  21  * Maintains information about a vertex partition of a graph.
  22  * This can be built from a map from vertices to vertex sets
  23  * or from a collection of (disjoint) vertex sets,
  24  * such as those created by various clustering methods.
  25  */
  26 public class VertexPartition<V,E>
  27 {
  28         private Map<V,Set<V>> vertex_partition_map;
  29         private Collection<Set<V>> vertex_sets;
  30         private Graph<V,E> graph;
  31
  32         /**
  33          * Creates an instance based on the specified graph and mapping from vertices
  34          * to vertex sets, and generates a set of partitions based on this mapping.
  35          * @param g the graph over which the vertex partition is defined
  36          * @param partition_map the mapping from vertices to vertex sets (partitions)
  37          */
  38         public VertexPartition(Graph<V,E> g, Map<V, Set<V>> partition_map)
  39         {
  40                 this.vertex_partition_map = Collections.unmodifiableMap(partition_map);
  41                 this.graph = g;
  42         }
  43
  44         /**
  45      * Creates an instance based on the specified graph, vertex-set mapping,
  46      * and set of disjoint vertex sets.  The vertex-set mapping and vertex
  47      * partitions must be consistent; that is, the mapping must reflect the
  48      * division of vertices into partitions, and each vertex must appear in
  49      * exactly one partition.
  50      * @param g the graph over which the vertex partition is defined
  51      * @param partition_map the mapping from vertices to vertex sets (partitions)
  52          * @param vertex_sets the set of disjoint vertex sets
  53          */
  54     public VertexPartition(Graph<V,E> g, Map<V, Set<V>> partition_map,
  55                 Collection<Set<V>> vertex_sets)
  56     {
  57         this.vertex_partition_map = Collections.unmodifiableMap(partition_map);
  58         this.vertex_sets = vertex_sets;
  59         this.graph = g;
  60     }
  61
  62     /**
  63      * Creates an instance based on the specified graph and set of disjoint vertex sets,
  64      * and generates a vertex-to-partition map based on these sets.
  65      * @param g the graph over which the vertex partition is defined
  66      * @param vertex_sets the set of disjoint vertex sets
  67      */
  68     public VertexPartition(Graph<V,E> g, Collection<Set<V>> vertex_sets)
  69     {
  70         this.vertex_sets = vertex_sets;
  71         this.graph = g;
  72     }
  73
  74     /**
  75      * Returns the graph on which the partition is defined.
  76      * @return the graph on which the partition is defined
  77      */
  78         public Graph<V,E> getGraph()
  79         {
  80                 return graph;
  81         }
  82
  83         /**
  84          * Returns a map from each vertex in the input graph to its partition.
  85          * This map is generated if it does not already exist.
  86          * @return a map from each vertex in the input graph to a vertex set
  87          */
  88         public Map<V,Set<V>> getVertexToPartitionMap()
  89         {
  90                 if (vertex_partition_map == null)
  91                 {
  92                 this.vertex_partition_map = new HashMap<V, Set<V>>();
  93                 for (Set<V> set : this.vertex_sets)
  94                     for (V v : set)
  95                         this.vertex_partition_map.put(v, set);
  96                 }
  97                 return vertex_partition_map;
  98         }
  99
 100         /**
 101          * Returns a collection of vertex sets, where each vertex in the
 102          * input graph is in exactly one set.
 103          * This collection is generated based on the vertex-to-partition map
 104          * if it does not already exist.
 105          * @return a collection of vertex sets such that each vertex in the
 106          * instance's graph is in exactly one set
 107          */
 108         public Collection<Set<V>> getVertexPartitions()
 109         {
 110                 if (vertex_sets == null)
 111                 {
 112                         this.vertex_sets = new HashSet<Set<V>>();
 113                         this.vertex_sets.addAll(vertex_partition_map.values());
 114                 }
 115             return vertex_sets;
 116         }
 117
 118         /**
 119          * Returns the number of partitions.
 120          */
 121         public int numPartitions()
 122         {
 123                 return vertex_sets.size();
 124         }
 125
 126         @Override
 127         public String toString()
 128         {
 129                 return "Partitions: " + vertex_partition_map;
 130         }
 131 }