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

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 CWGraph::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 CWis_adjacent() method, or query the distance between vertices by using the CWdistance() method.

By default the edge attribute used for distance is CWw, 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 CW$g.
new($g, options)
Construct the adjacency matrix of the graph CW$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 CWdistance_matrix with a true value to the new() constructor.
attribute_name => attribute_name
By default the edge attribute used for distance is CWw. You can change that by giving another attribute name with the CWattribute_name attribute to new() constructor. Using this attribute also implicitly causes the distance matrix to be computed.

Object Methods

Return true if the vertex CW$v is adjacent to vertex CW$u, or false if not. Return the distance between the vertices CW$u and CW$v, or CWundef 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.