kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

強連結成分分解(Decomposition of Strongly Connected Components)

リポジトリ
有向グラフ(directed graph, digraph)

  • 強連結(strongly connected): 有向グラフの任意の2頂点u, vに対して、uからvに到達可能かつvからuに到達可能、すなわち、任意の2頂点に双方向の道が存在するとき、その有向グラフは強連結であるという。
  • 強連結成分(SCC: Stronglu Connected Components):極大で強連結な(他の辺を加えると強連結ではなくなる)部分グラフ。
  • 強連結成分分解(Decomposition of SCC):

有向グラフは、いくつかの強連結成分の共通部分を持たない和集合に分解することができる。この分解を強連結成分という。
強連結成分を1つの頂点に縮約(contraction)すると、非閉路有向グラフ(DAG: Directed Acyclic Graph)になる。

Kosaraju's algorithm

Kosaraju's algorithm(なんて読むの?)を使うと2回のDFS(Depth-First Search)でSCC(の頂点集合)が求まる。
計算量は、グラフを隣接行列(adjacency matrix)として持つと O(|V|^2), 隣接リスト(adjacency list)として持つと O(|V|+|E|)となる。

G(V, E)を有向グラフ、SをVの部分集合( S\subseteq V)とする。Sのデータ構造はスタックとする。
1.  S \leftarrow \emptyset
2. S = Vとなるまで3. を繰り返す。
3.
  任意の頂点 v \in V-Sを選んで、vからGを後順走査(postorder traversal)する(GのDFS)。
  頂点uに降順訪問した際、uをSにプッシュする( S \cup \{u\})。
4. Gの逆グラフG'(V, E')(Gのアークの向きを逆にしたグラフ)を作る。
5.  S = \emptysetとなるまで6-7. を繰り返す。
6.
  Sから先頭の頂点vをポップし、vが既にSCCの一部として検出されている場合は7.をスキップする。
7.
  vからG'を前順走査(preorder taraversal)する(G'のDFS)。
  前順で訪問した頂点の集合がvを含むSCC(の頂点集合)として得られる。
※7.ではDFSの代わりに、BFS(Breadth-First Search)を使って求めることもできる。

まず、強連結と双方向の道があることは同値なので、有向グラフG(V, E)とその逆グラフG'(V, E')において、各強連結成分(の頂点集合)は等しい。 \cdots (1)
ここでSCC(v)を頂点 v\in Vが属す強連結成分の頂点集合とする。

GのDFSでは、頂点を後順(post order)でトポロジカル順序をナンバリングする(実際はスタックにプッシュしているだけ)。
そのナンバーが一番大きい頂点は、SCCを1つの頂点に縮約してできるDAGの先頭のSCCに属している。
なので、ナンバーの一番大きい頂点が属すSCCの任意の頂点から、他のSCCに移動することができない。 \cdots (2)
スタックSから頂点を取り出していくと、そのSCCに属する頂点がナンバーの大きい順ででてくる(スタックがDAGのトポロジカル順序の逆に対応する)。

次に、G'の1回目のDFS(スタックの先頭要素、つまりナンバーが一番大きい頂点から移動可能な頂点のDFS)について考える。
このG'の1回目のDFSの始点をv, 訪問できる頂点集合をD(v)とする。

(i) SCC(v)\subset D(v)は自明。
なぜなら、(1)より、G'にvから  u \in SCC(v)へ到達可能。

(ii) D(v)\subset SCC(v)
 a \in D(v),  b \in S-SCC(v)とすると、aからbへの道は存在しない(1回目のG'のDFSではS=V)。 \cdots (3)
なぜなら、aからbへの道が存在すれば、bはvより大きいナンバーとならなければならない。
これは、G'の1回目のDFS(ナンバーが一番大きい頂点をv)という仮定に反する。
従って、(3)が成立する。
(3)より c \in D(v)\cap SCC(v)から d \in D(v)-SCC(v)への道は存在しないので、(ii)が成立する。

(i), (ii)より、SCC(v)=D(v)となり、SCC(v)がG'の1回目のDFSで求まる。

そして、スタックから S\leftarrow S - SCC(v)とすれば、
帰納的に \{ SCC(v) | v \in V \}が求まる。

javaコード。もう一方のアルゴリズム(後述)でnumを参照渡ししたかったので、共通して使えるものをインナークラスにまとめた。
Kosaraju algorithmだけならクラスにする必要無いです。

private static class SCCDFSArg {
	int num = 0;
	Stack<Integer> stack = new Stack<Integer>();
	boolean[] used;
	List<List<Edge>> adjList;
	SCCDFSArg(int numV, List<List<Edge>> adjList) { used = new boolean[numV]; this.adjList = adjList; }
}
/** 
 * Gets list of SCC(Strongly Connected Components) via Kosaraju's algorithm. (O(|V|+|E|))
 * @param adjList AdjacencyList
 * @return SCC
 */
public static List<Set<Integer>> Kosaraju(List<List<Edge>> adjList) {
	int n = adjList.size();
	SCCDFSArg arg = new SCCDFSArg(n, adjList);
	for (int v = 0; v < n; ++v) if (!arg.used[v]) postOrderNumbering(v, arg);
	
	Arrays.fill(arg.used, false);
	arg.adjList = inverseAdjacencyList(adjList);
	List<Set<Integer>> ret = new ArrayList<Set<Integer>>();
	while (!arg.stack.isEmpty()) {
		int v = arg.stack.pop();
		if (!arg.used[v]) {
			Set<Integer> scc = new HashSet<Integer>();
			addSCC(v, arg, scc);
			ret.add(scc);
			arg.num++; //group number
		}
	}
	return ret;
}
private static void postOrderNumbering(int v, SCCDFSArg arg) {
	arg.used[v] = true;
	for (Edge e : arg.adjList.get(v)) if (!arg.used[e.d]) postOrderNumbering(e.d, arg);
	arg.stack.push(v);
}
private static void addSCC(int v, SCCDFSArg arg, Set<Integer> scc) {
	arg.used[v] =  true;
	scc.add(v);
	for (Edge e : arg.adjList.get(v)) if (!arg.used[e.d]) addSCC(e.d, arg, scc);
}

DFS1回版

Kosaraju's algorithmをそのまま実装したものの方が簡単だが、逆グラフを作る必要がある。
逆グラフを作らず、元のグラフのDFSだけで求めるアルゴリズムは、
Spaghetti Source - 強連結成分分解を参照。
よくわかってない。
num[v]はvのトポロジカルナンバー。ただし、Kosaraju's algorithmの場合とは異なり、
一番小さいナンバーが振られている頂点は、SCCを縮約したときにできるDAGの先頭に属す。
low[v]はSCC(v)中の頂点の最も小さいナンバー(だと思う。)
low[v]はvにpreorder traversalで訪問した際にnum[v]で初期化し、vをスタックSに加える。
順序走査(inorder traversal)で訪問した際にnum[v]を更新する。
  vからuへのアークがあったとき、uに行って、vに戻ってきた際に、low[v]よりlow[u]の方が小さければ、low[v]<-low[u]に更新。
  uが既にpreorder traversalで訪問した頂点だったとき、low[v]よりuのナンバーの方が小さければ、low[v]<-num[u]に更新。
postorder traversalでvに訪問した際に、num[v]=low[v]になっていれば、SCC(v)が決定する。
このとき、スタックの頭から、スタック中にある頂点vまでがSCC(v)に属す。

/** 
 * Gets list of SCC(Strongly Connected Components). (O(|V|+|E|))
 * @param adjList AdjacencyList
 * @return SCC
 */
public static List<Set<Integer>> getStronglyConnectedComponents(List<List<Edge>> adjList) {
	ArrayList<Set<Integer>> ret = new ArrayList<Set<Integer>>();
	int n = adjList.size();
	int[] num = new int[n], low = new int[n];
	SCCDFSArg arg = new SCCDFSArg(n, adjList);
	for (int v = 0; v < n; ++v) if (num[v] == 0) sccDFS(v, arg, low, num, ret);
	return ret;
}
private static void sccDFS(int v, SCCDFSArg arg, int[] low, int[] num, List<Set<Integer>> SCCs) {
	low[v] = num[v] = ++arg.num; //num[v]:= topological number of v. low[v]:= minimum topological number in SCC including v. 
	arg.stack.push(v); arg.used[v] = true; //used[v] := whether arg.S contains v or not.
	for (Edge e: arg.adjList.get(v)) {
		if (num[e.d] == 0) { //case: e.d is non visited vertex
			sccDFS(e.d, arg, low, num, SCCs);
			low[v] = Math.min(low[v], low[e.d]);
		} else if (arg.used[e.d]) { //arg.used[e.d] == false -> has already created scc containing e.d. 
			low[v] = Math.min(low[v], num[e.d]);
		}
	}
	if (low[v] == num[v]) { 
		HashSet<Integer> scc = new HashSet<Integer>();
		int sccV = 0;
		do {
			sccV = arg.stack.pop(); arg.used[sccV] = false; System.out.print(sccV + ", ");
			scc.add(sccV);
		} while (v != sccV);
		SCCs.add(scc);
	}
}