| Subject: | radius method incorrect |
The ->radius() method is implemented incorrectly.
In the pod it is defined as: "The shortest longest path over all the
vertex pairs is known as the graph radius" but the method actually
computes the shortest shortest path! As a result, the value returned for
radius is generally too low, and makes ->center_vertices() return nothing.
See http://mathworld.wolfram.com/GraphRadius.html
As a workaround for the center_vertices method, I've used:
my ($center, $radius) = (undef, 1_000_000);
for (@words) {
my $x = $apsp->vertex_eccentricity($_);
($center, $radius) = ($_, $x) if $x < $radius;
}
which does seem to return a correct center (I only needed one center).
I've attached a test case based on the graph from the mathworld link above.
| Subject: | test.pl |
use Graph;
use Test::More 'no_plan';
my $g = Graph::Undirected->new;
# example graph #1 from http://mathworld.wolfram.com/GraphRadius.html
#
# A
# |
# B
# / | \
# C D E
# | |
# F G
$g->add_edge( split //, $_ )
for qw[ AB BC BD BE CF EG ];
my $apsp = $g->all_pairs_shortest_paths;
diag( $Graph::VERSION );
is( $apsp->radius, 2, "radius" );
is_deeply( [$apsp->center_vertices], ["B"], "center_vertices" );
__DATA__
# 0.81
not ok 1 - radius
# Failed test 'radius'
# in test.pl at line 22.
# got: '1'
# expected: '2'
not ok 2 - center_vertices
# Failed test 'center_vertices'
# in test.pl at line 25.
# Structures begin differing at:
# $got->[0] = Does not exist
# $expected->[0] = 'B'
1..2
# Looks like you failed 2 tests of 2.