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

NAME

Graph::Weighted - A weighted graph implementation

VERSION

version 0.5303

SYNOPSIS

use Graph::Weighted;

$g->populate([
  [ 0, 1, 2, 0, 0 ], # V 0
  [ 1, 0, 3, 0, 0 ], # V 1
  [ 2, 3, 0, 0, 0 ], # V 2
  [ 0, 0, 1, 0, 0 ], # One lonely edge weighing one lonely unit.
  [ 0, 0, 0, 0, 0 ], # V 4 weighs nothing.
]);

my $attr = 'magnitude';

# Vertex 0 has 2 edges (1,3) of magnitude (4,6).
$g->populate({
    0 => { 1 => 4, 3 => 6 },
    1 => { 0 => 3, 2 => 7 },
    2 => 8, # Terminal value
    3 => 9, # Terminal value
  },
  $attr
);

# Show each (numeric) vertex.
for my $v (sort { $a <=> $b } $g->vertices) {
  printf "vertex: %s weight=%.2f, %s=%.2f\n",
      $v,    $g->get_weight($v),
      $attr, $g->get_attr($v, $attr);

  next if $g->neighbors($v) == 1;

  # Show each (numeric) edge.
  for my $n (sort { $a <=> $b } $g->neighbors($v)) {
      printf "\tedge to: %s weight=%.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 the Graph module with concise attribute handling (e.g. weight). As such, all of the Graph methods may be used as documented, but with the addition of custom weighting.

The built-in weighted node and edges can be defined literally, in a matrix or hash, or as callbacks to functions that return matrices or hashes based on the provided data.

METHODS

new()

my $g = Graph::Weighted->new;

Return a new Graph::Weighted object.

Please see Graph for the myriad possible constructor arguments.

populate()

$g->populate(\@vectors);
$g->populate(\@vectors, $attribute);
$g->populate(\%data_points, $attribute);
$g->populate($data, $attribute, \&vertex_method, \&edge_method);

Populate a graph with weighted nodes.

For arguments, the data can be a numeric value ("terminal node"), an arrayref of numeric vectors or a hashref of numeric edge values. The attribute is an optional string name, of default "weight." The vertex_method and edge_method are optional code-references giving alternate weighting functions.

Examples of data in array reference form, using the default vertex and edge methods:

[]      No edges.
[0]     1 vertex and 1 edge to node 0 having weight of 0.
[1]     1 vertex and 1 edge to node 0 weight 1.
[0,1]   2 vertices and 2 edges having edge weights 0,1 and vertex weight 1.
[0,1,9] 3 vertices and 3 edges having edge weights 0,1,9 and vertex weight 10.

An edge weight of zero can mean anything you wish. If weights are seen as conversation among associates, "In the same room" might be a good analogy, a value of zero would mean "no conversation."

The attribute is named 'weight' by default, but can be anything you like. Multiple attributes may be applied to a graph, thereby layering increasing the overall dimension.

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

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

The default edge weighting function (edge_method) simply returns the value in the node's neighbor position. Likewise, an alternative may be provided, as a callback, as with the vertex_weight_function. 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 Matrix::* objects.

Statistics::Descriptive::Weighted must be investigated...

Find the heaviest and lightest nodes and edges.

Find the total weight beneath (and above?) a node.

SEE ALSO

Graph

The eg/* and t/* file sources.

AUTHOR

Gene Boggs <gene@cpan.org>

COPYRIGHT AND LICENSE

This software is copyright (c) 2013 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.