[Algorithms II] Week 3-1 Maximum Flow

1. Introduction to Maxflow

Min-cut pb

  • input: edge-weighted digraph G, each edge e has weight("capacity") c[e]>=0, a source vertex s, a target vertex t.
  • def. an st-cut (A,B) is a partition of vertices into 2 disjoint sets A and B, with s in set A and t in set B.
  • def. the capacity of a cut (A,B) is sum of capacities of edges going from A to B (not considering B to A).


⇒ min-cut pb: find the cut (A,B) with min-capacity.

Max-flow pb

  • same input: graph G, source s, target t
  • def. an st-flow is an assignment of values to edges f: e→f[e] such that:
    • capacity constraint: 0<=f[e]<=c[e] for any e;
    • local equilibrium: for any vertex v (other than s or t), inflow=outflow;
  • def. the value of a flow f is the inflow at t. (assume no ingoing edge to s or outgoing edge to t)


⇒ max-flow pb: find f with max value.

remark: max-flow and min-cut are dual problems.

2. Ford-Fulkerson Algorithm

def. given a flow f for a graph, an "augment path" is an undirected path form s to t, if there exist df>0 ("bottleneck capacity") such that:

  • for forward edges e: can augment flow by df (not full: f[e]+df<=c[e])
  • for backward edges: can decrease flow by df (not empty: f[e]-df>=0)

  • def. residual capacity
    • for forward edge e, residual-cap = c[e]-f[e]
    • for backward edge e, residual-cap = f[e]

⇒ an aug-path is a path where each edge has residual capacity >0.

blocking edges: full forward edge or empty backward edge.

→ idea: increase flow along augment paths.
[algo]

  • start: 0 flow: f[e]=0 for all e.
  • find an augment path (and the corresponding df) in graph, and change the flows along the path by +/-df.
  • loop until no augment path exists. (ie. all path s→t are blocked either by a full forward edge or an empty backward edge, ie. by an edge with 0 residual capacity)

FF is a gernel algorithm:

3. Maxflow-Mincut Theorem

def. for a cut (A,B), the net flow across the cut (netflow(A,B)) is the sum of flows from A to B minus flows from B to A.

[flow-value Lemma]
For any flow f and any cut (A,B)netflow(A,B) = value(f).
pf.
induction on the size of set B.
base case, when B={t}, by def we have netflow(A,B) = value(f)
when moving any vertex v from A to B:
* netflow(A, B) augment by flow(A→v)+flow(B→v)=inflow(v),
* netflow(A, B) decrease by flow(v→A)+flow(v→B)=outflow(v),
* by equilibrium of flow, netflow(A',B')=netflow(A,B)=value(f)

ex. (A: gray vertices, B: white vertices)

[cor] outflow(s)=inflow(t)=value(f)

[weak duality]
For any flow f and any cut (A,B), ⇒ value(f) <= capacity(A,B).

[Augmenting path Th]
A flow f is maxflow iff there is no augment path.

[maxflow-mincut Th]
value(maxflow) = capacity(mincut).

pf.
for any flow f, prove the equivalence of the 3 following statements:
i. there exists a cut st: capacity(cut) = value(f).
ii. f is a maxflow.
iii. there is no augmenting path wrt f.

  • [i⇒ii]

suppose cut(A,B) st: capacity(A,B)=value(f)
⇒ by weak duality, for any other flow f', vlaue(f')<=capacity(A,B)=value(f)

  • [ii⇒iii] (eqv to prove ~iii⇒~ii)

suppose there is an aug-path from s to t, of bottleneck capacity=df,
⇒ by improving f with df, we get a f' > f

  • [iii⇒i]

suppose there is no aug-path, ie, all path from s to t are blocked by some full-forward edge or empty backward edge.
⇒ let A:=vertices connected with s by a path with no blocking edges, and B := the rest
(so once we get a maxflow, we can compute the mincut in this way)

→ for all edges across A and B, all forward edges are full, all backward edges are empty
⇒ capacity(A,B) = netflow(A,B) = value(f) by flow-value lemma
CQFD... 过瘾...

4. Running Time Analysis

  • getting a mincut form maxflow? → easy (as discussed in the pf above)
  • computing an aug-path? → BFS
  • does FF algo always terminate? how many augmentations? → ...

integer capacity graphs

special case of FF algo: edge capacities are integers between 1 and U.

invariant: flow is always integer all along FF algo.

[prop] nb of augmentations <= value of maxflow.
pf. each augmentation will add flow by >=1.

[integrality Th] There exist an integer-valued maxflow.

Bad case for FF

nb of augmentation == value of maxflow
(each time, the path through the middle edge is chosen as aug-path)

can be easily avoided⇒ by using shortest(nb of edges)/fastest(biggest df) path

Performance of FF depends on the algo for choosing aug-path:

5. Java Implementation

representation of flow graph

  • flow edge:

each e= v→w, have flow f[e] and capacity c[e].

  • flow graph:

put e in both v and w's adj-list.

  • flow augmentation (by delta)
    • for forward edge e, f[e] += delta
    • for backward edge e, f[e] -= delta

Residual graph Gr

def. For a flow f and a graph G, the residual graph Gr is obtained by:

for each edge e=v→w, (with c[e] and f[e]) in G, put in Gr:
e1=v→w, with weight=c[e]-f[e]
e2=w→v, with weight=f[e] (即两个方向上的weight都为residual capacity)

(rmq: Gr is just a weighted digraph, not a flow graph)

[prop] Augment path in G is equivalent to a path in Gr (df of aug-path in G = min edge weight in Gr).
(但是实现的时候其实不用显式构造Gr, 只需BFS的时候修改一下即可)

APIs

这里的API设计的非常合理... 导致每一部分的代码量都不大... NB

  • flow-edge:
    rmq. both calculate residual-cap and augmentation need to specify a direction, so we need a index v as parameter for these 2 functions.

    public class FlowEdge{   
        private final int v, w;   
        private final double capacity;   
        private double flow=0.0;   
        FlowEdge(int v, int w, double cap);   
        int from();   
        int to();   
        int other(int v);   
        double capacity();   
        double flow();   
        double residualCapTo(int v);// residual capacity   
        void addFlowTo(int v, double delta);// augment residual flow   
    }
    
  • flow graph:

    public class FlowNetwork{   
        private Bag<FlowEdge>[] adj;//use adj-list representation for flow graph   
        FlowNetwork(int V);   
        void addEdge(FlowEdge e);   
        Iterable<FlowEdge> adj(int v);// both incoming and outgoing edges   
        ...   
    }
    
  • FF algo:

    • use a function hasAugPath() to test termination
    • use a function bottleNeck() to get delta
    • if a augpath is found, use two arrays reached[] and edgeTo[] to get the augpath (find the path backwards).

code:

public class FordFulkerson{   
private boolean[] reached; //reached[v] indicates if a path s-->v exists in Gr, used in DFS   
private FlowEdge[] edgeTo;// edgeTo[v] = last edge on the path s-->v   
private double value=0.0;// value of flow   
public FordFulkerson(FlowNetwork G, int s, int t){   
    while(this.hasAugPath(G,s,t)){   
        double delta = this.bottleNeck();   
        for(int v=t; v!=s; v=edgeTo[v].other(v))   
            edgeTo[v].addFlowTo(v, delta);   
        this.value += delta;// each time the flow value augments by delta   
    }   
}   
private double bottleNeck(){//bottleneck-cap = min residual flow on the aut-path   
    double bottleneck = 9999999;   
    assert(reached[t]);// the aug-path should exsit   
    for(int v=t; v!=s; v = edgeTo[v].other(v))   
        bottleneck = Math.min(bottleneck, edgeTo[v].);   
    return bottleneck;   
}   
private boolean hasAugPath(FlowNetwork G, int s, int t){   
    // perform a BFS    
    Queue<Integer> q = new LinkedList<Integer>();   
    this.reached = new boolean[G.V()];   
    this.edgeTo = new FlowEdge[G.V()];   
    q.add(s);   
    while(!q.isEmpty()){   
        int v = q.deque();   
        for(FlowEdge e:G.adj(v)){   
            int w = e.other(v);   
            if(!reached[w] && e.residualCapTo(w)>0){// modified BFS: valid edges are those with  residualCap>0   
                edgeTo[w] = e;   
                reached[w] = true;   
                if(w==t) return true;// t is reached by BFS  
                q.enqueue(w);   
            }   
        }   
    }// BFS while loop    
    return false;   
}   
}//class FF

6. Maxflow Applications

关键是建模很巧妙...

ex1. bipartite matching pb

二分图的最大匹配问题. (有点像marriage stable问题...但是不一样 因为没有preference order)

⇒ is there a way to match all students to a job?
ie. given a bipartite graph, find a perfect matching.

modeling

  • add source s and target t
  • all edges from s to students: capacity=1
  • all edges from companies to t: capacity=1
  • all edges from student to company: capacity=INF

⇒ find maxflow in the graph

when no perfect matching: mincut can explain why

in the above case, student 2,4,5 can only be matched to 7,10
⇒ mincut can help us find such cases!

recall: how to get mincut from maxflow

mincut = (A,B), where:
A:=vertices connected with s by a path with non blocking edges,
B := the rest
(blocking edges: full forward edge or empty backward edge on path)

ex.

  • let S=students on s side of mincut (in above case, S={2,4,5})
  • let T=companies on s side of mincut (in above case, T={7,10})
  • |S|>|T|, that's why no perfect matching!

ex2. baseball elimination


(前三列是目前成绩, 后面四列是接下来赛程矩阵)
Montreal is mathematically eliminated → easy to see
→ Philly is mathematically eliminated also !

  • another case:


Detroit is mathematically eliminated !

whether team-4 still has a chance to win?
modelling

  • remaining games flow from s to t.
  • use team-pairs ans teams as vertices
  • carefully chosen capacities(see below)


⇒ team 4 could win iff all flow from s are full (ie. all match points can be repartitioned over other teams without depassing team 4's maximum wins).
总之很巧妙....

comments powered by Disqus