/ 
Graph-Weighted-0.53
River stage zero No dependents
/ Graph::Weighted

NAME

Graph::Weighted - A weighted graph implementation

VERSION

version 0.53

SYNOPSIS

use Graph::Weighted;
my $g = Graph::Weighted->new();
my $attr = 'magnitude';
$g->populate(
  [ [ 0, 1, 2, 0, 0 ], # Vertex 0 with 5 edges of weight 3
    [ 1, 0, 3, 0, 0 ], #    "   1        "               4
    [ 2, 3, 0, 0, 0 ], #    "   2        "               5
    [ 0, 0, 1, 0, 0 ], #    "   3        "               1
    [ 0, 0, 0, 0, 0 ], #    "   4        "               0
  ]
);
$g->populate(
  { 0 => { 1=>2, 2=>1 },             # Vertex with 2 edges of weight 3
    1 => { 0=>3, 2=>1 },             #      "      2        "        4
    2 => { 0=>3, 1=>2 },             #      "      2        "        5
    3 => { 1=>2, 5=>1 },             #      "      2        "        3
    4 => { 0=>1, 1=>1, 2=>1, 3=>1 }, #      "      4        "        4
    5 => 3.1415,                     # A terminal node!
  },
  $attr
);
# Show each vertex and its edges.
for my $v (sort { $a <=> $b } $g->vertices) {
   warn sprintf "V: %s w=%.2f, %s=%.2f\n",
      $v,
      $g->get_weight($v),
      $attr, $g->get_attr($v, $attr);
   for my $n (sort { $a <=> $b } $g->neighbors($v)) {
      warn sprintf "\tE: >%s w=%.2f, %s=%.2f\n",
          $n,
          $g->get_weight([$v, $n]),
          $attr, $g->get_attr([$v, $n], $attr);
  }
}

DESCRIPTION

A Graph::Weighted object is a subclass of Graph with weighted attributes. As such, all of the Graph methods may be used as documented. This module is a streamlined version of the weight based accessors provided by the Graph module.

NAME

Graph::Weighted - A weighted graph implementation

METHODS

new()

Return a new Graph::Weighted object.

See Graph for the possible constructor arguments.

populate()

$g->populate(\@vectors)
$g->populate(
  { a => { b=>2, c=>1 },
    b => { a=>3, c=>1 },
    c => { a=>3, b=>2 },
    d => { b=>2 },
    e => { a=>1, b=>1, c=>1, d=>1 },
  },
);

Populate a graph with weighted nodes. Arguments:

data          => Array ref of numeric vectors or HASH ref of numeric edge values
attribute     => Optional string name
vertex_method => Optional code ref weighting function
edge_method   => Optional code ref weighting function

Examples of data in array reference form:

[]      No edges
[0]     1 vertex and 1 edge to node 0 (weight 0)
[1]     1 vertex and 1 edge to node 0 (vertex & edge weight 1)
[0,1]   2 vertices and 2 edges (edge weights 0,1; vertex weight 1)
[0,1,9] 3 vertices and 3 edges (edge weights 0,1,9; vertex weight 10)

Data can also be given explicitly as a hash reference of nodes and edges.

The attribute is named 'weight' by default, but may be anything of your choosing. This method can be called multiple times on the same graph, for nodes of the same name but different attributes values.

The default vertex weighting function (given by vertex_method) is a simple sum of the neighbor weights. An alternative may be provided, which should accept of the current node weight, current weight total and the attribute as arguments to update. For example:

sub vertex_weight_function {
  my ($current_node_weight, $current_weight_total, attribute);
  return $current_weight_total / $current_node_weight;
}

The default edge weighting function (given by edge_method) simply returns the value in the node's neighbor position. An alternative may be provided, as a subroutine reference, which should accept the current edge weight and the attribute to update. For example:

sub edge_weight_function {
  my ($weight, attribute);
  return $current_weight_total / $current_node_weight;
}

get_weight()

$w = $g->get_weight($vertex);
$w = $g->get_weight(\@edge);

Return the weight for the vertex or edge.

A vertex is a numeric value. An edge is an array reference with 2 elements. If no value is found, zero is returned.

get_attr()

$w = $g->get_attr($vertex, $attribute);
$w = $g->get_attr(\@edge, $attribute);

Return the named attribute value for the vertex or edge or zero.

TO DO

Accept hashrefs and Matrix::* objects instead of just LoLs. Also, possibly Statistics::Descriptive::Weighted.

Find the heaviest and lightest nodes.

Find the total weight beneath a node.

SEE ALSO

Graph

The eg/ and t/* sources.

AUTHOR

Gene Boggs, <gene@cpan.org>

LICENSE AND COPYRIGHT

Copyright 2003-2012 Gene Boggs

This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.

AUTHOR

Gene Boggs <gene@cpan.org>

COPYRIGHT AND LICENSE

This software is copyright (c) 2012 by Gene Boggs.

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