blib/lib/Graph/MaxFlow.pm

filter: Statementstmt 94.8% 73 / 77 Branchbran 91.6% 22 / 24 Conditioncond 100% 3 / 3 MC/DCmcdc 100% 2 / 2 Subroutinesub 100% 9 / 9 Podpod 20.0% 1 / 5 totaltotal 91.6% 110 / 120 CC 19 SCAR 19.0
CC
19
Cov
94%
max_flow
10.4
shortest_path
8.0
init_flow
2.0
CRAP 6.7
↑ Summary
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
BranchTrueFalseTotal
if ($g->is_undirected) 0 2 2
21 0 carp "Graph must be directed";
22 0 return;
23 }
24  
25 2 ▶ if ($g->vertices < 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($g->vertices < 2) 0 2 2
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
BranchTrueFalseTotal
unless @$path 2 6 8
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
BranchTrueFalseTotal
if not defined $min or $weight < $min 9 10 19
Condition100%3/3
not defined $min or $weight < $min
l!l&&r!l&&!r
6310
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
ABresult
1X1
011
000
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
BranchTrueFalseTotal
$weight > 0 ? : 16 11 27
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
BranchTrueFalseTotal
if (@next) 58 2 60
90 58 my $u = shift @next;
91 58 ▶ if ($u eq $to) {
Branch: 1 branch
BranchTrueFalseTotal
if ($u eq $to) 6 52 58
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
BranchTrueFalseTotal
if exists $parent{$v} 87 74 161
98 74 ▶ next unless residual_capacity($g, $flow, $u, $v) > 0;
Branch: 1 branch
BranchTrueFalseTotal
unless residual_capacity($g, $flow, $u, $v) > 0 20 54 74
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
BranchTrueFalseTotal
if ($found) 6 2 8
107 6 my $u = $to;
108 6 ▶ while (defined $parent{$u}) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $parent{$u}) 19 6 25
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
BranchTrueFalseTotal
if ($g->has_edge($u, $v)) { } 82 11 93
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
↑ Summary