# Flow_Edmonds_Karp
#
#       $F = $G->Flow_Edmonds_Karp($source, $sink)
#
#       Return the maximal flow network of the graph $G built
#       using the Edmonds-Karp version of Ford-Fulkerson.
#       The input graph $G must have 'capacity' attributes on
#       its edges; resulting flow graph will have 'capacity' and 'flow'
#       attributes on its edges.
#
sub Flow_Edmonds_Karp {
    my ( $G, $source, $sink ) = @_;

    my $S;

    $S->{ source } = $source;
    $S->{ sink   } = $sink;
    $S->{ next_augmenting_path } =
        sub {
            my ( $F, $S ) = @_;

            my $source = $S->{ source };
            my $sink   = $S->{ sink   };

            # Initialize our "todo" heap.
            unless ( exists $S->{ todo } ) {
                # The first element is a hash recording the vertices
                # seen so far, the rest are the path from the source.
                push @{ $S->{ todo } },
                     [ { $source => 1 }, $source ];
            }

            while ( @{ $S->{ todo } } ) {
                # $ap: The next augmenting path.
                my $ap = shift @{ $S->{ todo } };
                my $sv = shift @$ap;    # The seen vertices.
                my $v  = $ap->[ -1 ];   # The last vertex of path.

                if ( $v eq $sink ) {
                    return $ap;
                } else {
                    foreach my $s ( $G->successors( $v ) ) {
                        unless ( exists $sv->{ $s } ) {
                            push @{ $S->{ todo } },
                                [ { %$sv, $s => 1 }, @$ap, $s ];
                        }
                    }
                }
            }
        };

    return $G->Flow_Ford_Fulkerson( $S );
}

use Graph;

my $roads = Graph->new;

# add_capacity_path() is defined using add_path()
# and set_attribute('capacity', ...).
$roads->add_capacity_path( qw( CoolCity 20 VanillaFlats 18
                               HotCity ) );
$roads->add_capacity_path( qw( CoolCity 5 StrawberryFields 7
                               HotCity ) );
$roads->add_capacity_path( qw( CoolCity 10 ChocolateGulch 8
                               PecanPeak 10 BlueberryWoods 6
                               HotCity ) );
$roads->add_capacity_path( qw( ChocolateGulch 3 StrawberryFields 0
                               StrawberryFields ) );
$roads->add_capacity_path( qw( BlueberryWoods 15 StrawberryFields ) );
$roads->add_capacity_path( qw( VanillaFlats 11 StrawberryFields ) );
$roads->add_capacity_path( qw( PecanPeak 12 StrawberryFields ) );

my $f = $roads->Flow_Edmonds_Karp( 'CoolCity', 'HotCity' );
my @e = $f->edges;

my (@E, @C, @F);
while (my ($u, $v) = splice(@e, 0, 2)) {
    push @E, [ $u, $v ];
    push @C, $f->get_attribute("capacity", $u, $v);
    push @F, $f->get_attribute("flow",     $u, $v);
}

foreach my $e ( map { $_->[0] }
                    sort { $b->[3]      <=> $b->[3] ||
                           $b->[2]      <=> $a->[2] ||
                           $a->[1]->[0] cmp $b->[1]->[0] ||
                           $a->[1]->[1] cmp $b->[1]->[1] }
                        map { [ $_, $E[$_], $C[$_], $F[$_] ] }
                            0..$#E ) {
    printf "%-40s %2d/%2d\n",
           $E[$e]->[0] . "-" . $E[$e]->[1], $F[$e], $C[$e]
}