NAME

Graph::Weighted - An abstract, weighted graph implementation

SYNOPSIS

  use Graph::Weighted;

  $g = Graph::Weighted->new(
      data => [
        [ 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.
      ]
  );

  $g = Graph::Weighted->new(
      data => {
          weight => {
              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.
          }
          foo => [
              [ 1, 2, 3 ],
              [ 4, 5, 6 ],
              [ 7, 8, 9 ]
          ],
     }
  );

  $g = Graph::Weighted->new(
      data => $Math_Matrix_object,
      retrieve_as => 'ARRAY',
  );

  $data = $g->weight_data;

  $w = $g->graph_weight;

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

  $w = $g->edge_weight($v1, $v2);
  $w = $g->edge_weight($v1, $v2, $w + 1);

  $vertices = $g->heaviest_vertices;
  $vertices = $g->lightest_vertices;

  $w = $g->max_weight;  # Weight of the largest vertices.
  $w = $g->min_weight;  # Weight of the smallest vertices.

  # Call the weight methods of the inherited Graph module.
  $x = $g->MST_Kruskal;
  $x = $g->APSP_Floyd_Warshall;
  $x = $g->MST_Prim($p);

DESCRIPTION

A Graph::Weighted object represents a subclass of Graph::Directed with weighted attributes that are taken from a two dimensional matrix of numerical values.

This module can use a standard array or hash reference for data. It 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.

This module allows you to create a graph with edges that have values defined in a given matrix. You can have as many of these matrices as you like. Each one is referenced by an attribute name. For a weighted graph, this attribute is named "weight". For a capacity graph, this attribute is named "capacity". Each attribute corresponds to one matrix of values.

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.

default_attribute => STRING

The attribute to use by default, if the generic (load, data, and *_attr) methods are called without an attribute as an argument (which should never actually happen, if you are doing thing corrdctly).

This is set to 'weight', by default, of course.

data => $HASHREF | $ARRAYREF | $OBJECT

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

Math::Matrix, Math::MatrixReal, and Math::MatrixBool objects can also be loaded.

retrieve_as => 'HASH' | 'ARRAY'

Flag to tell the weight_data method to output as a hash or array reference. Defaults to HASH.

If this object attribute is set to ARRAY, the zero_edges attribute is automatically turned on.

load_weights $HASHREF | $ARRAYREF | $OBJECT
Turn the given two dimensional hash, (NxN) array, or object reference into the vertices and weighted edges of a Graph::Directed object.

Math::Matrix, Math::MatrixReal, and Math::MatrixBool objects can also be loaded.
weight_data
Return a two dimensional representation of the vertices and all their weighted edges.

The representation can be either a hash or array reference, depending on the retrieve_as object attribute setting.
graph_weight
Get the total weight of the graph, which is the sum of the vertex weights.
vertex_weight $VERTEX [, $WEIGHT]
Return the weight of a vertex, which is the sum of the successor edge weights.

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

API METHODS

This section briefly describes the methods to use when creating your own, custom subclass of Graph::Weighted. Please see the Graph::Weighted::Capacity module for a simple example.

These are generic methods used in the public methods of Graph::Weighted and Graph::Weighted::Capacity. Primarily, they each accept an extra attribute argument and use the class default attribute, if none is provided.

Please remember that the default_attribute should probably be set, even though it is not required. Also, it is recommended that you specifically call your methods with an attribute (shown as [$ATTR] below), even though you may have already defined a default. This is to avoid the mixups that result in "multi-attributed" graphs, where the default may be something other than the data attribute of interest.

All the following methods are described in greater detail under the PUBLIC METHODS section, above.

new %ARGS

Using a default attribute and an array reference:

  $g = Graph::Weighted::Foo->new(
      default_attribute => 'foo',
      data => $array_ref,
  );

Using a set of data (which can be either array or hash references), with keys as attributes:

  $g = Graph::Weighted::Bar->new(
      data => {
          foo => $data_1,
          bar => $data_2,
          baz => $data_3,
      },
  );

load $DATA [, $ATTR]
This method can accept either a Math::Matrix* object, an array or hash reference for the data.

If given an array reference, the attribute argument or class default attribute is used.

If given a hash reference, the keys are used as attributes and the values can be either Math::Matrix* objects, array or hash references.
data [$ATTR]
```
  $data = $g->data($attr);
```
Return a two dimensional representation of the vertices and all their valued edges.

The representation can be either a hash or array reference, depending on the retrieve_as object attribute setting.
graph_attr [$ATTR]
```
  $x = $g->graph_attr($attr);
```
Get the total value of the across the entire graph, which is the sum of the vertex attributes.
vertex_attr $VERTEX [, $VALUE] [, $ATTR]
```
  $x = $g->vertex_attr(
      vertex => $v,
      value => $val,
      attr => $attr,
  );
```
Return the attribute value of a vertex, which is the sum of the successor edge attribute values.

This generic API method requires named parameters.
edge_attr $VERTEX, $SUCCESSOR [, $VALUE] [, $ATTR]
```
  $x = $g->edge_attr(
      vertex => $v,
      successor => $s,
      value => $val,
      attr => $attr,
  );
```
Return the attribute value of an edge between the two given vertices.

This generic API method requires named parameters.
largest_vertices [$ATTR]
```
  $array_ref = $g->largest_vertices($attr);
```
Return an array reference of vertices with the largest value of the given attribute.
smallest_vertices [$ATTR]
```
  $array_ref = $g->smallest_vertices($attr);
```
Return an array reference of vertices with the smallest value of the given attribute.
max_attr [$ATTR]
```
  $x = $g->max_attr($attr);
```
Return the attribute value of the "largest" vertices (as defined above).
min_attr [$ATTR]
```
  $x = $g->min_attr($attr);
```
Return the attribute value of the "smallest" vertices (as defined above).

TO DO

Handle arbitrary string attribute values.

Handle algebraic expression attribute values (probably via Math::Symbolic). Lisp expressions come to mind also...

That is, use some sort of callback to update values, instead of addition and subtraction.

AUTHOR

Gene Boggs <gene@cpan.org>

COPYRIGHT AND LICENSE

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

Graph::Weighted - An abstract, weighted graph implementation