NAME
Graph::Weighted - A weighted graph implementation
VERSION
version 0.5906
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 as documented (e.g. "SHORTEST PATHS"), but 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.
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";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.