#!/usr/bin/perl

# TransitiveClosure_Floyd_Warshall
#
#       $TransitiveClosure = $G->TransitiveClosure_Floyd_Warshall
#
#       Returns the Transitive Closure graph of the graph $G computed
#       using the Floyd-Warshall algorithm.
#       The resulting graph has an edge between each *ordered* pair of
#       vertices in which the second vertex is reachable from the first.
#

sub TransitiveClosure_Floyd_Warshall {
    my $G = shift;
    my @V = $G->vertices;
    my @E = $G->edges;
    my (%V2I, @I2V);
    my @C = ( '' ) x @V;

    # Compute the vertex <-> index mappings.
    @V2I{ @V     } = 0..$#V;
    @I2V[ 0..$#V ] = @V;

    # Initialize the closure matrix @C.
    # (The graph is converted into adjacency-matrix representation.)
    # (The matrix is a bit matrix.  Well, a list of bit vectors.)
    foreach my $i ( 0..$#V ) { vec( $C[ $i ], $i, 1 ) = 1 }
    while ( my ($u, $v) = splice(@E, 0, 2) ) {
        vec( $C[ $V2I{ $u } ], $V2I{ $v }, 1 ) = 1
    }

    # Do the O(N**3) loop.
    for ( my $k = 0; $k < @V; $k++ ) {
        my @nC = ( '' ) x @V; # new @C

        for ( my $i = 0; $i < @V; $i++ ) {
            for ( my $j = 0; $j < @V; $j++ ) {
                vec( $nC[ $i ], $j, 1 ) =
                  vec( $C[ $i ], $j, 1 ) |
                    vec( $C[ $i ], $k, 1 ) & vec( $C[ $k ], $j, 1 );
            }
        }

        @C = @nC; # Update the closure.
    }

    # Now construct the TransitiveClosure graph.

    my $TransitiveClosure = (ref $G)->new;

    $TransitiveClosure->directed( $G->directed ); # Copy the directedness.

    # Convert the (closure-)adjacency-matrix representation
    # into a Graph (adjacency-list representation).
    for ( my $i = 0; $i < @V; $i++ ) {
        for ( my $j = 0; $j < @V; $j++ ) {
            $TransitiveClosure->add_edge( $I2V[ $i ], $I2V[ $j ] )
                if vec( $C[ $i ], $j, 1 );
        }
    }

    return $TransitiveClosure;
}