Diploma Thesis Sourcecode Documentation C++ Percolation Simulation ( WWW.AndreasKrueger.de---

00001 // analyze.h
00002 // analyzes the histograms made by the clustercount
00003 // Andreas Krueger 25.1.2000
00004 // v1.3, last change : 2.5.2000
00005 
00006 
00007 namespace analyze{
00008 
00009 void erasehisto(NUMBER *histo,NUMBER first,NUMBER last) {
00010         for (NUMBER i=first;i<=last;i++){
00011                 histo[i]=0;
00012         }
00013 }
00014 
00015 NUMBER show_shorthisto(NUMBER *histogram, NUMBER first, NUMBER last) {
00016         NUMBER clusters=0;                      // the number of clusters
00017         NUMBER counted=0;                       // the number of spheres
00018 
00019         cout <<"size\t\tnumber of these clusters"<<endl;
00020         for (NUMBER i=first; i<=last; i++) {
00021                 if (histogram[i]!=0) {                                  // the last entry in "histogram" must be 0 !
00022                         cout << i << "\t\t" << histogram[i] <<endl;
00023                         clusters += histogram[i];
00024                         counted += histogram[i]*i; if (counted>=last) break;
00025                 }
00026         }
00027         return clusters;                                        
00028 }
00029 
00030 
00031 void show_histo(NUMBER *histo1, NUMBER last) {
00032         cout <<"size\t\tnumber of these clusters"<<endl;
00033         for (NUMBER i=1; i<=last; i++) {
00034                 if (histo1[i]!=0)
00035                         cout << i << "\t\t" << histo1[i] <<endl;
00036         }
00037 }
00038 
00039 void show_twohisto(NUMBER *histo1, NUMBER *histo2, NUMBER last) {
00040         cout <<"size\t\tcount1\tcount2 number of these clusters"<<endl;
00041         for (NUMBER i=1; i<=last; i++) {
00042                 if (histo2[i]!=0 && histo2[i]!=0)
00043                         cout << i << "\t\t" << histo1[i] << "\t" << histo2[i] <<endl;
00044         }
00045 }
00046 
00047 void show_threehisto(NUMBER *histo1, NUMBER *histo2, NUMBER *histo3, NUMBER last) {
00048         cout <<"size\t\tcount1\tcount2\tcount3 number of these clusters"<<endl;
00049         for (NUMBER i=1; i<=last; i++) {
00050                 if (histo1[i]!=0 || histo2[i]!=0 || histo3[i]!=0)
00051                         cout << i << "\t\t" << histo1[i] << "\t" << histo2[i] << "\t" << histo3[i] <<endl;
00052         }
00053 }
00054 
00055 void show_fourhisto(NUMBER *histo1, NUMBER *histo2, NUMBER *histo3, NUMBER *histo4, NUMBER last) {
00056         cout <<"size\t\tcount1\tcount2\tcount3\tcount4 number of these clusters"<<endl;
00057         for (NUMBER i=1; i<=last; i++) {
00058                 if ((histo1[i]!=0) || (histo2[i]!=0) || (histo3[i]!=0) || (histo4[i]!=0) ){
00059                         cout << i << "\t\t" << histo1[i] << "\t" << histo2[i];
00060                         cout << "\t" << histo3[i] << "\t" << histo4[i] <<endl;
00061                 }
00062         }
00063 }
00064 
00065 void show_fivehisto(NUMBER *histo1, NUMBER *histo2, NUMBER *histo3, NUMBER *histo4, NUMBER *histo5, NUMBER last) {
00066         cout <<"size\t\tcount1\tcount2\tcount3\tcount4\tcount4 number of these clusters"<<endl;
00067         for (NUMBER i=1; i<=last; i++) {
00068                 if ((histo1[i]!=0) || (histo2[i]!=0) || (histo3[i]!=0) || (histo4[i]!=0) || (histo5[i]!=0) ){
00069                         cout << i << "\t\t" << histo1[i] << "\t" << histo2[i];
00070                         cout << "\t" << histo3[i] << "\t" << histo4[i] << "\t" << histo4[i] <<endl;
00071                 }
00072         }
00073 }
00074 
00075 void show_sixhisto(NUMBER *histo1, NUMBER *histo2, NUMBER *histo3, NUMBER *histo4, NUMBER *histo5, NUMBER *histo6, NUMBER last) {
00076         cout <<"size\t\tcount1\tcount2\tcount3\tcount4\tcount5\tcount6 number of these clusters"<<endl;
00077         for (NUMBER i=1; i<=last; i++) {
00078                 if ((histo1[i]!=0) || (histo2[i]!=0) || (histo3[i]!=0) || (histo4[i]!=0) || (histo5[i]!=0) ){
00079                         cout << i << "\t\t" << histo1[i] << "\t" << histo2[i];
00080                         cout << "\t" << histo3[i] << "\t" << histo4[i] << "\t" << histo5[i] << "\t" << histo6[i] <<endl;
00081                 }
00082         }
00083 }
00084 
00085 void show_sevenhisto(NUMBER *histo1, NUMBER *histo2, NUMBER *histo3, NUMBER *histo4, NUMBER *histo5, NUMBER *histo6, NUMBER *histo7, NUMBER last) {
00086         cout <<"size\t\tcount1\tcount2\tcount3\tcount4\tcount5\tcount6\tcount7 number of these clusters"<<endl;
00087         for (NUMBER i=1; i<=last; i++) {
00088                 if ((histo1[i]!=0) || (histo2[i]!=0) || (histo3[i]!=0) || (histo4[i]!=0) || (histo5[i]!=0) || (histo6[i]!=0) || (histo7[i]!=0) ){
00089                         cout << i << "\t\t" << histo1[i] << "\t" << histo2[i];
00090                         cout << "\t" << histo3[i] << "\t" << histo4[i] << "\t" << histo5[i] << "\t" << histo6[i] << "\t" << histo7[i]<<endl;
00091                 }
00092         }
00093 }
00094 
00095 
00096 NUMBER mstfreqcluster(NUMBER *histogram, NUMBER first, NUMBER last) {
00097         NUMBER mstfreq=0;
00098         NUMBER highest=0;
00099         for (NUMBER i=first; i<=last; i++) {
00100                 if (histogram[i] >= highest) {
00101                         highest=histogram[i];
00102                         mstfreq=i;
00103                 }
00104         }
00105         return mstfreq;
00106 }
00107 
00108 
00109 bool sameresult(NUMBER *histo1, NUMBER *histo2, NUMBER first, NUMBER last) {
00110         for (NUMBER i=first;i<=last;i++){
00111                 if (histo1[i]!=histo2[i]) return 0;
00112         }
00113         return 1;
00114 }
00115 
00116 
00117 void makehistogram(NUMBER *tableofclusters,                     // each cluster has a size (last one: size=0)
00118                                    NUMBER *histogram,                                           // how many of that size ?
00119                                    NUMBER& biggest,
00120                                    NUMBER& biggestcl_no) {
00121         
00122 
00123         NUMBER clusterno=1;
00124         biggest=0;
00125 
00126         NUMBER size = tableofclusters[clusterno];
00127         while ( !(size==0) ){
00128                 histogram[size]++;                                                      // count all of that size
00129 
00130                 if (size>biggest) {
00131                         biggest=size;                                                   
00132                         biggestcl_no=clusterno;                                 // biggest cluster up to here
00133                 }
00134 
00135                 clusterno++;
00136                 size = tableofclusters[clusterno];
00137         }
00138 }
00139 
00140 
00141 NUMBER makehistogram (cluson *clusters,                 // returns total number of counted spheres
00142                                           NUMBER firstclno,
00143                                           NUMBER lastclno,
00144                                           NUMBER *histogram,
00145                                           NUMBER &biggestcluster_clno,
00146                                           NUMBER &biggestcluster_size,
00147                                           REAL &averagecluster_size)
00148 {
00149         NUMBER size; 
00150         NUMBER totalnumber=0;
00151         biggestcluster_clno=0, biggestcluster_size=0; 
00152         averagecluster_size=0;
00153 
00154         for (NUMBER clno=firstclno;clno<=lastclno;clno++){
00155                 size = clusters[clno].sphlist.size();
00156                 histogram[size]++;
00157 
00158                 if (size>biggestcluster_size) {
00159                         biggestcluster_size=size;
00160                         biggestcluster_clno=clno;
00161                 }
00162                 totalnumber +=size;
00163                 averagecluster_size += (REAL) size * (REAL) size;   // e.g. size 173 is mentioned 173 times
00164         }
00165         averagecluster_size /= (REAL) totalnumber;             // each sphere belongs to this clustersize by average
00166         return totalnumber;
00167 }
00168 
00169 
00170 NUMBER analyze_clusters (cluson* clst, 
00171                                                  NUMBER firstclno, 
00172                                                  NUMBER lastclno, 
00173                                                  NUMBER *histogram,
00174                                                  NUMBER N,
00175                                                  NUMBER &biggestcl, 
00176                                                  REAL &averagecl)
00177 {
00178         NUMBER biggestcl_no;
00179 
00180         erasehisto(histogram,1,N);
00181         makehistogram ( clst,firstclno,lastclno,
00182                                                 histogram, 
00183                                                 biggestcl_no, 
00184                                                 biggestcl,
00185                                                 averagecl);
00186         return (biggestcl_no);
00187 }
00188 
00189 void edgespheres (sphere *array,
00190                                                 NUMLIST & original,
00191                                                 NUMLIST & edgelist, 
00192                                                 COORDFLOAT border,
00193                                                 REAL radius,                            // positive radius (must be BIGGEST ocurring radius!)
00194                                                 int direction)                          // negative if the edge is at the lower side
00195 {
00196         int sign=(direction/abs(direction)); 
00197         NUMLIST::iterator iter1=original.begin();
00198         sphere sph(getdim(array[*iter1].c));
00199 
00200         if (sign<0) {
00201                 COORDFLOAT cut=border+(COORDFLOAT)radius;
00202                 for (iter1 ; iter1 != original.end(); ++iter1){
00203                         sph=array[*iter1];
00204                         if ( lower(sph.c, cut, abs(direction) )   ) 
00205                                 edgelist.insert(edgelist.end(), *iter1);
00206                 }
00207         }
00208         else    {
00209                 COORDFLOAT cut=border-(COORDFLOAT)radius;
00210                 for (iter1 ; iter1 != original.end(); ++iter1){
00211                         sph=array[*iter1];
00212                         if (! lower(sph.c, cut, abs(direction) )   ) 
00213                                 edgelist.insert(edgelist.end(), *iter1);
00214                 }
00215         }
00216 }
00217 
00218 
00219 void occuring_clusternumbers(sphere* spheres, NUMLIST all, NUMLIST &clusternumbers){
00220         
00221         NUMLIST::iterator sph;
00222         for (sph=all.begin(); sph!=all.end(); sph++){
00223                 clusternumbers.push_back(spheres[*sph].clno);
00224         }
00225         clusternumbers.sort();
00226         clusternumbers.unique();  // throws out doubles
00227 }
00228 
00229 
00230 
00231 
00232 COUNTER intersection_of_unsortedlists(NUMLIST list_one, NUMLIST list_two, NUMLIST &result){
00233         COUNTER found = 0;
00234         NUMLIST::iterator one, two;
00235         for (one=list_one.begin();one!=list_one.end(); one++){
00236                 for (two=list_two.begin();two!=list_two.end(); two++){
00237                         if (*one==*two){
00238                                 result.push_back(*one);
00239                                 found++;
00240                         }
00241                 }
00242         }
00243         return found;
00244 }
00245 
00246 COUNTER intersection_of_sortedlists(NUMLIST list_one, NUMLIST list_two, NUMLIST &result){
00247         COUNTER found = 0;
00248         NUMLIST::iterator one, two;
00249         one=list_one.begin();
00250         two=list_two.begin();
00251 
00252         while ( (one != list_one.end()) && (two != list_two.end()) ) {
00253 
00254                 while ( (*one < *two) && ( one != list_one.end()) ) one++;
00255                   // if ( one == list_one.end() && *one==*two) Beep(50,5000); 
00256                   //  this was the reason for a non(!)spanning spanningcluster!!!
00257                   //  so the next line (if... break) is necessary!!!
00258                 if ( one == list_one.end() ) break;
00259 
00260                 if ( *one==*two) {
00261                         found++;
00262                         result.push_back(*one);
00263                         two++;
00264                 }
00265                 else {
00266                         while ((*two<*one)&&(two!=list_two.end())) two++;
00267                         // here it is not necessary because of the main-while condition
00268                 }
00269         }
00270         return found;
00271 }
00272 
00273 
00274 
00275 
00276 
00277 clock_t time1, time2, time3;   // perhaps I can further improve the speed ?
00278 
00279 COUNTER find_spanningclusters (sphere* spheres, NUMLIST all,
00280                                            NUMLIST &spclusters, 
00281                                            unsigned int direction, 
00282                                            COORDFLOAT left, COORDFLOAT right,
00283                                            REAL radius)
00284 {
00285 
00286         NUMLIST left_edgespheres;
00287         NUMLIST right_edgespheres;
00288         time1=clock();
00289         edgespheres(spheres, all, left_edgespheres, left, radius, -(int)direction);
00290         edgespheres(spheres, all, right_edgespheres, right, radius, direction);
00291         time1=clock()-time1;
00292 
00293         NUMLIST left_edgeclusters;
00294         NUMLIST right_edgeclusters;
00295         time2=clock();
00296         occuring_clusternumbers(spheres, left_edgespheres, left_edgeclusters);
00297         occuring_clusternumbers(spheres, right_edgespheres, right_edgeclusters);
00298         time2=clock()-time2;
00299 
00300         time3=clock();
00301         COUNTER found=intersection_of_sortedlists(left_edgeclusters, right_edgeclusters, spclusters);
00302         time3=clock()-time3;
00303 
00304         return found;        // and spanningclusters
00305 }
00306 
00307 
00308 
00309 
00310 LONGBITS spanning_dirs_and_clusters(sphere* spheres, NUMLIST all,
00311                                                                         COORDFLOAT left, COORDFLOAT right,
00312                                                                         REAL radius, int dim,
00313                                                                         cluson* clusters,
00314                                                                         NUMLIST &L_spanningclusters)
00315         // returns 0        if there is no spanning cluster 
00316         //         00000101 if there are spanning clusters in direction 1 and 3
00317         
00318 {
00319         if (dim>sizeof(LONGBITS)*8-1) {
00320                 errorout("too many directions-bits necessary");
00321                 exit(1);
00322         }
00323         NUMLIST L_spanning_this_direction;
00324         LONGBITS bits=0; 
00325 
00326         for (int direction=1;direction<=dim;direction++){
00327                 if(0!=find_spanningclusters(spheres, all, L_spanning_this_direction, direction, left, right, radius)){
00328                         add_spanning_dir_to_clusters(clusters, L_spanning_this_direction, direction);
00329                         L_spanningclusters.splice(L_spanningclusters.end(), L_spanning_this_direction);
00330                         bits|=(LONGBITS)pow(2,direction-1);
00331                 }
00332         }
00333         L_spanningclusters.sort();
00334         L_spanningclusters.unique();  // throws out doubles
00335 
00336         return bits;            // and L_spanningclusters
00337 }
00338 
00339 
00340 
00341 LONGBITS spanning_directions(sphere* spheres, NUMLIST all,
00342                                                    COORDFLOAT left, COORDFLOAT right,
00343                                                    REAL radius, int dim)
00344         // returns 0        if there is no spanning cluster 
00345         //         00000101 if there are spanning clusters in direction 1 and 3
00346         
00347 {
00348         if (dim>sizeof(LONGBITS)*8-1) {
00349                 errorout("too many directions-bits necessary");
00350                 exit(1);
00351         }
00352         NUMLIST spanningclusters;
00353         LONGBITS bits=0; 
00354         for (COUNTER direction=1;direction<=dim;direction++){
00355                 if(find_spanningclusters(spheres, all, spanningclusters, direction, left, right, radius)){
00356                         bits|=(LONGBITS)pow(2,direction-1);
00357                 }
00358         }
00359         return bits;
00360 }
00361 
00362 REAL mean_without_lr_spanningcls(REAL mean_clsz, NUMBER N, cluson* clusters, 
00363                                                           NUMLIST& L_spanningclusters, LONGBITS spcl_dirs){
00364 
00365         if (spcl_dirs&1==0) return mean_clsz;   // no spanningcluster in left-right direction
00366 
00367         REAL temp=mean_clsz;
00368         temp *= (REAL)N;
00369 
00370         NUMBER clno, clsz;
00371         NUMLIST::iterator spcl;
00372         for (spcl=L_spanningclusters.begin();spcl!=L_spanningclusters.end();spcl++){
00373                 clno=*spcl;
00374                 if (clusters[clno].sp_lr()) {                   // subtract only left-right spanningclusters
00375                         clsz=clusters[clno].sphlist.size();
00376                         temp-= clsz * clsz;
00377                 }
00378         }
00379         temp/=(REAL)N;
00380         return temp;
00381 }
00382 
00383 
00384 NUMBER mass_of_all_spanningclusters(cluson* clusters,NUMLIST& L_spanningclusters){
00385         NUMBER temp=0;
00386         NUMLIST::iterator spcl;
00387         for (spcl=L_spanningclusters.begin();spcl!=L_spanningclusters.end();spcl++){
00388                 temp+=clusters[*spcl].sphlist.size();
00389         }
00390         return temp;
00391 }
00392 
00393 } // end of namespace analyze
00394