Maximum Flow Networks Suppose G = (V, E)

Maximum Flow Networks Suppose G = (V, E)

Maximum Flow Networks Suppose G = (V, E) is a directed network. Each edge (i,j) in E has an associated capacity uij. Goal: Determine the maximum amount of flow between two specified vertices s and t. The capacity v of a path P is the sum of its constituent edge flows: v = xxij where xij is the flow from vertex i to vertex j. Applications to design: supply networks oil pipelines road traffic 1 Background Assumptions: Integer data Directed network Nonnegative capacities on each arc Vertex s is the source Vertex t is the sink Definitions: Residual network Cut Techniques: 1. Augmenting Paths Examine residual network for s-t paths. 2. Preflow-Push Flow moved according to individual edge not path. 2 Maximum Flow as Linear Programming Problem maximize v subject to x x ji 0 for each i s, t x

sj v x jt v ij j j j j 0 x ij u ij (i, j) E v 0 3 Example 2,4 2 3,9 s 1,2 8,8 3 4 2,6 4,7 t 7,9 Each edge is labeled as (xij, uij) = (flow, capacity). However, this flow value, v(x) = 11, is not a maximum.

4 Residual Network Given a current flow x, keep track of how much further the flow can be increased in each direction of the edge. For any edge in G: The corresponding edge (with capacities) in residual network of G: i xij, uij j uij -xij i j xij The residual network of G, G(x), has edges with positive residual capacity, rij = uij xij + xji. In general, it is the amount by which we can further increase flow from i to j in the current network. 5 Example Re-examined 2,4 2 3,9 s 1,2 8,8 3 4 3 4,7 2,6 t

7,9 Network with flows and capacities. s 2 1 6 1 2 3 2 6 8 4 2 4 2 t 7 3 Residual network with capacities. We know this network flow is not a maximum. How can we get a better one? What do we do in general? 6 Cuts A cut is defined by a partition of the vertex set E into subsets S and S* = E S. The cut [S,S*] consists of all edges with one endpoint in S and the other in S*. The forward edges of [S,S*] are denoted (S, S*). The backward edges are denoted as (S*,S). An s-t cut [S,S*] has s in S and t in S*. The removal of the forward edges in an s-t cut will separate vertices s and t. That is, there is no longer a directed s to t path. The capacity of any cut [S,S*], u[S,S*], is the sum of the capacities of the

forward edges of the cut. u[S,S*] is an upper bound on the amount of flow sent from S to S*. A minimum s-t cut has the smallest capacity among all s-t cuts. 7 Examples of 1-6 cuts 2 10 1 10 4 5 4 8 8 3 5 10 6 8 5 S={ } S* = { } Forward edges of [S,S*]= { } u[S, S*] = = 2 1 10 4

5 4 8 6 8 8 3 5 5 S={ } S* = { } Forward edges of [S,S*]= { } u[S, S*] = = 8 Theorems Theorem If x is any feasible flow and if [S,S*] is any s-t cut, then the flow value, v(x), from s to t is at most u[S,S*]. Corollary the max flow value the minimum cut capacity Max-Flow Min-Cut Theorem For any capacitated network, the value of the maximum s-t flow, x, equals the capacity of a minimum s-t cut, [S,S*]. v(x) = u [S,S*] 9 Improving a Flow Given the flow x, look for a path P from s to t in the residual network G(x) along which flow can be sent. Then send as much flow along P as possible. We call any directed path P from s to t in the residual network an

augmenting path. The residual capacity of such a path is (P) = min{rij:(i, j) P). To augment along P is to send (P) units of flow along each edge of the path. We then modify x and the residual capacities rij appropriately. rij := rij (P) for each edge (i,j) P rji := rji + (P) for each edge (i, j) P Result: flow value, v, increases by (P). 10 Example 2,4 2 3,9 1,2 s 8,8 4 3 4,7 2,6 t s 1 6 1 8 7,9 3

2 2 4 2 3 2 6 4 2 t 7 3 Network with flows and capacities. v Residual network with capacities. =11 Augment along path P = s-2-4-t. (P) = min{6, 2, 3} = 2. new flow value =13 4,4 2 5,9 s 8,8 1,2 3 4 2,6 5 6,7 t 7,9 s

2 1 4 1 8 1 2 6 3 4 4 6 2 t 7 11 Example Augmenting Paths Step 0: initial residual graph is original 2 6 1 4 8 2 8 4 2 4 3 6

2 3 5 1 5 5 4 2 2 3 4 2 1 2 4 1 5 3 2 8 4 3 2 3 5 2 6 6 5

6 Step 2: Push 5 units along path 1-3-5-6 2 6 5 5 Step 3: Push 2 units along path 1-2-5-4-6 4 4 4 3 6 Step 1: Push 4 units along path 1-2-4-6 4 4 1 5 4 2 3 3 2 1 1 5 6 4

2 5 2 6 5 Step 4: Push 1 units along path 1-3-5-4-6 12 Example continued 2 6 1 6 4 2 2 3 1 3 6 7 4 2 5 6 5 2 6 1 No more augmenting paths

8 4 4 8 2 3 6 2 3 5 5 6 2 6,6 1 0,2 6,8 4,4 2,2 3 4 7,8 3,3 5 6 5,5 6,6 Maximum Flow in G is 12

13 THEOREM The following are equivalent statements 1. 2. 3. The s-t flow x with value v(x) is maximum G(x) contains no augmenting path. There is an s-t cut [S,S*] with u[S,S*] = v(x) 14 Generic Augmenting Path Algorithm In this algorithm, we keep sending flow along augmenting paths until no s-t path exists in the residual network. Can carry out calculations entirely on G(x). Flows in G are found at the very end. algorithm augmenting_path; begin x := 0 while G(x) contains a directed path from s to t do begin P = Find_Path(s, t, G(x)); (P) := min{rij: (i,j) P}; augment (P) units of flow along P; update G(x); end; end; 15 Find_Path Options More than one way to pick an augmenting path Poor choices can lead to many augmentations.

Info lost when successive paths are found. Balance effort to find a good path with the reduction in # of augmentations. Maximum capacity select path P such that (P) is as large as possible. Shortest path use the path with the minimum number of edges. Scaling successively solve subproblems with a certain capacity. 3 50 50 1 1 50 4 50 2 16 Distance Labels For the shortest path version of the augmenting path algorithm and for another max flow algorithm, the pre-flow push, the notion of distance labels is needed. The distance label d(j) is a nonnegative integer assigned to each j in G(x). The distance labels are valid if d(t) = 0 d(i) d(j)+1 for each (i,j) G(x) If d(j) are valid, then d(j) is a lower bound on the shortest distance from j to t. If d(s) n then there is no s-t path in G(x). (n = number of vertices in G) An admissible edge in G(x) is one where d(i) = d(j) + 1. An admissible path is a path from s to t consisting of admissible edges and is a shortest

augmenting path from s to t. 3 1 4 5 2 17 Shortest Distance Algorithm Admissible paths are successively built by advancing until vertex t is reached. If no admissible edge is available at some point, then retreat and relabel will be a way of updating distances in the new residual graph. In this way, we maintain valid distance labels without starting from scratch. algorithm shortest augmenting path; begin x:= 0; calculate exact distance labels, d(j) to vertex t; j := s; while d(s) 0}; if E(j) with rjk > 0 empty then d(j) = n; if j s then j := pred(k);

end; algorithm augment; begin derive path P from pred; (P) := min{rij: (i,j) P}; augment (P) units of flow along P; end; 19 Example d(3)=1 3 4 1 5 d(1)=2 3 2 4 1 1 2 3 4 1 1 5 d(4)=0 3 2 4 1 d(2)=1

1. Calculate d(j) 3. Advance 1-2, retreat, relabel vertex 2 d(3)=1 d(1)=2 1 3 4 2 d(3)=1 5 d(4)=0 3 2 4 1 d(2)=1 2. Advance 1-2-4, (P) =1, augment d(1)=2 3 4 1 1 1 5 d(4)=0 3 2 4 1

d(2)=2 4. Advance 1-3-4, (P) =4, augment 20 Example d(3)=1 d(1)=2 3 4 1 1 4 1 3 1 d(3)=1 d(4)=0 4 d(1)=3 5 d(4)=0 2 1 1 2 3 4 1

2 4 1 2 d(2)=2 d(2)=2 5. Advance 1, retreat relabel 1 7. Advance 1, retreat, relabel 1 d(3)=1 d(3)=1 d(1)=3 3 4 1 1 1 3 4 d(1)=4 1 2 d(4)=0 4 1 d(2)=2 6. Advance 1-2-3-4, (P) =1, augment

3 4 5 d(4)=0 2 1 2 1 2 4 1 d(2)=2 8. Maximum Flow achieved 21 Example - Results 4,4 1 2,2 3 5,5 1,3 2 Note monotonicity of distance labels 4 1,1 Note monotonicity of path lengths 1-2-4 1-3-4 1-2-3-4 1 2

3 4 5 6 7 d(1) 2 2 2 2 3 3 4 d(2) 1 1 2 2 2 2 2 d(3) 1 1 1 1 1

1 1 d(4) 0 0 0 0 0 0 0 22 Additional Exercises 18 3 22 25 17 11 1 source 13 4 1 source 9 10 2 11 5

8 21 5 6 8 sink 24 6 6 4 30 26 22 7 3 19 17 2 8 6 9 11 7 5 7 3

source 7 sink 4 3 1 2 1 1 4 1 3 2 5 2 2 1 7 6 sink 23 Preflow-push Algorithm Distance labels d(t) = 0; d(i) d(j) + 1 for each (i,j) in G(x) Excess flow e(i) = excess at each vertex for a given preflow Active vertices vertices with positive excess Admissible edges edges that satisfy the condition that d(i) = d(j) + 1 Preflow infeasible solution;

Algorithm strives for feasibility/optimality when all excess at sink and source algorithm preflow-push; begin preprocess; while network contains an active vertex do begin select an active node i; push/relabel(i); end; end; 24 algorithm preprocess; begin x := 0; compute the exact distance labels d(i) from s; xsj := usj for each edge (s,j) in E(s); d(s) := n end; algorithm push/relabel(i); begin if the networks contains an admissible edge (i,j) then push = min{e(i), rij} units of flow from vertex i to vertex j; else replace d(i) by min{d(j)+1: (i,j) in E(i) and r ij > 0}; end; 25 Example 1. Network G 2. preprocess: first residual graph Active nodes: 2, 3 Active nodes: e(1)=0 d(1)=2 e(3)=0 d(3)=1 e(3)=4 d(3)=1 3

3 5 4 3 1 2 4 1 e(4)=0 d(4)=0 e(1)=0 d(1)=4 5 4 3 1 2 4 e(4)=0 d(4)=0 1 2 2 e(2)=0 d(2)=1 e(2)=2 d(2)=1 26 Example Selected node: 2 Active nodes: 3 Selected node: 3

Active nodes: 2 3. Saturating push of 1 unit along 2-4; Relabel distance node 2 Active nodes: 3, 2 e(1)=0 d(1)=4 Active nodes: 2 e(3)=4 d(3)=1 e(3)=0 d(3)=1 3 3 5 4 3 1 4. Push of 4 units along 3-4 2 4 1 e(4)=1 d(4)=0 e(1)=0 d(1)=4 1 4 3 1 2

4 4 e(4)=5 d(4)=0 1 2 2 e(2)=1 d(2)=2 e(2)=1 d(2)=2 27 Example Selected node: 2 Active nodes: Selected node: 3 Active nodes: 5. Push of 1 unit along 2-3 6. Saturating Push of 1 units along 3-4 Active nodes: 3 e(1)=0 d(1)=4 Active nodes: e(3)=1 d(3)=1 e(3)=0 d(3)=1 3 3 1 4

4 2 1 1 2 4 1 2 e(2)=0 d(2)=2 e(4)=5 d(4)=0 e(1)=0 d(1)=4 4 2 1 1 2 5 4 e(4)=6 d(4)=0 1 2 e(2)=0 d(2)=2 28 Preflow-Push: Example 2 10 2

1 10 5 4 8 6 8 8 3 5 5 29 Checking if feasible flow exists Let G = (V,E) be a network with supplies and demands at each vertex b(j) > 0 indicates supply at vertex j b(j)<0 indicates demand at vertex j Assumption: xb(j) = 0 Does a flow, x, exist? Transform into a maximum flow network, G Add a source vertex, s, and a sink vertex, t. Add edge (s, j) with capacity, rsj=b(j), if b(j)>0 Add edge (j, t) with capacity, rjt=b(j), if b(j)<0 Solve max flow from s to t Result: If the max flow in G saturates all the source and sink edges,

then the original problem has a feasible solution. Otherwise, infeasible. 30 Example 1-Feasible Flow? b(2) = 5 2 b(1) = 4 1 6 2 4 4 4 b(4) = -7 8 3 b(3) = -2 31 Example 2-Feasible flow? b(2) = 5 2 b(1) = 4 1 6 3 1 4 4 b(4) = -7 8 3 b(3) = -2 32

Recently Viewed Presentations

  • Dealing with Difference

    Dealing with Difference

    Forgiveness Objectives Understand forgiveness Learn the health benefits Decide to forgive How to's Live forgiving Forgiveness Is... A decision to let go of resentment and thoughts of revenge Source: The Mayo Clinic Words That Show Hurt Emotions Betrayed Humiliated Abused...
  • English accents - UCL

    English accents - UCL

    Arial Tahoma Times New Roman Ipa-sams Uclphon1 SILSophiaL PalmSprings ucl English accents consonants prosody sociolinguistic work PowerPoint Presentation PowerPoint Presentation PowerPoint Presentation standard lexical sets PowerPoint Presentation PowerPoint Presentation
  • Formula Mass or Molecular Mass - SJ HS Chemistry

    Formula Mass or Molecular Mass - SJ HS Chemistry

    Chapter 5 5.5 The Mole 5.6 Molar Mass 5.7 Mole Relationships in Chemical Equations 5.8 Mass Calculations for Reactions
  • Comparative Endings  Add er to a word to

    Comparative Endings Add er to a word to

    Comparative Endings Add -er to a word to compare two people, places, things, or animals Add -est to a word to compare three or more people, places, things, or animals. Don't forget that some words will be spelled differently when...
  • Misleading or Falsification? Inferring Deceptive Strategies and Types

    Misleading or Falsification? Inferring Deceptive Strategies and Types

    Psycholinguistic analysis across deception types in the news pages (Rashkin et al., 2017) Predicting credibility of PolitiFact statements (Rashkin et al., 2017; Wang et al., 2017) and analyzing credibility of tweets (Mitra et al., 2017) Models to classify deceptive news...
  • Reclaimed Appliances Ltd - Basel Convention

    Reclaimed Appliances Ltd - Basel Convention

    Also visits to markets, informal recycling centres etc August 2008 Nigerian delegation visited UK including tour of Reclaimed Appliances and meeting with DEFRA and the Environment Agency. Unregulated import, collection, treatment, recycling and disposal process Perceived large scale WEEE ...
  • TeX4PPT - About | Department of Physics

    TeX4PPT - About | Department of Physics

    Contributing Group Manuel J Paez, University of Medellin, Colombia, SA, CoAuthor C. E. Yaguna, J. Zuluaga, Oscar A. Restrepo, Guillermo Avendano-Franco Cristian Bordeianu, University of Bucharest, Romania, CoAuthor Paul Fink, Robyn Wangberg, CoAuthors Justin Elser, Chris Sullivan (system support) Sally...
  • October 24, 2013 - WordPress.com

    October 24, 2013 - WordPress.com

    Poem Analysis. What groups and individuals are treated like outsiders in America today? What did you learn from this experience and the poem that might help you to better understand the feelings of outsiders in the future? How might you...