Graph::Weighted - A weighted graph implementation
version 0.9
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 ] ); $gw->dump(); 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 }, 1 => { label => 'B', 0=>0.3, 2=>0.7 }, 2 => { label => 'C', 0=>0.5, 2=>0.5 }, 3 => { label => 'D', 0=>0.2, 1=>0.8 }, }, $attr ); $gw->dump($attr);
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.
Graph::Weighted
my $gw = Graph::Weighted->new;
Return a new Graph::Weighted object.
Please see "Constructors" in Graph for the possible constructor arguments.
$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 edge values.
Math::Matrix
Math::MatrixReal
Data given as a hash reference may also contain multiple node labels. Also, the keys need not be numeric, just unique.
The optional attribute argument is a string with the default "weight."
attribute
$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. If no attribute name is given, the string "weight" is used.
($lightest, $heaviest) = $gw->vertex_span(); ($lightest, $heaviest) = $gw->vertex_span($attr);
Return the lightest and heaviest vertices as array references.
($lightest, $heaviest) = $gw->edge_span(); ($lightest, $heaviest) = $gw->edge_span($attr);
Return the lightest and heaviest edges as array references.
$c = $gw->path_cost(\@vertices); $c = $gw->path_cost(\@vertices, $attr);
Return the summed weight (or 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.
path_length
$gw->dump() $gw->dump($attr)
Print out the graph showing vertices, edges and costs.
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";
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";
Graph, the parent of this module
Graph::Easy::Weighted, the sibling
The eg/* and t/* file sources
Gene Boggs <gene@cpan.org>
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.
To install Graph::Weighted, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Weighted
CPAN shell
perl -MCPAN -e shell install Graph::Weighted
For more information on module installation, please visit the detailed CPAN module installation guide.