File Coverage

blib/lib/Graph/UnionFind.pm

Criterion	Covered	Total	%
statement	43	43	100.0
branch	23	28	82.1
condition	2	6	33.3
subroutine	9	9	100.0
pod	5	5	100.0
total	82	91	90.1

package Graph::UnionFind;

use strict;
use warnings;

sub _PARENT  () { 0 }
sub _RANK    () { 1 }

sub new {
    my $class = shift;
    bless { }, $class;
}

sub add {
    my ($self, @elems) = @_;
    @elems = grep !defined $self->{$_}, @elems;
    @$self{ @elems } = map [ $_, 0 ], @elems;
}

sub _parent {
    return undef unless defined $_[1];
    Graph::__carp_confess(__PACKAGE__ . "::_parent: bad arity") if @_ < 2 or @_ > 3;
    if (@_ == 2) {
	exists $_[0]->{ $_[ 1 ] } ? $_[0]->{ $_[1] }->[ _PARENT ] : undef;
    } else {
	$_[0]->{ $_[1] }->[ _PARENT ] = $_[2];
    }
}

sub _rank {
    return unless defined $_[1];
    Graph::__carp_confess(__PACKAGE__ . "::_rank: bad arity") if @_ < 2 or @_ > 3;
    if (@_ == 2) {
	exists $_[0]->{ $_[1] } ? $_[0]->{ $_[1] }->[ _RANK ] : undef;
    } else {
	$_[0]->{ $_[1] }->[ _RANK ] = $_[2];
    }
}

sub find {
    my ($self, @v) = @_;
    my @ret;
    for my $x (@v) {
	push(@ret, undef), next unless defined(my $px = $self->_parent($x));
	$self->_parent( $x, $self->find( $px ) ) if $px ne $x;
	push @ret, $self->_parent( $x );
    }
    @ret;
}

sub union {
    my ($self, @edges) = @_;
    $self->add(map @$_, @edges);
    for my $e (@edges) {
	my ($px, $py) = $self->find( @$e );
	next if $px eq $py;
	my $rx = $self->_rank( $px );
	my $ry = $self->_rank( $py );
	# print "union($x, $y): px = $px, py = $py, rx = $rx, ry = $ry\n";
	if ( $rx > $ry ) {
	    $self->_parent( $py, $px );
	} else {
	    $self->_parent( $px, $py );
	    $self->_rank( $py, $ry + 1 ) if $rx == $ry;
	}
    }
}

sub same {
    my ($uf, $u, $v) = @_;
    my ($fu, $fv) = $uf->find($u, $v);
    return undef if grep !defined, $fu, $fv;
    $fu eq $fv;
}

1;
__END__