NAME
Graph::Weighted - A weighted graph implementation
VERSION
version 0.60
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_cost($vertex);
for my $neighbor (sort { $a <=> $b } $gw->neighbors($vertex)) {
warn sprintf "\tedge to: %s weight=%.2f\n",
$neighbor, $gw->get_cost([$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::Matrix object, 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()
$c = $gw->get_cost($vertex);
$c = $gw->get_cost($vertex, $attribute);
$c = $gw->get_cost(\@edge);
$c = $gw->get_cost(\@edge, $attribute);Return the named attribute value for the vertex or edge.
vertex_span()
($lightest, $heaviest) = $gw->vertex_span();
($lightest, $heaviest) = $gw->vertex_span($attr);Return the lightest and heaviest vertices.
edge_span()
($lightest, $heaviest) = $gw->edge_span();
($lightest, $heaviest) = $gw->edge_span($attr);Return the lightest to heaviest edges.
path_cost()
$c = $gw->path_cost(\@vertices);
$c = $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.