Optimization: principles and algorithms, by Michel Bierlaire
fordFulkerson.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 24.2: Ford-Fulkerson. Implementation of algorithm 24.2 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run2402.m
5 %> @note Calls \ref unsaturatedPath
6 %>
7 %> @author Michel Bierlaire
8 %> @date Thu Apr 9 18:43:39 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap24
11 
12 %> Find the maximum flow between two nodes using the Ford Fulkerson algorithm
13 %> @param adj adjacency matrix of the network. Each nonzero entry corresponds to an arc. The value of the entry is the ID of the arc.
14 %> @param orig the origin node
15 %> @param dest the destination node
16 %> @param lb the lower bound on the flow
17 %> @param ub the upper bound on the flow
18 %> @return flow the optimal flow vector
19 %> @return total the total flow sent
20 function [flow, total] = fordFulkerson(adj,orig,dest,lb,ub)
21  nnodes = rows(adj) ;
22  narcs = max(max(adj)) ;
23  if (columns(adj) != nnodes)
24  error("Adjacency matrix must be square\n") ;
25  endif
26  if (length(lb) != narcs)
27  error("lb vector has incorrect size %f instead of %d\n",length(lb),narcs) ;
28  endif
29 
30  if (length(ub) != narcs)
31  error("ub vector has incorrect size %f instead of %d\n",length(ub),narcs) ;
32  endif
33 
34  for i=1:narcs
35  if lb(i) > ub(i)
36  error("Incompatible bounds [%f,%f]\n",lb(i),ub(i)) ;
37  endif
38  end
39 
40  flow = zeros(narcs,1) ;
41  total = 0 ;
42  proceed = 1 ;
43  iter = 1 ;
44  printf("Iter\t") ;
45  printf("%d\t",1:narcs) ;
46  printf("Flow sent\tPath\n") ;
47  while (proceed != 0)
48  printf("%d\t", iter) ;
49  iter += 1 ;
50  printf("%d\t",flow) ;
51  [path, cut, pathFound] = unsaturatedPath(adj,orig,dest,lb,ub,flow) ;
52  if pathFound
53 % printf("Unsaturated path found\n") ;
54  send = realmax ;
55  for i = 1:length(path.arcs)
56  theArc = path.arcs(i) ;
57  if (path.dir(i) == 1)
58  f = ub(theArc) - flow(theArc) ;
59  if (f < send)
60  send = f ;
61  endif
62  else
63  f = flow(theArc) - lb(theArc) ;
64  if (f < send)
65  send = f ;
66  endif
67  endif
68  endfor
69 
70 % printf("Send %f units of flows along path ",send)
71  printf("%d\t\t",send)
72  printf("%d\t",path.arcs)
73  printf("\n") ;
74 
75  for i = 1:length(path.arcs)
76  theArc = path.arcs(i) ;
77  if (path.dir(i) == 1)
78  flow(theArc) += send ;
79  else
80  flow(theArc) -= send ;
81  endif
82  endfor
83  total += send ;
84  else
85  printf("\n") ;
86  printf("Cut found: ") ;
87  printf("%d ",cut) ;
88  printf("\n",cut) ;
89  proceed = 0 ;
90  endif
91  endwhile
92 endfunction
function unsaturatedPath(in adj, in orig, in dest, in lb, in ub, in flow, in printlevel)
Find an unsaturated path from o to d.
function fordFulkerson(in adj, in orig, in dest, in lb, in ub)
Find the maximum flow between two nodes using the Ford Fulkerson algorithm.
Copyright 2015-2016 Michel Bierlaire