Logo

Programming-Idioms

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

Idiom #187 Disjoint Set

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

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

CPAN provides Graph::UnionFind for this. The algorithm is a bit too long to include within the 500 char Code limit of this site. List references are dereferenced with the @{ } idiom. (This module ought to provide a partitions method to do what the first foreach loop does.)
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();
  }
}

The class is usually subclassed with each element holding information about that specific element, and information about the aggregated set. The aggregated information is only used on the representative node
New implementation...
< > ⌨
Shaftway 
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

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)))))
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)
 
a.disjoint?(b)