Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!

Idiom #187 Disjoint Set

Disjoint Sets hold elements that are partitioned into a number of disjoint (non-overlapping) sets.

public class DisjointSetElement {
  private DisjointSetElement representative = this;

  public DisjointSetElement getRepresentative() {
    if (representative != this) {
      representative = representative.getRepresentative();
    }
    return representative;
  }

  public void union(DisjointSetElement other) {
    other.getRepresentative().representative = getRepresentative();
  }
}
  
(defstruct disjoint-set
  elements)

(defun make-disjoint-set (elements) 
  (make-disjoint-set :elements elements))

(defun partition (disjoint-set)
  (loop for element in (disjoint-set-elements disjoint-set) 
       collect 
        (let ((found (find element (mapcar #'first (rest disjoint-set)) 
                    :test #'equal)))
          (if found
              (acons element element found :test #'equal)
              (acons element element nil :test #'equal)))))
use feature 'say';
use Graph::UnionFind;
my @vert = (1..5);
my @edges = ( [1, 2], [2, 3], [4, 5] );

$uf->add( $_ )   for @vert;
$uf->union( $_ ) for @edges;

# find and consolidate partitions into a hash
my %part;
foreach my $v( @vert ) {
    my @pa = $uf->find($v);
    my $p = shift @pa;
    $part{$p} //= [];
    push @{ $part{$p} }, $v;
}

foreach my $k (sort keys %part) {
    my $vals = join ' ', @{ $part{$k} };
    say "$k : $vals";
}
# prints:
#   2 : 1 2 3
#   5 : 4 5
class UnionFind:
    def __init__(self, size):
        self.rank = [0] * size
        self.p = [i for i in range(size)]

    def find_set(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.find_set(self.p[i])
            return self.p[i]

    def is_same_set(self, i, j):
        return self.find_set(i) == self.find_set(j)

    def union_set(self, i, j):
        if not self.is_same_set(i, j):
            x, y = self.find_set(i), self.find_set(j)
 
require 'set'
a.disjoint?(b)

New implementation...
< >
Shaftway