2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
11 * Created on Feb 3, 2004
13 package edu.uci.ics.jung.algorithms.blockmodel;
17 import edu.uci.ics.jung.graph.Graph;
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.
26 public class VertexPartition<V,E>
28 private Map<V,Set<V>> vertex_partition_map;
29 private Collection<Set<V>> vertex_sets;
30 private Graph<V,E> graph;
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)
38 public VertexPartition(Graph<V,E> g, Map<V, Set<V>> partition_map)
40 this.vertex_partition_map = Collections.unmodifiableMap(partition_map);
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
54 public VertexPartition(Graph<V,E> g, Map<V, Set<V>> partition_map,
55 Collection<Set<V>> vertex_sets)
57 this.vertex_partition_map = Collections.unmodifiableMap(partition_map);
58 this.vertex_sets = vertex_sets;
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
68 public VertexPartition(Graph<V,E> g, Collection<Set<V>> vertex_sets)
70 this.vertex_sets = vertex_sets;
75 * Returns the graph on which the partition is defined.
76 * @return the graph on which the partition is defined
78 public Graph<V,E> getGraph()
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
88 public Map<V,Set<V>> getVertexToPartitionMap()
90 if (vertex_partition_map == null)
92 this.vertex_partition_map = new HashMap<V, Set<V>>();
93 for (Set<V> set : this.vertex_sets)
95 this.vertex_partition_map.put(v, set);
97 return vertex_partition_map;
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
108 public Collection<Set<V>> getVertexPartitions()
110 if (vertex_sets == null)
112 this.vertex_sets = new HashSet<Set<V>>();
113 this.vertex_sets.addAll(vertex_partition_map.values());
119 * Returns the number of partitions.
121 public int numPartitions()
123 return vertex_sets.size();
127 public String toString()
129 return "Partitions: " + vertex_partition_map;