NAME
Graph::Undirected::Components - Computes components of an undirected graph.
SYNOPSIS
use Data::Dump qw(dump);
use Graph::Undirected::Components;
my $componenter = Graph::Undirected::Components->new();
my $vertices = 10;
for (my $i = 0; $i < $vertices; $i++)
{
$componenter->add_edge (int rand $vertices, int rand $vertices);
}
dump $componenter->connected_components ();DESCRIPTION
Graph::Undirected::Components computes the components of an undirected graph using a disjoint set data structure, so the memory used is bounded by the number of vertices only.
CONSTRUCTOR
new
The method new creates an instance of the Graph::Undirected::Components class; it takes no parameters.
METHODS
add_edge (vertexA, vertexB)
The method add_edge updates the components of the graph using the edge (vertexA, vertexB).
- vertexA, vertexB
-
The vertices of the edge
(vertexA, vertexB)are Perl strings. If onlyvertexAis defined, then the edge(vertexA, vertexA)is added to the graph. The method always returns undef.
getSizeBytes
The method getSizeBytes returns the aggregate byte length of all the vertices currently in the graph.
getSizeVertices
The method getSizeVertices returns the total number of vertices currently in the graph.
connected_components
The method connected_components returns the components of the graph. In list context connected_components returns the vertices of the connected components as a list of array references; in scalar context the list is returned as an array reference. No specific ordering is applied to the list of components or the vertices inside the lists.
get_vertexCompIdPairs (PercentageToKeep)
The method get_vertexCompIdPairs returns an array reference of pairs of the form [vertex,component-id]. The parameter PercentageToKeep sets the percentage of most recently used vertices that are retained in the graph. This method is used by Graph::Undirected::Components::External to potentially speedup the computation of the components.
INSTALLATION
Use CPAN to install the module and all its prerequisites:
perl -MCPAN -e shell
cpan[1]> install Graph::Undirected::ComponentsBUGS
Please email bugs reports or feature requests to bug-graph-undirected-components@rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Graph-Undirected-Components. The author will be notified and you can be automatically notified of progress on the bug fix or feature request.
AUTHOR
Jeff Kubina<jeff.kubina@gmail.com>COPYRIGHT
Copyright (c) 2009 Jeff Kubina. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
The full text of the license can be found in the LICENSE file included with this module.
KEYWORDS
connected components, network, undirected graph