graph::unionfind(3pm) [debian man page]

Graph::UnionFind(3pm)					User Contributed Perl Documentation				     Graph::UnionFind(3pm)

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 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.

perl v5.10.0							    2008-11-27						     Graph::UnionFind(3pm)

Graph::AdjacencyMatrix(3pm)				User Contributed Perl Documentation			       Graph::AdjacencyMatrix(3pm)

NAME

       Graph::AdjacencyMatrix - create and query the adjacency matrix of graph G

SYNOPSIS

	   use Graph::AdjacencyMatrix;
	   use Graph::Directed; # or Undirected

	   my $g  = Graph::Directed->new;
	   $g->add_...(); # build $g

	   my $am = Graph::AdjacencyMatrix->new($g);
	   $am->is_adjacent($u, $v)

	   my $am = Graph::AdjacencyMatrix->new($g, distance_matrix => 1);
	   $am->distance($u, $v)

	   my $am = Graph::AdjacencyMatrix->new($g, attribute_name => 'length');
	   $am->distance($u, $v)

	   my $am = Graph::AdjacencyMatrix->new($g, ...);
	   my @V  = $am->vertices();

DESCRIPTION

       You can use "Graph::AdjacencyMatrix" to compute the adjacency matrix and optionally also the distance matrix of a graph, and after that
       query the adjacencyness between vertices by using the "is_adjacent()" method, or query the distance between vertices by using the
       "distance()" method.

       By default the edge attribute used for distance is "w", but you can change that in new(), see below.

       If you modify the graph after creating the adjacency matrix of it, the adjacency matrix and the distance matrix may become invalid.

Methods
   Class Methods
       new($g)
	   Construct the adjacency matrix of the graph $g.

       new($g, options)
	   Construct the adjacency matrix of the graph $g with options as a hash.  The known options are

	   distance_matrix => boolean
		   By default only the adjacency matrix is computed.  To compute also the distance matrix, use the attribute "distance_matrix"
		   with a true value to the new() constructor.

	   attribute_name => attribute_name
		   By default the edge attribute used for distance is "w".  You can change that by giving another attribute name with the
		   "attribute_name" attribute to new() constructor.  Using this attribute also implicitly causes the distance matrix to be
		   computed.

   Object Methods
       is_adjacent($u, $v)
	   Return true if the vertex $v is adjacent to vertex $u, or false if not.

       distance($u, $v)
	   Return the distance between the vertices $u and $v, or "undef" if the vertices are not adjacent.

       adjacency_matrix
	   Return the adjacency matrix itself (a list of bitvector scalars).

       vertices
	   Return the list of vertices (useful for indexing the adjacency matrix).

ALGORITHM

       The algorithm used to create the matrix is two nested loops, which is O(V**2) in time, and the returned matrices are O(V**2) in space.

SEE ALSO

       Graph::TransitiveClosure, Graph::BitMatrix

AUTHOR AND COPYRIGHT

       Jarkko Hietaniemi jhi@iki.fi

LICENSE

       This module is licensed under the same terms as Perl itself.

perl v5.10.0							    2005-04-16					       Graph::AdjacencyMatrix(3pm)