File Coverage

blib/lib/Algorithm/Graphs/TransitiveClosure/Tiny.pm
Criterion Covered Total %
statement 27 27 100.0
branch 6 6 100.0
condition 12 12 100.0
subroutine 5 5 100.0
pod 0 1 0.0
total 50 51 98.0


line stmt bran cond sub pod time code
1             package Algorithm::Graphs::TransitiveClosure::Tiny;
2            
3 2     2   109812 use 5.010;
  2         15  
4 2     2   10 use strict;
  2         3  
  2         53  
5 2     2   14 use warnings;
  2         4  
  2         53  
6            
7 2     2   8 use Exporter 'import';
  2         3  
  2         458  
8            
9             our @EXPORT_OK = qw(floyd_warshall);
10            
11             our $VERSION = '1.01';
12            
13            
14             sub floyd_warshall {
15 9     9 0 7235 my $graph = shift;
16 9         15 my $delEmpty = !shift;
17            
18 9         14 my @vertices = do {
19 9         10 my %vertices;
20 9         23 foreach my $v (keys(%$graph)) {
21 26 100       31 if (%{$graph->{$v}}) {
  26 100       47  
22 24         28 @vertices{$v, keys(%{$graph->{$v}})} = ();
  24         57  
23             } elsif ($delEmpty) {
24 1         3 delete $graph->{$v};
25             }
26             }
27 9         23 keys %vertices;
28             };
29 9         15 foreach my $k (@vertices) {
30 28         39 foreach my $i (@vertices) {
31 106         121 foreach my $j (@vertices) {
32             $graph->{$i}->{$j} = undef if (exists($graph->{$k}) && exists($graph->{$k}->{$j}) &&
33             exists($graph->{$i}) && exists($graph->{$i}->{$k})
34 424 100 100     1279 && !exists($graph->{$i}->{$j}));
      100        
      100        
      100        
35             }
36             }
37             }
38 9         21 return $graph;
39             }
40            
41            
42            
43             1; # End of Algorithm::Graphs::TransitiveClosure::Tiny
44            
45            
46            
47            
48             __END__