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.