##
table of contents

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

# 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(); $g = Graph->new(multiedged => 1); $g->add_...(); # build $g $am = Graph::AdjacencyMatrix->new($g, distance_matrix => 1); $am->distance($u, $v) # returns hash-ref of ID => distance

# 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.
If the underlying graph is multiedged, returns hash-ref of ID mapped to distance. If a given edge ID does not have the attribute defined, it will not be represented. If no edge IDs have the attribute, "undef" will be returned.

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

2024-07-01 | perl v5.40.0 |