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/networksFlow 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 constraintsin-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 graphThe 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 propertiesIf 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 variantsEdmunds-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 graphideas? 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 matchingIs 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 matchingRun-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 matchingRun-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 graphCS 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 DesignDesign 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 designIs 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 ProblemGiven 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 edge11111111111111max-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 vcreate 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 variationsProof: 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 networkThe 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 problemnpeople 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) < rsolve for max-flow check if flow = m k1……1kCorrectnessIf 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 RuntimeE = 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

Related Documents

Oct 3, 2017

Oct 4, 2017

Oct 11, 2017

Oct 11, 2017

Oct 27, 2017

Mar 9, 2018

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