Graph AlgorithmsNetwork FlowNetwork Flow ApproachNetwork Flow ApplicationsNetwork Flow ProblemNetwork FlowMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmMaximum Flow AlgorithmNetwork Flow111111Graph AlgorithmsCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State UniversityNetwork Flow2How much freight can flow from Seattle to Pullman?From Seattle to Chicago?From Washington to Illinois?Network Flow Approach Let the waypoints (cities, distribution centers) be vertices in a graph Let the routes (roads, rails, waterways, airways) between waypoints be directed edges in the graph Each edge has a weight representing the route’s capacity Choose a starting point s and an ending point t Determine the maximum rate (e.g., tons/hour) at which we can flow freight from point s to point t Without the freight piling up anywhere along the way3Network Flow Applications Freight flow through shipping networks Fluid flow through a network of pipes Data flow (bandwidth) through computer networks Nutrient flow through food networks Electricity flow through power distribution systems People flow through mass transportation systems Traffic flow through a city4Network Flow Problem Given Directed graph G=(V,E) with edge capacities cv,w Source vertex s Sink vertex t Constraints Flow along directed edge (v,w) cannot exceed capacity cv,w At every vertex (except s and t) the total flow coming in must equal the total flow going out Find Maximum amount of flow from s to t5Network Flow Example network graph (left) and its maximum flow (right)6Maximum Flow Algorithm Flow graph Gf Indicates the amount of flow on each edge in the network Residual graph Gr Indicates how much more flow can be added to each edge in the network Residual capacity = (capacity – current flow) Edges with zero residual capacity removed Augmenting path Path from s to t in Gr Edge with smallest residual capacity in the path indicates amount by which flow can increase along path7Maximum Flow Algorithm Example8Network Graph Initial Flow Graph Residual GraphAugmentingPath (s,b,d,t)Maximum Flow Algorithm While an augmenting path exists in Gr Choose one Flow increase FI = minimum residual capacity along augmenting path Increase flows along augmenting path in flow graph Gfby FI Update residual graph Gr9Maximum Flow Algorithm Example (cont.) after choosing (s,b,d,t)10Network GraphFlow Graph (f=2)Residual GraphMaximum Flow Algorithm Example (cont.) after choosing (s,a,c,t)11Network GraphFlow Graph (f=4)Residual GraphMaximum Flow Algorithm Example (cont.) after choosing (s,a,d,t)12Network GraphFlow Graph (f=5)Residual GraphTerminates with maximum flow f = 5.Maximum Flow Algorithm Problem: Suppose we chose augmenting path (s,a,d,t) first13Network GraphFlow Graph (f=3)Residual GraphTerminates with flow f = 3.Maximum Flow Algorithm Solution Indicate potential for back flow in residual graph I.e., allow another augmenting path to undo some of the flow used by a previous augmenting path14Network GraphFlow Graph (f=3)Residual GraphMaximum Flow Algorithm Example (cont.) after choosing (s,b,d,a,c,t)15Network GraphFlow Graph (f=5)Residual GraphTerminates with maximum flow f = 5.Maximum Flow Algorithm Analysis If edge capacities are rational numbers, then this algorithm always terminates with maximum flow If capacities are integers and maximum flow is f, then running time is O(f · |E|) Flow always increases by at least 1 with each augmenting path Augmenting path can be found on O(|E|) time using unweighted shortest-path algorithm Problem: Can be slow for large f16Maximum Flow Algorithm Variants Always choose augmenting path allowing largest increase in flow O(|E|) calls to O(|E| log |V|) Dijkstra algorithm Running time O(|E|2log |V|) Always choose the augmenting path with the fewest edges (unweighted shortest path) At most O(|E||V|) augmenting steps, each costing O(|E|) for call to BFS Running time O((|E|2|V|)17Network Flow Variants Multiple sources and sinks Create super-source with infinite-capacity links to each source Create super-sink with infinite-capacity links from each sink Min-cost flow Each edge has capacity and cost Find maximum flow with minimum cost No known fast