GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages
Graph::AdjacencyMatrix(3) User Contributed Perl Documentation Graph::AdjacencyMatrix(3)

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

    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

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.

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.

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

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.

Graph::TransitiveClosure, Graph::BitMatrix

Jarkko Hietaniemi jhi@iki.fi

This module is licensed under the same terms as Perl itself.
2021-08-02 perl v5.32.1

Search for    or go to Top of page |  Section 3 |  Main Index

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with ManDoc.