Gene Boggs > Graph-Weighted-0.5301 > Graph::Weighted

Download:
Graph-Weighted-0.5301.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.5301   Source  

NAME ^

Graph::Weighted - A weighted graph implementation

VERSION ^

version 0.5301

SYNOPSIS ^

  use Graph::Weighted;

  $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
    ]
  );
  my $attr = 'magnitude';
  $g->populate(
    { 0 => { 1 => 4, 3 => 6 },
      1 => { 0 => 3, 2 => 7 },
      2 => 8, # Terminal value
      3 => 9, # Terminal value
    },
    $attr
  );

  # Show each vertex and its edges.
  for my $v (sort { $a <=> $b } $g->vertices) {
    warn sprintf "vertex: %s weight=%.2f, %s=%.2f\n",
        $v, $g->get_weight($v),
        $attr, $g->get_attr($v, $attr);
    next if $g->neighbors($v) == 1;
    for my $n (sort { $a <=> $b } $g->neighbors($v)) {
        warn sprintf "\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 weighted attributes. As such, all of the Graph methods may be used as documented.

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(\@vectors, $attribute)
  $g->populate(\%data_points, $attribute)

Populate a graph with weighted nodes.

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

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)

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

syntax highlighting: