Max Flow Applications

Publish in

Documents

5 views

Please download to get full document.

View again

of 61
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Max Flow Applications. CS302, Spring 2012 David Kauchak. S. A. B. T. Flow graph/networks. Flow network directed, weighted graph (V, E) positive edge weights indicating the “capacity” ( generally, assume integers ) contains a single source s  V with no incoming edges
Transcript
Max Flow ApplicationsCS302, Spring 2012 David KauchakSABTFlow graph/networks
  • Flow network
  • directed, weighted graph (V, E)
  • positive edge weights indicating the “capacity” (generally, assume integers)
  • contains a single source s V with no incoming edges
  • contains a single sink/target t  V with no outgoing edges
  • every vertex is on a path from s to t
  • 2010301020SABTFlow constraints
  • in-flow = out-flow for every vertex (except s, t)
  • flow along an edge cannot exceed the edge capacity
  • flows are positive
  • 2010301020SABTMax flow problemGiven a flow network:what is the maximum flow we can send from s to t that meet the flow constraints?2010301020The residual graph
  • The residual graph Gf is constructed from G
  • For each edge e in the original graph (G):
  • if flow(e) < capacity(e)
  • introduce an edge in Gf with capacity = capacity(e)-flow(e)
  • this represents the remaining flow we can still push
  • if flow(e) > 0
  • introduce an edge in Gfin the opposite direction with capacity = flow(e)
  • this represents the flow that we can reroute/reverse
  • SCDATTBASCDBResidual graph2/4G2/1010/108/86210/102/102/92Gf82826210102287Network flow properties
  • If one of these is are true then all are true (i.e. each implies the the others):
  • f is a maximum flow
  • Gf has no paths from s to t
  • |f| = minimum capacity cut
  • Ford-FulkersonFord-Fulkerson(G, s, t) flow = 0 for all edgesGf = residualGraph(G) while a simple path exists from s to t in Gf send as much flow along the path as possibleGf = residualGraph(G) return flowFord-Fulkerson: runtime?Ford-Fulkerson(G, s, t) flow = 0 for all edgesGf = residualGraph(G) while a simple path exists from s to t in Gf send as much flow along path as possibleGf = residualGraph(G) return flowOverall runtime?
  • O(max-flow * E)
  • SABTO(max-flow * E)Can you construct a graph that could get this running time?Hint:100100100100SABTO(max-flow * E)Can you construct a graph that could get this running time?1001001100100SABTO(max-flow * E)Can you construct a graph that could get this running time?1/1001001/11001/100SABTO(max-flow * E)Can you construct a graph that could get this running time?1/1001/1000/11/1001/100SABTO(max-flow * E)Can you construct a graph that could get this running time?2/1001/1001/11/1002/100SABTO(max-flow * E)Can you construct a graph that could get this running time?2/1002/1000/12/1002/100SABTO(max-flow * E)Can you construct a graph that could get this running time?3/1002/1001/12/1003/100SABTO(max-flow * E)Can you construct a graph that could get this running time?3/1003/1000/13/1003/100What is the problem here? Could we do better?Faster variants
  • Edmunds-Karp
  • Select the shortest path (in number of edges) from s to t in Gf
  • How can we do this?
  • use BFS for search
  • Running time: O(V E2)
  • avoids issues like the one we just saw
  • see the book for the proof
  • or http://www.cs.cornell.edu/courses/CS4820/2011sp/handouts/edmondskarp.pdf
  • preflow-push (aka push-relabel) algorithms
  • O(V3)
  • Other variations…http://akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/08/Goldberg88.pdfhttp://en.wikipedia.org/wiki/Maximum_flowABCEDFGApplication: bipartite graph matchingBipartite graph – a graph where every vertex can be partitioned into two sets X and Y such that all edges connect a vertex u  X and a vertex v  YABCEDFGApplication: bipartite graph matchingAmatching Mis a subset of edges such that each node occurs at most once in MABCEDFGApplication: bipartite graph matchingAmatching Mis a subset of edges such that each node occurs at most once in MmatchingABCEDFGApplication: bipartite graph matchingAmatching Mis a subset of edges such that each node occurs at most once in MmatchingABCEDFGApplication: bipartite graph matchingAmatching Mis a subset of edges such that each node occurs at most once in Mnot a matchingABCEDFGApplication: bipartite graph matchingAmatching can be thought of as pairing the verticesABCEDFGApplication: bipartite graph matchingBipartite matching problem: find the largest matching in a bipartite graphWhere might this problem come up?
  • CS department has n courses and m faculty
  • Every instructor can teach some of the courses
  • What course should each person teach?
  • Anytime we want to match n things with m, but not all things can match
  • ABCEDFGApplication: bipartite graph matchingBipartite matching problem: find the largest matching in a bipartite graph
  • ideas?
  • greedy?
  • dynamic programming?
  • ABCEDFGApplication: bipartite graph matchingSetup as a flow problem:ABCEDFGSTApplication: bipartite graph matchingSetup as a flow problem:edge weights?ABCEDFGSTApplication: bipartite graph matchingSetup as a flow problem:all edge weights are 1ABCEDFGSTApplication: bipartite graph matchingSetup as a flow problem:after we find the flow, how do we find the matching?ABCEDFGSTApplication: bipartite graph matchingSetup as a flow problem:match those nodes with flow between themApplication: bipartite graph matching
  • Is it correct?
  • Assume it’s not
  • there is a better matching
  • because of how we setup the graph flow = # of matches
  • therefore, the better matching would have a higher flow
  • contradiction (max-flow algorithm find maximal!)
  • Application: bipartite graph matching
  • Run-time?
  • Cost to build the flow?
  • O(E)
  • each existing edge gets a capacity of 1
  • introduce E new edges (to and from s and t)
  • Max-flow calculation?
  • Basic Ford-Fulkerson: O(max-flow * E)
  • Edmunds-Karp: O(V E2)
  • Preflow-push: O(V3)
  • Application: bipartite graph matching
  • Run-time?
  • Cost to build the flow?
  • O(E)
  • each existing edge gets a capacity of 1
  • introduce E new edges (to and from s and t)
  • Max-flow calculation?
  • Basic Ford-Fulkerson: O(max-flow * E)
  • max-flow = O(V)
  • O(V E)
  • ABCEDFGApplication: bipartite graph matchingBipartite matching problem: find the largest matching in a bipartite graph
  • CS department has n courses and m faculty
  • Every instructor can teach some of the courses
  • What course should each person teach?
  • Each faculty can teach at most 3 courses a semester?
  • Change the s and t edge weights to 3Survey Design
  • Design a survey with the following requirements:
  • Design survey asking nconsumers about m products
  • Can only survey consumer about a product if they own it
  • Question consumers about at most q products
  • Each product should be surveyed at most stimes
  • Maximize the number of surveys/questions asked
  • How can we do this?
  • p1p2p3c1c2c3c4STSurvey Designconsumersproductscapacity 1 edge if consumer owned producteach consumer can answer at most q questionseach product can be questioned about at most s timesqsqsqsqSurvey design
  • Is it correct?
  • Each of the comments above the flow graph match the problem constraints
  • max-flow finds the maximum matching, given the problem constraints
  • What is the run-time?
  • Basic Ford-Fulkerson: O(max-flow * E)
  • Edmunds-Karp: O(V E2)
  • Preflow-push: O(V3)
  • Edge Disjoint PathsTwo paths are edge-disjoint if they have no edge in common25s36t47Edge Disjoint PathsTwo paths are edge-disjoint if they have no edge in common25s36t47Edge Disjoint Paths ProblemGiven a directed graph G = (V, E) and two nodes s and t, find the max number of edge-disjoint paths from s to t25s36t47Why might this be useful?Edge Disjoint Paths Problem
  • Given a directed graph G = (V, E) and two nodes s and t, find the max number of edge-disjoint paths from s to t
  • Why might this be useful?
  • edges are unique resources (e.g. communications, transportation, etc.)
  • how many concurrent (non-conflicting) paths do we have from s to t
  • Edge Disjoint PathsAlgorithm ideas?25s36t47stEdge Disjoint PathsMax flow formulation: assign unit capacity to every edge11111111111111What does the max flow represent?Why?stEdge Disjoint PathsMax flow formulation: assign unit capacity to every edge11111111111111
  • max-flow = maximum number of disjoint paths
  • correctness:
  • each edge can have at most flow = 1, so can only be traversed once
  • therefore, each unit out of s represents a separate path to t
  • SSTSTTMax-flow variationsWhat if we have multiple sources and multiple sinks (e.g. the Russian train problem has multiple sinks)?capacity networkSSTSTTS’T’Max-flow variationsCreate a new source and sink and connect up with infinite capacities…capacity networkSABTMax-flow variationsVertex capacities: in addition to having edge capacities we can also restrict the amount of flow through each vertex15201030102010What is the max-flow now?SABTMax-flow variationsVertex capacities: in addition to having edge capacities we can also restrict the amount of flow through each vertex10/1510/2010/103010/1010/2010/1020 unitsSABTMax-flow variationsVertex capacities: in addition to having edge capacities we can also restrict the amount of flow through each vertex15201030102010How can we solve this problem?SA’B’TABMax-flow variationsFor each vertex v
  • create a new node v’
  • create an edge with the vertex capacity from v to v’
  • move all outgoing edges from v to v’
  • 15201030102010Can you now prove it’s correct?Max-flow variations
  • Proof: show that if a solution exists in the modified graph, then a solution exists in the original graph
  • we know that the vertex constraints are satisfied
  • no incoming flow can exceed the vertex capacity since we have a single edge with that capacity from v to v’
  • we can obtain the solution, by collapsing each v and v’ back to the original v node
  • in-flow = out-flow since there is only a single edge from v to v’
  • because there is only a single edge from v to v’ and all the in edges go in to v and out to v’, they can be viewed as a single node in the original graph
  • More problems:maximum independent pathTwo paths are independentif they have no verticesin common25s36t47More problems:maximum independent pathTwo paths are independentif they have no verticesin common25s36t47More problems:maximum independent pathFind the maximum number of independent pathsIdeas?25s36t47stmaximum independent pathMax flow formulation:
  • assign unit capacity to every edge (though any value would work)
  • assign unit capacity to every vertex
  • 11111111111111111111Same idea as the maximum edge-disjoint paths, but now we also constrain the verticesMore problems: wireless network
  • The campus has hired you to setup the wireless network
  • There are currently m wireless stations positioned at various (x,y) coordinates on campus
  • The range of each of these stations is r (i.e. the signal goes at most distance r)
  • Any particular wireless station can only host k people connected
  • You’ve calculate the n most popular locations on campus and have their (x,y) coordinates
  • Could the current network support n different people trying to connect at each of the n most popular locations (i.e. one person per location)?
  • Prove correctness and state run-time
  • Sp1w1TpnwmAnother matching problem
  • npeople nodes and n station nodes
  • if dist(pi,wj) < r then add an edge from pi to wj with weigth 1 (where distis euclidean distance)
  • add edges s -> pi with weight 1
  • add edges wj -> t with weight k
  • add edge if dist(pi, wj) < r
  • solve for max-flow
  • check if flow = m
  • k1……1kCorrectness
  • If there is flow from a person node to a wireless node then that person is attached to that wireless node
  • if dist(pi,wj) < r then add an edge from pi to wj with weigth 1 (where dist is euclidean distance)
  • only people able to connect to node could have flow
  • add edges s -> pi with weight 1
  • each person can only connect to one wireless node
  • add edges wj -> t with weight L
  • at most L people can connect to a wireless node
  • If flow = m, then every person is connected to a node
  • Runtime
  • E = O(mn): every person is within range of every node
  • V = m + n + 2
  • max-flow = O(m), s has at most m out-flow
  • O(max-flow * E) = O(m2n): Ford-Fulkerson
  • O(VE2) = O((m+n)m2n2): Edmunds-Karp
  • O(V3) = O((m+n)3): preflow-push variant
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks