| 1 | package Graph::MaxFlow; | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | 1 | require Exporter; | |||||||||||||||||||||||||||
| 4 | 1 | ▶ | use Graph; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 5 | 1 | ▶ | use Carp 'carp'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 6 | |||||||||||||||||||||||||||||
| 7 | 1 | @ISA = qw(Exporter); | |||||||||||||||||||||||||||
| 8 | 1 | @EXPORT_OK = qw(max_flow); | |||||||||||||||||||||||||||
| 9 | |||||||||||||||||||||||||||||
| 10 | 1 | $VERSION = '0.04'; | |||||||||||||||||||||||||||
| 11 | |||||||||||||||||||||||||||||
| 12 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 13 | 1 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 14 | |||||||||||||||||||||||||||||
| 15 | # Edmonds-Karp algorithm to find the maximum flow in $g between | ||||||||||||||||||||||||||||
| 16 | # $source and $sink | ||||||||||||||||||||||||||||
| 17 | 2 | ▶ | sub max_flow { | ||||||||||||||||||||||||||
|
Subroutine
max_flow: called CC=10 SCAR=23.4
Pod
documented
| |||||||||||||||||||||||||||||
| 18 | 2 | my ($g, $source, $sink) = @_; | |||||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||||||
| 20 | 2 | ▶ | if ($g->is_undirected) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 21 | 0 | carp "Graph must be directed"; | |||||||||||||||||||||||||||
| 22 | 0 | return; | |||||||||||||||||||||||||||
| 23 | } | ||||||||||||||||||||||||||||
| 24 | |||||||||||||||||||||||||||||
| 25 | 2 | ▶ | if ($g->vertices < 2) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 26 | 0 | carp "Graph must have at least 2 vertices"; | |||||||||||||||||||||||||||
| 27 | 0 | return; | |||||||||||||||||||||||||||
| 28 | } | ||||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||
| 30 | 2 | my $resid = init_flow($g); | |||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||
| 32 | 2 | while (1) { | |||||||||||||||||||||||||||
| 33 | # find the shortest augmenting path between $source and $sink | ||||||||||||||||||||||||||||
| 34 | 8 | my $path = shortest_path($g, $resid, $source, $sink); | |||||||||||||||||||||||||||
| 35 | 8 | ▶ | last unless @$path; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||
| 37 | # find min weight in path | ||||||||||||||||||||||||||||
| 38 | 6 | my $min; | |||||||||||||||||||||||||||
| 39 | 6 | for my $i (0..$#$path - 1) { | |||||||||||||||||||||||||||
| 40 | 19 | my $weight = residual_capacity($g, $resid, $path->[$i], $path->[$i+1]); | |||||||||||||||||||||||||||
| 41 | 19 | ▶ | $min = $weight if !defined $min || $weight < $min; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
not defined $min or $weight < $min
MC/DC100%2/2
not defined $min or $weight < $min
not defined $min
$weight < $min
Truth table100%3/3
not(A) or B
A= not defined $minB= $weight < $min
| |||||||||||||||||||||||||||||
| 42 | } | ||||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||
| 44 | # update the flow network | ||||||||||||||||||||||||||||
| 45 | 6 | for my $i (0..$#$path - 1) { | |||||||||||||||||||||||||||
| 46 | 19 | add_edge_weight($resid, $path->[$i], $path->[$i+1], $min); | |||||||||||||||||||||||||||
| 47 | 19 | add_edge_weight($resid, $path->[$i+1], $path->[$i], -$min); | |||||||||||||||||||||||||||
| 48 | } | ||||||||||||||||||||||||||||
| 49 | |||||||||||||||||||||||||||||
| 50 | } | ||||||||||||||||||||||||||||
| 51 | |||||||||||||||||||||||||||||
| 52 | # convert the residual flow graph into a copy of the original | ||||||||||||||||||||||||||||
| 53 | # graph, but with the edge weights set to the flow | ||||||||||||||||||||||||||||
| 54 | 2 | my $flow = $g->copy_graph; | |||||||||||||||||||||||||||
| 55 | 2 | for my $e ($flow->edges) { | |||||||||||||||||||||||||||
| 56 | 27 | my ($u, $v) = @$e; | |||||||||||||||||||||||||||
| 57 | 27 | my $weight = $resid->get_edge_weight($u, $v); | |||||||||||||||||||||||||||
| 58 | 27 | ▶ | $flow->set_edge_weight($u, $v, $weight > 0 ? $weight : 0); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 59 | } | ||||||||||||||||||||||||||||
| 60 | |||||||||||||||||||||||||||||
| 61 | 2 | return $flow; | |||||||||||||||||||||||||||
| 62 | } | ||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||
| 64 | # init the flow so that f(u,v) = 0 for all edges | ||||||||||||||||||||||||||||
| 65 | 2 | ▶ | sub init_flow { | ||||||||||||||||||||||||||
|
Subroutine
init_flow: called CC=2 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 66 | 2 | my $g = shift; | |||||||||||||||||||||||||||
| 67 | 2 | my $flow = new Graph; | |||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||
| 69 | 2 | for my $e ($g->edges) { | |||||||||||||||||||||||||||
| 70 | 27 | $flow->add_weighted_edge($e->[0], $e->[1], 0); | |||||||||||||||||||||||||||
| 71 | 27 | $flow->add_weighted_edge($e->[1], $e->[0], 0); | |||||||||||||||||||||||||||
| 72 | } | ||||||||||||||||||||||||||||
| 73 | |||||||||||||||||||||||||||||
| 74 | 2 | return $flow; | |||||||||||||||||||||||||||
| 75 | } | ||||||||||||||||||||||||||||
| 76 | |||||||||||||||||||||||||||||
| 77 | # do a breadth-first search over edges with positive residual capacity | ||||||||||||||||||||||||||||
| 78 | 8 | ▶ | sub shortest_path { | ||||||||||||||||||||||||||
|
Subroutine
shortest_path: called CC=8 SCAR=20.8
Pod
undocumented
| |||||||||||||||||||||||||||||
| 79 | 8 | my ($g, $flow, $from, $to) = @_; | |||||||||||||||||||||||||||
| 80 | |||||||||||||||||||||||||||||
| 81 | 8 | my %parent; | |||||||||||||||||||||||||||
| 82 | my @next; | ||||||||||||||||||||||||||||
| 83 | |||||||||||||||||||||||||||||
| 84 | 8 | $parent{$from} = undef; | |||||||||||||||||||||||||||
| 85 | 8 | $next[0] = $from; | |||||||||||||||||||||||||||
| 86 | 8 | my $found = 0; | |||||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||||||
| 88 | # loop until we either reach $to or run out of nodes in the @next queue | ||||||||||||||||||||||||||||
| 89 | 8 | ▶ | while (@next) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 90 | 58 | my $u = shift @next; | |||||||||||||||||||||||||||
| 91 | 58 | ▶ | if ($u eq $to) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 92 | 6 | $found = 1; | |||||||||||||||||||||||||||
| 93 | 6 | last; | |||||||||||||||||||||||||||
| 94 | } | ||||||||||||||||||||||||||||
| 95 | |||||||||||||||||||||||||||||
| 96 | 52 | for my $v ($g->neighbors($u)) { | |||||||||||||||||||||||||||
| 97 | 161 | ▶ | next if exists $parent{$v}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 98 | 74 | ▶ | next unless residual_capacity($g, $flow, $u, $v) > 0; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 99 | 54 | $parent{$v} = $u; | |||||||||||||||||||||||||||
| 100 | 54 | push @next, $v; | |||||||||||||||||||||||||||
| 101 | } | ||||||||||||||||||||||||||||
| 102 | } | ||||||||||||||||||||||||||||
| 103 | |||||||||||||||||||||||||||||
| 104 | # reconstruct path | ||||||||||||||||||||||||||||
| 105 | 8 | my @path; | |||||||||||||||||||||||||||
| 106 | 8 | ▶ | if ($found) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 107 | 6 | my $u = $to; | |||||||||||||||||||||||||||
| 108 | 6 | ▶ | while (defined $parent{$u}) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 109 | 19 | unshift @path, $u; | |||||||||||||||||||||||||||
| 110 | 19 | $u = $parent{$u}; | |||||||||||||||||||||||||||
| 111 | } | ||||||||||||||||||||||||||||
| 112 | 6 | unshift @path, $from; | |||||||||||||||||||||||||||
| 113 | } | ||||||||||||||||||||||||||||
| 114 | |||||||||||||||||||||||||||||
| 115 | 8 | return \@path; | |||||||||||||||||||||||||||
| 116 | } | ||||||||||||||||||||||||||||
| 117 | |||||||||||||||||||||||||||||
| 118 | # add $delta to the weight of the edge ($u, $v) | ||||||||||||||||||||||||||||
| 119 | 38 | ▶ | sub add_edge_weight { | ||||||||||||||||||||||||||
|
Subroutine
add_edge_weight: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 120 | 38 | my ($g, $u, $v, $delta) = @_; | |||||||||||||||||||||||||||
| 121 | |||||||||||||||||||||||||||||
| 122 | 38 | my $weight = $g->get_edge_weight($u, $v); | |||||||||||||||||||||||||||
| 123 | 38 | $g->set_edge_weight($u, $v, $weight + $delta); | |||||||||||||||||||||||||||
| 124 | } | ||||||||||||||||||||||||||||
| 125 | |||||||||||||||||||||||||||||
| 126 | # returns the residual capacity between $u and $v | ||||||||||||||||||||||||||||
| 127 | 93 | ▶ | sub residual_capacity { | ||||||||||||||||||||||||||
|
Subroutine
residual_capacity: called CC=2 SCAR=6.9
Pod
undocumented
| |||||||||||||||||||||||||||||
| 128 | 93 | my ($g, $flow, $u, $v) = @_; | |||||||||||||||||||||||||||
| 129 | |||||||||||||||||||||||||||||
| 130 | 93 | ▶ | if ($g->has_edge($u, $v)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 131 | 82 | return $g->get_edge_weight($u, $v) - $flow->get_edge_weight($u, $v); | |||||||||||||||||||||||||||
| 132 | } else { | ||||||||||||||||||||||||||||
| 133 | 11 | return -$flow->get_edge_weight($u, $v); | |||||||||||||||||||||||||||
| 134 | } | ||||||||||||||||||||||||||||
| 135 | } | ||||||||||||||||||||||||||||
| 136 | |||||||||||||||||||||||||||||
| 137 | |||||||||||||||||||||||||||||
| 138 | 1 | 1; | |||||||||||||||||||||||||||
| 139 | |||||||||||||||||||||||||||||
| 140 | =head1 NAME | ||||||||||||||||||||||||||||
| 141 | |||||||||||||||||||||||||||||
| 142 | Graph::MaxFlow - compute maximum flow between 2 vertices in a graph | ||||||||||||||||||||||||||||
| 143 | |||||||||||||||||||||||||||||
| 144 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||
| 145 | |||||||||||||||||||||||||||||
| 146 | use Graph::MaxFlow qw(max_flow); | ||||||||||||||||||||||||||||
| 147 | |||||||||||||||||||||||||||||
| 148 | my $g = new Graph; | ||||||||||||||||||||||||||||
| 149 | # construct graph | ||||||||||||||||||||||||||||
| 150 | my $flow = max_flow($g, "source", "sink"); | ||||||||||||||||||||||||||||
| 151 | |||||||||||||||||||||||||||||
| 152 | =head1 DESCRIPTION | ||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||
| 154 | Computes the maximum flow in a graph, represented using Jarkko | ||||||||||||||||||||||||||||
| 155 | Hietaniemi's Graph.pm module. | ||||||||||||||||||||||||||||
| 156 | |||||||||||||||||||||||||||||
| 157 | =head1 FUNCTIONS | ||||||||||||||||||||||||||||
| 158 | |||||||||||||||||||||||||||||
| 159 | This module provides the following function: | ||||||||||||||||||||||||||||
| 160 | |||||||||||||||||||||||||||||
| 161 | =over 4 | ||||||||||||||||||||||||||||
| 162 | |||||||||||||||||||||||||||||
| 163 | =item max_flow($g, $s, $t) | ||||||||||||||||||||||||||||
| 164 | |||||||||||||||||||||||||||||
| 165 | Computes the maximum flow in the graph $g between vertices $s and $t | ||||||||||||||||||||||||||||
| 166 | using the Edmonds-Karp algorithm. $g must be a Graph.pm object, and | ||||||||||||||||||||||||||||
| 167 | must be a directed graph where the edge weights indicate the capacity | ||||||||||||||||||||||||||||
| 168 | of each edge. The edge weights must be nonnegative. $s and $t must | ||||||||||||||||||||||||||||
| 169 | be vertices in the graph. The graph $g must be connected, and for | ||||||||||||||||||||||||||||
| 170 | every vertex v besides $s and $t there must be a path from $s to $t | ||||||||||||||||||||||||||||
| 171 | that passes through v. | ||||||||||||||||||||||||||||
| 172 | |||||||||||||||||||||||||||||
| 173 | The return value is a new directed graph which has the same vertices | ||||||||||||||||||||||||||||
| 174 | and edges as $g, but where the edge weights have been adjusted to | ||||||||||||||||||||||||||||
| 175 | indicate the flow along each edge. | ||||||||||||||||||||||||||||
| 176 | |||||||||||||||||||||||||||||
| 177 | =back | ||||||||||||||||||||||||||||
| 178 | |||||||||||||||||||||||||||||
| 179 | =head1 AUTHOR | ||||||||||||||||||||||||||||
| 180 | |||||||||||||||||||||||||||||
| 181 | Walt Mankowski, E<lt>waltman@pobox.comE<gt> | ||||||||||||||||||||||||||||
| 182 | |||||||||||||||||||||||||||||
| 183 | =head1 COPYRIGHT AND LICENSE | ||||||||||||||||||||||||||||
| 184 | |||||||||||||||||||||||||||||
| 185 | Copyright 2024 by Walt Mankowski | ||||||||||||||||||||||||||||
| 186 | |||||||||||||||||||||||||||||
| 187 | This library is free software; you can redistribute it and/or modify | ||||||||||||||||||||||||||||
| 188 | it under the same terms as Perl itself. | ||||||||||||||||||||||||||||
| 189 | |||||||||||||||||||||||||||||
| 190 | =head1 ACKNOWLEDGEMENTS | ||||||||||||||||||||||||||||
| 191 | |||||||||||||||||||||||||||||
| 192 | The algorithms are adapted from Introduction to Algorithms, Second | ||||||||||||||||||||||||||||
| 193 | Edition, Cormen-Leiserson-Rivest-Stein, MIT Press. | ||||||||||||||||||||||||||||
| 194 | |||||||||||||||||||||||||||||
| 195 | =cut | ||||||||||||||||||||||||||||