001 import swarm.space.*;
002 import swarm.defobj.*;
003 import swarm.*;
004 import java.util.*;
005
006 public class PatternSpace extends Discrete2dImpl{
007 int width,height;
008
009 LinkedList remainingPoints;
010 LinkedList largestCluster;
011 LinkedList clusterData;
012 LinkedList clusterSizeData;
013 boolean checked[][];
014
015 public PatternSpace(Zone aZone,int W,int H){
016 super(aZone,W,H);
017 width=W;
018 height=H;
019 initializeSpace();
020 }
021
022 /**
023 * コンストラクタの補助メソッド
024 */
025 void initializeSpace(){
026 remainingPoints=new LinkedList();
027 checked=new boolean[height][width];
028 clusterSizeData=new LinkedList();
029 for(int i=0;i<height;++i){
030 for(int j=0;j<width;++j){
031 int[] pair={i,j};
032 remainingPoints.add(pair);
033 this.putValue$atX$Y(0,i,j);
034 }
035 }
036 }
037
038 /**
039 * まだ点の置かれていない格子があるか
040 */
041 public boolean remainingQ(){
042 return !remainingPoints.isEmpty();
043 }
044
045 /**
046 * PatternSpaceに新しい点をランダムに追加する。<BR>
047 * ここではクラスタリングの計算は行わない。
048 * この計算は重いと予想されるため、getPercolationProbが呼ばれたときのみ行う。
049 */
050 public void update(){
051 int pIndex=Globals.env.uniformIntRand.getIntegerWithMin$withMax(0,remainingPoints.size()-1);
052 int[] p=(int[])remainingPoints.get(pIndex);
053 remainingPoints.remove(pIndex);
054 int i=p[0];
055 int j=p[1];
056 this.putValue$atX$Y(1,i,j);
057 }
058
059 /**
060 * クラスタに分ける処理を行うメソッド<BR>
061 * ・はじめ、すべての点はunchecked<BR>
062 * ・点を順番に調べていく<BR>
063 * ・uncheckedの点につながっている点を再帰的に調べる(traceCluster)<BR>
064 * ・できあがったclusterDataの中で、最大のものが最大クラスタ<BR>
065 * <BR>
066 * これは再帰的な処理だが、もちろん反復でもできる。<BR>
067 * 参考：小田垣孝「パーコレーションの科学」第3章
068 */
069 public void trace(){
070 int clusterIndex=-1;
071 clusterData=new LinkedList();
072
073 for(int i=0;i<height;++i){
074 for(int j=0;j<width;++j){
075 checked[i][j]=false;
076 }
077 }
078
079 for(int i=0;i<height;++i){
080 for(int j=0;j<width;++j){
081 if(!checked[i][j]){
082 if(getValueAtX$Y(i,j)!=0){
083 clusterIndex++;
084 clusterData.add(new LinkedList());
085 traceCluster(i,j,clusterIndex);
086 }
087 }
088 }
089 }
090
091 int s,maxSize=0;
092 clusterSizeData.clear();
093 Iterator it=clusterData.iterator();
094 while(it.hasNext()){
095 LinkedList cluster=(LinkedList)it.next();
096 s=cluster.size();
097 clusterSizeData.add(new Integer(s));
098 if(maxSize<s){
099 maxSize=s;
100 largestCluster=cluster;
101 }
102 }
103
104 for(int i=0;i<height;++i){
105 for(int j=0;j<width;++j){
106 if(this.getValueAtX$Y(i,j)==2){
107 this.putValue$atX$Y(1,i,j);
108 }
109 }
110 }
111
112 it=largestCluster.iterator();
113 int[] tmp;
114 while(it.hasNext()){
115 tmp=(int[])it.next();
116 int i=tmp[0];
117 int j=tmp[1];
118 putValue$atX$Y(2,i,j);
119 }
120 }
121
122 /**
123 * traceの補助メソッド
124 */
125 void traceCluster(int i,int j,int ci){
126 if(!checked[i][j]){
127 checked[i][j]=true;
128 if(getValueAtX$Y(i,j)!=0){
129 int[] pair={i,j};
130 ((LinkedList)clusterData.get(ci)).add(pair);
131 if(i!=0) traceCluster(i-1,j,ci);
132 if(i!=height-1) traceCluster(i+1,j,ci);
133 if(j!=0) traceCluster(i,j-1,ci);
134 if(j!=width-1) traceCluster(i,j+1,ci);
135 }
136 }
137 }
138
139 /**
140 * 浸透確率を計算する。<BR>
141 * 内部で、PatternSpaceに最大クラスタサイズを問い合わせ、
142 * その結果と、全格子数の比が浸透確率である。
143 */
144 public double getPercolationProb(){
145 trace();
146 return (double)largestCluster.size()/(width*height);
147 }
148
149 public LinkedList getClusterSizeData(){
150 return clusterSizeData;
151 }
152
153 public int getClusterNum(){
154 return clusterData.size();
155 }
156 }