Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Graph::TransitiveClosuUserMContributed PerlGraph::TransitiveClosure::Matrix(3)

NAME
       Graph::TransitiveClosure::Matrix	- create and query transitive closure
       of graph

SYNOPSIS
	   use Graph::TransitiveClosure::Matrix;
	   use Graph::Directed;	# or Undirected

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

	   # Compute the transitive closure matrix.
	   my $tcm = Graph::TransitiveClosure::Matrix->new($g);

	   # Being reflexive is	the default,
	   # meaning that null transitions are included.
	   my $tcm = Graph::TransitiveClosure::Matrix->new($g, reflexive => 1);
	   $tcm->is_reachable($u, $v)

	   # is_reachable(u, v)	is always reflexive.
	   $tcm->is_reachable($u, $v)

	   # The reflexivity of	is_transitive(u, v) depends of the reflexivity
	   # of	the transitive closure.
	   $tcg->is_transitive($u, $v)

	   my $tcm = Graph::TransitiveClosure::Matrix->new($g, path_length => 1);
	   my $n = $tcm->path_length($u, $v)

	   my $tcm = Graph::TransitiveClosure::Matrix->new($g, path_vertices =>	1);
	   my @v = $tcm->path_vertices($u, $v)

	   my $tcm =
	       Graph::TransitiveClosure::Matrix->new($g,
						     attribute_name => 'length');
	   my $n = $tcm->path_length($u, $v)

	   my @v = $tcm->vertices

DESCRIPTION
       You can use "Graph::TransitiveClosure::Matrix" to compute the
       transitive closure matrix of a graph and	optionally also	the minimum
       paths (lengths and vertices) between vertices, and after	that query the
       transitiveness between vertices by using	the "is_reachable()" and
       "is_transitive()" methods, and the paths	by using the "path_length()"
       and "path_vertices()" methods.

       If you modify the graph after computing its transitive closure, the
       transitive closure and minimum paths may	become invalid.

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

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

	   "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 the new() constructor.

	   reflexive =>	boolean
		   By default the transitive closure matrix is not reflexive:
		   that	is, the	adjacency matrix has zeroes on the diagonal.
		   To have ones	on the diagonal, use true for the "reflexive"
		   option.

		   NOTE: this behaviour	has changed from Graph 0.2xxx:
		   transitive closure graphs were by default reflexive.

	   path_length => boolean
		   By default the path lengths are not computed, only the
		   boolean transitivity.  By using true	for "path_length" also
		   the path lengths will be computed, they can be retrieved
		   using the path_length() method.

	   path_vertices => boolean
		   By default the paths	are not	computed, only the boolean
		   transitivity.  By using true	for "path_vertices" also the
		   paths will be computed, they	can be retrieved using the
		   path_vertices() method.

   Object Methods
       is_reachable($u,	$v)
	   Return true if the vertex $v	is reachable from the vertex $u, or
	   false if not.

       path_length($u, $v)
	   Return the minimum path length from the vertex $u to	the vertex $v,
	   or undef if there is	no such	path.

       path_vertices($u, $v)
	   Return the minimum path (as a list of vertices) from	the vertex $u
	   to the vertex $v, or	an empty list if there is no such path,	OR
	   also	return an empty	list if	$u equals $v.

       has_vertices($u,	$v, ...)
	   Return true if the transitive closure matrix	has all	the listed
	   vertices, false if not.

       is_transitive($u, $v)
	   Return true if the vertex $v	is transitively	reachable from the
	   vertex $u, false if not.

       vertices
	   Return the list of vertices in the transitive closure matrix.

       path_predecessor
	   Return the predecessor of vertex $v in the transitive closure path
	   going back to vertex	$u.

RETURN VALUES
       For path_length() the return value will be the sum of the appropriate
       attributes on the edges of the path, "weight" by	default.  If no
       attribute has been set, one (1) will be assumed.

       If you try to ask about vertices	not in the graph, undefs and empty
       lists will be returned.

ALGORITHM
       The transitive closure algorithm	used is	Warshall and Floyd-Warshall
       for the minimum paths, which is O(V**3) in time,	and the	returned
       matrices	are O(V**2) in space.

SEE ALSO
       Graph::AdjacencyMatrix

AUTHOR AND COPYRIGHT
       Jarkko Hietaniemi jhi@iki.fi

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

perl v5.24.1			  2009-01-1Graph::TransitiveClosure::Matrix(3)

NAME | SYNOPSIS | DESCRIPTION | Methods | RETURN VALUES | ALGORITHM | SEE ALSO | AUTHOR AND COPYRIGHT | LICENSE

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Graph::TransitiveClosure::Matrix&sektion=3&manpath=FreeBSD+12.0-RELEASE+and+Ports>

home | help