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 => $Math_MatrixReal_object,
);

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

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

$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;

$weight = $g->graph_weight;

$heaviest = $g->heaviest_vertices;
$lightest = $g->lightest_vertices;

# You can call the weight aware methods of the
# Graph::Directed module, of course.
$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.

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

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

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

load $HASHREF | $ARRAYREF

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

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. This method can also be used to set the vertex weight, if a second argument is provided.

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

When the second argument is provided, the weight it represents is distributed evenly to the vertex's outgoing edges, and the total weight of the entire graph is adjusted accordingly.

edge_weight $VERTEX, $NEIGHBOR [, $WEIGHT]

Return the weight of an edge between the two given vertices. This method can also be used to set the edge weight, if a third argument is provided.

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

When the 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 neighbor (second argument). Lastly, the total weight of the entire graph and the weight of the vertex are adjusted accordingly.

heaviest_vertices

Return the array reference of vertices with the most weight.

lightest_vertices

Return the array reference of vertices with the least weight.

PRIVATE METHODS

_debug @STUFF

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

SEE ALSO

Graph::Base

TO DO

Handle "capacity graphs" as detailed in the Graph::Base module.

Handle clusters of vertices and sub-graphs.

AUTHOR

Gene Boggs <cpan@ology.net>

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.