1package Graph::UnionFind; 2 3use strict; 4 5sub _PARENT () { 0 } 6sub _RANK () { 1 } 7 8sub new { 9 my $class = shift; 10 bless { }, $class; 11} 12 13sub add { 14 my ($self, $elem) = @_; 15 $self->{ $elem } = [ $elem, 0 ] unless defined $self->{$elem}; 16} 17 18sub has { 19 my ($self, $elem) = @_; 20 exists $self->{ $elem }; 21} 22 23sub _parent { 24 return undef unless defined $_[1]; 25 if (@_ == 2) { 26 exists $_[0]->{ $_[ 1 ] } ? $_[0]->{ $_[1] }->[ _PARENT ] : undef; 27 } elsif (@_ == 3) { 28 $_[0]->{ $_[1] }->[ _PARENT ] = $_[2]; 29 } else { 30 require Carp; 31 Carp::croak(__PACKAGE__ . "::_parent: bad arity"); 32 } 33} 34 35sub _rank { 36 return unless defined $_[1]; 37 if (@_ == 2) { 38 exists $_[0]->{ $_[1] } ? $_[0]->{ $_[1] }->[ _RANK ] : undef; 39 } elsif (@_ == 3) { 40 $_[0]->{ $_[1] }->[ _RANK ] = $_[2]; 41 } else { 42 require Carp; 43 Carp::croak(__PACKAGE__ . "::_rank: bad arity"); 44 } 45} 46 47sub find { 48 my ($self, $x) = @_; 49 my $px = $self->_parent( $x ); 50 return unless defined $px; 51 $self->_parent( $x, $self->find( $px ) ) if $px ne $x; 52 $self->_parent( $x ); 53} 54 55sub union { 56 my ($self, $x, $y) = @_; 57 $self->add($x) unless $self->has($x); 58 $self->add($y) unless $self->has($y); 59 my $px = $self->find( $x ); 60 my $py = $self->find( $y ); 61 return if $px eq $py; 62 my $rx = $self->_rank( $px ); 63 my $ry = $self->_rank( $py ); 64 # print "union($x, $y): px = $px, py = $py, rx = $rx, ry = $ry\n"; 65 if ( $rx > $ry ) { 66 $self->_parent( $py, $px ); 67 } else { 68 $self->_parent( $px, $py ); 69 $self->_rank( $py, $ry + 1 ) if $rx == $ry; 70 } 71} 72 73sub same { 74 my ($uf, $u, $v) = @_; 75 my $fu = $uf->find($u); 76 return undef unless defined $fu; 77 my $fv = $uf->find($v); 78 return undef unless defined $fv; 79 $fu eq $fv; 80} 81 821; 83__END__ 84=pod 85 86=head1 NAME 87 88Graph::UnionFind - union-find data structures 89 90=head1 SYNOPSIS 91 92 use Graph::UnionFind; 93 my $uf = Graph::UnionFind->new; 94 95 # Add the vertices to the data structure. 96 $uf->add($u); 97 $uf->add($v); 98 99 # Join the partitions of the vertices. 100 $uf->union( $u, $v ); 101 102 # Find the partitions the vertices belong to 103 # in the union-find data structure. If they 104 # are equal, they are in the same partition. 105 # If the vertex has not been seen, 106 # undef is returned. 107 my $pu = $uf->find( $u ); 108 my $pv = $uf->find( $v ); 109 $uf->same($u, $v) # Equal to $pu eq $pv. 110 111 # Has the union-find seen this vertex? 112 $uf->has( $v ) 113 114=head1 DESCRIPTION 115 116I<Union-find> is a special data structure that can be used to track the 117partitioning of a set into subsets (a problem known also as I<disjoint sets>). 118 119Graph::UnionFind() is used for Graph::connected_components(), 120Graph::connected_component(), and Graph::same_connected_components() 121if you specify a true C<union_find> parameter when you create an undirected 122graph. 123 124Note that union-find is one way: you cannot (easily) 'ununion' 125vertices once you have 'unioned' them. This means that if you 126delete edges from a C<union_find> graph, you will get wrong results 127from the Graph::connected_components(), Graph::connected_component(), 128and Graph::same_connected_components(). 129 130=head2 API 131 132=over 4 133 134=item add 135 136 $uf->add($v) 137 138Add the vertex v to the union-find. 139 140=item union 141 142 $uf->union($u, $v) 143 144Add the edge u-v to the union-find. Also implicitly adds the vertices. 145 146=item has 147 148 $uf->has($v) 149 150Return true if the vertex v has been added to the union-find, false otherwise. 151 152=item find 153 154 $uf->find($v) 155 156Return the union-find partition the vertex v belongs to, 157or C<undef> if it has not been added. 158 159=item new 160 161 $uf = Graph::UnionFind->new() 162 163The constructor. 164 165=item same 166 167 $uf->same($u, $v) 168 169Return true of the vertices belong to the same union-find partition 170the vertex v belongs to, false otherwise. 171 172=back 173 174=head1 AUTHOR AND COPYRIGHT 175 176Jarkko Hietaniemi F<jhi@iki.fi> 177 178=head1 LICENSE 179 180This module is licensed under the same terms as Perl itself. 181 182=cut 183 184