---
name: "Graph::UnionFind"
section: "3pm"
platform: "linux"
package: "libgraph-perl"
version: "1:0.9735-1"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Graph::UnionFind"
---

# Graph::UnionFind(3pm)

union-find data structures

## NAME

Graph::UnionFind - union-find data structures

## SYNOPSIS

```
    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

*Union-find* is a special data structure that can be used to track the partitioning of a set into subsets (a problem also known as *disjoint sets*).

`"Graph::UnionFind"` is used for "connected\_components" in Graph, "connected\_component" in Graph, and "same\_connected\_components" in Graph if you specify a true `"unionfind"` parameter when you create an undirected graph.

Union-find is one way: you cannot (easily) 'ununion' vertices once you have 'unioned' them. This is why Graph throws an exception if you try to delete edges from a union-find graph.

### API

- add

  ```
      $uf->add(@v)
  ```

  Add the vertices to the union-find.

- union

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

  Add the edge u-v to the union-find.  Also implicitly adds the vertices.

- find

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

  For each given vertex, return the union-find partition it belongs to, or `"undef"` if it has not been added.

- new

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

  The constructor.

- same

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

  Return true of the vertices belong to the same union-find partition the vertex v belongs to, false otherwise.

## AUTHOR AND COPYRIGHT

Jarkko Hietaniemi *jhi@iki.fi*

## LICENSE

This module is licensed under the same terms as Perl itself.