1Graph::UnionFind(3)   User Contributed Perl Documentation  Graph::UnionFind(3)
2
3
4

NAME

6       Graph::UnionFind - union-find data structures
7

SYNOPSIS

9           use Graph::UnionFind;
10           my $uf = Graph::UnionFind->new;
11
12           # Add the vertices to the data structure.
13           $uf->add($u);
14           $uf->add($v);
15
16           # Join the partitions of the vertices.
17           $uf->union( $u, $v );
18
19           # Find the partitions the vertices belong to
20           # in the union-find data structure.  If they
21           # are equal, they are in the same partition.
22           # If the vertex has not been seen,
23           # undef is returned.
24           my $pu = $uf->find( $u );
25           my $pv = $uf->find( $v );
26           $uf->same($u, $v) # Equal to $pu eq $pv.
27
28           # Has the union-find seen this vertex?
29           $uf->has( $v )
30

DESCRIPTION

32       Union-find is a special data structure that can be used to track the
33       partitioning of a set into subsets (a problem known also as disjoint
34       sets).
35
36       Graph::UnionFind() is used for Graph::connected_components(),
37       Graph::connected_component(), and Graph::same_connected_components() if
38       you specify a true "union_find" parameter when you create an undirected
39       graph.
40
41       Note that union-find is one way: you cannot (easily) 'ununion' vertices
42       once you have 'unioned' them.  This means that if you delete edges from
43       a "union_find" graph, you will get wrong results from the Graph::con‐
44       nected_components(), Graph::connected_component(), and Graph::same_con‐
45       nected_components().
46
47       API
48
49       add
50               $uf->add($v)
51
52           Add the vertex v to the union-find.
53
54       union
55               $uf->union($u, $v)
56
57           Add the edge u-v to the union-find.  Also implicitly adds the ver‐
58           tices.
59
60       has
61               $uf->has($v)
62
63           Return true if the vertex v has been added to the union-find, false
64           otherwise.
65
66       find
67               $uf->find($v)
68
69           Return the union-find partition the vertex v belongs to, or "undef"
70           if it has not been added.
71
72       new
73               $uf = Graph::UnionFind->new()
74
75           The constructor.
76
77       same
78               $uf->same($u, $v)
79
80           Return true of the vertices belong to the same union-find partition
81           the vertex v belongs to, false otherwise.
82

84       Jarkko Hietaniemi jhi@iki.fi
85

LICENSE

87       This module is licensed under the same terms as Perl itself.
88
89
90
91perl v5.8.8                       2004-11-08               Graph::UnionFind(3)
Impressum