Struct DisjointSet 

pub struct DisjointSet<T: Clone + Hash + Eq> { /* private fields */ }

Disjoint Set (Union-Find) data structure

This data structure maintains a collection of disjoint sets and supports efficient union and find operations. It’s commonly used in clustering algorithms for tracking connected components.

Examples

use scirs2_cluster::hierarchy::DisjointSet;

let mut ds = DisjointSet::new();

// Add some elements
ds.make_set(1);
ds.make_set(2);
ds.make_set(3);
ds.make_set(4);

// Union some sets
ds.union(1, 2);
ds.union(3, 4);

// Check connectivity
assert_eq!(ds.find(&1), ds.find(&2)); // 1 and 2 are connected
assert_eq!(ds.find(&3), ds.find(&4)); // 3 and 4 are connected
assert_ne!(ds.find(&1), ds.find(&3)); // 1 and 3 are in different sets

Implementations

impl<T: Clone + Hash + Eq> DisjointSet<T>

pub fn new() -> Self

Create a new empty disjoint set

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let ds: DisjointSet<i32> = DisjointSet::new();

pub fn with_capacity(capacity: usize) -> Self

Create a new disjoint set with a specified capacity

This can improve performance when you know approximately how many elements you’ll be adding.

Arguments

• capacity - Expected number of elements

pub fn make_set(&mut self, x: T)

Add a new element as its own singleton set

If the element already exists, this operation has no effect.

Arguments

• x - Element to add

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
ds.make_set(42);
assert!(ds.contains(&42));

pub fn find(&mut self, x: &T) -> Option<T>

Find the representative (root) of the set containing the given element

Uses path compression for optimization: all nodes on the path to the root are made to point directly to the root.

Arguments

• x - Element to find the representative for

Returns

• Some(representative) if the element exists in the structure
• None if the element doesn’t exist

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
ds.make_set(1);
ds.make_set(2);
ds.union(1, 2);

let root1 = ds.find(&1).unwrap();
let root2 = ds.find(&2).unwrap();
assert_eq!(root1, root2); // Same representative

pub fn union(&mut self, x: T, y: T) -> bool

Union two sets containing the given elements

Uses union by rank: the root of the tree with smaller rank becomes a child of the root with larger rank.

Arguments

• x - Element from first set
• y - Element from second set

Returns

• true if the sets were successfully unioned (they were different sets)
• false if the elements were already in the same set or don’t exist

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
ds.make_set(1);
ds.make_set(2);

assert!(ds.union(1, 2)); // Successfully unioned
assert!(!ds.union(1, 2)); // Already in same set

pub fn connected(&mut self, x: &T, y: &T) -> bool

Check if two elements are in the same set

Arguments

• x - First element
• y - Second element

Returns

• true if both elements exist and are in the same set
• false if they’re in different sets or don’t exist

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
ds.make_set(1);
ds.make_set(2);
ds.make_set(3);
ds.union(1, 2);

assert!(ds.connected(&1, &2)); // Connected
assert!(!ds.connected(&1, &3)); // Not connected

pub fn contains(&self, x: &T) -> bool

Check if an element exists in the disjoint set

Arguments

• x - Element to check

Returns

• true if the element exists
• false otherwise

pub fn num_sets(&self) -> usize

Get the number of disjoint sets

Returns

The number of disjoint sets currently in the structure

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
assert_eq!(ds.num_sets(), 0);

ds.make_set(1);
ds.make_set(2);
assert_eq!(ds.num_sets(), 2);

ds.union(1, 2);
assert_eq!(ds.num_sets(), 1);

pub fn size(&self) -> usize

Get the total number of elements

Returns

The total number of elements in all sets

pub fn is_empty(&self) -> bool

Check if the disjoint set is empty

Returns

• true if no elements have been added
• false otherwise

pub fn get_set_members(&mut self, x: &T) -> Option<Vec<T>>

Get all elements in the same set as the given element

Arguments

• x - Element to find set members for

Returns

• Some(Vec<T>) containing all elements in the same set
• None if the element doesn’t exist

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
ds.make_set(1);
ds.make_set(2);
ds.make_set(3);
ds.union(1, 2);

let set_members = ds.get_set_members(&1).unwrap();
assert_eq!(set_members.len(), 2);
assert!(set_members.contains(&1));
assert!(set_members.contains(&2));
assert!(!set_members.contains(&3));

pub fn get_all_sets(&mut self) -> Vec<Vec<T>>

Get all disjoint sets as a vector of vectors

Returns

A vector where each inner vector contains the elements of one set

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
ds.make_set(1);
ds.make_set(2);
ds.make_set(3);
ds.union(1, 2);

let all_sets = ds.get_all_sets();
assert_eq!(all_sets.len(), 2); // Two disjoint sets

pub fn clear(&mut self)

Clear all elements from the disjoint set

Examples

use scirs2_cluster::hierarchy::DisjointSet;
let mut ds = DisjointSet::new();
ds.make_set(1);
ds.make_set(2);

assert_eq!(ds.size(), 2);
ds.clear();
assert_eq!(ds.size(), 0);

Trait Implementations

impl<T: Clone + Clone + Hash + Eq> Clone for DisjointSet<T>

fn clone(&self) -> DisjointSet<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Clone + Hash + Eq> Debug for DisjointSet<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Clone + Hash + Eq> Default for DisjointSet<T>

fn default() -> Self

Returns the “default value” for a type.