1 /* Copyright (C) 2012  Gilleain Torrance <gilleain.torrance@gmail.com>
2  *
3  * Contact: cdk-devel@lists.sourceforge.net
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public License
7  * as published by the Free Software Foundation; either version 2.1
8  * of the License, or (at your option) any later version.
9  * All we ask is that proper credit is given for our work, which includes
10  * - but is not limited to - adding the above copyright notice to the beginning
11  * of your source code files, and to any copyright notice that you may distribute
12  * with programs based on this work.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public License
20  * along with this program; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
22  */
23 package org.openscience.cdk.group;
24 
25 import java.util.Arrays;
26 
27 
28 /**
29  * Implementation of a union-find data structure, largely copied from
30  * code due to Derrick Stolee.
31  *
32  * @author maclean
33  * @cdk.module standard
34  * @cdk.keyword union-find
35  */
36 public class DisjointSetForest {
37 
38     /**
39      * The sets stored as pointers to their parents. The root of each
40      * set is stored as the negated size of the set - ie a set of size
41      * 5 with a root element 2 will mean forest[2] = -5.
42      */
43     private int[] forest;
44 
45     /**
46      * Initialize a disjoint set forest with a number of elements.
47      *
48      * @param numberOfElements the number of elements in the forest
49      */
DisjointSetForest(int numberOfElements)50     public DisjointSetForest(int numberOfElements) {
51         forest = new int[numberOfElements];
52         for (int i = 0; i < numberOfElements; i++) {
53             forest[i] = -1;
54         }
55     }
56 
57     /**
58      * Get the value of the forest at this index - note that this will <i>not</i>
59      * necessarily give the set for that element : use {@link #getSets} after
60      * union-ing elements.
61      *
62      * @param i the index in the forest
63      * @return the value at this index
64      */
get(int i)65     public int get(int i) {
66         return forest[i];
67     }
68 
69     /**
70      * Travel up the tree that this element is in, until the root of the set
71      * is found, and return that root.
72      *
73      * @param element the starting point
74      * @return the root of the set containing element
75      */
getRoot(int element)76     public int getRoot(int element) {
77         if (forest[element] < 0) {
78             return element;
79         } else {
80             return getRoot(forest[element]);
81         }
82     }
83 
84     /**
85      * Union these two elements - in other words, put them in the same set.
86      *
87      * @param elementX an element
88      * @param elementY an element
89      */
makeUnion(int elementX, int elementY)90     public void makeUnion(int elementX, int elementY) {
91         int xRoot = getRoot(elementX);
92         int yRoot = getRoot(elementY);
93 
94         if (xRoot == yRoot) {
95             return;
96         }
97 
98         if (forest[xRoot] < forest[yRoot]) {
99             forest[yRoot] = forest[yRoot] + forest[xRoot];
100             forest[xRoot] = yRoot;
101         } else {
102             forest[xRoot] = forest[xRoot] + forest[yRoot];
103             forest[yRoot] = xRoot;
104         }
105     }
106 
107     /**
108      * Retrieve the sets as 2D-array of ints.
109      *
110      * @return the sets
111      */
getSets()112     public int[][] getSets() {
113         int n = 0;
114         for (int i = 0; i < forest.length; i++) {
115             if (forest[i] < 0) {
116                 n++;
117             }
118         }
119         int[][] sets = new int[n][];
120         int currentSet = 0;
121         for (int i = 0; i < forest.length; i++) {
122             if (forest[i] < 0) {
123                 int setSize = 1 - forest[i] - 1;
124                 sets[currentSet] = new int[setSize];
125                 int currentIndex = 0;
126                 for (int element = 0; element < forest.length; element++) {
127                     if (getRoot(element) == i) {
128                         sets[currentSet][currentIndex] = element;
129                         currentIndex++;
130                     }
131                 }
132                 currentSet++;
133             }
134         }
135         return sets;
136     }
137 
138     @Override
toString()139     public String toString() {
140         return Arrays.toString(forest);
141     }
142 
143 }
144