001 /*--------------------------------------------------------------------------+
002 $Id: UnionFind.java 26283 2010-02-18 11:18:57Z juergens $
003 | |
004 | Copyright 2005-2010 Technische Universitaet Muenchen |
005 | |
006 | Licensed under the Apache License, Version 2.0 (the "License"); |
007 | you may not use this file except in compliance with the License. |
008 | You may obtain a copy of the License at |
009 | |
010 | http://www.apache.org/licenses/LICENSE-2.0 |
011 | |
012 | Unless required by applicable law or agreed to in writing, software |
013 | distributed under the License is distributed on an "AS IS" BASIS, |
014 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015 | See the License for the specific language governing permissions and |
016 | limitations under the License. |
017 +--------------------------------------------------------------------------*/
018 package edu.tum.cs.commons.algo;
019
020 import edu.tum.cs.commons.collections.ManagedIntArray;
021
022 /**
023 * Implementation of a simple union find data structure. It implements the
024 * "partial path compression" heuristic but does not use "union by rank" but
025 * instead uses randomization.
026 *
027 * @author hummelb
028 * @author $Author: juergens $
029 * @version $Rev: 26283 $
030 * @levd.rating GREEN Hash: CF81A002CA0755AAD2BB6B1A6C75BA03
031 */
032 public class UnionFind extends ManagedIntArray {
033
034 /** Finds and returns the representative for the given element. */
035 public int find(int element) {
036 if (element >= size) {
037 throw new IllegalArgumentException("Unknown element!");
038 }
039
040 while (element != array[element]) {
041 int next = array[element];
042 array[element] = array[next];
043 element = next;
044 }
045
046 return element;
047 }
048
049 /**
050 * Merges the classes in which element1 and element2 are, by giving them the
051 * same representative.
052 */
053 public void union(int element1, int element2) {
054 if (element1 >= size || element2 >= size) {
055 throw new IllegalArgumentException("Unknown elements!");
056 }
057
058 // locate representatives
059 element1 = find(element1);
060 element2 = find(element2);
061
062 if (element1 != element2) {
063 if (Math.random() > .5) {
064 connectToRepresentative(element1, element2);
065 } else {
066 connectToRepresentative(element2, element1);
067 }
068 }
069 }
070
071 /**
072 * Connects the given element (must also be representative) to the given
073 * representative.
074 */
075 protected void connectToRepresentative(int element, int representative) {
076 array[element] = representative;
077 }
078
079 /** Adds a new element to this union find structure and returns its index. */
080 public int addElement() {
081 int index = size;
082 addArrayElement();
083 array[index] = index;
084 return index;
085 }
086 }