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

package Algorithm::Graphs::TransitiveClosure::Tiny;

use 5.010;
use strict;
use warnings;

use Exporter 'import';

our @EXPORT_OK = qw(floyd_warshall);

our $VERSION = '1.00';


sub floyd_warshall {
  my $graph    = shift;
  my $delEmpty = !shift;

  my @vertices = do {
    my %vertices;
    foreach my $v (keys(%$graph)) {
      if (%{$graph->{$v}}) {
        @vertices{$v, keys(%{$graph->{$v}})} = ();
      } elsif ($delEmpty) {
        delete $graph->{$v};
      }
    }
    keys %vertices;
  };
  foreach my $k (@vertices) {
    foreach my $i (@vertices) {
      foreach my $j (@vertices) {
        $graph->{$i}->{$j} = undef if (exists($graph->{$k}) && exists($graph->{$k}->{$j}) &&
                                       exists($graph->{$i}) && exists($graph->{$i}->{$k})
                                       && !exists($graph->{$i}->{$j}));
      }
    }
  }
  return $graph;
}



1; # End of Algorithm::Graphs::TransitiveClosure::Tiny




__END__