StronglyConnectedComponent
Last-Modified: 2008-04-05 19:51:04
/* StronglyConnectedComponent.java
* グラフの強連結成分分解を求める
* Time-stamp: <2008-03-16 14:40:59>
*
* 各ノードについての枝順方向接続リスト、枝逆方向接続リスト。各枝についてその始点、終点を
* 格納したリストから強連結成分分解を求める。
* 各強連結成分が含むノードはsccNodeList,各強連結成分が含むエッジはsccEdgeList,
* （データ構造がリストであるのは各強連結成分をラベル付けして考えたいから）
* 各強連結成分間の半順序はsccOrderSetにそれぞれ格納。
* 強連結成分分解のアルゴリズムは深さ優先探索を一回実行するもの。詳細は以下のurlで。
* http://www.ics.uci.edu/~eppstein/161/960220.html#sca
*/
import java.util.*;
public class StronglyConnectedComponent {
/*
* Field List> nodeList : グラフの各ノードの順方向枝接続リスト List>
* invNodeList : グラフの各ノードの逆方向枝接続リスト List edgeList :
* グラフの各枝の始点と終点のリスト int [] dfsnum : 強連結成分分解の際に用いられるノードに関するデータ int [] low :
* 強連結成分分解の際に用いられるノードに関するデータ Deque stack :
* 強連結成分分解の際に用いられるスタック。部分木のノードを記憶しておく
*
* List> sccNodeList : 各強連結成分が含むノード List>
* sccEdgeList : 各強連結成分が含むエッジ Set sccOrderSet : 各強連結成分間の半順序 int []
* referComponent : 各ノードが属す連結成分 Method
*
* void sccDecomposition() : グラフの強連結成分分解を行う void dfsFirst() :
* 強連結成分分解のための深さ優先探索一回目 void dfsSecond() : 強連結成分分解のための深さ優先探索二回目 void
*/
private List> nodeList;
private List edgeList;
private List> sccNodeSetList;
private List> sccEdgeSetList;
private Set sccOrderSet;
private Deque dfsTree;
private boolean[] visit;
private int[] referComponent;
private int[] dfsnum;
private int[] low;
private int index;
private boolean debug = true;
public StronglyConnectedComponent(List> nodeList,
List edgeList) {
this.nodeList = nodeList;
this.edgeList = edgeList;
}
/**
* 強連結成分分解を行う。
*
*
*/
public void sccDecomposition() {
// 各変数を初期化する。
sccNodeSetList = new ArrayList>();
int nodeSize = nodeList.size();
dfsnum = new int[nodeSize];
low = new int[nodeSize];
referComponent = new int[nodeSize];
for (int i = 0; i < nodeSize; i++) {
referComponent[i] = -1;
}
visit = new boolean[nodeSize];
index = 0;
dfsTree = new ArrayDeque();
for (int node = 0; node < nodeSize; node++) {
if (referComponent[node] == -1)
dfs(node);
}
createSCCEdgeAndOrder();
if (debug)
dispSCC();
}
/**
* 強連結成分のための深さ優先探索。 各ノードについてdfsnum,lowを計算して、そのノードが連結成分のheadになるかをしらべる。
* ノードxがhead <==> (low[x] == dfsnum[x] )
* headノードを見つけたら、そのノードを根としたDFS木の部分木を取り除き、連結成分とする。 連結成分内の枝、連結成分間の半順序は後回し。
*
* @param startNode
* 深さ優先探索の開始ノード
*/
private void dfs(int node) {
dfsTree.push(node);
visit[node] = true;
dfsnum[node] = index++;
low[node] = dfsnum[node];
// nodeに接続している枝について
for (int edge : nodeList.get(node)) {
// edgeの終点、nodeの隣接点について
int neighbor = edgeList.get(edge)[1];
// 既に連結成分に含まれていた場合
if (referComponent[neighbor] != -1)
continue;
if (!visit[neighbor]) {
dfs(neighbor);
low[node] = Math.min(low[node], low[neighbor]);
} else {
low[node] = Math.min(low[node], dfsnum[neighbor]);
}
}
if (low[node] == dfsnum[node]) {
sccNodeSetList.add(createNodeSet(node));
}
}
/**
* 連結成分に含まれるノードをもとめる。
*
* @param head
* 連結成分のhead
* @return 連結成分内のノードの集合
*/
private Set createNodeSet(int head) {
Set nodeSet = new TreeSet();
int node;
int componentLabel = sccNodeSetList.size();
do {
node = dfsTree.pop();
referComponent[node] = componentLabel;
nodeSet.add(node);
} while (node != head);
return nodeSet;
}
/**
* 連結成分内の枝、連結成分間の順序をもとめる。
*/
private void createSCCEdgeAndOrder() {
sccEdgeSetList = new ArrayList>();
for (int i = 0, n = sccNodeSetList.size(); i < n; i++) {
sccEdgeSetList.add(new HashSet());
}
sccOrderSet = new HashSet();
for (Integer[] edge : edgeList) {
int src = referComponent[edge[0]];
int dst = referComponent[edge[1]];
if (src == dst) {
// 連結成分内の枝の場合
sccEdgeSetList.get(src).add(edge);
} else {
// 連結成分間の順序の場合
Integer[] order = new Integer[2];
order[0] = src;
order[1] = dst;
sccOrderSet.add(order);
}
}
}
public List> getSCCNodeSetList(){
return sccNodeSetList;
}
public List> getSCCEdgeSetList(){
return sccEdgeSetList;
}
public Set getSCCOrder(){
return sccOrderSet;
}
/**
* 連結成分を出力するデバグ用メソッド。
*/
private void dispSCC() {
for (int i = 0, n = sccNodeSetList.size(); i < n; i++) {
System.out.println("Strongly Connected Component[" + i + "]:");
System.out.print(sccNodeSetList.get(i) + " [");
for (Integer[] edge : sccEdgeSetList.get(i)) {
System.out.print("(" + edge[0] + "," + edge[1] + ")");
}
System.out.println("]");
}
System.out.println("\nOrder:");
for (Integer[] order : sccOrderSet) {
System.out
.println("scc[" + order[0] + "] -> scc[" + order[1] + "]");
}
System.out.println();
}
}