| Diploma Thesis Percolation Simulation C++ Sourcecode Documentation |
00001 // clusterproperties.h 00002 // spanning? 00003 // 00004 // (c) 2000 Andreas Krueger 00005 // Version 1.0 00006 // last change: 2.11.2000 00007 00008 00009 void occuring_clusternumbers(sphere* spheres, NUMLIST all, NUMLIST &clusternumbers){ 00010 00011 NUMLIST::iterator sph; 00012 for (sph=all.begin(); sph!=all.end(); sph++){ 00013 clusternumbers.push_back(spheres[*sph].clno); 00014 } 00015 clusternumbers.sort(); 00016 clusternumbers.unique(); // throws out doubles 00017 } 00018 00019 00020 void test_occuring_clusternumbers(){ 00021 NUMBER N=200; 00022 int dimension=2; 00023 REAL radius=0.03; 00024 COUNTER cuts=0; 00025 NUMBER numberofcl; NUMBER biggestcl; REAL averagecl; 00026 NUMBER *histogram=new NUMBER[(N+1)]; 00027 sphere *spheres = new sphere[N+1]; set_dim(spheres,0,N,dimension); 00028 NUMLIST all; 00029 00030 increasing_integers (all, N); // fill the list "all" with the numbers of all spheres 00031 throw_spheres(spheres, 1, N); // randomly throw spheres from 1 to N in array spheres 00032 set_radius(spheres, 1,N,radius); 00033 00034 set_clusternumber(spheres,1,N,0); // no sphere is found yet (initialization for counter) 00035 numberofcl=divide_by_c_cuts_count_and_analyze(spheres, all, cuts,histogram, biggestcl, averagecl); 00036 00037 NUMLIST clusternumbers; 00038 occuring_clusternumbers(spheres, all, clusternumbers); 00039 00040 cout <<"\n# of clusters: "<<numberofcl<<" biggestcl: "<<biggestcl<<" meancl:"<<averagecl<<"\noccuring clusternumbers:\n"; 00041 NUMLIST::iterator clno; 00042 for (clno=clusternumbers.begin();clno!=clusternumbers.end();clno++){ 00043 cout<<*clno<<"\t"; 00044 } 00045 cout <<"\n"; 00046 } 00047 00048 COUNTER intersection_of_unsortedlists(NUMLIST list_one, NUMLIST list_two, NUMLIST &result){ 00049 COUNTER found = 0; 00050 NUMLIST::iterator one, two; 00051 for (one=list_one.begin();one!=list_one.end(); one++){ 00052 for (two=list_two.begin();two!=list_two.end(); two++){ 00053 if (*one==*two){ 00054 result.push_back(*one); 00055 found++; 00056 } 00057 } 00058 } 00059 return found; 00060 } 00061 00062 COUNTER intersection_of_sortedlists(NUMLIST list_one, NUMLIST list_two, NUMLIST &result){ 00063 COUNTER found = 0; 00064 NUMLIST::iterator one, two; 00065 one=list_one.begin(); 00066 two=list_two.begin(); 00067 00068 while ( (one != list_one.end()) && (two != list_two.end()) ) { 00069 00070 while ( (*one < *two) && ( one != list_one.end()) ) one++; 00071 // if ( one == list_one.end() && *one==*two) Beep(50,5000); 00072 // this was the reason for a non(!)spanning spanningcluster!!! 00073 // so the next line (if... break) is necessary!!! 00074 if ( one == list_one.end() ) break; 00075 00076 if ( *one==*two) { 00077 found++; 00078 result.push_back(*one); 00079 two++; 00080 } 00081 else { 00082 while ((*two<*one)&&(two!=list_two.end())) two++; 00083 // here it is not necessary because of the main-while condition 00084 } 00085 } 00086 return found; 00087 } 00088 00089 00090 void testspeedof_intersection_procedures(){ 00091 NUMLIST a, b, c1, c2; 00092 NUMBER N1,N2; 00093 cout <<"How many random numbers? "<<endl; 00094 cout <<"in list a: "; 00095 cin >>N1; 00096 cout <<"in list b: "; 00097 cin >>N2; 00098 00099 cout <<"generating random numbers in two lists..."<<endl; 00100 NUMBER i; 00101 for (i=0;i<N1;i++){ 00102 a.push_back(rand()); 00103 } 00104 for (i=0;i<N2;i++){ 00105 b.push_back(rand()); 00106 } 00107 cout <<"sorting the numbers in each list..."<<endl; 00108 clock_t t3=clock(); 00109 a.sort(); 00110 b.sort(); 00111 t3=clock()-t3; 00112 00113 cout <<"erasing the doubles in each list..."<<endl; 00114 clock_t t4=clock(); 00115 a.unique(); 00116 b.unique(); 00117 t4=clock()-t4; 00118 00119 cout <<"intersection of lists as if they were unsorted (NAIVE)..."<<endl; 00120 c1.clear(); 00121 clock_t t1=clock(); 00122 COUNTER n1=intersection_of_unsortedlists(a,b,c1); 00123 t1=clock()-t1; 00124 00125 cout <<"intersection of lists knowing they are sorted (CLEVER)..."<<endl; 00126 c2.clear(); 00127 clock_t t2=clock(); 00128 COUNTER n2=intersection_of_sortedlists(a,b,c2); 00129 t2=clock()-t2; 00130 00131 cout <<"\n"; 00132 cout <<a.size()<<" in list a, "<<b.size()<<" in list b."<<endl; 00133 cout <<c1.size()<<" in intersection:"<<endl; 00134 NUMLIST::iterator each1, each2; 00135 each2=c2.begin(); 00136 00137 for (each1=c1.begin(); each1!=c1.end(); each1++){ 00138 if ((*each1!=*each2)) { 00139 cout <<"\n"<<*each1<<"\t"<<*each2<<"\t"<<*each2<<"\t"<<endl; 00140 exit(0); 00141 } 00142 else cout <<*each1<<"\t"; 00143 each2++; 00144 } 00145 cout <<endl; 00146 cout <<"time(ms) \tfor 2*sort:\t"<<ms(t3)<<" \n\t\tfor 2*unique:\t"<<ms(t4)<<endl; 00147 cout <<"for intersection of unsorted list:\t"<<ms(t1)<<" \n\t\t of sorted list: \t"<<ms(t2)<<"\t"<<endl; 00148 cout <<"number of intersections: "<<n1<<"\t"<<n2<<endl; 00149 cout <<"completely equal? "<< ((c1==c2)?"yes":"no") <<endl; 00150 00151 } 00152 00153 00154 00155 clock_t time1, time2, time3; // perhaps I can further improve the speed ? 00156 00157 COUNTER find_spanningclusters (sphere* spheres, NUMLIST all, 00158 NUMLIST &spclusters, 00159 unsigned int direction, 00160 COORDFLOAT left, COORDFLOAT right, 00161 REAL radius) 00162 { 00163 00164 NUMLIST left_edgespheres; 00165 NUMLIST right_edgespheres; 00166 time1=clock(); 00167 edgespheres(spheres, all, left_edgespheres, left, radius, -(int)direction); 00168 edgespheres(spheres, all, right_edgespheres, right, radius, direction); 00169 time1=clock()-time1; 00170 00171 NUMLIST left_edgeclusters; 00172 NUMLIST right_edgeclusters; 00173 time2=clock(); 00174 occuring_clusternumbers(spheres, left_edgespheres, left_edgeclusters); 00175 occuring_clusternumbers(spheres, right_edgespheres, right_edgeclusters); 00176 time2=clock()-time2; 00177 00178 time3=clock(); 00179 COUNTER found=intersection_of_sortedlists(left_edgeclusters, right_edgeclusters, spclusters); 00180 time3=clock()-time3; 00181 00182 return found; // and spanningclusters 00183 } 00184 00185 00186 00187 00188 LONGBITS spanning_dirs_and_clusters(sphere* spheres, NUMLIST all, 00189 COORDFLOAT left, COORDFLOAT right, 00190 REAL radius, int dim, 00191 cluson* clusters, 00192 NUMLIST &L_spanningclusters) 00193 // returns 0 if there is no spanning cluster 00194 // 00000101 if there are spanning clusters in direction 1 and 3 00195 00196 { 00197 if (dim>sizeof(LONGBITS)*8-1) { 00198 errorout("too many directions-bits necessary"); 00199 exit(1); 00200 } 00201 NUMLIST L_spanning_this_direction; 00202 LONGBITS bits=0; 00203 00204 for (int direction=1;direction<=dim;direction++){ 00205 if(0!=find_spanningclusters(spheres, all, L_spanning_this_direction, direction, left, right, radius)){ 00206 add_spanning_dir_to_clusters(clusters, L_spanning_this_direction, direction); 00207 L_spanningclusters.splice(L_spanningclusters.end(), L_spanning_this_direction); 00208 bits|=(LONGBITS)pow(2,direction-1); 00209 } 00210 } 00211 L_spanningclusters.sort(); 00212 L_spanningclusters.unique(); // throws out doubles 00213 00214 return bits; // and L_spanningclusters 00215 } 00216 00217 00218 00219 LONGBITS spanning_directions(sphere* spheres, NUMLIST all, 00220 COORDFLOAT left, COORDFLOAT right, 00221 REAL radius, int dim) 00222 // returns 0 if there is no spanning cluster 00223 // 00000101 if there are spanning clusters in direction 1 and 3 00224 00225 { 00226 if (dim>sizeof(LONGBITS)*8-1) { 00227 errorout("too many directions-bits necessary"); 00228 exit(1); 00229 } 00230 NUMLIST spanningclusters; 00231 LONGBITS bits=0; 00232 for (COUNTER direction=1;direction<=dim;direction++){ 00233 if(find_spanningclusters(spheres, all, spanningclusters, direction, left, right, radius)){ 00234 bits|=(LONGBITS)pow(2,direction-1); 00235 } 00236 } 00237 return bits; 00238 } 00239 00240 00241 00242 00243 00244 00245 00246 00247 00248 void test_spanningclusters(){ 00249 NUMBER N=20000; 00250 int dimension=5; 00251 REAL radius=1.01*R_critical_guessed(N,GRIDSIZE, dimension); 00252 COUNTER cuts=6; 00253 NUMBER numberofcl; NUMBER biggestcl; REAL averagecl; 00254 NUMBER *histogram=new NUMBER[(N+1)]; 00255 sphere *spheres = new sphere[N+1]; set_dim(spheres,0,N,dimension); 00256 NUMLIST all; 00257 00258 increasing_integers (all, N); // fill the list "all" with the numbers of all spheres 00259 throw_spheres(spheres, 1, N); // randomly throw spheres from 1 to N in array spheres 00260 set_radius(spheres, 1,N,radius); 00261 00262 set_clusternumber(spheres,1,N,0); // no sphere is found yet (initialization for counter) 00263 numberofcl=divide_by_c_cuts_count_and_analyze(spheres, all, cuts,histogram, biggestcl, averagecl); 00264 00265 NUMLIST spanningclusters; 00266 00267 COUNTER spcl=find_spanningclusters(spheres, all, spanningclusters, 1, 0, GRIDSIZE, radius); 00268 00269 00270 cout <<"\n# of clusters: "<<numberofcl<<" biggestcl: "<<biggestcl<<" meancl:"<<averagecl; 00271 cout <<"\ntimes for finding spanningcluster \n"; 00272 cout <<"finding edgespheres: "<<time1<<endl; 00273 cout <<"finding edgeclusters: "<<time2<<endl; 00274 cout <<"finding intersection set: "<<time3<<endl; 00275 cout <<"\nthe following "<<spcl<<" clusters are spanning clusters:\n"; 00276 NUMLIST::iterator clno; 00277 for (clno=spanningclusters.begin();clno!=spanningclusters.end();clno++){ 00278 cout<<*clno<<"\t"; 00279 } 00280 cout <<"\n"; 00281 }
| Diploma Thesis Sourcecode
Documentation check out the text and the executable binaries |