File Coverage

blib/lib/Algorithm/Graphs/TransitiveClosure.pm
Criterion Covered Total %
statement 30 30 100.0
branch 5 6 83.3
condition 9 9 100.0
subroutine 6 6 100.0
pod 1 1 100.0
total 51 52 98.0


line stmt bran cond sub pod time code
1             package Algorithm::Graphs::TransitiveClosure;
2              
3 1     1   1527 use 5.006;
  1         4  
  1         43  
4              
5 1     1   5 use strict;
  1         2  
  1         35  
6 1     1   5 use warnings;
  1         15  
  1         37  
7 1     1   79 no warnings 'syntax';
  1         1  
  1         46  
8              
9 1     1   5 use Exporter ();
  1         1  
  1         334  
10              
11             our @ISA = qw /Exporter/;
12             our @EXPORT = qw //;
13             our @EXPORT_OK = qw /floyd_warshall/;
14              
15             our $VERSION = '2009110901';
16              
17              
18             sub floyd_warshall ($) {
19 2     2 1 75 my $graph = shift;
20 2 100       11 if (ref $graph eq 'HASH') {
    50          
21 1         3 my @vertices = keys %{$graph};
  1         5  
22              
23 1         4 foreach my $k (@vertices) {
24 4         13 foreach my $i (@vertices) {
25 16         20 foreach my $j (@vertices) {
26             # Don't use ||= here, to avoid autovivication.
27 64 100 100     529 $graph -> {$i} -> {$j} = 1 if $graph -> {$k} -> {$j} &&
28             $graph -> {$i} -> {$k};
29             }
30             }
31             }
32             }
33             elsif (ref $graph eq 'ARRAY') {
34 1         2 my $count = @{$graph};
  1         2  
35 1         4 for (my $k = 0; $k < $count; $k ++) {
36 4         8 for (my $i = 0; $i < $count; $i ++) {
37 16         31 for (my $j = 0; $j < $count; $j ++) {
38 64   100     242 $graph -> [$i] -> [$j] ||= $graph -> [$k] -> [$j] &&
      100        
39             $graph -> [$i] -> [$k];
40             }
41             }
42             }
43             }
44              
45 2         5 $graph;
46             }
47              
48             1;
49              
50             __END__