class VertexSetCollection
1: //VertexSetCollection.java
3: import java.util.Collection;
4: import java.util.HashMap;
5: import java.util.HashSet;
7: // Stores a collection of vertex sets that collectively store all vertices
8: // in a graph. Each vertex is in only one set in the collection.
9: class VertexSetCollection
10: {
11: private HashMap<Vertex, HashSet<Vertex>> vertexMap;
13: public VertexSetCollection(Collection<Vertex> allVertices)
14: {
15: vertexMap = new HashMap<Vertex, HashSet<Vertex>>();
16: for (Vertex vertex : allVertices)
17: {
18: HashSet<Vertex> vertexSet = new HashSet<Vertex>();
19: vertexSet.add(vertex);
20: vertexMap.put(vertex, vertexSet);
21: }
22: }
24: // Gets the set containing the specified vertex
25: public HashSet<Vertex> getSet(Vertex vertex)
26: {
27: return vertexMap.get(vertex);
28: }
30: // Merges two distinct sets from the collection. Remaps each vertex from
31: // the two sets to the merged set.
32: public void merge
33: (
34: HashSet<Vertex> vertexSet1,
35: HashSet<Vertex> vertexSet2
36: )
37: {
38: // First create the union
39: HashSet<Vertex> merged = new HashSet<Vertex>(vertexSet1);
40: merged.addAll(vertexSet2);
42: // Now remap all vertices in the merged set
43: for (Vertex vertex : merged)
44: {
45: vertexMap.put(vertex, merged);
46: }
47: }
48: }