NAME

Graph::Weighted::Capacity - A capacity graph implementation

SYNOPSIS

use Graph::Weighted::Capacity;

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

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

$data = $g->capacity_data;

$c = $g->graph_capacity;

$c = $g->vertex_capacity($v1);
$c = $g->vertex_capacity($v1, $c + 1);

$c = $g->edge_capacity($v1, $v2);
$c = $g->edge_capacity($v1, $v2, $c + 1);

$vertices = $g->largest_vertices;
$vertices = $g->smallest_vertices;

$c = $g->max_capacity;  # Capacity of the largest vertices.
$c = $g->min_capacity;  # Capacity of the smallest vertices.

# Call the capacity methods of the inherited Graph module.
$x = $g->Flow_Ford_Fulkerson($state);
$x = $g->Flow_Edmonds_Karp($source, $sink);

DESCRIPTION

A Graph::Weighted::Capacity object represents a subclass of Graph::Weighted with capacity 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 capacities of the vertices are set to the sum of their outgoing edge capacities. This is mutable, however, and can be reset to any value desired, after initialization, with the vertex_capacity and edge_capacity methods.

This module is an extension of a more generic module that can handle multiple attributes - not just capacity and weight. Please see the Graph::Weighted documentation.

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 capacity 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 (HoH), (NxN) array, or object reference to use for vertex and edge capacities.

  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_capacity $HASHREF | $ARRAYREF | $OBJECT

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

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

• capacity_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_capacity

  Get the total capacity of the graph, which is the sum of all the vertex capacities.

• vertex_capacity $VERTEX [, $CAPACITY]

  Return the capacity 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 capacity is set to that value and is distributed evenly to the vertex's outgoing edges, and the total capacity of the graph is adjusted accordingly.

• edge_capacity $VERTEX, $SUCCESSOR [, $CAPACITY]

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

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

• largest_vertices

  Return an array reference of vertices with the most capacity.

• smallest_vertices

  Return an array reference of vertices with the least capacity.

• max_capacity

  Return the capacity of the largest vertices.

• min_capacity

  Return the capacity of the smallest vertices.

PRIVATE METHODS

• _debug @STUFF

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

SEE ALSO

Graph::Base

Graph::Weighted

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.