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 also known as disjoint
34       sets).
35
36       "Graph::UnionFind" is used for "connected_components" in Graph,
37       "connected_component" in Graph, and "same_connected_components" in
38       Graph if you specify a true "unionfind" parameter when you create an
39       undirected graph.
40
41       Union-find is one way: you cannot (easily) 'ununion' vertices once you
42       have 'unioned' them. This is why Graph throws an exception if you try
43       to delete edges from a union-find graph.
44
45   API
46       add
47               $uf->add(@v)
48
49           Add the vertices to the union-find.
50
51       union
52               $uf->union([$u, $v], [$w, $x], ...)
53
54           Add the edge u-v to the union-find.  Also implicitly adds the
55           vertices.
56
57       find
58               @partitions = $uf->find(@v)
59
60           For each given vertex, return the union-find partition it belongs
61           to, or "undef" if it has not been added.
62
63       new
64               $uf = Graph::UnionFind->new()
65
66           The constructor.
67
68       same
69               $uf->same($u, $v)
70
71           Return true of the vertices belong to the same union-find partition
72           the vertex v belongs to, false otherwise.
73

75       Jarkko Hietaniemi jhi@iki.fi
76

LICENSE

78       This module is licensed under the same terms as Perl itself.
79
80
81
82perl v5.36.0                      2022-07-22               Graph::UnionFind(3)
Impressum