view release on metacpan or  search on metacpan

README  view on Meta::CPAN

NAME
    Algorithms::Graphs::TransitiveClosure - Calculate the transitive
    closure.

SYNOPSIS
        use Algorithms::Graphs::TransitiveClosure qw /floyd_warshall/;

        my $graph = [[1, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 0], [1, 0, 1, 1]];
        floyd_warshall $graph;
        print "There is a path from 2 to 0.\n" if $graph -> [2] -> [0];

        my $graph2 = {one   => {one => 1},
                      two   => {two => 1, three => 1, four => 1},
                      three => {two => 1, three => 1},
                      four  => {one => 1, four  => 1}};
        floyd_warshall $graph2;
        print "There is a path from three to one.\n" if
            $graph2 -> {three} -> {one};

DESCRIPTION
    This is an implementation of the well known *Floyd-Warshall* algorithm.
    [1,2]

    The subroutine "floyd_warshall" takes a directed graph, and calculates
    its transitive closure, which will be returned. The given graph is
    actually modified, so be sure to pass a copy of the graph to the routine
    if you need to keep the original graph.

    The subroutine takes graphs in one of the two following formats:

    floyd_warshall ARRAYREF
        The graph *G = (V, E)* is described with a list of lists, $graph,
        representing *V x V*. If there is an edge between vertices $i and $j
        (or if "$i == $j"), then "$graph -> [$i] -> [$j] == 1". For all
        other pairs "($k, $l)" from *V x V*, "$graph -> [$k] -> [$l] == 0".

        The resulting $graph will have "$graph -> [$i] -> [$j] == 1" iff "$i
        == $j" or there is a path in *G* from $i to $j, and "$graph -> [$i]
        -> [$j] == 0" otherwise.

    floyd_warshall HASHREF
        The graph *G = (V, E)*, with labeled vertices, is described with a
        hash of hashes, $graph, representing *V x V*. If there is an edge
        between vertices $label1 and $label2 (or if "$label1 eq $label2"),
        then "$graph -> {$label1} -> {$label2} == 1". For all other pairs
        "($label3, $label4)" from *V x V*, "$graph -> {$label3} ->
        {$label4}" does not exist.

        The resulting $graph will have "$graph -> {$label1} -> {$label2} ==
        1" iff "$label1 eq $label2" or there is a path in *G* from $label1
        to $label2, and "$graph -> {$label1} -> {$label2}" does not exist
        otherwise.

EXAMPLES
        my $graph = [[1, 0, 0, 0],
                     [0, 1, 1, 1],
                     [0, 1, 1, 0],
                     [1, 0, 1, 1]];
        floyd_warshall $graph;
        foreach my $row (@$graph) {print "@$row\n"}

        1 0 0 0
        1 1 1 1
        1 1 1 1
        1 1 1 1

        my $graph = {one   => {one => 1},
                     two   => {two => 1, three => 1, four => 1},
                     three => {two => 1, three => 1},
                     four  => {one => 1, three => 1, four => 1}};
        floyd_warshall $graph;
        foreach my $l1 (qw /one two three four/) {
            print "$l1: ";
            foreach my $l2 (qw /one two three four/) {
                next if $l1 eq $l2;
                print "$l2 " if $graph -> {$l1} -> {$l2};
            }
            print "\n";
        }

        one: 
        two: one three four 
        three: one two four 
        four: one two three

COMPLEXITY
    The running time of the algorithm is cubed in the number of vertices of