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


Manual Reference Pages  -  GRAPH::UNIONFIND (3)

.ds Aq ’

NAME

Graph::UnionFind - union-find data structures

CONTENTS

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 known also as disjoint sets).

Graph::UnionFind() is used for Graph::connected_components(), Graph::connected_component(), and Graph::same_connected_components() if you specify a true union_find parameter when you create an undirected graph.

Note that union-find is one way: you cannot (easily) ’ununion’ vertices once you have ’unioned’ them. This means that if you delete edges from a union_find graph, you will get wrong results from the Graph::connected_components(), Graph::connected_component(), and Graph::same_connected_components().

    API

add


    $uf->add($v)



Add the vertex v to the union-find.

union


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



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

has


    $uf->has($v)



Return true if the vertex v has been added to the union-find, false otherwise.

find


    $uf->find($v)



Return the union-find partition the vertex v 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.
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 GRAPH::UNIONFIND (3) 2008-11-27

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