最大流問題(Maximum Flow Problem) - kanetaiの二次記憶装置

最小費用流問題を特殊化。
ソース節点sが複数ユニットを配布節点w経由でシンク節点に到達するように流す。各辺には、容量と実際のフローが付随する。
目標：ネットワークフローFを最大にする

コード

残余ネットワークから増加パスを求める系のアルゴリズムを使う場合に必要な、
求めた各辺のフローと最大フローと、増加パスのバックポインタ等。
列挙型でアルゴリズムを作ることにした。

public interface MaximumFlowSolver {
	public class Result {
		final int[][] capacity, flow;
		final int[] trace;
		public int maximumFlow;
		public Result(final List<List<Edge>> adjList) {
			int n = adjList.size();
			capacity = new int[n][n]; flow = new int[n][n]; trace = new int[n];
			maximumFlow = 0;
			for (final List<Edge> row : adjList) for (final Edge e : row) capacity[e.s][e.d] += e.w;
		}
		protected int residualCapacity(int src, int dst) {
			return capacity[src][dst] - flow[src][dst];
		}
	}
	public Result solve(final List<List<Edge>> adjList, int s, int t);
}

public enum MaximumFlowAlgorithm implements MaximumFlowSolver {
	Algorithm1 { 
               @Override public Result solve(List<List<Edge>> adjList, int s, int t){/*...*/}
        } /*,Algorithm2 { 
             ....
        }*/;
}

Ford-Fulkerson algorithm

増加パスPを(DFSで)見つけて、P上の辺の残余容量の最小値分のフローを増加させる。
最大流最小カット定理より増加パスPが存在しなくなった時点で最大フローとなる。
1回の増加パスで少なくともフローが1増えるとすると、whileループの繰り返しは高々 $F_{\max}$ 回。
増加パスPはO(|E|)で求まり、他の操作もO(|E|)で計算できるので、
Ford-Fulkerson algorithmの計算量は $O(|E|F_{\max})$ .
※容量が実数だと無限ループして求まらない場合がある。
→容量は非負の整数である必要がある。(実は負でも良い?)
Algorithm Ford-Fulkerson $(G=(V,E),s,t)$
1: 　for ( $(u,v) \in E$ ) {
2: 　　　　 $f(u,v):=0; f(v,u):=0;$
3: 　}
4: 　while (増加パスPが存在する) {
5: 　　　　 $c_P:= \min \{ c_f(u,v) |(u,v)\in P \}$
6: 　　　　for ( $(u,v)\in P$ ) { //augment flow.
7: 　　　　　　　 $f(u,v):= f(u,v)+c_P;$
8: 　　　　　　　 $f(v,u):= -f(u,v);$
9: 　　　　}
10:　}
※ $\sum_{e\in \delta^+(s)}f(e) = F_{\max}$ になっている。

Edmonds-Karp algorithm

Ford-Fulkerson algrithmの増加パスの求め方を限定したもの。
最短(ホップ数)となる増加パスをBFSで求める。
一つの辺が臨界辺するには、高々O(|V|)回行使すればよいので、
増加パスを求める回数はO(|V||E|).
従ってEdmonds-Karp algorithmの計算量は $O(|V||E|^2)$ となる。
参考http://www.comp.cs.gunma-u.ac.jp/~koichi/ALG2/7.4.pdf
※容量が非負の実数であれば必ず停止する(整数でなくても良い?)
※下のコードだとnew Result()で隣接行列の生成コスト $O(|V|^2)$ が発生している。

EdmondsKarp { /** O(|V||E|^2) */
	@Override public Result solve(List<List<Edge>> adjList, int s, int t) {
		Result res = new Result(adjList);
		while (augmentingPathExists(res, adjList, s, t)) {
			int cp = INF;
			for (int j = t; res.trace[j] != j; j = res.trace[j])
				cp = Math.min(cp, res.residualCapacity(res.trace[j], j));
			for (int j = t; res.trace[j] != j; j = res.trace[j]) {
				res.flow[res.trace[j]][j] += cp;
				res.flow[j][res.trace[j]] -= cp;
			}
			res.maximumFlow += cp;
		}
		return res;
	}
	private boolean augmentingPathExists(final Result res, final List<List<Edge>> adjList, int s, int t) { //BFS
		Arrays.fill(res.trace, -1);
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(s); res.trace[s] = s;
		while (!q.isEmpty() && res.trace[t] == -1) {
			int u = q.poll();
			for(final Edge e : adjList.get(u)) if (res.trace[e.d] == -1 && res.residualCapacity(u, e.d) > 0) {
				res.trace[e.d] = u;
				q.add(e.d);
			}
		}
		return (res.trace[t] >= 0); // trace[x] == -1 <=> t-side
	}
}

Dinic's(Dinitz')algorihtm

層別ネットワークをBFS $O(|E|)$ で作成し、DFSで流せるだけ流してブロッキングフローを作るというステップを繰り返す。
１ステップあたりのDFSによるフローの増加に要する計算量はO(|V||E|).※層別ネットワーク上でsからtへのホップ数<|V|
ブロッキングフローを流すと少なくとも残余ネットワークの増加パスが１長くなるので、繰り返し回数は高々 $O(|V|)$ 回となる。
よって計算量は $O(|V|^2|E|)$ .
Algorithm Dinic $(G=(V,E),s,t)$
1: 　for ( $(u,v) \in E$ ) {
2: 　　　　 $f(u,v):=0; f(v,u):=0;$
3: 　}
4: 　while (s-t path exists in Dinic's layered netrowk) {
5: 　　　　f:= blocking flow;
6: 　　　　augment flow by f;
7:　}

Dinic { /** O(|V|^2|E|) */
	@Override public Result solve(List<List<Edge>> adjList, int s, int t) {
		Result res = new Result(adjList);
		int n = adjList.size();
		boolean[] used = new boolean[n];
		for (boolean augmented = true; augmented; ) {
			augmented = false;
			calcLayreLevel(res, adjList, s, t); //make layered network
			Arrays.fill(used, false);
			while (true) {
				int f = augment(used, res, adjList, s, t, INF);
				if (f == 0) break;
				res.maximumFlow += f; augmented = true;
			}
		}
		return res;
	}
	private void calcLayreLevel(Result res, final List<List<Edge>> adjList, int s, int t) {
		Arrays.fill(res.trace, -1); res.trace[s] = 0; //trace[v] indicates level of v.
		Queue<Integer> q = new LinkedList<Integer>(); q.add(s);
		for (int lm = adjList.size(); !q.isEmpty() && res.trace[q.peek()] < lm; ) { //BFS
			int u = q.poll();
			if (u == t) lm = res.trace[u];
			for (Edge e : adjList.get(u)) if (res.trace[e.d] == -1 && res.residualCapacity(u, e.d) > 0) {
				res.trace[e.d] = res.trace[u] + 1;
				q.add(e.d);
			}
		}
	}
	private int augment(boolean[] used, Result res, final List<List<Edge>> adjList, int u, int t, int minC) { //DFS
		if (u == t) return minC;
		if (minC == 0 || used[u]) return 0;
		used[u] = true;
		for(Edge e : adjList.get(u)) if (res.trace[e.d] > res.trace[u]) { //level(e.d) > level(u)
			int f = augment(used, res, adjList, e.d, t, Math.min(minC, res.residualCapacity(u, e.d)));
			if (f > 0) {
				res.flow[u][e.d] += f; res.flow[e.d][u] -= f;
				used[u] = false;
				return f;
			}
		}
		return 0;
	}
}