BipartiteGraphMatching
Last-Modified: 2008-04-05 19:46:53
二部グラフのマッチングを行うプログラム。Graphvizで画像化できるdotファイルを作る。
/**
* Time-stamp: <2008-03-15 13:22:07>
*/
import java.io.*;
import java.util.*;
public class BipartiteGraphMatching{
/*
* 2部グラフのマッチング
* グラフのデータ構造は頂点に対する接続枝の隣接リスト
* （始点として接続している枝集合、終点として接続してる枝集合のリスト）
* さらに、各枝についての始点・終点の情報もあわせて持つ
*
* 入力グラフフォーマット
* 第一行目に点数、枝数
* 6 6
* 0 4
* 0 5
* 1 4
* 1 6
* 2 5
* 3 6
*/
protected List> nodeList ;//順方向枝接続リスト
protected List> invNodeList ;//逆方向枝接続リスト
protected boolean [] left , match;//2部グラフにおいてどちら側に属すか,マッチされているか
protected List edgeList;//枝の始点と終点
private int dotFileCount ;
protected Deque deque;
protected boolean [] visit;
protected int [] prev ;
//デバグ用に途中経過を表示するか
public boolean debug = true ;
//Graphviz形式のdotファイルを出力するか
public boolean dotFile = true ;
static final String graphvizHead = "digraph sample {\ngraph [ranksep = 2.0 ,rankdir = LR];\nnode [shape = circle];";
private BufferedReader in = null;
private BufferedWriter out = null;
/**
*
*/
public BipartiteGraphMatching(){
in = new BufferedReader(new InputStreamReader(System.in));
}
public void init(int nodeSize , int edgeSize) throws IOException,NumberFormatException{
if(debug) System.out.println("node size : "+nodeSize +", edge size :"+edgeSize);
dotFileCount = 0 ;
nodeList = new ArrayList>(nodeSize);
for(int i = 0 ; i < nodeSize ; i++)
nodeList.add(new ArrayList());
invNodeList = new ArrayList>(nodeSize);
for(int i = 0 ; i < nodeSize ; i++)
invNodeList.add(new ArrayList());
edgeList = new ArrayList(edgeSize);
for(int i = 0 ; i < edgeSize ; i++)
edgeList.add(new Integer [2]);
left = new boolean [nodeSize];
match = new boolean [nodeSize];
}
/**
* 交互道(alternating path)を返す
* @return 交互道を枝の列として含むArrayList、交互道がない場合はnull
*/
private List findAltPath(){
deque = new ArrayDeque();
visit = new boolean [nodeList.size()];
prev = new int [nodeList.size()];
List altPath = new ArrayList();
for(int i = 0 , n = prev.length ; i < n ; i++){
prev[i]=-1;
}
//左側の各点から幅優先探索を行い交互道を発見する
for(int startNode = 0 , n = nodeList.size() ; startNode < n ; startNode++){
//マッチされているか、すでに訪れているか、右側にあるものは調べない
if(match[startNode]||visit[startNode]||(!left[startNode]))
continue;
//幅優先探索を行う
altPath = breadthFirstSearch(startNode);
if(altPath != null)
return altPath;
}
return null;
}
/**
* 交互道を見つけるための幅優先探索（交互道が見つかれば探索終了）
* @param startNode 幅優先探索の開始点
* @return 交互道を枝の列として含むArrayList、交互道がない場合はnull
*/
private List breadthFirstSearch(int startNode){
deque.push(startNode);
visit[startNode]=true;
while(!deque.isEmpty()){
int nowNode = deque.poll();
//nowNodeに接続している枝について
for(int edge : nodeList.get(nowNode)){
//nowNodeに隣接点について
int neighbor = edgeList.get(edge)[1];
//まだ訪れていないときのみ
if(!visit[neighbor]){
prev[neighbor]=edge;
visit[neighbor]=true;
deque.add(neighbor);
//交互道か（マッチされていない右側の点で終わっているか）
if(!left[neighbor]&&!match[neighbor]){
return altPath(startNode,edge);
}
}
}
}
return null;
}
/**
* 幅優先探索終了時に呼び出され、幅優先探索の結果から
* 交互道を構成する
* @param startNode 幅優先探索の開始点
* @param edge 幅優先探索で訪れた最後の枝
* @return 交互道を枝の列として含むArrayList
*/
private List altPath(int startNode,int edge){
List path = new LinkedList();
path.add(edge);
while(edgeList.get(edge)[0]!=startNode){
edge = prev[edgeList.get(edge)[0]];
path.add(edge);
}
return path;
}
/**
* 交互道からマッチングを一つ増やす
* @param 交互道（枝の列）
*/
private void matchingExchange(List altPath){
if(debug) dispPath(altPath);
int lastEdge = altPath.get(0);//交互道の最後の枝
int firstEdge = altPath.get(altPath.size()-1);//交互道の最初の枝
match[edgeList.get(lastEdge)[1]] = true;
match[edgeList.get(firstEdge)[0]]= true;
for(int edgeIndex : altPath){
changeDirection(edgeIndex);
}
}
/**
* 枝の向きを逆向きに変える
*
* @param edgeIndex 向きを変える枝の番号
*/
private void changeDirection(int edgeIndex){
int src = edgeList.get(edgeIndex)[0];
int dst = edgeList.get(edgeIndex)[1];
nodeList.get(src).remove(new Integer(edgeIndex));
nodeList.get(dst).add(new Integer(edgeIndex));
invNodeList.get(dst).remove(new Integer(edgeIndex));
invNodeList.get(src).add(new Integer(edgeIndex));
edgeList.get(edgeIndex)[0]=dst;
edgeList.get(edgeIndex)[1]=src;
}
/**
* 2部グラフの最大マッチングの1つを求める
*/
public void findMaxMatching() throws IOException{
List altPath = null;
if(dotFile) toDotFile(toGraphviz(null,"Start Bipartite Graph Matching."));
while((altPath = findAltPath())!=null){
if(dotFile) toDotFile(toGraphviz(altPath,"Alternating-Path(Bold)"));
matchingExchange(altPath);
if(dotFile) toDotFile(toGraphviz(null,"Mathing(Red)"));
if(debug) dispGraph();
}
if(dotFile) toDotFile(toGraphviz(altPath,"Matching is complete."));
}
/**
* データの内容を表示する。デバグ用メソッド
*/
private void dispGraph(){
System.out.println("node size = "+nodeList.size() +" , edge size = "+edgeList.size());
//順方向枝接続リストの表示
System.out.println("node -> edges:");
int j = 0;
for(List list : nodeList){
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 : invNodeList){
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 : edgeList)
System.out.println("edge ["+(j++)+"] ("+e[0]+","+e[1]+")");
//マッチング状況の表示
System.out.print("matching:");
for(boolean b : match)
System.out.print(b+" ");
System.out.println();
}
/**
* 交互道を表示する。デバグ用メソッド。
*/
private void dispPath(List path){
System.out.print("alt path : ");
for(int edge : path){
System.out.print("("+edgeList.get(edge)[0]+","+edgeList.get(edge)[1]+")");
}
System.out.println();
}
/**
* 現在のグラフの状態をGraphviz形式で出力
* @param label グラフのラベル
* @return String型で現在のグラフの状態
*/
private String toGraphviz(List path,String label){
StringBuffer sb = new StringBuffer(graphvizHead +"\n");
if(path == null)
path = new LinkedList();
sb.append("label = \""+label+"\";\n");
//ノードについて出力 マッチされているノードは赤
for(int i = 0 , n = nodeList.size() ; i < n ; i++){
sb.append(i+"[");
if(match[i])
sb.append("style = filled , color = black , fillcolor = red ];\n");
else
sb.append("color = black];\n");
}
//エッジについて出力 マッチに使われているエッジは赤
for(int i = 0 , n = edgeList.size() ; i < n ; i++){
sb.append(edgeList.get(i)[0] +" -> "+edgeList.get(i)[1]);
if(left[edgeList.get(i)[1]])
sb.append("[color = red , ");
else
sb.append("[color = black , ");
if(path.contains(new Integer(i)))
sb.append("style = bold];\n");
else
sb.append("style = solid];\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() ;
}
/**
* out<連番>.dot（例,out000.dot,out001.dot,...）というファイルに引数の文字列を出力
* 想定している使い方は
* toDotFile(toGraphviz(path))等
* @param dot 出力する文字列
* @return 出力したファイルの連番
*/
protected int toDotFile(String dot) throws IOException{
out = new BufferedWriter(new FileWriter("out"+String.format("%03d",dotFileCount)+".dot"));
out.write(dot);
out.close();
return dotFileCount++ ;
}
/**
* 標準入力からデータを読み込みグラフのデータ構造を作る
*/
public void readGraph() throws IOException {
int [] tmp ;
tmp = readNums();
init(tmp[0],tmp[1]);
for(int i = 0 , n = edgeList.size() ; i < n ; i++){
tmp = readNums();
int leftNode = tmp[0];
int rightNode = tmp[1];
//順方向の枝の接続リストを作る
nodeList.get(leftNode).add(i);
//逆方向の枝の接続リストを作る
invNodeList.get(rightNode).add(i);
edgeList.get(i)[0] = leftNode;
edgeList.get(i)[1] = rightNode;
left[leftNode] = true;
left[rightNode] = false;
}
if(debug) dispGraph();
}
/**
* 一行読んでそこにある二つの数字を返す
* @return 0番目に最初に読んだ数、1番目に次に読んだ数が格納されたint型配列
*/
private int [] readNums() throws IOException{
String [] strs = in.readLine().split("\\s+");
int [] nums = new int [2];
nums[0]= Integer.parseInt(strs[0]);
nums[1]= Integer.parseInt(strs[1]);
return nums ;
}
public static void main(String []args){
try{
BipartiteGraphMatching bgm = new BipartiteGraphMatching();
bgm.readGraph();
bgm.findMaxMatching();
}catch (IOException e ){
e.printStackTrace();
}
}
}