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

NAME

Graph::Weighted - A weighted graph implementation

VERSION

version 0.5907

SYNOPSIS

use Graph::Weighted;

my $gw = Graph::Weighted->new();
$gw->populate(
   [ [ 0,1,2,0,0 ], # Vertex 0 with 2 edges of weight 3
     [ 1,0,3,0,0 ], #    "   1      2 "               4
     [ 2,3,0,0,0 ], #    "   2      2 "               5
     [ 0,0,1,0,0 ], #    "   3      1 "               1
     [ 0,0,0,0,0 ], #    "   4      0 "               0
   ]
);
for my $vertex (sort { $a <=> $b } $gw->vertices) {
   warn sprintf "vertex: %s weight=%.2f\n",
       $vertex, $gw->get_weight($vertex);
   for my $neighbor (sort { $a <=> $b } $gw->neighbors($vertex)) {
       warn sprintf "\tedge to: %s weight=%.2f\n",
           $neighbor, $gw->get_weight([$vertex, $neighbor]);
   }
}

my ($lightest, $heaviest) = $gw->vertex_span();
($lightest, $heaviest) = $gw->edge_span();

my $weight = $gw->path_cost(\@vertices);

my $attr = 'probability';
$gw = Graph::Weighted->new();
$gw->populate(
   {
       0 => { label => 'A', 1=>0.4, 3=>0.6 }, # Vertex A with 2 edges, weight 1
       1 => { label => 'B', 0=>0.3, 2=>0.7 }, # Vertex B "    2 "
       2 => { label => 'C', 0=>0.5, 2=>0.5 }, # Vertex C "    2 "
       3 => { label => 'D', 0=>0.2, 1=>0.8 }, # Vertex D "    2 "
   },
   $attr
);
for my $vertex (sort { $a <=> $b } $gw->vertices) {
   warn sprintf "%s vertex: %s %s=%.2f\n",
       $gw->get_vertex_attribute($vertex, 'label'),
       $vertex, $attr, $gw->get_cost($vertex, $attr);
   for my $neighbor (sort { $a <=> $b } $gw->neighbors($vertex)) {
       warn sprintf "\tedge to: %s %s=%.2f\n",
           $neighbor, $attr, $gw->get_cost([$vertex, $neighbor], $attr);
   }
}

DESCRIPTION

A Graph::Weighted object is a subclass of the Graph module with attribute handling. As such, all of the Graph methods may be used, with the addition of custom weighting.

METHODS

new()

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

Return a new Graph::Weighted object.

Please see "Constructors" in Graph for the possible constructor arguments.

populate()

$gw->populate($matrix);
$gw->populate($matrix, $attribute);
$gw->populate(\@vectors);
$gw->populate(\@vectors, $attribute);
$gw->populate(\%data_points);
$gw->populate(\%data_points, $attribute);

Populate a graph with weighted nodes.

The data can be an arrayref of numeric vectors, a Math::MatrixReal object, or a hashref of numeric edge values.

Data given as a hash reference may also contain an optional node label, as shown in the SYNOPSIS.

The optional edge attribute argument is a string with the default "weight."

Multiple attributes may be applied to a graph, thereby layering and increasing the overall dimension.

Examples of vertices in array reference form:

[]      1 vertex with no edges.
[0]     1 vertex with no edges.
[1]     1 vertex and 1 edge to itself, weight 1.
[0,1]   2 vertices and 1 edge, weight 1.
[1,0,9] 3 vertices and 2 edges having, weight 10.
[1,2,3] 3 vertices and 3 edges having, weight 6.

get_weight()

$w = $gw->get_weight($vertex);
$w = $gw->get_weight([$vertex, $neighbor]);

Return the weight for the vertex or edge.

get_cost()

$w = $gw->get_cost($vertex);
$w = $gw->get_cost($vertex, $attribute);
$w = $gw->get_cost(\@edge);
$w = $gw->get_cost(\@edge, $attribute);

Return the named attribute value for the vertex or edge.

vertex_span()

my ($lightest, $heaviest) = $gw->vertex_span();
my ($lightest, $heaviest) = $gw->vertex_span($attr);

Return the lightest and heaviest vertices.

edge_span()

my ($lightest, $heaviest) = $gw->edge_span();
my ($lightest, $heaviest) = $gw->edge_span($attr);

Return the lightest to heaviest edges.

path_cost()

my $weight = $gw->path_cost(\@vertices);
my $weight = $gw->path_cost(\@vertices, $attr);

Return the summed weight (or given cost attribute) of the path edges.

For the cost of the shortest path, please see path_length under "All-Pairs Shortest Paths (APSP)" in Graph.

EXAMPLES

Shortest Paths

my $g = Graph::Weighted->new();
$g->populate({
  A => { B => 4, C => 2 },
  B => { C => 5, D => 10 },
  C => { E => 3 },
  D => { F => 11 },
  E => { D => 4 },
  F => { },
});
my @path = $g->SP_Dijkstra( 'A', 'F' ); # A->C->E->D->F
print 'Dijkstra: ', join( '->', @path ), "\n";

$g = Graph::Weighted->new();
$g->populate({
  S => { A =>  7, B => 6 },
  A => { C => -3, T => 9 },
  B => { A =>  8, C => 5, T => -4 },
  C => { B => -5 },
  T => { },
});
@path = $g->SP_Bellman_Ford( 'S', 'T' ); # S->A->C->B->T
print 'Bellman-Ford: ', join( '->', @path ), "\n";

$g = Graph::Weighted->new();
$g->populate({
  1 => { 2 => 8, 4 => 1 },
  2 => { 3 => 1 },
  3 => { 1 => 4 },
  4 => { 2 => 2, 3 => 9 },
});
my $apsp = $g->APSP_Floyd_Warshall();
@path = $apsp->path_vertices( 1, 3 ); # 1->4->2->3
print 'Floyd-Warshall: ', join( '->', @path ), "\n";

Minimum Spanning Trees

my $g = Graph::Weighted->new( undirected => 1 );
$g->populate({
      A => { B => 4, F => 2 },
      B => { C => 6, F => 5 },
      C => { F => 1 },
      D => { },
});

my @path = $g->MST_Kruskal; # A=B,A=F,C=F
print 'Kruskal: ', join( '->', @path ), "\n";

@path = $g->MST_Prim; # same
print 'Prim: ', join( '->', @path ), "\n";

SEE ALSO

Graph, the parent of this module

Graph::Easy::Weighted, the sibling

The eg/* and t/* file sources

AUTHOR

Gene Boggs <gene@cpan.org>

COPYRIGHT AND LICENSE

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