NAME "Graph::Undirected::Components::External" - Computes components of an undirected graph. SYNOPSIS use Data::Dump qw(dump); use Log::Log4perl qw(:easy); use Graph::Undirected::Components::External; Log::Log4perl->easy_init ($WARN); my $componenter = Graph::Undirected::Components::External->new(outputFile => 'vertexCompId.txt', purgeSizeBytes => 5000); my $vertices = 10000; for (my $i = 0; $i < $vertices; $i++) { $componenter->add_edge (int rand $vertices, int rand $vertices); } dump $componenter->finish (); DESCRIPTION "Graph::Undirected::Components::External" computes the components of an undirected graph limited only by the amount of free disk space. All errors, warnings, and informational messages are logged using Log::Log4perl. CONSTRUCTOR "new" The method "new" creates an instance of "Graph::Undirected::Components::External" with the following parameters. "workingDirectory" workingDirectory => File::Temp::tempdir() "workingDirectory" is an optional parameter specifying the path to a directory that all temporary files are written to; the default is set using File::Temp::tempdir(). "purgeSizeBytes" purgeSizeBytes => 1000000 "purgeSizeBytes" is an optional parameter specifying the aggregate byte size that all the vertices added to the internal instance of Graph::Undirected::Components must exceed before its content is purged to disk. The optimal value depends on the total internal memory available. "purgeSizeVertices" purgeSizeVertices => undef "purgeSizeVertices" is an optional parameter specifying the total vertices added to the internal instance of Graph::Undirected::Components that must be exceed before its content is purged to disk. If "purgeSizeBytes" and "purgeSizeVertices" are both defined, then a purge occurs when either threshold is exceeded. "retainPercentage" retainPercentage => 0.10 "retainPercentage" is an optional parameter specifying the percentage of the most recently used vertices to be retained in the internal instance of Graph::Undirected::Components when it is purged. If the edges of the graph are not added in a random order, caching some of the vertices can speedup the computation of the components. "outputFile" outputFile => ... "outputFile" is the path to the file that the "(vertex,component-id)" pairs are written to; the directory of the file should exist. An exception is thrown if "outputFile" is undefined or the file cannot be written to. "delimiter" delimiter => ',' "delimiter" is the delimiter used to separate the vertices of an edge when they are written to temporary files. All vertices should be encoded so that they do not contain the delimiter, that is, it should be true that "index($vertex,$delimiter)==-1" for all vertices. 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 only "vertexA" is defined, then the edge "(vertexA, vertexA)" is added to the graph. The method always returns undef. "add_file" The method "add_file" adds all the edges in a file to the graph. fileOfEdges => ... "fileOfEdges" specifies the path to the file containing the edges to add. An exception is thrown if there are problems openning or reading the file. delimiter The edges are read from "fileOfEdges" using Text::CSV; "delimiter" must be to the delimiter used to separate the vertices of an edge in the file. The default is the value set with the "new" constructor. "finish" The method "finish" completes the computation of the connected components and writes the pairs "(vertex,component-id)" to the "outputFile". For each component "component-id" is the lexographical minimum of all the vertices in the component. No edges can be added to the graph after "finish" is called. INSTALLATION Use CPAN to install the module and all its prerequisites: perl -MCPAN -e shell cpan[1]> install Graph::Undirected::Components BUGS Please email bugs reports or feature requests to "bug-graph-undirected-components@rt.cpan.org", or through the web interface at . The author will be notified and you can be automatically notified of progress on the bug fix or feature request. AUTHOR Jeff Kubina 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 SEE ALSO Graph, Graph::Undirected::Components, Log::Log4perl, Sort::External