/* * Disjoint-set data structure - Library (Rust) * * Copyright (c) 2018 Project Nayuki. (MIT License) * https://www.nayuki.io/page/disjoint-set-data-structure * * Permission is hereby granted, free of charge, to any person obtaining a copy of * this software and associated documentation files (the "Software"), to deal in * the Software without restriction, including without limitation the rights to * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of * the Software, and to permit persons to whom the Software is furnished to do so, * subject to the following conditions: * - The above copyright notice and this permission notice shall be included in * all copies or substantial portions of the Software. * - The Software is provided "as is", without warranty of any kind, express or * implied, including but not limited to the warranties of merchantability, * fitness for a particular purpose and noninfringement. In no event shall the * authors or copyright holders be liable for any claim, damages or other * liability, whether in an action of contract, tort or otherwise, arising from, * out of or in connection with the Software or the use or other dealings in the * Software. */ use std; /* * Represents a set of disjoint sets. Also known as the union-find data structure. * Main operations are querying if two elements are in the same set, and merging two sets together. * Useful for testing graph connectivity, and is used in Kruskal's algorithm. */ #[derive(Clone)] pub struct DisjointSet { numberofsets: usize, nodes: Vec, } // Private helper structure. #[derive(Clone, Copy)] struct DisjointSetNode { // The index of the parent element. An element is a representative iff its parent is itself. parent: usize, // Always in the range [0, floor(log2(NumberOfElements))]. Thus has a maximum value of 63. rank: i8, // Positive number if the element is a representative, otherwise zero. size: usize, } impl DisjointSet { // Constructs a new set containing the given number of singleton sets. // For example, new DisjointSet(3) --> {{0}, {1}, {2}}. pub fn new(numelems: usize) -> Self { Self { numberofsets: numelems, nodes: (0 .. numelems).map(|i| DisjointSetNode{ parent: i, rank: 0, size: 1, }).collect(), } } // Returns the number of elements among the set of disjoint sets; this was the number passed // into the constructor and is constant for the lifetime of the object. All the other methods // require the argument elemindex to satisfy 0 <= elemindex < number_of_elements(). pub fn number_of_elems(&self) -> usize { self.nodes.len() } // The number of disjoint sets overall. This number decreases monotonically as time progresses; // each call to merge_sets() either decrements the number by one or leaves it unchanged. 0 <= number_of_sets() <= number_of_elements(). pub fn number_of_sets(&self) -> usize { self.numberofsets } // (Private) Returns the representative element for the set containing the given element. This method is also // known as "find" in the literature. Also performs path compression, which alters the internal state to // improve the speed of future queries, but has no externally visible effect on the values returned. fn get_repr(&mut self, mut elemindex: usize) -> usize { // Follow parent pointers until we reach a representative let mut parent: usize = self.nodes[elemindex].parent; if parent == elemindex { return elemindex; } loop { let grandparent: usize = self.nodes[parent].parent; if grandparent == parent { return parent; } self.nodes[elemindex].parent = grandparent; // Partial path compression elemindex = parent; parent = grandparent; } } // Returns the size of the set that the given element is a member of. 1 <= result <= number_of_elements(). pub fn get_size_of_set(&mut self, elemindex: usize) -> usize { let repr = self.get_repr(elemindex); self.nodes[repr].size } // Tests whether the given two elements are members of the same set. Note that the arguments are orderless. pub fn are_in_same_set(&mut self, elemindex0: usize, elemindex1: usize) -> bool { self.get_repr(elemindex0) == self.get_repr(elemindex1) } // Merges together the sets that the given two elements belong to. This method is also known as "union" in the literature. // If the two elements belong to different sets, then the two sets are merged and the method returns true. // Otherwise they belong in the same set, nothing is changed and the method returns false. Note that the arguments are orderless. pub fn merge_sets(&mut self, elemindex0: usize, elemindex1: usize) -> bool { // Get representatives let mut repr0: usize = self.get_repr(elemindex0); let mut repr1: usize = self.get_repr(elemindex1); if repr0 == repr1 { return false; } // Compare ranks let cmp: i8 = self.nodes[repr0].rank - self.nodes[repr1].rank; if cmp == 0 { // Increment repr0's rank if both nodes have same rank self.nodes[repr0].rank += 1; } else if cmp < 0 { // Swap to ensure that repr0's rank >= repr1's rank std::mem::swap(&mut repr0, &mut repr1); } // Graft repr1's subtree onto node repr0 self.nodes[repr1].parent = repr0; self.nodes[repr0].size += self.nodes[repr1].size; self.nodes[repr1].size = 0; self.numberofsets -= 1; true } // For unit tests. This detects many but not all invalid data structures, panicking if a // structural invariant is known to be violated. This always returns silently on a valid object. pub fn check_structure(&self) { let mut numrepr: usize = 0; for (i, node) in self.nodes.iter().enumerate() { let isrepr: bool = node.parent == i; numrepr += isrepr as usize; assert!(node.parent < self.nodes.len()); assert!(0 <= node.rank && (isrepr || node.rank < self.nodes[node.parent].rank)); assert!(!isrepr && node.size == 0 || isrepr && node.size >= (1usize << node.rank)); } assert_eq!(self.numberofsets, numrepr); assert!(self.numberofsets <= self.nodes.len()); } }