Graph::UnionFind(3pm)

💖 Graph::UnionFind 💖

okay bestie, so this is the Graph::UnionFind page from the User Contributed Perl Documentation section of the manual (that's the 3pm zone, iykyk) — it's a whole little module and honestly it's giving main character energy for a data structure.

---

🌸 NAME 🌸

Graph::UnionFind — union-find data structures 🫶

---

✨ SYNOPSIS ✨

like, here's the whole vibe in code, no cap:

use Graph::UnionFind;
my $uf = Graph::UnionFind->new;

# Add the vertices to the data structure.
$uf->add($u);
$uf->add($v);

# Join the partitions of the vertices.
$uf->union( $u, $v );

# Find the partitions the vertices belong to
# in the union-find data structure.  If they
# are equal, they are in the same partition.
# If the vertex has not been seen,
# undef is returned.
my $pu = $uf->find( $u );
my $pv = $uf->find( $v );
$uf->same($u, $v) # Equal to $pu eq $pv.

# Has the union-find seen this vertex?
$uf->has( $v )

---

🦋 DESCRIPTION 🦋

so union-find is this special data structure that tracks how a set gets partitioned into subsets — a problem that also goes by the name disjoint sets, in case you see that name out in the wild and go "wait, do I know her?" 🎀

Graph::UnionFind is what powers connected_components in Graph, connected_component in Graph, and same_connected_components in Graph — but only if you pass a true unionfind parameter when you create an undirected graph. that's the deal, fr fr. 💅

and bestie, important: union-find is one way. you cannot (easily) 'ununion' vertices once you have 'unioned' them. it's giving "no takebacks". 😭 that is exactly why Graph throws an exception if you try to delete edges from a union-find graph — it is not playing about it.

---

👑 API 👑

💖 add

$uf->add(@v)

adds the vertices to the union-find. simple as that, slay. ✨

💖 union

$uf->union([$u, $v], [$w, $x], ...)

adds the edge u-v to the union-find. it also implicitly adds the vertices, so you don't gotta do that part yourself. 🫶

💖 find

@partitions = $uf->find(@v)

for each vertex you hand it, it returns the union-find partition that vertex belongs to — or undef if it hasn't been added. undef is the "never seen her" of return values. 🙈

💖 new

$uf = Graph::UnionFind->new()

the constructor. the origin story. the birth of the vibe. 🌱

💖 same

$uf->same($u, $v)

returns true if the vertices belong to the same union-find partition the vertex v belongs to, and false otherwise. 🎀

---

🌈 AUTHOR AND COPYRIGHT 🌈

Jarkko Hietaniemi jhi@iki.fi — icon, legend, the moment. 👑

---

💜 LICENSE 💜

this module is licensed under the same terms as Perl itself. periodt. 🎀

---

and that's the whole page, bestie!! thank you for coming to my TED talk 💅

perl v5.40.1 · 2025-03-28 · Graph::UnionFind(3pm) — mwah, go union some vertices, you got this 🦋✨