001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.commons.util; 018 019/** 020 * The well-known disjoint-set forest data structure for dealing with partitions 021 * on a fixed-range integer domain. 022 * 023 * @author fhowar 024 * @author Malte Isberner <malte.isberner@gmail.com> 025 */ 026public final class UnionFind { 027 028 private final int[] p; 029 private final int[] rank; 030 031 /** 032 * Initializes the disjoint-set data structure. 033 * @param n the overall size of the domain 034 */ 035 public UnionFind(int n) { 036 p = new int[n]; 037 rank = new int[n]; 038 039 for(int i = 0; i < n; i++) { 040 // primitive arrays are always zero initialized 041 // rank[i] = 0; 042 p[i] = i; 043 } 044 } 045 046 /** 047 * Unites the sets containing the two given elements. 048 * @param p the first element 049 * @param q the second element 050 * @return the identifier of the resulting set 051 */ 052 public int union(int p, int q) { 053 return link(find(p), find(q)); 054 } 055 056 /** 057 * Unites two given sets. Note that the behavior of this method is not specified 058 * if the given parameters are normal elements and no set identifiers. 059 * @param x the first set 060 * @param y the second set 061 * @return the identifier of the resulting set (either <tt>x</tt> or <tt>y</tt>) 062 */ 063 public int link(int x, int y) { 064 if(rank[x] > rank[y]) { 065 p[y] = x; 066 return x; 067 } 068 p[x] = y; 069 if(rank[x] == rank[y]) 070 rank[y]++; 071 return y; 072 } 073 074 /** 075 * Finds the set of a given element, and compresses the path to the root node. 076 * @param x the element 077 * @return the identifier of the set which contains the given element 078 */ 079 public int find(int x) { 080 int r = p[x]; 081 if(x != r) 082 p[x] = r = find(r); 083 084 return r; 085 } 086 087 // public synchronized boolean findAndUnite(int x, int y) 088 // { 089 // int r1 = find(x); 090 // int r2 = find(y); 091 // 092 // if (r1 == r2) 093 // return false; 094 // 095 // union(r1, r2); 096 // return true; 097 // } 098}