| 1 | package tuffy.util; |
| 2 | import java.util.*; |
| 3 | |
| 4 | /** |
| 5 | * Union-Find Data structure. |
| 6 | * By calling the makeUnionFind(S) a one element set is made for every object s contained in S |
| 7 | * Objects are stored within Records which are put in trees. A Set can be recognised |
| 8 | * by a toplevel record (with a parent pointing to null) |
| 9 | * |
| 10 | * This not a general "Set handling" class, but made for being used with for example |
| 11 | * Kruskal's Algortihm. |
| 12 | * See http://en.wikipedia.org/wiki/Disjoint-set_data_structure for more info! |
| 13 | * ------------------------------------- |
| 14 | * Implements makeUnionFind(S) in O(n), Union in O(log n), or O(1) if you a record representing a set, |
| 15 | * and find(u) called n times yieald an amortized running time of per calling of O(a(n)) ~= O(1). |
| 16 | * |
| 17 | **/ |
| 18 | |
| 19 | |
| 20 | public class UnionFind<E> { |
| 21 | |
| 22 | /* Record class. Defines a set, or a record within a set */ |
| 23 | @SuppressWarnings("hiding") |
| 24 | public class Record<E> { |
| 25 | private int size; |
| 26 | private double weight; |
| 27 | private E name; |
| 28 | private Record<E> parent = null; |
| 29 | |
| 30 | public Record(E name) { |
| 31 | this.name = name; |
| 32 | size = 1; |
| 33 | weight = 1; |
| 34 | } |
| 35 | |
| 36 | public void setWeight(double wt){ |
| 37 | weight = wt; |
| 38 | } |
| 39 | |
| 40 | public void setParent(Record<E> parent) { |
| 41 | this.parent = parent; |
| 42 | } |
| 43 | public boolean isRoot(){ |
| 44 | return parent == null; |
| 45 | } |
| 46 | public E getName() { |
| 47 | return name; |
| 48 | } |
| 49 | private int getSize() { |
| 50 | return size; |
| 51 | } |
| 52 | |
| 53 | private double getWeight(){ |
| 54 | return weight; |
| 55 | } |
| 56 | |
| 57 | private void absorb(Record<E> sub){ |
| 58 | sub.setParent(this); |
| 59 | size += sub.size; |
| 60 | weight += sub.weight; |
| 61 | nClusters --; |
| 62 | } |
| 63 | |
| 64 | public Record<E> getParent() { |
| 65 | return parent; |
| 66 | } |
| 67 | @SuppressWarnings("unchecked") |
| 68 | public boolean equals(Object obj) { |
| 69 | if(obj == null || getClass() != obj.getClass() ) { |
| 70 | return false; |
| 71 | } |
| 72 | else { |
| 73 | Record<E> o = (Record<E>) obj; |
| 74 | return name.equals(o.getName()); |
| 75 | } |
| 76 | } |
| 77 | } |
| 78 | /* data member - ArrayList containing all the records */ |
| 79 | private ArrayList<Record<E>> records = new ArrayList<Record<E>>(); |
| 80 | private HashMap<E,Record<E>> map = new HashMap<E, Record<E>>(); |
| 81 | |
| 82 | private int nClusters = 0; |
| 83 | |
| 84 | public int getNumClusters(){ |
| 85 | return nClusters; |
| 86 | } |
| 87 | |
| 88 | public HashSet<E> getRoots(){ |
| 89 | HashSet<E> roots = new HashSet<E>(); |
| 90 | for(Record<E> rec : records){ |
| 91 | if(rec.isRoot()){ |
| 92 | roots.add(rec.getName()); |
| 93 | } |
| 94 | } |
| 95 | return roots; |
| 96 | } |
| 97 | |
| 98 | /* Initalizes all sets, one for every element in list set */ |
| 99 | public void makeUnionFind(List<E> Set, HashMap<E,Double> wts) { |
| 100 | for(E it : Set){ |
| 101 | Record<E> rec = new Record<E>(it); |
| 102 | if(wts.containsKey(it)){ |
| 103 | rec.setWeight(wts.get(it)); |
| 104 | } |
| 105 | records.add(rec); |
| 106 | map.put(it, rec); |
| 107 | } |
| 108 | nClusters = map.size(); |
| 109 | } |
| 110 | |
| 111 | public void makeUnionFind(List<E> Set) { |
| 112 | for(E it : Set){ |
| 113 | Record<E> rec = new Record<E>(it); |
| 114 | records.add(rec); |
| 115 | map.put(it, rec); |
| 116 | } |
| 117 | nClusters = map.size(); |
| 118 | } |
| 119 | |
| 120 | |
| 121 | public void addSingleton(E node, Double wts) { |
| 122 | if(map.containsKey(node)){ |
| 123 | return; |
| 124 | } |
| 125 | |
| 126 | Record<E> rec = new Record<E>(node); |
| 127 | rec.setWeight(wts); |
| 128 | records.add(rec); |
| 129 | map.put(node, rec); |
| 130 | } |
| 131 | |
| 132 | public ArrayList<Record<E>> getRecords() { |
| 133 | return records; |
| 134 | } |
| 135 | |
| 136 | |
| 137 | /* "Unionizes two sets */ |
| 138 | public E unionByValue(E xx, E yy) { |
| 139 | Record<E> x = map.get(xx); |
| 140 | Record<E> y = map.get(yy); |
| 141 | Record<E> xroot = find(x); |
| 142 | Record<E> yroot = find(y); |
| 143 | |
| 144 | if(xroot == yroot) return xroot.name; |
| 145 | |
| 146 | if((Integer)xroot.name < (Integer)yroot.name) { |
| 147 | xroot.absorb(yroot); |
| 148 | return xroot.name; |
| 149 | }else { |
| 150 | yroot.absorb(xroot); |
| 151 | return yroot.name; |
| 152 | } |
| 153 | } |
| 154 | |
| 155 | |
| 156 | /* "Unionizes two sets */ |
| 157 | public E union(E xx, E yy) { |
| 158 | Record<E> x = map.get(xx); |
| 159 | Record<E> y = map.get(yy); |
| 160 | Record<E> xroot = find(x); |
| 161 | Record<E> yroot = find(y); |
| 162 | |
| 163 | if(xroot == yroot) return xroot.name; |
| 164 | |
| 165 | if(xroot.getSize() > yroot.getSize()) { |
| 166 | xroot.absorb(yroot); |
| 167 | return xroot.name; |
| 168 | }else { |
| 169 | yroot.absorb(xroot); |
| 170 | return yroot.name; |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | /* "Unionizes two sets */ |
| 175 | public E unionWithOrder(E xx, E yy) { |
| 176 | Record<E> x = map.get(xx); |
| 177 | Record<E> y = map.get(yy); |
| 178 | Record<E> xroot = find(x); |
| 179 | Record<E> yroot = find(y); |
| 180 | |
| 181 | if(xroot == yroot) return xroot.name; |
| 182 | |
| 183 | xroot.absorb(yroot); |
| 184 | return xroot.name; |
| 185 | } |
| 186 | |
| 187 | public int clusterSize(E x){ |
| 188 | Record<E> rec = map.get(x); |
| 189 | return find(rec).getSize(); |
| 190 | } |
| 191 | |
| 192 | public double clusterWeight(E x){ |
| 193 | Record<E> rec = map.get(x); |
| 194 | return find(rec).getWeight(); |
| 195 | } |
| 196 | |
| 197 | public HashMap<E,E> getPartitionMap(){ |
| 198 | HashMap<E,E> pmap = new HashMap<E, E>(); |
| 199 | for(Record<E> rec : records){ |
| 200 | pmap.put(rec.getName(), find(rec).getName()); |
| 201 | } |
| 202 | return pmap; |
| 203 | } |
| 204 | |
| 205 | public E getRoot(E x){ |
| 206 | return find(map.get(x)).getName(); |
| 207 | } |
| 208 | |
| 209 | /* Given a records returns the top-record that represents the set |
| 210 | * containing that record. Re-links the given record to the top-record (Path compression, |
| 211 | * the key to gain the amortized running time). |
| 212 | **/ |
| 213 | public Record<E> find(Record<E> rec) { |
| 214 | if(rec.getParent() == null) |
| 215 | return rec; |
| 216 | else { |
| 217 | rec.setParent(find(rec.getParent())); |
| 218 | return rec.getParent(); |
| 219 | } |
| 220 | } |
| 221 | |
| 222 | /* Checks if to records are in the same set. */ |
| 223 | public boolean sameSet(Record<E> r1, Record<E> r2) { |
| 224 | return find(r1).equals(find(r2)); |
| 225 | } |
| 226 | |
| 227 | } |