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.