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

package Algorithm::Graphs::TransitiveClosure;

use 5.006;

use strict;
use warnings;
no  warnings 'syntax';

use Exporter ();

our @ISA       = qw /Exporter/;
our @EXPORT    = qw //;
our @EXPORT_OK = qw /floyd_warshall/;

our $VERSION   = '2009110901';


sub floyd_warshall ($) {
    my $graph = shift;
    if (ref $graph eq 'HASH') {
        my @vertices = keys %{$graph};

        foreach my $k (@vertices) {
            foreach my $i (@vertices) {
                foreach my $j (@vertices) {
                    # Don't use ||= here, to avoid autovivication.
                    $graph -> {$i} -> {$j} = 1 if $graph -> {$k} -> {$j} &&
                                                  $graph -> {$i} -> {$k};
                }
            }
        }
    }
    elsif (ref $graph eq 'ARRAY') {
        my $count = @{$graph};
        for (my $k = 0; $k < $count; $k ++) {
            for (my $i = 0; $i < $count; $i ++) {
                for (my $j = 0; $j < $count; $j ++) {
                    $graph -> [$i] -> [$j] ||= $graph -> [$k] -> [$j] &&
                                               $graph -> [$i] -> [$k];
                }
            }
        }
    }

    $graph;
}

1;

__END__