Flow network and min cut

A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. A flow network has designated source and sink nodes s and t. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. min cut is one of flow network problem.

disjoint set

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. A s-t cut is a cut that requires the source ‘s’ and sink ‘t’ to be in different subsets. The cut-set only consists of edges going from the source’s side to the sink’s side. The capacity of s-t cut is defined by the sum of the capacity of each edge in the cut-set. A minimum s-t cut, or min cut, has the minimum capacity of the cut-set. For example, in the above graph, the min s-t cut-set is {{A, C}{B,T}}.

After you find the minimum s-t cut-set, you classify nodes in a graph as upstream, downstream and central: Upstream nodes: contains all nodes v such that, for all minimum s-t cuts (A, B), v is in A (always on the source side). Downstream nodes: contains all nodes v such that, for all minimum s-t cuts (A, B), v is in B (always on the sink side). Central nodes: contains all nodes v such that there exists some minimum cut where v is on the source side and there exists some minimum cut where v is on the sink side. In the above diagram, the upstream is {A, B, S}, downstream is {C, T}, central is {}.

The min cut is important in flow network analysis because it represents the bottleneck in the network that limits the maximum flow that can be sent from the source to the sink. The max-flow min-cut theorem states that the maximum flow in a flow network is equal to the minimum capacity of any cut in the network. Here you will learn how to implement min cut in flow network.

1. Implement FlowNetwok

A flow network is implemented as a weighted, directed graph. It is represented as a map of maps. In the map G, keys are nodes (of generic type T), and values are map of edges.

In the map of edges, keys are nodes (of generic type T), and values are integers. So, if a node u is a key in the map G, and its map has a key-value pair v, i, then this should be interpreted as the graph having directed edge (u, v) with capacity i. The source and sink parameters are of generic type T; these identify the source and sink nodes of the flow network and can be assumed to be keys in the map G.

Residual Graph of a flow network is a graph which indicates additional possible flow. To make out FlowNetwork class working as residual graph, you have two additional methods fillEmptyEdge(). If an edge has not capacity, set capacity to 0. Another method cloneGraph(), since you update capacity on the way to find the path. After you clone the graph, you make the changes to the cloned graph.




2. Implement cut-partition

Implement an algorithm to produce this partition of nodes. In particular, you should implement a function

static Map cut_partition(<Map> G, T source, T sink)

In the method, clone the graph first. Then by using bfs, you find out if there is a path from source to sink. bfs also builds parent[] array. Using the parent[] array, you traverse through the found path and find possible flow through this path by finding minimum residual capacity along the path. You add the found path flow to overall flow. Meanwhile, you update residual capacities. Subtract path flow from all edges along the path and add path flow along the reverse edges. Meantime you add path flow along reverse edges because you may later need to send flow in reverse direction.

Now use dfs to find all reachable nodes from source and mark it in a Boolean map visited. If reachable, visited value for the node is true, otherwise is false. Now it is time to find the min cut, Check all pairs of nodes, when their edge has capacity, if one’s visited is true and the other’s visited is false, you can add first one to upstream and the second one in downstream.





upstream: [0, 1, 4]
downstream: [3, 5]
central: [2]

upstream: [A, B, S]
downstream: [C, T]
central: []

O Notation:

Time complexity: O(V2+E)
Space complexity: O(V)
V is number of nodes, E is number of edges


Download FlowNetworkMinCutJava.zip
Download FlowNetworkMinCutJavaScript.zip
Download FlowNetworkMinCutPython.zip

Comments are closed