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