#!/usr/bin/perl

# APSP_Floyd_Warshall
#
#       $APSP = $G->APSP_Floyd_Warshall
#
#       Returns the All-pairs Shortest Paths graph of the graph $G
#       computed using the Floyd-Warshall algorithm and the attribute
#       'weight' on the edges.
#       The returned graph has an edge for each shortest path.
#       An edge has attributes "weight" and "path"; for the length of
#       the shortest path and for the path (an anonymous list) itself.
#

sub APSP_Floyd_Warshall {
    my $G = shift;
    my @V = $G->vertices;
    my @E = $G->edges;
    my (%V2I, @I2V);
    my (@P, @W);

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

    # Initialize the predecessor matrix @P and the weight matrix @W.
    # (The graph is converted into adjacency-matrix representation.)
    # (The matrix is a list of lists.)
    foreach my $i ( 0..$#V ) { $W[ $i ][ $i ] = 0 }
    while ( my ($u, $v) = splice(@E, 0, 2) ) {
        my ( $ui, $vi ) = ( $V2I{ $u }, $V2I{ $v } );
        $P[ $ui ][ $vi ] = $ui unless $ui == $vi;
        $W[ $ui ][ $vi ] = $G->get_attribute( 'weight', $u, $v );
    }

    # Do the O(N**3) loop.
    for ( my $k = 0; $k < @V; $k++ ) {
        my (@nP, @nW); # new @P, new @W

        for ( my $i = 0; $i < @V; $i++ ) {
            for ( my $j = 0; $j < @V; $j++ ) {
                my $w_ij    = $W[ $i ][ $j ];
                my $w_ik_kj = $W[ $i ][ $k ] + $W[ $k ][ $j ]
                    if defined $W[ $i ][ $k ] and
                       defined $W[ $k ][ $j ];

                # Choose the minimum of w_ij and w_ik_kj.
                if ( defined $w_ij ) {
                    if ( defined $w_ik_kj ) {
                        if ( $w_ij <= $w_ik_kj ) {
                          $nP[ $i ][ $j ] = $P[ $i ][ $j ];
                          $nW[ $i ][ $j ] = $w_ij;
                        } else {
                          $nP[ $i ][ $j ] = $P[ $k ][ $j ];
                          $nW[ $i ][ $j ] = $w_ik_kj;
                        }
                    } else {
                        $nP[ $i ][ $j ] = $P[ $i ][ $j ];
                        $nW[ $i ][ $j ] = $w_ij;
                    }
                } elsif ( defined $w_ik_kj ) {
                    $nP[ $i ][ $j ] = $P[ $k ][ $j ];
                    $nW[ $i ][ $j ] = $w_ik_kj;
                }
            }
        }

        @P = @nP; @W = @nW; # Update the predecessors and weights.
    }

    # Now construct the APSP graph.

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

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

    # Convert the adjacency-matrix representation
    # into a Graph (adjacency-list representation).
    for ( my $i = 0; $i < @V; $i++ ) {
        my $iv = $I2V[ $i ];

        for ( my $j = 0; $j < @V; $j++ ) {
            if ( $i == $j ) {
                $APSP->add_weighted_edge( $iv, 0, $iv );
                $APSP->set_attribute("path", $iv, $iv, [ $iv ]);
                next;
            }
            next unless defined $W[ $i ][ $j ];

            my $jv = $I2V[ $j ];

            $APSP->add_weighted_edge( $iv, $W[ $i ][ $j ], $jv );

            my @path = ( $jv );
            if ( $P[ $i ][ $j ] != $i ) {
                my $k = $P[ $i ][ $j ];  # Walk back the path.

                while ( $k != $i ) {
                    push @path, $I2V[ $k ];
                    $k = $P[ $i ][ $k ]; # Keep walking.
                }
            }
            $APSP->set_attribute( "path", $iv, $jv,
                                     [ $iv, reverse @path ] );
        }
    }

    return $APSP;
}

use Graph::Directed;

my $g = Graph::Directed->new;

$g->add_weighted_path(qw(a 1 b 4 c 1 d));
$g->add_weighted_path(qw(a 3 f 1 e 2 d));
$g->add_weighted_edges(qw(a 2 c  a 4 d  b 2 e  f 2 d));

my $APSP = $g->APSP_Floyd_Warshall;

print "      ";
foreach my $v ( $APSP->vertices ) { printf "%-9s ", "$v" } print "\n";
foreach my $u ( $APSP->vertices ) {
    print "$u: ";
    foreach my $v ( $APSP->vertices ) {
        my $w = $APSP->get_attribute("weight", $u, $v);

        if (defined $w) {
            my $p = $APSP->get_attribute("path",   $u, $v);

            printf "(%-5s)=%d ", "@$p", $w
        } else {
            printf "%-9s ", "-"
        }
    }
    print "\n";
}