DMdecomposition
Last-Modified: 2008-04-05 19:56:54
/* DMdedomposition.java --- Dulmage-Mendelsohn decomposition
* 2グラフのDM分解を求めるプログラム
* Time-stamp: <2008-03-16 16:29:39>
*
* 入力:標準入力から次のようなグラフのデータ
* （第一行目は頂点数と枝数、以降は枝のデータ）
* 3 3
* 0 1
* 0 2
*
* 出力:DM分解によって得られる各成分とその半順序関係
*
* G1={1,2,3}
* G2={3,4,5}
* G1 -> G2
*
*/
import java.io.*;
import java.util.*;
public class DMdecomposition extends BipartiteGraphMatching {
/* Field
* dmNodeSetList : DM分解の各成分のノード
* dmEdgeSetList : DM分解の各成分のエッジ
* dmOrderSet : DM分解の各成分間の半序順
* referDMComponent : 各ノードがどの成分に属すか
* minComponentNodeSet : DM分解における最小元に属す頂点
* minComponentEdgeSet : DM分解における最小元に属す枝
* maxComponentNodeSet : DM分解における最大元に属す頂点
* maxComponentEdgeSet : DM分解における最大元に属す枝
* auxiliaryNodeLabel : 補助グラフの頂点の元のグラフでのラベル
* auxiliaryNodeInvLabel : 元のグラフの頂点の補助グラフでのラベル（補助グラフに含まれない頂点は-1）
* auxiliaryNodeList : 補助グラフにおける頂点の順方向枝接続リスト
* auxiliaryInvNodeList : 補助グラフにおける頂点の逆方向枝接続リスト
* auxiliaryEdgeList : 補助グラフの枝の始点と終点
* Method
*
* void findMinComponent() : DM分解における最小元を探す
* void findMaxComponent() : DM分解における最大元を探す
* Set findUnMatchedLeftNode() : マッチされていない左側の点を探す
* Set findUnMatchedRightNode() : マッチされていない右側の点を探す
* void createAuxiliaryGraph() : DM分解のための補助グラフを作りだす
* boolean addAuxiliaryNode(int node) : 補助グラフに頂点を追加
* boolean addAuxiliaryEdge(int edge) : 補助グラフに枝を追加
* String auxiliaryGraphToGraphviz() : 補助グラフをGraphviz形式で出力
* void DFS() : 深さ優先探索を実行し各頂点に探索終了順に番号をつける
*/
private List> dmNodeSetList,dmEdgeSetList;
private Set dmOrderSet;
private Set
minComponentNodeSet,
minComponentEdgeSet,
maxComponentNodeSet,
maxComponentEdgeSet;
//ノードが属すDM分解の各成分のラベル（最小元が0、最大元は最も大きい）
private int [] referDMComponent;
private List auxiliaryNodeLabel;
private int [] auxiliaryNodeInvLabel;
private List> auxiliaryNodeList,auxiliaryInvNodeList;
private List auxiliaryEdgeList;
private static final double HUE_OF_BLUE = 0.663888889 ;
protected boolean debug = true ;
public DMdecomposition() throws IOException{
super();
super.debug = false ;
readGraph();
findMaxMatching();
minComponentNodeSet = new TreeSet();
minComponentEdgeSet = new TreeSet();
maxComponentNodeSet = new TreeSet();
maxComponentEdgeSet = new TreeSet();
}
/**
* DM分解を行う
*/
public void decomposition() throws IOException{
if(dotFile)
toDotFile(minMaxToGraphviz("Start Dulmage-Mendelsohn Decomposition."));
findMinComponent();
findMaxComponent();
if(dotFile)
toDotFile(minMaxToGraphviz("MaxComponent(Blue) and MinComponent(Red)"));
createAuxiliaryGraph();
if(dotFile)
toDotFile(auxiliaryGraphToGraphviz());
StronglyConnectedComponent scc = new StronglyConnectedComponent
(auxiliaryNodeList,auxiliaryEdgeList);
scc.sccDecomposition();
createDMNodeSet(scc.getSCCNodeSetList());
createDMEdgeAndOrder();
if(debug)
dispDMDecomposition();
if(dotFile){
toDotFile(dmDecompositionToGraphviz());
toDotFile(dmComponentToGraphviz());
}
}
/**
* 強連結成分分解の結果を用いてDM分解の各成分が含むノードを調べ、dmNodeSetListに格納
* @param sccNodeSetList 補助グラフの強連結成分が含むノード
*/
private void createDMNodeSet(List> sccNodeSetList){
referDMComponent = new int [nodeList.size()];
dmNodeSetList = new ArrayList>();
//まず、最小元を加える
dmNodeSetList.add(minComponentNodeSet);
int label = 0;
for(int node : minComponentNodeSet){
referDMComponent[node] = label ;
}
label++;
//次に補助グラフの連結成分をそれぞれ加える
for(Set sccNodeSet : sccNodeSetList){
Set dmNodeSet = pullBackLabel(sccNodeSet);
dmNodeSetList.add(dmNodeSet);
for(int node : dmNodeSet){
referDMComponent[node] = label ;
}
label++;
}
//最後に最大元を加える
dmNodeSetList.add(maxComponentNodeSet);
for(int node : maxComponentNodeSet){
referDMComponent[node] = label ;
}
if(debug){
System.out.println("DM component node :\n"+dmNodeSetList+"\n");
}
}
/**
* 補助グラフのノードの部分集合のそれぞれのラベルを元のグラフのラベルに変えたものを返す
* @param auxiliaryNodeSubset 補助グラフのノード集合の部分集合
* @return もとのグラフのノード集合の部分集合
*/
private Set pullBackLabel(Set auxiliaryNodeSubset){
Set NodeSubset = new TreeSet();
for(int node : auxiliaryNodeSubset){
NodeSubset.add(auxiliaryNodeLabel.get(node));
}
return NodeSubset;
}
/**
* DM分解の各成分内の枝、各成間の順序をもとめる。
*/
private void createDMEdgeAndOrder() {
dmEdgeSetList = new ArrayList>();
for (int i = 0, n = dmNodeSetList.size(); i < n; i++) {
dmEdgeSetList.add(new TreeSet());
}
dmOrderSet = new HashSet();
int edgeIndex = 0;
for (Integer[] edge : edgeList) {
int src = referDMComponent[edge[0]];
int dst = referDMComponent[edge[1]];
if (src == dst) {
// 成分内の枝の場合
dmEdgeSetList.get(src).add(edgeIndex);
} else {
// 成分間の順序の場合
Integer[] order = new Integer[2];
order[0] = src;
order[1] = dst;
dmOrderSet.add(order);
}
edgeIndex++;
}
}
/**
* DM分解における最小元を求める
* 結果はField minComponentNodeSet,minComponentEdgeSetに格納される
* マッチされていない左側の点から深さ優先探索を行う。
*/
void findMinComponent(){
Set unMatchedLeftNodeSet = findUnMatchedLeftNode();
if(this.debug) System.out.println("Unmatched left node:"+unMatchedLeftNodeSet);
minComponentNodeSet = new TreeSet();
minComponentEdgeSet = new TreeSet();
deque.clear();
visit = new boolean[nodeList.size()];
//マッチされていない左側の点について
for(int node : unMatchedLeftNodeSet){
//深さ優先探索を行う
depthFirstSearchForMinComponent(node);
}
if(debug){
System.out.println("min component:");
System.out.println(minComponentNodeSet);
dispEdge(minComponentEdgeSet);
System.out.println();
}
}
/**
* マッチされていない左側の点を返す
*/
private Set findUnMatchedLeftNode(){
Set unMatchedLeftNodeSet = new TreeSet();
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
if(left[i] && !match[i])
unMatchedLeftNodeSet.add(i);
}
return unMatchedLeftNodeSet ;
}
/**
* DM分解の最小元を探すための深さ優先探索
* 結果はField minComponentNodeSet,minComponentEdgeSetに格納される
* @param startNode 深さ優先探索の開始点
*/
void depthFirstSearchForMinComponent(int startNode){
minComponentNodeSet.add(startNode);
deque.push(startNode);
visit[startNode]=true;
//深さ優先探索を行う
while(!deque.isEmpty()){
int nowNode = deque.pop();
//nowNodeに接続している枝について
for(int edge : nodeList.get(nowNode)){
minComponentEdgeSet.add(edge);
//nowNodeの隣接点について
int neighbor = edgeList.get(edge)[1];
//まだ訪れていないときのみ
if(!visit[neighbor]){
visit[neighbor]=true;
deque.push(neighbor);
minComponentNodeSet.add(neighbor);
}
}
}
}
/**
* DM分解における最大元を求める
* 結果はField maxComponentNodeSet,maxComponentEdgeSetに格納される
* マッチされていない右側の点から枝を逆向きにした深さ優先探索を行う。
*/
void findMaxComponent(){
Set unMatchedRightNodeSet = findUnMatchedRightNode();
if(this.debug) System.out.println("Unmatched right node:"+unMatchedRightNodeSet);
maxComponentNodeSet = new TreeSet();
maxComponentEdgeSet = new TreeSet();
deque.clear();
visit = new boolean[nodeList.size()];
//マッチされていない右側の点について
for(int node : unMatchedRightNodeSet){
//深さ優先探索を行う
depthFirstSearchForMaxComponent(node);
}
if(debug){
System.out.println("max component :");
System.out.println(maxComponentNodeSet);
dispEdge(maxComponentEdgeSet);
System.out.println();
}
}
/**
* マッチされていない右側の点を返す
*/
private Set findUnMatchedRightNode(){
Set unMatchedRightNodeSet = new TreeSet();
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
if(!left[i] && !match[i])
unMatchedRightNodeSet.add(i);
}
return unMatchedRightNodeSet ;
}
/**
* DM分解の最大元を探すための枝を逆向きにした深さ優先探索
* 結果はField maxComponentNodeSet,maxComponentEdgeSetに格納される
* @param startNode 深さ優先探索の開始点
*/
void depthFirstSearchForMaxComponent(int startNode){
maxComponentNodeSet.add(startNode);
deque.push(startNode);
visit[startNode]=true;
//深さ優先探索を行う
while(!deque.isEmpty()){
int nowNode = deque.pop();
//nowNodeに逆向きに接続している枝について
for(int edge : invNodeList.get(nowNode)){
maxComponentEdgeSet.add(edge);
//nowNodeの隣接点について
int neighbor = edgeList.get(edge)[0];
//まだ訪れていないときのみ
if(!visit[neighbor]){
visit[neighbor]=true;
deque.push(neighbor);
maxComponentNodeSet.add(neighbor);
}
}
}
}
/**
* 最大元、最小元に関する頂点、枝を除去した後マッチングの枝を逆向きに付加した補助グラフを作りだす。
*/
private void createAuxiliaryGraph(){
auxiliaryNodeList = new ArrayList>();
auxiliaryInvNodeList = new ArrayList>();
auxiliaryEdgeList = new ArrayList();
auxiliaryNodeLabel = new ArrayList();
auxiliaryNodeInvLabel = new int [nodeList.size()];
for(int node=0 , n = nodeList.size() ; node < n ; node++){
addAuxiliaryNode(node);
}
for(int edge=0 , n = edgeList.size() ; edge < n ; edge++){
addAuxiliaryEdge(edge);
}
if(debug) dispAuxiliaryGraph();
}
/**
* 補助グラフに頂点を追加する、ただし追加するのは最小元にも最大元にも含まれないものに限る
* @param node 追加しようとする頂点
* @return 追加できた場合はtrue、追加できなかった場合はfalse
*/
private boolean addAuxiliaryNode(int node){
//頂点が最小元か最大元に含まれる場合
if(minComponentNodeSet.contains(node) ||
maxComponentNodeSet.contains(node)){
auxiliaryNodeInvLabel[node]=-1;
return false ;
}
//頂点を追加
auxiliaryNodeList.add(new ArrayList());
auxiliaryInvNodeList.add(new ArrayList());
auxiliaryNodeLabel.add(new Integer(node));
auxiliaryNodeInvLabel[node]=auxiliaryNodeList.size()-1;
return true ;
}
/**
* 補助グラフに枝を追加する、ただし追加するのは最小元の頂点にも最大元の頂点にも接続しないものに限る
* さらに、枝がマッチングされていた場合は逆向きの枝も同時に追加する
* @param edge 追加しようとする枝
* @return 追加できた場合はtrue、追加できなかった場合はfalse
*/
private boolean addAuxiliaryEdge(int edge){
int src = edgeList.get(edge)[0];//枝の始点
int dst = edgeList.get(edge)[1];//枝の終点
//最小元か最大元に接続している場合（追加しない）
if(minComponentNodeSet.contains(src)||
minComponentNodeSet.contains(dst)||
maxComponentNodeSet.contains(src)||
maxComponentNodeSet.contains(dst)){
return false ;
}
//枝を追加
Integer [] auxiliaryEdge = new Integer [2];
auxiliaryEdge[0] = auxiliaryNodeInvLabel[src];//補助グラフでの始点
auxiliaryEdge[1] = auxiliaryNodeInvLabel[dst];//補助グラフで終点
auxiliaryEdgeList.add(auxiliaryEdge);
auxiliaryNodeList.get(auxiliaryEdge[0]).add(auxiliaryEdgeList.size()-1);
auxiliaryInvNodeList.get(auxiliaryEdge[1]).add(auxiliaryEdgeList.size()-1);
//枝がマッチングに使われている場合は逆向きの枝も追加
if(left[edgeList.get(edge)[1]]){//マッチングの枝の終点は左側
auxiliaryEdge = new Integer [2];
//逆向きの枝
auxiliaryEdge[1] = auxiliaryNodeInvLabel[src];//補助グラフでの始点
auxiliaryEdge[0] = auxiliaryNodeInvLabel[dst];//補助グラフで終点
auxiliaryEdgeList.add(auxiliaryEdge);
auxiliaryNodeList.get(auxiliaryEdge[0]).add(auxiliaryEdgeList.size()-1);
auxiliaryInvNodeList.get(auxiliaryEdge[1]).add(auxiliaryEdgeList.size()-1);
}
return true;
}
/**
* Graphviz形式で最小元、最大元を出力する
* @param グラフにつけるラベル
* @return Graphvizのdot形式なString
*/
private String minMaxToGraphviz(String label){
StringBuffer sb = new StringBuffer(graphvizHead +"\nlabel = \""+label+"\";\n");
//ノードについて出力
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
sb.append(i);
//マッチされていないノードは二重丸で
if(!match[i])
sb.append("[shape = doublecircle ];\n");
else sb.append("[style = solid];\n");
}
//エッジについて出力 マッチに使われているエッジは逆向きもつける
for(int i = 0 , n = edgeList.size() ; i < n ; i++){
sb.append(edgeList.get(i)[0] +" -> "+edgeList.get(i)[1]);
if(maxComponentEdgeSet.contains(i))
sb.append("[color = blue];\n");
else if(minComponentEdgeSet.contains(i))
sb.append("[color = red];\n");
else sb.append(";\n");
if(left[edgeList.get(i)[1]]){
sb.append(edgeList.get(i)[1] +" -> "+edgeList.get(i)[0]);
if(maxComponentEdgeSet.contains(i))
sb.append("[color = blue];\n");
else if(minComponentEdgeSet.contains(i))
sb.append("[color = red];\n");
else sb.append(";\n");
}
}
//最大元を出力
sb.append("subgraph maxComponent{\n");
for(int node : maxComponentNodeSet){
sb.append(node+"[style = filled , fillcolor = blue];\n");
}
sb.append("}\n");
//最小元を出力
sb.append("subgraph minComponent{\n");
for(int node : minComponentNodeSet){
sb.append(node+"[style = filled , fillcolor = red];\n");
}
sb.append("}\n");
sb.append("{rank = same ");
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
if(left[i])
sb.append(";"+i);
}
sb.append("}\n{rank = same ");
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
if(!left[i])
sb.append(";"+i);
}
sb.append("}\n}");
return sb.toString() ;
}
/**
* Graphviz形式で補助グラフを出力する
* @return Graphvizのdot形式なString
*/
private String auxiliaryGraphToGraphviz(){
StringBuffer sb = new StringBuffer(graphvizHead +"\nlabel = \"Auxiliary Graph(remove MaxComponent and MinComponent)\";\n");
//ノードについて出力
for(int i = 0 , n = auxiliaryNodeLabel.size() ; i < n ; i++){
sb.append(i+"[label = "+auxiliaryNodeLabel.get(i)+"];\n");
}
//エッジについて出力
for(int i = 0 , n = auxiliaryEdgeList.size() ; i < n ; i++){
sb.append(auxiliaryEdgeList.get(i)[0] +" -> "+auxiliaryEdgeList.get(i)[1]+";\n");
}
sb.append("{rank = same ");
for(int i = 0 , n = auxiliaryNodeLabel.size() ; i < n ; i++){
if(left[auxiliaryNodeLabel.get(i)])
sb.append(";"+i);
}
sb.append("}\n{rank = same ");
for(int i = 0 , n = auxiliaryNodeLabel.size() ; i < n ; i++){
if(!left[auxiliaryNodeLabel.get(i)])
sb.append(";"+i);
}
sb.append("}\n}");
return sb.toString() ;
}
/**
* Graphviz形式でDM分解を出力する
* @return Graphvizのdot形式なString
*/
private String dmDecompositionToGraphviz(){
StringBuffer sb = new StringBuffer(graphvizHead +"\nlabel = \"Dulmage-Mendelsohn Decomposition is complete.\";\n");
int dmDecompositionSize = dmNodeSetList.size()-1;
//ノードについて出力
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
sb.append(i+"[style = filled , ");
//マッチされていないノードは二重丸で
if(!match[i])
sb.append("shape = doublecircle , ");
sb.append("fillcolor =\""+HUE_OF_BLUE/dmDecompositionSize*referDMComponent[i]+
" 1 1\"];\n");
}
//エッジについて出力 マッチに使われているエッジは逆向きもつける
for(Integer[] edge : edgeList){
// DM分解の成分内の枝の場合
if(referDMComponent[edge[0]] == referDMComponent[edge[1]]){
double color = HUE_OF_BLUE/dmDecompositionSize*referDMComponent[edge[0]];
sb.append(edge[0]+" -> "+edge[1]+"[color = \""+color+" 1 1\"];\n");
//マッチされいる場合
if(left[edge[1]]){
sb.append(edge[1]+" -> "+edge[0]+"[color = \""+color+" 1 1\"];\n");
}
}else{
// DM分解の成分間の順序の場合
sb.append(edge[0]+" -> "+edge[1]+";\n");
}
}
sb.append("{rank = same ");
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
if(left[i])
sb.append(";"+i);
}
sb.append("}\n{rank = same ");
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
if(!left[i])
sb.append(";"+i);
}
sb.append("}\n}");
return sb.toString() ;
}
/**
* Graphviz形式でDM分解の各成分の順序を出力する
* @return Graphvizのdot形式なString
*/
private String dmComponentToGraphviz(){
StringBuffer sb = new StringBuffer("digraph sample {\nlabel = \"DM Decomposition : Component and order\";\n");
int dmDecompositionSize = dmNodeSetList.size()-1;
//各成分をノードとして出力
int componentIndex = 0;
for(Set nodeSet : dmNodeSetList){
sb.append(componentIndex+"[style = filled , ");
sb.append("fillcolor =\""+HUE_OF_BLUE/dmDecompositionSize*(componentIndex++)+
" 1 1\" , ");
sb.append("label = \""+nodeSet+"\"];\n");
}
//成分間の順序を表示
for(Integer[] order : dmOrderSet){
sb.append(order[0]+" -> "+order[1]+";\n");
}
sb.append("}");
return sb.toString();
}
/**
* ArrayListに格納されたエッジを表示するデバグ用メソッド。
*/
private void dispEdge(Collection edgeCollection){
System.out.println("edge :");
for(int edge : edgeCollection){
System.out.print("["+edgeList.get(edge)[0]+","+edgeList.get(edge)[1]+"]");
}
System.out.println();
}
/**
* 補助グラフを表示するためのデバグ用メソッド。
*/
private void dispAuxiliaryGraph(){
//補助グラフの元のグラフでのラベルを表示
System.out.println("node label :");
for(int i = 0 , n = auxiliaryNodeList.size() ; i < n ; i++ ){
System.out.println("auxiliary node["+i+"]: label("+auxiliaryNodeLabel.get(i)+")");
}
//元のグラフの頂点が補助グラフではどの頂点に対応するかを表示（補助グラフにおいて含まれない場合は-1）
System.out.println("inverse label :");
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
System.out.println("node ["+i+"]: auxiliary node ["+auxiliaryNodeInvLabel[i]+"]");
}
//順方向枝接続リストの表示
System.out.println("node -> edges:");
int j = 0;
for(List list : auxiliaryNodeList){
System.out.print("node["+(j++)+"]");
for(Integer i : list)
System.out.print(" "+i);
System.out.println();
}
//逆方向枝接続リストの表示
System.out.println("node <- edges:");
j = 0;
for(List list : auxiliaryInvNodeList){
System.out.print("node["+(j++)+"]");
for(Integer i : list)
System.out.print(" "+i);
System.out.println();
}
//枝の始点、終点の表示
System.out.println("edge:");
j = 0 ;
for(Integer[] e : auxiliaryEdgeList)
System.out.println("edge ["+(j++)+"] ("+e[0]+","+e[1]+")");
}
/**
* DM分解の各成分を表示 デバグ用メソッド
*/
private void dispDMDecomposition(){
System.out.println("## DM Decomposition ##");
//成分内のノードを表示
System.out.println("node :");
int componentIndex = 0;
for(Set nodeSet : dmNodeSetList){
System.out.println("component["+(componentIndex++)+"]'s node :");
System.out.println(nodeSet);
}
//成分内の枝を表示
System.out.println("\nedge :");
componentIndex=0;
for(Set edgeSet: dmEdgeSetList){
System.out.print("component["+(componentIndex++)+"]'s ");
dispEdge(edgeSet);
}
//成分間の順序を表示
System.out.println("\nOrder:");
for (Integer[] order : dmOrderSet) {
System.out
.println("component[" + order[0] + "] -> component[" + order[1] + "]");
}
System.out.println();
}
public static void main(String args []){
try{
DMdecomposition dmd = new DMdecomposition();
dmd.decomposition();
}catch (IOException e ){
e.printStackTrace();
}
}
}