GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages
Graph::UnionFind(3) User Contributed Perl Documentation Graph::UnionFind(3)

Graph::UnionFind - union-find data structures

    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 )

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.

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.

Jarkko Hietaniemi jhi@iki.fi

This module is licensed under the same terms as Perl itself.
2021-08-02 perl v5.32.1

Search for    or go to Top of page |  Section 3 |  Main Index

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with ManDoc.