4up

Share

Transcript

1 Mincut problem 6.4 Maximum Flow Given. A weighted digraph with identified source s and target t. Def. A cut is a partition of the vertices into two disjoint sets. Def. An st-cut is a cut that places s in one of its sets (Cs) and t in the other (Ct). Def. An st-cuts weight is the sum of the weights of its st-crossing edges. edges from Cs to Ct Minimum st-cut (mincut) problem. Find an st-cut of minimal weight. overview Ford-Fulkerson 22 implementations applications 23 Figure 2 29 From Harris and Ross [1955]: Schematic diagram of the railway network of the Western So- viet Union and Eastern European countries, with a maximum flow of value 163,000 tons from Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as The bottleneck. Note: dont count edges from Ct to Cs Algorithms, 4th Edition Robert Sedgewick and Kevin Wayne Copyright 20022010 April 18, 2011 11:02:27 AM 2 Typical mincut application Mincut application (1950s) Find cheapest way to cut connection between s and t. Rail network connecting Soviet Union with Eastern European countries s t www.blog.spoongraphics.co.uk/tutorials/creating-road-maps-in-adobe-illustrator Free world goal: Know how to cut supplies if cold war turns into real war Figure 2 From Harris (map and Rossdeclassified by Pentagon [1955]: Schematic diagram of the railway in 1999). network of the Western So- 3 viet Union and Eastern European countries, with a maximum flow of value 163,000 tons from 4 Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as The bottleneck.

2 Potential mincut application (2010s) Maxflow problem Facebook graph Flow network. Weighted digraph with a source s (indegree 0) and sink t (outdegree 0) An edges weight is its capacity (positive) Add additional flow variable to each edge(no greater than its capacity) Maximum st-flow (maxflow) problem: Assign flows to edges that Maintain local equilibrium: inflow = outflow at every vertex (except s and t). Maximize total flow into t. Government-in-powers goal: Cut off communication to specified set of people. 5 6 A physical model Typical maxflow application Oil flowing in pipes all flow goes down Find best way to distribute goods from s to t. (just to simplify diagrams) local equilibrium s at each vertex 4 in s 2o 2 out ut room for improvement? t t www.blog.spoongraphics.co.uk/tutorials/creating-road-maps-in-adobe-illustrator Shortest augmenting paths in a larger flow network 7 8

3 Maxflow application (1950s) Potential mincut application (2010s) Rail network connecting Soviet Union with Eastern European countries Facebook graph flow capacity Figure 2 Free world goal: Maximize flow of information to specified set of people. Soviet Union From Harris goal: and Ross Know [1955]: howdiagram Schematic to maximize flowofof of the railway network the supplies Western So- to Eastern Europe. viet Union and Eastern European countries, with a maximum flow of value 163,000 tons from Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as The bottleneck. 9 10 Overview (summary) Maxflow / mincut applications Given. A weighted digraph, Maxflow/mincut is a widely applicable problem-solving model source s and target t. Data mining. Open-pit mining. Project selection. Minimum st-cut (mincut) problem. Find an st-cut of minimal weight. Image processing. Airline scheduling. Maximum st-flow (maxflow) problem: Assign flows to edges that Bipartite matching. Maintain local equilibrium: inflow = outflow at every vertex (except s and t). Baseball elimination. Maximize total flow into t. Distributed computing. Egalitarian stable matching. Remarkable fact. These two problems are equivalent! Security of statistical data. Two very rich algorithmic problems Network connectivity/reliability. Cornerstone problems in combintorial optimixation Many many more . . . Beautiful mathematical duality 11 12

4 APIs (cf. EdgeWeightedDigraph, DirectedEdge) overview APIs Ford Fulkerson implementations applications manipulate flow values (stay tuned) 13 14 Flow edge: implementation in Java (cf. DirectedEdge) Flow network representation A flow network is an array of bags of flow edges. public class FlowEdge { private final int v; // from private final int w; // to private final double capacity; // capacity private double flow; // flow flow variable public FlowEdge(int v, int w, double capacity, double flow) tinyFN.txt references to the { 0 2 3.0 1.0 0 1 2.0 2.0 same Edge object V this.v = v; 6 adj[] this.w = w; E 8 0 1 4 1.0 0.0 1 3 3.0 2.0 0 1 2.0 2.0 this.capacity = capacity; 0 1 2.0 this.flow = flow; 1 0 2 3.0 } 2 2 4 1.0 1.0 2 3 1.0 0.0 0 2 3.0 1.0 1 3 3.0 1 4 1.0 3 public int from() { return v; } 2 3 1.0 3 5 2.0 2.0 2 3 1.0 0.0 1 3 3.0 2.0 public int to() { return w; } 4 2 4 1.0 public double capacity() { return capacity; } 5 3 5 2.0 4 5 3.0 1.0 2 4 1.0 1.0 1 4 1.0 0.0 public double flow() { return flow; } 4 5 3.0 public int other(int vertex) 4 5 3.0 1.0 3 5 2.0 2.0 Bag { objects if (vertex == v) return w; Flow network representation else if (vertex == w) return v; else throw new RuntimeException("Illegal endpoint"); } public double residualCapacityTo(int vertex) {...} stay tuned public void addResidualFlowTo(int vertex, double delta) {...} } 15 16

5 Flow network: implementation in Java (cf. EdgeWeightedDigraph) Typical client code: check that a flow is feasible public class FlowNetwork { private boolean localEq(FlowNetwork G, int v) private final int V; { // Check local equilibrium at v. private int E; double EPSILON = 1E-11; private Bag[] adj; array of bags of flow edges double netflow = 0.0; public FlowNetwork(int V) for (FlowEdge e : G.adj(v)) { if (v == e.from()) netflow -= e.flow(); this.V = V; this.E = 0; constructor else netflow += e.flow(); adj = (Bag[]) new Bag[V]; return Math.abs(netflow) < EPSILON; for (int v = 0; v < V; v++) } adj[v] = new Bag(); private boolean isFeasible(FlowNetwork G) } { public int V() { return V; } for (int v = 0; v < G.V(); v++) public int E() { return E; } for (FlowEdge e : G.adj(v)) check that each flow public void addEdge(FlowEdge e) if (e.flow() < 0 || e.flow() > e.capacity()) is nonnegative { return false; and no greater than capacity E++; int v = e.from(); add edge (to both adj lists) for (int v = 0; v < G.V(); v++) int w = e.to(); adj[v].add(e); if (v !=s && v != t && !localEq(G, v)) check local equilibrium adj[w].add(e); at each vertex return false; } public Iterable adj(int v) iterator for adjacent edges return true; { return adj[v]; } } } 17 18 Idea: increase flow along augmenting paths 9 10 4 15 15 10 APIs s 5 8 10 t Ford Fulkerson implementations 4 6 15 15 10 applications 16 19 20

6 Idea: increase flow along augmenting paths Idea: increase flow along augmenting paths s t s t 0 + 10 = 10 21 22 Idea: increase flow along augmenting paths Idea: increase flow along augmenting paths Problem: Can get stuck with no way to add more flow to t. s t 10 +10 = 20 s +5 t 23 24

7 Idea: increase flow along augmenting paths Idea: increase flow along augmenting paths Problem: Can get stuck with no way to add more flow to t. Augmenting paths in general Solution: Go backwards along an edge with flow (removing some flow). increase flow on forward edge (if not full) decrease flow on backward edge (if not empty) +5 s t s t 20 + 5 = 25 25 26 Idea: increase flow along augmenting paths Idea: increase flow along augmenting paths Eventually all paths from s to t are blocked by either a full forward edge empty backward edge s t 25 + 3 = 28 s t maxflow value = 28 27 28

8 Ford-Fulkerson algorithm Mincut problem (revisited) Generic method for solving maxflow problem. Given. A weighted digraph with identified source s and target t. Start with 0 flow everywhere. Find an augmenting path. Def. A cut is a partition of the vertices into two disjoint sets. Increase the flow on that path, by as much as possible. Def. An st-cut is a cut that places s in one of its sets (Cs) and t in the other (Ct). Repeat until no augmenting paths are left. Def. An st-cuts weight is the sum of the weights of its st-crossing edges. edges from Cs to Ct Questions. Mincut problem. Find an st-cut of minimal weight. Q. Does this process give a maximum flow? A. Yes! It also finds a mincut (!!). [Classic result] 22 s s s Q. How do we find an augmenting path? A. Easy. Adapt standard graph-searching methods. 23 Q. How many augmenting paths (does the process even terminate)? A. Difficult to know: depends on graph model, search method. t t t 29 Note: dont count edges from Ct to Cs 29 30 Mincut problem (revisited with slight change in terminology) Relationship between flows and cuts Given. A weighted flow network digraph with identified source s and target t. Def. The flow across an st-cut is the sum of the flows on its st-crossing edges minus the sum of the flows of its ts-crossing edges. Def. A cut is a partition of the vertices into two disjoint sets. Def. An st-cut is a cut that places s in one of its sets (Cs) and t in the other (Ct). Thm. For any st-flow, the flow across every st-cut Def. An st-cuts capacity weight is the sum of the capacities weights of its st-crossing edges. equals the value of the flow. s Cs edges from Cs to Ct Mincut problem. Find an st-cut of minimal weight. capacity. Pf. By induction on the size of Ct. difference between inflow and outflow is flow across cut true when Ct = {t}. s s s 22 true by local equilibrium when moving Ct 2 7 4 7 7 4 a vertex from Cs to Ct 2 t 2 6 2 2 2 inflow to t is value of the flow 2 4 23 3 2 2 3 2 4 5 Corollary 1. Outflow from s = inflow to t = value. t 29 t Corollary 2. No st-flows value can exceed the capacity t of any st-cut. Amazing fact. Mincut and maxflow problems are equivalent. 31 32

9 Relationship between flows and cuts (example) Maxflow-mincut theorem For any st-flow, the flow across every st-cut equals the value of the flow. Thm. The following three conditions are equivalent for any st-flow f: i. There exists an st-cut whose capacity equals the value of the flow f. ii. f is a maxflow. iii. There is no augmenting path with respect to f. 5 2 2 2 2 22 Pf. 19 -1 i. implies ii. [no flows value can exceed any cuts capacity] 3 ii. implies iii. by contradiction [aug path would give higher-value flow, so f 2 2 2 2 19 19 could not be maximal]. 3 3 1 4 4 5 6 iii. implies i. Shortest augmenting 4 paths in a larger flow network Cs: set of all vertices connected to s by an undirected path with no full forward or empty backward edges. Ct: all other vertices. Shortest augmenting paths in a larger flow network capacity = flow across [st-crossing edges full, ts-crossing edges empty] . = value of f [capacity of any cut = value of f]. 33 34 Shortest augmenting paths in a larger flow network FF termination Maxflow/mincut application (1950s) Eventually all paths from s to t are blocked by either a full forward edge empty backward edge s t maxflow value = 28 mincut capacity = 28 Figure 2 From Harris and Ross [1955]: Schematic diagram of the railway network of the Western So- Mincut: viet Union and Eastern European countries, with a maximum flow of value 163,000 tons from Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as The bottleneck. Consider only paths with no full forward or empty backward edges. bottleneck is mincut (all forward edges full) Cs is the set of vertices reachable from s; Ct is the set of remaining vertices. value of flow = 30+17+36+16+24+6+10+5+19 = 163,000 tons 35 36 Figure 2

10 Integrality property Possible strategies for augmenting paths Corollary to maxflow-mincut theorem. When capacities are integers, there FF algorithm: any strategy for choosing augmenting paths will give a maxflow. exists an integer-valued maxflow, and the Ford Fulkerson algorithm finds it. [Caveat: Can have convergence problems when weights are not integers.] Pf. Flow increases by augmenting path value, which is either unused capacity in Shortest path? aug path with fewest number a forward edge or flow in a backwards edge [and always an integer]. of edges DFS path? This lecture (guaranteed to converge) Random path? s t 20 + 5 = 25 Fattest path? max capacity aug path All easy to implement Bottom line: Ford-Fulkerson always works when weights are integers. Define residual graph Find paths in residual graph. Note: When weights are not integers, it could converge to the wrong value! Performance depends on network properties (stay tuned) 37 38 Shortest augmenting path Fattest augmenting path Shortest augmenting paths in a larger flow network 39 40

11 Random augmenting path Bad case for Ford-Fulkerson Bad news: Even when weights are integers, number of augmenting paths could be equal to the value of the maxflow. s U U 1 U U t Good news: This case is easily avoided [use shortest augmenting path]. 41 42 first iteration s s t t 0+1=1

12 second iteration third iteration s s backwards edge t t 1+2=2 2+1=3 fourth iteration s backwards edge . . . t 3+4=4

13 (2i-1)st iteration (2i)th iteration s s backwards edge t t 2i 2 + 1 = 2i 1 2i 1 + 1 = 2i Bad case for Ford-Fulkerson Flow network representation (revisited) Bad news: Even when weights are integers, number of augmenting paths Residual digraph. Another view of a flow network could be equal to the value of the maxflow. drawing with flow flow representation residual network s 0 1 2.0 2.0 backward edge U 0 2 3.0 1.0 2.0 1.0 (flow) U 1 3 3.0 2.0 2.0 1 4 1.0 0.0 2 3 1.0 0.0 1 2 4 1.0 1.0 1.0 2.0 1.0 3 5 2.0 2.0 1.0 U 4 5 3.0 1.0 1.0 U 1.0 capacity flow 2.0 2.0 t forward edge (remaining capacity) Anatomy of a network-flow problem (revisited) Good news: This case is easily avoided [use shortest augmenting path]. Finding an augmenting path is equivalent to finding a path in residual digraph. 51 52

14 Residual network implementation Ford-Fulkerson: Java implementation public class FlowEdge public class FordFulkerson { { private final int v; // from private boolean[] marked; // true if s->v path in residual digraph private final int w; // to private FlowEdge[] edgeTo; // last edge on s->v path private final double capacity; // capacity private double value; private double flow; // flow public FordFulkerson(FlowNetwork G, int s, int t) { public double residualCapacityTo(int vertex) value = 0; { while (hasAugmentingPath(G, s, t)) if (vertex == v) return flow; { else if (vertex == w) return capacity - flow; else throw new RuntimeException("Illegal endpoint"); double bottle = Double.POSITIVE_INFINITY; compute } for (int v = t; v != s; v = edgeTo[v].other(v)) bottleneck bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v)); capacity public void addResidualFlowTo(int vertex, double delta) for (int v = t; v != s; v = edgeTo[v].other(v)) augment { edgeTo[v].addResidualFlowTo(v, bottle); flow if (vertex == v) flow -= delta; else if (vertex == w) flow += delta; value += bottle; else throw new RuntimeException("Illegal endpoint"); } } } } public double hasAugmentingPath(FlowNetwork G, int s, int t) { /* See next slide. */ } flow public double value() { return value; } v v w w public boolean inCut(int v) capacity - flow { return marked[v]; } 53 54 Finding a shortest augmenting path (cf. breadth-first search) Analysis of Ford-Fulkerson (shortest augmenting path) Thm. Ford-Fulkerson (shortest augmenting path) uses at most EV/2 private boolean hasAugmentingPath(FlowNetwork G, int s, int t) { augmenting paths. edgeTo = new FlowEdge[G.V()]; marked = new boolean[G.V()]; Queue q = new Queue(); Pf. [see text] q.enqueue(s); marked[s] = true; while (!q.isEmpty()) { int v = q.dequeue(); for (FlowEdge e : G.adj(v)) { is there a path from s to w int w = e.other(v); in the residual graph? if (e.residualCapacityTo(w) > 0 && !marked[w]) { edgeTo[w] = e; save last edge on path, marked[w] = true; mark w, q.enqueue(w); and add w to the queue } Shortest augmenting paths in a larger flow network } } return marked[t]; Cor. Ford-Fulkerson (shortest augmenting path) examines at most E2V/2 edges. } Pf. Each BFS examines at most E edges. 55 56

15 Summary: possible strategies for augmenting paths Analysis of maxflow algorithms All easy to implement (Yet another) holy grail for mathematicians/theoretical computer scientists. Define residual graph For sparse graphs with E edges, integer capacities (max U). Find paths in residual graph. year method worst case order of growth discovered by 1951 simplex O ( E3 U ) Dantzig 1955 augmenting paths O( E2 U) Ford-Fulkerson Shortest path: Use BFS. 1970 shortest aug path O ( E3 ) Edmunds-Karp DFS path: Use DFS. 1970 fattest aug path O ( E2 log E log U ) Edmunds-Karp Fattest path: Use a PQ, ala shortest paths. 1973 capacity scaling O( E2 log U ) Dinitz-Gabow Random path: Use a randomized queue. 1983 preflow-push O ( E2 log E ) Sleator-Tarjan ~ 1997 length function O( E3/2 ) Goldberg-Rao ~ Christiano-Kelner-Madry- Performance depends on network properties 2011 electrical flow O ( E4/3 ) * Spielman-Teng ~ ignore log factors how many augmenting paths? ? O(E) * approximation how many edges examined to find each augmenting path? Warning: Worst-case order-of-growth analysis is generally not useful for predicting or comparing algorithm performance in practice. 57 58 O-notation considered harmful (Lecture 2 revisited) O-notation considered harmful Facebook and Google: Huge sparse graphs are of interest (1010 1011 edges). Time to solve maxflow: ~ Algorithm A: O(E3/2). ~ Algorithm B: O(E4/3).* ~ ignore log factors * approximation algorithm Source? Schrijvers authoritative survey attributes T. E. Harris Q. Which algorithm should Facebook and Google be interested in? (author of the Soviet rail network report) as A. Who knows? These mathematical results are not relevant! the first to formulate Upper bound on worst case [may never take stated time]. the problem in 1954. Unknown constants [most published maxflow algs never are implemented]. E1/6 savings likely offset by ignored log factors [40-50 vs. 30-40+]. Performance for practical graph models likely unknown [and not studied]. Approximation algorithm [cost of accuracy may be too high]. 59 60

16 O-notation considered harmful Summary Minimum st-cut (mincut) problem. Find an st-cut of minimal weight. Maximum st-flow (maxflow) problem: Assign flows to edges that Maintain local equilibrium: inflow = outflow at every vertex (except s and t). up to 100 Maximize total flow into t. if the constant-factor costs were the same for both algorithms and if the internet were the Proven successful approaches. worst case for both algorithms, which there is no reason to believe. Ford-Fulkerson (various augmenting-path strategies). Moreover, these mathematical results are Preflow-push (various versions). approximate, ignoring factors that could run The algorithm has not been implemented or into the hundreds for the internet graph. tested on graphs the size of the internet (or Open research challenges. at all, for that matter). The algorithm would The algorithm also computes an approximation to the maxflow, not the Practice: Solve maxflow/mincut problems for real networks in linear time. have to be implemented and tested before any claim to immediate practicality could be actual maxflow, and slows down as the approximation improves. Theory: Prove it for worst-case networks. assessed. It is likely that simpler approaches involving parallelism will be used in practice. 61 62 Maxflow / mincut applications Maxflow/mincut is a widely applicable problem-solving model Data mining. Open-pit mining. Project selection. Image processing. Airline scheduling. APIs Bipartite matching. Ford Fulkerson Baseball elimination. implementations Distributed computing. applications Egalitarian stable matching. Security of statistical data. Network connectivity/reliability. Many many more . . . 63 64

17 Bipartite matching problem Network flow formulation of bipartite matching N students apply for N jobs To formulate a bipartite matching problem as a network flow problem 1 Alice 7 Adobe Adobe Alice create s, t, one vertex for each student, and one vertex for each job Amazon Facebook Bob Dave add edge from s to each student 2 Bob 8 Amazon add edge from each job to t Each get several offers Adobe Amazon Alice Bob add edge from student to each job offered s Yahoo 3 Carol 9 Dave Facebook give all edges capacity 1 Facebook Alice Google Carol 1 2 3 4 5 6 IBM 10 Google 4 Dave Carol Adobe Eliza Amazon 11 IBM Is there a way to match all student to jobs? 5 Eliza Carol 7 8 9 10 11 12 Google Eliza IBM Frank Yahoo 12 Yahoo 6 Frank Bob IBM Eliza s Yahoo Frank 65 66 Bipartite matching problem formulated as a network flow problem Maxflow solution (FF shortest augmenting path) 1 Alice 7 Adobe Adobe Alice Amazon Bob Facebook Dave 2 Bob 8 Amazon Adobe Alice Amazon Bob s Yahoo Dave 3 Carol 9 Facebook Facebook Alice Google Carol IBM 10 Google 1 2 3 4 5 6 4 Dave Carol Adobe Eliza Amazon 11 IBM 5 Eliza Carol Google Eliza 7 8 9 10 11 12 IBM Frank Yahoo 12 Yahoo 6 Frank Bob IBM Eliza Yahoo Frank s 1-1 correspondence between maxflow solution and bipartite matching solution 67 68

18 Maxflow solution (FF shortest augmenting path) Maxflow solution (FF shortest augmenting path) 69 70 Maxflow solution (FF shortest augmenting path) Maxflow solution (FF shortest augmenting path) path with back edges 71 72

19 Maxflow solution (FF shortest augmenting path) Maxflow solution path with back edges ss 1 2 3 4 5 6 7 8 9 10 11 12 ts 73 74 Maxflow solution corresponds directly to matching solution Overview (summary) Given. A weighted digraph, source s and target t. 1 Alice 7 Adobe ss Adobe Alice Amazon Bob Facebook Dave 2 Bob 8 Amazon Adobe Alice Amazon Bob Yahoo Dave 1 2 3 4 5 6 Minimum st-cut (mincut) problem. Find an st-cut of minimal weight. 3 Carol Alice Amazon 9 Facebook Facebook Alice Bob Yahoo Carol Facebook Google Carol Dave Adobe Maximum st-flow (maxflow) problem: Assign flows to edges that IBM 10 Google 4 Dave Adobe Carol Eliza Eliza Frank Google IBM Maintain local equilibrium: inflow = outflow at every vertex (except s and t). Amazon 5 Eliza 11 IBM Carol 7 8 9 10 11 12 Maximize total flow into t. Google Eliza IBM Frank Yahoo 12 Yahoo Remarkable fact. These two problems are equivalent! 6 Frank Bob IBM Yahoo Eliza Frank ts Two very rich algorithmic problems Cornerstone problems in combinatorial optimisation Beautiful mathematical duality Still much to be learned! 75 76

Load More