Maximum Flow

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

1.  Definitions:

--  Input : An edge-weighted digraph (edge capacity) , source vertex s, and target vertex t.

--  st-cut : A partition of the vertices into two disjoint sets, with s in one set A and t in the other set B.

--  capacity of the cut (A, B) : The sum of the capacities of the edges from A to B.

--  Minimum st-cut (mincut) problem: Find a cut of minimum capacity.

2.  Maxflow problem ：

--  Input: An edge-weighted (capacity) digraph , source vertex s, and target vertex t.

--  An st-flow (flow) is an assignment of values to the edges such that:

-  Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity.

-  Local equilibrium: inflow = outflow at every vertex (except s and t).

--  The value of a flow is the inflow at t.( we assume no edge points to s or from t. )

--  Maximum st-flow (maxflow) problem: Find a flow of maximum value.

3.  Remarkable fact: Mincut problem and Maxflow problem are dual!

4.  Ford-Fulkerson algorithm

--  Find an augmenting path : undirected path from s to t such that:

--  Can increase flow on forward edges (not full).

--  Can decrease flow on backward edge (not empty).

--  Increase flow along augmenting paths

--  Termination: No augmenting path : All paths from s to t are blocked by either a

--  Full forward edge.

--  Empty backward edge.

5.  Relationship between flows and cuts:

--  The net flow across a cut (A, B) is the sum of the flows on its edges from A to B minus the sum of the flows on its edges from from B to A.

--  Flow-value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.

--  Pf. By induction on the size of B.

-  Base case: B = { t }.

-  Induction step: remains true by local equilibrium when moving any vertex from A to B.

--  Weak duality: Let f be any flow and let (A, B) be any cut. Then, the value of the flow ≤ the capacity of the cut.

--  Pf. Value of flow f = net flow across cut (A, B) ≤ capacity of cut (A, B).

6.  Maxflow-mincut theorem

--  Augmenting path theorem: A flow f is a maxflow iff no augmenting paths.

--  Maxflow-mincut theorem. Value of the maxflow = capacity of mincut.

--  Pf. The following three conditions are equivalent for any flow f :

i. There exists a 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.

--  [ i ⇒ ii ]

-  Suppose that (A, B) is a cut with capacity equal to the value of f.

-  Then, the value of any flow f ' ≤ capacity of (A, B) = value of f.

-  Thus, f is a maxflow.

--  [ ii ⇒ iii ] We prove contrapositive: ~iii ⇒ ~ii.

-  Suppose that there is an augmenting path with respect to f.

-  Can improve flow f by sending flow along this path.

-  Thus, f is not a maxflow.

--  [ iii ⇒ i ]

-  Suppose that there is no augmenting path with respect to f.

-  Let (A, B) be a cut where A is the set of vertices connected to s by an undirected path with no full forward or empty backward edges.

-  By definition, s is in A; since no augmenting path, t is in B.

-  Capacity of cut = net flow across cut = value of flow f.

7.  Computing a mincut from a maxflow:

--  By augmenting path theorem, no augmenting paths with respect to f.

--  Compute A = set of vertices connected to s by an undirected path with no full forward or empty backward edges.

8.  Does FF always terminate?

yes, provided edge capacities are integers (or augmenting paths are chosen carefully)

9.  Ford-Fulkerson algorithm with integer capacities :

--  Important special case: Edge capacities are integers between 1 and U.

--  Invariant: The flow is integer-valued throughout Ford-Fulkerson.

-- Pf. [by induction]

-  Bottleneck capacity is an integer.

- Flow on an edge increases/decreases by bottleneck capacity.

--  Proposition. Number of augmentations ≤ the value of the maxflow.

--  Pf. Each augmentation increases the value by at least 1.

--  Integrality theorem. There exists an integer-valued maxflow.

--  Pf. Ford-Fulkerson terminates and maxflow that it finds is integer-valued.

--  Bad news : Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow.

--  Good news : This case is easily avoided. [use shortest/fattest path]

10.  FF performance depends on choice of augmenting paths :

11.  Implementation Considerations of FF:

--  Flow edge data type: Associate flow fe and capacity ce with edge e = v→w.

--  Flow network data type: Need to process edge e = v→w in either direction: Include e in both v and w's adjacency lists.

--  Residual capacity:

-  Forward edge: residual capacity = ce - fe.

-  Backward edge: residual capacity = fe.

--  Augment flow.

-  Backward edge: subtract Δ.

--  Residual network : Augmenting path in original network is equivalent to directed path in residual network.

12.  Flow edge: Java implementation:

```public class FlowEdge
{
private final int v, w; // from v to w
private final double capacity; // capacity
private double flow; // flow

public FlowEdge(int v, int w, double capacity)
{
this.v = v;
this.w = w;
this.capacity = capacity;
}

public int from() { return v; }
public int to() { return w; }
public double capacity() { return capacity; }
public double flow() { return flow; }
public int other(int vertex)
{
if (vertex == v) return w;
else if (vertex == w) return v;
else throw new RuntimeException("Illegal endpoint");
}

public double residualCapacityTo(int vertex)
{
if (vertex == v) return flow; // from w to v , backward edge
else if (vertex == w) return capacity - flow; // from v to w, forward edge
else throw new IllegalArgumentException();
}

public void addResidualFlowTo(int vertex, double delta)
{
if (vertex == v) flow -= delta; //backward edge
else if (vertex == w) flow += delta; //forward edge
else throw new IllegalArgumentException();
}
}```

13.  Flow network: Java implementation :

```public class FlowNetwork
{
private final int V;
public FlowNetwork(int V)
{
this.V = V;
for (int v = 0; v < V; v++)
}

{
int v = e.from();
int w = e.to();
}

}```

14.  Ford-Fulkerson: Java implementation :

```public class FordFulkerson
{
private boolean[] marked; // true if s->v path in residual network
private FlowEdge[] edgeTo; // last edge on s->v path
private double value; // value of flow

public FordFulkerson(FlowNetwork G, int s, int t)
{
value = 0.0;
while (hasAugmentingPath(G, s, t))
{
double bottle = Double.POSITIVE_INFINITY;
for (int v = t; v != s; v = edgeTo[v].other(v))
bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
for (int v = t; v != s; v = edgeTo[v].other(v))
value += bottle;
}
}

public double value()
{ return value; }

public boolean inCut(int v)
{ return marked[v]; }

private boolean hasAugmentingPath(FlowNetwork G, int s, int t)
{
edgeTo = new FlowEdge[G.V()];
marked = new boolean[G.V()];
Queue<Integer> queue = new Queue<Integer>();
queue.enqueue(s);
marked[s] = true;
while (!queue.isEmpty())
{
int v = queue.dequeue();
{
int w = e.other(v);
if (e.residualCapacityTo(w) > 0 && !marked[w])
{
edgeTo[w] = e;
marked[w] = true;
queue.enqueue(w);
}
}
}
return marked[t];
}
}```

15.  Maxflow application on bipartite matching :

--  Problem definition: (Given a bipartite graph, find a perfect matching.)

-  N students apply for N jobs.

-  Is there a way to match all students to jobs?

--  Network flow formulation of bipartite matching :

-  Create s, t, one vertex for each student, and one vertex for each job.

-  Add edge from s to each student (capacity 1).

-  Add edge from each job to t (capacity 1).

-  Add edge from student to each job offered (infinite capacity).

--  When no perfect matching, mincut explains why :

Consider mincut (A, B).

-  Let S = students on s side of cut.

-  Let T = companies on s side of cut.

-  Fact: | S | > | T |; students in S can be matched only to companies in T.

16.  Maxflow application on Baseball elimination problem :

--  Problem definition: Which teams have a chance of finishing the season with the most wins?

--  Observation. Answer depends not only on how many games already won and left to play, but on whom they're against.

--  maxflow formulation : Remaining games flow from s to t.

--   Team 4 not eliminated iff all edges pointing from s are full in maxflow.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Cliff at July 15, 2014 - 9:11 PM