NAME

Graph::Weighted - A weighted graph implementation

SYNOPSIS

use Graph::Weighted;

$g = Graph::Weighted->new(
    data => {
        a => { b => 1, c => 2, },  # A vertex with two edges.
        b => { a => 1, c => 3, },  # "
        c => { a => 2, b => 3, },  # "
        d => { c => 1, },          # A vertex with one edge.
        e => {},                   # A vertex with no edges.
   }
);

$g = Graph::Weighted->new(data => $object);  # See documentation.

$g = Graph::Weighted->new();
$g->load(
    [ [ 0, 1, 2, 0, 0, ],    # A vertex with two edges.
      [ 1, 0, 3, 0, 0, ],    # "
      [ 2, 3, 0, 0, 0, ],    # "
      [ 0, 0, 1, 0, 0, ],    # A vertex with one edge.
      [ 0, 0, 0, 0, 0, ], ]  # A vertex with no edges.
);

$data = $g->data;

$w = $g->graph_weight;

$w = $g->vertex_weight($p);
$w = $g->vertex_weight($p, $w + 1);

$w = $g->edge_weight($p, $q);
$w = $g->edge_weight($p, $q, $w + 1);

$heavies = $g->heaviest_vertices;
$lights  = $g->lightest_vertices;

$x = $g->max_weight;  # Equal to the weight of the $heavies.
$y = $g->min_weight;  # Equal to the weight of the $lights.

# Call any methods of the inherited Graph module.
@v = $g->vertices;
@v = $g->successors($p);  # etc.
$z = $g->MST_Kruskal;
$z = $g->APSP_Floyd_Warshall;
$z = $g->MST_Prim($p);

ABSTRACT

A weighted graph implementation

DESCRIPTION

A Graph::Weighted object represents a subclass of Graph::Directed with weighted attributes that are taken from a two dimensional matrix (HoH or NxN LoL) of numerical values.

This module can also load the matrix portions of Math::Matrix, Math::MatrixReal, and Math::MatrixBool objects.

Initially, the weights of the vertices are set to the sum of their outgoing edge weights. This is mutable, however, and can be reset to any value desired, after initialization, with the vertex_weight and edge_weight methods.

PUBLIC METHODS

new %ARGUMENTS

debug => 0 | 1

Flag to invoke verbose mode while processing. Defaults to zero.

zero_edges => 0 | 1

Flag to add edges between vertices with a weight of zero. Defaults to zero.

data => $HASHREF | $ARRAYREF | $OBJECT

Two dimensional hash, (NxN) array, or known object reference to use for vertices and weighted edges.

The known objects are Math::Matrix, Math::MatrixReal, and Math::MatrixBool.

load $HASHREF | $ARRAYREF | $OBJECT

Turn the given two dimensional hash, (NxN) array, or known object reference into the vertices and weighted edges of a Graph::Directed object.

The known objects are Math::Matrix, Math::MatrixReal, and Math::MatrixBool.

data

Return the two dimensional hash used for vertices and weighted edges.

graph_weight

Get the total weight of the graph, by summing all the vertex weights.

vertex_weight $VERTEX [, $WEIGHT]

Return the weight of a vertex.

(The vertices are just the keys of the data, not some glorified object, by the way.)

If a second argument is provided, the vertex weight is set to that value and is distributed evenly to the vertex's outgoing edges, and the total weight of the graph is adjusted accordingly.

edge_weight $VERTEX, $SUCCESSOR [, $WEIGHT]

Return the weight of an edge between the two given vertices.

If a third argument is provided, the weight it represents is used to replace the weight of the edge between the vertex (first argument) and it's successor (second argument). Finally, the weight of the vertex and the total weight of the graph are adjusted accordingly.

heaviest_vertices

Return an array reference of vertices with the most weight.

lightest_vertices

Return an array reference of vertices with the least weight.

max_weight

Return the weight of the heaviest vertices.

min_weight

Return the weight of the lightest vertices.

PRIVATE METHODS

_debug @STUFF

Print the contents of the argument array with a newline appended.

SEE ALSO

Graph::Base

TO DO

Handle clusters of vertices and sub-graphs.

AUTHOR

Gene Boggs <gene@cpan.org>

COPYRIGHT AND LICENSE

Copyright 2003 by Gene Boggs

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.