perllib/Graph/UnionFind.pm

   1 package Graph::UnionFind;
   2
   3 use strict;
   4
   5 sub _PARENT  () { 0 }
   6 sub _RANK    () { 1 }
   7
   8 sub new {
   9     my $class = shift;
  10     bless { }, $class;
  11 }
  12
  13 sub add {
  14     my ($self, $elem) = @_;
  15     $self->{ $elem } = [ $elem, 0 ];
  16 }
  17
  18 sub has {
  19     my ($self, $elem) = @_;
  20     exists $self->{ $elem };
  21 }
  22
  23 sub _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
  35 sub _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
  47 sub 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
  55 sub 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
  73 sub 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
  82 1;
  83 __END__
  84 =pod
  85
  86 =head1 NAME
  87
  88 Graph::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
 116 I<Union-find> is a special data structure that can be used to track the
 117 partitioning of a set into subsets (a problem known also as I<disjoint sets>).
 118
 119 Graph::UnionFind() is used for Graph::connected_components(),
 120 Graph::connected_component(), and Graph::same_connected_components()
 121 if you specify a true C<union_find> parameter when you create an undirected
 122 graph.
 123
 124 Note that union-find is one way: you cannot (easily) 'ununion'
 125 vertices once you have 'unioned' them.  This means that if you
 126 delete edges from a C<union_find> graph, you will get wrong results
 127 from the Graph::connected_components(), Graph::connected_component(),
 128 and Graph::same_connected_components().
 129
 130 =head2 API
 131
 132 =over 4
 133
 134 =item add
 135
 136     $uf->add($v)
 137
 138 Add the vertex v to the union-find.
 139
 140 =item union
 141
 142     $uf->union($u, $v)
 143
 144 Add the edge u-v to the union-find.  Also implicitly adds the vertices.
 145
 146 =item has
 147
 148     $uf->has($v)
 149
 150 Return true if the vertex v has been added to the union-find, false otherwise.
 151
 152 =item find
 153
 154     $uf->find($v)
 155
 156 Return the union-find partition the vertex v belongs to,
 157 or C<undef> if it has not been added.
 158
 159 =item new
 160
 161     $uf = Graph::UnionFind->new()
 162
 163 The constructor.
 164
 165 =item same
 166
 167     $uf->same($u, $v)
 168
 169 Return true of the vertices belong to the same union-find partition
 170 the vertex v belongs to, false otherwise.
 171
 172 =back
 173
 174 =head1 AUTHOR AND COPYRIGHT
 175
 176 Jarkko Hietaniemi F<jhi@iki.fi>
 177
 178 =head1 LICENSE
 179
 180 This module is licensed under the same terms as Perl itself.
 181
 182 =cut
 183