| Diploma Thesis Percolation Simulation C++ Sourcecode Documentation |
Functions | |
| NUMBER | coordinate_to_slots (COORDFLOAT x, REAL xmin, REAL xmax, NUMBER n, REAL b, NUMLIST &slotlist) |
| void | test_coordinate_to_slots () |
| void | test_2dim_vector_to_boxes () |
| double | maximal_slots_that_can_be_numbered (int dim) |
| NUMBER | maximal_slots_that_can_be_numbered2 (int dim) |
| NUMBER | put_vector_into_boxes (myVector &x, REAL min, REAL max, NUMBER n, REAL b, NUMLIST &boxes) |
| void | test_vector2boxes () |
| NUMBER | spheres_into_boxes (sphere *spheres, NUMLIST &sph, REAL min, REAL max, NUMBER n, REAL b, std::vector< NUMLIST > &box) |
| void | test_spheres2boxes () |
| void | find_neighbours_in_a_box_recursion (sphere *spheres, std::vector< NUMBER > &sphno, bool *counted, NUMBER first, NUMBER N, NUMBER actualsph, NUMBER *clusterlinker, NUMBER &clnumber) |
| NUMBER | count_clusters_in_a_box (sphere *spheres, std::vector< NUMBER > &sphno, NUMBER N, NUMBER first_clno, NUMBER *clusterlinker) |
| NUMBER | clusterlinker_to_clusternumbers (NUMBER *clusterlinker, NUMBER N, NUMBER first_clno) |
| void | relabel_clusternumbers_in_spheres (sphere *spheres, NUMLIST &sphno, NUMBER *clusterlinker) |
| void | show_clusterlinker (NUMBER *clusterlinker, NUMBER N) |
| NUMBER | divide_spheres_into_overlapping_boxes_and_conquer (sphere *spheres, NUMLIST &sphno, NUMBER n, REAL border, NUMBER first_clno) |
| NUMBER | boxcount_analyze_and_return_clusters (sphere *spheres, NUMLIST &sphno, NUMBER n, REAL border, cluson *clusters, NUMBER *histogram, NUMBER &biggestclsz, REAL &meanclsz, NUMBER &biggestclno) |
| NUMBER | boxcount_and_analyze (sphere *spheres, NUMLIST &sphno, NUMBER n, REAL border, NUMBER *histogram, NUMBER &biggestclsz, REAL &meanclsz, NUMBER &biggestclno) |
|
||||||||||||||||||||||||||||||||||||||||
|
Definition at line 473 of file boxing.h. References divide_spheres_into_overlapping_boxes_and_conquer(), analyze::erasehisto(), errorout(), make_clusterlist_array(), NUMBER, REAL, reset_clusters(), and waitanykey(). Referenced by boxcount_and_analyze().
00478 {
00479 NUMBER first_clno=1;
00480 NUMBER last_clno=divide_spheres_into_overlapping_boxes_and_conquer(spheres, sphno, n, border, first_clno);
00481
00482 reset_clusters(clusters, sphno.size());
00483 make_clusterlist_array (spheres, sphno, clusters);
00484 erasehisto(histogram,1,sphno.size());
00485 NUMBER totalnumber= makehistogram ( clusters,
00486 first_clno, last_clno,
00487 histogram, biggestclno,
00488 biggestclsz, meanclsz);
00489
00490 if (totalnumber != (NUMBER)sphno.size()) {
00491 errorout("not all the spheres are in clusters! (boxcount)");
00492 cout << "number of spheres: N="<<sphno.size();
00493 cout <<" counted="<<totalnumber<<endl;
00494 waitanykey();
00495 exit(1);
00496 }
00497 return (last_clno-first_clno+1); // returns the number of clusters (M0)
00498 }
|
|
||||||||||||||||||||||||||||||||||||
|
Definition at line 502 of file boxing.h. References boxcount_analyze_and_return_clusters(), NUMBER, REAL, and set_clustersizes().
00507 {
00508 cluson *clusters=new cluson[sphno.size()+1];
00509
00510 NUMBER number_of_clusters= boxcount_analyze_and_return_clusters(spheres, sphno,
00511 n, border,
00512 clusters, histogram,
00513 biggestclsz, meanclsz, biggestclno);
00514 // only for checking:
00515 set_clustersizes(spheres, sphno, clusters);
00516
00517
00518 delete[] clusters;
00519
00520 return number_of_clusters;
00521 }
|
|
||||||||||||||||
|
Definition at line 390 of file boxing.h. References NUMBER. Referenced by divide_spheres_into_overlapping_boxes_and_conquer().
00390 {
00391 NUMBER i, j, k;
00392 k=first_clno;
00393 for (i=0; i<=N;i++){
00394 j=clusterlinker[i];
00395 if (j==i){
00396 clusterlinker[i]=-k;
00397 k++;
00398 }
00399 else{
00400 while (clusterlinker[j]>0){
00401 j=clusterlinker[j];
00402 }
00403 clusterlinker[i]=clusterlinker[j];
00404 }
00405 }
00406 return k-1;
00407 }
|
|
||||||||||||||||||||||||||||
|
Definition at line 11 of file boxing.h. References COORDFLOAT, fabs(), NUMBER, and REAL. Referenced by put_vector_into_boxes(), test_2dim_vector_to_boxes(), and test_coordinate_to_slots().
00013 {
00014 // x=coordinate
00015 // xmin,xmax=intervall of possible coordinates
00016 // n=# of slots
00017 // b=half border-size (=border around slot) = 2*radius of sphere
00018 // slotlist=list of slots that the coordinate belongs to
00019 // slots are [0,a+b], [a-b,2a+b] , ... ,[(n-1)a-b, na]
00020
00021 REAL L=xmax-xmin; if (L<=0) return 0; // total length
00022 REAL a=L/(REAL)n; if (a<0) return 0; // slot-size
00023 if (a<=b) return -1; // only direct neighbour slots can be checked!
00024 if (x>xmax) return 0;
00025 x=x-xmin; if (x<0) return 0; // relative coordinate (now positive!)
00026
00027 NUMBER fl=(NUMBER)floor(x/a);
00028 if (fl>=n) fl--; // right rim is part of last slot
00029 slotlist.push_back(fl); // is definitely part of this slot
00030 NUMBER slotcounter=1;
00031
00032 REAL relx;
00033 if (fl+1<n){
00034 relx=fabs(x - (fl+1)*a);
00035 if (relx <= b) {
00036 slotlist.push_back(fl+1);
00037 slotcounter++;
00038 }
00039 }
00040 if (fl-1 >= 0){
00041 relx=x - fl*a;
00042 if (relx <= b) {
00043 slotlist.push_back(fl-1);
00044 slotcounter++;
00045 }
00046 }
00047
00048 return slotcounter; // and slotlist, of course
00049 // or error=-1 if border>slot
00050 }
|
|
||||||||||||||||||||||||
|
Definition at line 360 of file boxing.h. References find_neighbours_in_a_box_recursion(), and NUMBER. Referenced by divide_spheres_into_overlapping_boxes_and_conquer().
00365 {
00366 bool *counted_flag=new bool[N];
00367 NUMBER k;
00368 for (k=0;k<N;k++) {
00369 counted_flag[k]=false;
00370 }
00371
00372 NUMBER clusternumber, clno_backup;
00373 clusternumber=first_clno;
00374
00375 for (k=0; k<N; k++) {
00376 if (!counted_flag[k]) {
00377 clno_backup=clusternumber;
00378 find_neighbours_in_a_box_recursion(spheres, sphno, counted_flag, k, N,
00379 k, clusterlinker, clusternumber);
00380 clusternumber=clno_backup+1;
00381 }
00382 }
00383 delete[] counted_flag;
00384 return clusternumber;
00385 }
|
|
||||||||||||||||||||||||
|
Definition at line 430 of file boxing.h. References clusterlinker_to_clusternumbers(), count_clusters_in_a_box(), getdim(), GRIDSIZE, NUMBER, pow(), REAL, relabel_clusternumbers_in_spheres(), show_clusterlinker(), spheres_into_boxes(), and waitanykey(). Referenced by boxcount_analyze_and_return_clusters().
00433 {
00434 int dim=getdim(spheres[sphno.front()]);
00435 NUMBER nboxes=(NUMBER)pow(n,dim);
00436 std::vector<NUMLIST > box; box.resize(nboxes);
00437 NUMBER nsphnow=spheres_into_boxes(spheres, sphno, 0, GRIDSIZE, n, border, box);
00438 if (nsphnow<=0) {
00439 cout<<"ERROR: nsphnow="<<nsphnow<<endl;
00440 waitanykey();
00441 exit(1);
00442 }
00443
00444 NUMBER* clusterlinker=new NUMBER[nsphnow+1];
00445 for (NUMBER i=0;i<=nsphnow;i++) clusterlinker[i]=i;
00446
00447 std::vector<NUMBER> onebox_sphno;
00448
00449 NUMBER nextclno=first_clno;
00450 NUMLIST::iterator sn;
00451 NUMBER b;
00452 for (b=0;b<nboxes;b++){
00453 onebox_sphno.clear();
00454 if (box[b].size()>0){
00455 for (sn=box[b].begin();sn!=box[b].end();sn++){
00456 onebox_sphno.push_back(*sn);
00457 }
00458 nextclno=count_clusters_in_a_box (spheres, onebox_sphno, box[b].size(),
00459 nextclno, clusterlinker);
00460 }
00461 }
00462
00463 cout<<endl; show_clusterlinker(clusterlinker, nextclno-1);
00464 NUMBER last_clno=clusterlinker_to_clusternumbers(clusterlinker, nextclno-1, first_clno);
00465 cout<<endl; show_clusterlinker(clusterlinker, nextclno-1);
00466 relabel_clusternumbers_in_spheres(spheres, sphno, clusterlinker);
00467
00468 delete [] clusterlinker;
00469 return last_clno;
00470 }
|
|
||||||||||||||||||||||||||||||||||||
|
Definition at line 309 of file boxing.h. References getdim(), NUMBER, and overlap2(). Referenced by count_clusters_in_a_box().
00313 {
00314
00315 counted[actualsph]=true;
00316 NUMBER asph=sphno[actualsph];
00317 spheres[asph].clno = clnumber;
00318
00319 sphere temp( getdim(spheres[asph].c) ); // used as a temporary distance vector
00320
00321 NUMBER clno2, clink;
00322 NUMBER nextsph, nsph;
00323 for (nextsph=first;nextsph<N;nextsph++) {
00324
00325 if (!counted[nextsph]) {
00326 nsph=sphno[nextsph];
00327 if ( overlap2(spheres[asph], spheres[nsph], temp) )
00328 {
00329 clno2=spheres[nsph].clno;
00330
00331 if (clno2 != 0){
00332 if (clnumber != clno2){
00333 clink=clno2;
00334
00335 while (clusterlinker[clink]!=clink){
00336 clink=clusterlinker[clink];
00337 }
00338
00339 if (clnumber > clink) {
00340 clusterlinker[clnumber]=clink;
00341 clnumber=clink;
00342 }
00343 else {
00344 if (clnumber < clink) {
00345 clusterlinker[clink]=clnumber;
00346 clusterlinker[clno2]=clnumber;
00347 }
00348 }
00349 }
00350 }
00351
00352 find_neighbours_in_a_box_recursion (spheres, sphno, counted, first, N,
00353 nextsph, clusterlinker, clnumber);
00354 }
00355 }
00356 }
00357 }
|
|
|
Definition at line 139 of file boxing.h. Referenced by optimize::new_vs_old_algo(), put_vector_into_boxes(), test_spheres2boxes(), and test_vector2boxes().
|
|
|
Definition at line 143 of file boxing.h.
|
|
||||||||||||||||||||||||||||
|
Definition at line 147 of file boxing.h. References myVector::coord(), coordinate_to_slots(), getdim(), maximal_slots_that_can_be_numbered(), NUMBER, pow(), and REAL. Referenced by spheres_into_boxes(), and test_vector2boxes().
00149 {
00150 int dim=getdim(x);
00151 if (n>maximal_slots_that_can_be_numbered(dim)) return -2; // two many box-numbers for NUMBER
00152
00153 std::vector<NUMLIST > slots; slots.resize(dim);
00154 int dir; NUMBER nslots;
00155 for(dir=0; dir<dim;dir++){
00156 slots[dir].clear();
00157 nslots=coordinate_to_slots(x.coord(dir),min,max,n,b,slots[dir]);
00158 if (nslots<=0) return nslots; // at least one coordinate not in intervall or slotsize<=slot-edge
00159 }
00160
00161 NUMBER offset;
00162 NUMLIST::iterator box, firstbox, lastbox;
00163 NUMLIST::iterator slot;
00164 boxes.push_back(0);
00165
00166 //NUMBER temp;
00167 for (dir=0;dir<dim;dir++){
00168 offset=(NUMBER)pow(n,dim-dir-1);
00169 firstbox=boxes.begin();
00170 lastbox=boxes.end();
00171 for(box=firstbox;box!=lastbox;box++){
00172 for(slot=slots[dir].begin();slot!=slots[dir].end();slot++){
00173 //temp=*box;
00174 boxes.push_front(*box + *slot*offset);
00175 }
00176 }
00177 boxes.erase(firstbox, lastbox);
00178 }
00179 return boxes.size();
00180 }
|
|
||||||||||||||||
|
Definition at line 409 of file boxing.h. References sphere::clno, NUMBER, and waitanykey(). Referenced by divide_spheres_into_overlapping_boxes_and_conquer().
00409 {
00410 NUMBER i,j;
00411 for (NUMLIST::iterator s=sphno.begin();s!=sphno.end();s++){
00412 i=spheres[*s].clno;
00413 j=clusterlinker[i];
00414 spheres[*s].clno=-j;
00415 if (j>0){
00416 waitanykey();
00417 }
00418 }
00419 }
|
|
||||||||||||
|
Definition at line 421 of file boxing.h. References NUMBER. Referenced by divide_spheres_into_overlapping_boxes_and_conquer().
|
|
||||||||||||||||||||||||||||||||
|
Definition at line 222 of file boxing.h. References NUMBER, put_vector_into_boxes(), and REAL. Referenced by divide_spheres_into_overlapping_boxes_and_conquer(), and test_spheres2boxes().
00225 {
00226 // ATTENTION: to use this for 'combine':
00227 // this will check ANY direction, even the edge
00228 // one could leave out this edge-direction to save boxnumber-space!!!
00229 // (all edgespheres will be in one (d-1)dimensional plane)
00230
00231 NUMLIST::iterator sn;
00232 NUMLIST::iterator bn;
00233 NUMBER nboxes;
00234 NUMLIST boxnumbers;
00235 NUMBER spherecounter=0;
00236 //NUMBER temp;
00237 for (sn=sph.begin();sn!=sph.end();sn++){
00238 boxnumbers.clear();
00239 nboxes=put_vector_into_boxes(spheres[*sn].c, min, max, n, b, boxnumbers);
00240 if (nboxes<=0) return nboxes;
00241 for (bn=boxnumbers.begin();bn!=boxnumbers.end();bn++){
00242 //temp=*bn;
00243 box[*bn].push_back(*sn);
00244 spherecounter++;
00245 }
00246 }
00247 return spherecounter; // and box of course
00248 }
|
|
|
Definition at line 81 of file boxing.h. References COORDFLOAT, coordinate_to_slots(), NUMBER, and REAL.
00081 {
00082 COORDFLOAT x, y;
00083 REAL xymin; REAL xymax;
00084 NUMBER n; REAL b;
00085
00086 cout<<"coordinate2boxes:\n( | 1 | | | 2 | | | 3 | ) ^ 2\n";
00087 cout<<"xymin, xymax = ?,? ";
00088 cin >>xymin>>xymax;
00089 cout<<"# of slots in one direction= ? ";
00090 cin>>n;
00091 cout <<"half size of (linear) slot-egde = ? ";
00092 cin>>b;
00093
00094 NUMLIST slotlist1, slotlist2; NUMLIST::iterator slot1,slot2;
00095 std::set<NUMBER> boxset; std::set<NUMBER>::iterator box;
00096 do {
00097 cout<<"give x-coordinate in ["<<xymin<<";"<<xymax<<"] = ? (42 = end) ";
00098 cin >>x;
00099 cout<<"give y-coordinate in ["<<xymin<<";"<<xymax<<"] = ? ";
00100 cin >>y;
00101 slotlist1.clear();
00102 slotlist2.clear();
00103
00104 NUMBER xs=coordinate_to_slots(x,xymin,xymax,n,b,slotlist1);
00105 NUMBER ys=coordinate_to_slots(y,xymin,xymax,n,b,slotlist2);
00106 cout<<"\nx="<<x<<" is in ";
00107 cout<<xs<<" slots, with the numbers: ";
00108 if (slotlist1.size()!=0)
00109 for(slot1=slotlist1.begin();slot1!=slotlist1.end();slot1++){
00110 cout<<*slot1<<" ";
00111 }
00112 cout<<"\ny="<<y<<" is in ";
00113 cout<<ys<<" slots, with the numbers: ";
00114 if (slotlist2.size()!=0)
00115 for(slot2=slotlist2.begin();slot2!=slotlist2.end();slot2++){
00116 cout<<*slot2<<" ";
00117 }
00118
00119 cout<<"\n\nSo (x,y)=("<<x<<"; "<<y<<") is in ";
00120 cout<<xs*ys<<" boxes, with the numbers: ";
00121
00122 boxset.clear();
00123 if (slotlist1.size()!=0 && slotlist2.size()!=0 ){
00124 for(slot1=slotlist1.begin();slot1!=slotlist1.end();slot1++){
00125 for(slot2=slotlist2.begin();slot2!=slotlist2.end();slot2++){
00126 boxset.insert(*slot1 * n + *slot2);
00127 }
00128 }
00129 for(box=boxset.begin();box!=boxset.end();box++){
00130 cout<<*box<<" ";
00131 }
00132 }
00133 cout <<"\n\n";
00134 } while(x!=42);
00135 }
|
|
|
Definition at line 53 of file boxing.h. References COORDFLOAT, coordinate_to_slots(), NUMBER, and REAL.
00053 {
00054 COORDFLOAT x;
00055 REAL xmin; REAL xmax;
00056 NUMBER n; REAL b;
00057
00058 cout<<"coordinate2slot:\n| 1 | | | 2 | | | 3 |\nxmin, xmax = ?,? ";
00059 cin >>xmin>>xmax;
00060 cout<<"# of slots = ? ";
00061 cin>>n;
00062 cout <<"half size of slot-egde = ? ";
00063 cin>>b;
00064
00065 NUMLIST slotlist; NUMLIST::iterator slot;
00066 do {
00067 cout<<"give coordinate in ["<<xmin<<";"<<xmax<<"] = ? (42 = end) ";
00068 cin >>x;
00069 slotlist.clear();
00070 cout<<"x="<<x<<" is in ";
00071 cout<<coordinate_to_slots(x,xmin,xmax,n,b,slotlist);
00072 cout<<" slots, with the numbers: ";
00073 if (slotlist.size()!=0)
00074 for(slot=slotlist.begin();slot!=slotlist.end();slot++){
00075 cout<<*slot<<" ";
00076 }
00077 cout <<"\n\n";
00078 } while(x!=42);
00079 }
|
|
|
Definition at line 251 of file boxing.h. References GRIDSIZE, increasing_integers(), maximal_slots_that_can_be_numbered(), NUMBER, pow(), REAL, set_dim(), spheres_into_boxes(), throw_spheres(), and waitanykey().
00251 {
00252 cout<<"\nspheres2boxes\n";
00253
00254 REAL min; REAL max;
00255 NUMBER n; REAL b;
00256 int dim;
00257 NUMBER N;
00258
00259 cout <<"dimension = ? ";
00260 cin>>dim;
00261 cout<<"# of slots in one direction( <"<<maximal_slots_that_can_be_numbered(dim)<<") = ? ";
00262 cin>>n;
00263 cout<<"coordmin, coordmax = ?,? ";
00264 cin >>min>>max;
00265 cout <<"half size of (linear) slot-egde = ? ";
00266 cin>>b;
00267 cout <<"number of spheres = ? ";
00268 cin >>N;
00269
00270 sphere* spheres= new sphere[N+1];
00271 set_dim(spheres,0,N,dim);
00272 NUMLIST all; increasing_integers (all, N);
00273 cout <<"OK. Now I throw "<<N<<" random coordinates. Gimme a random seed: ? ";
00274 int randseed;
00275 cin>>randseed;
00276 srand(randseed);
00277 throw_spheres(spheres, all);
00278
00279 std::vector<NUMLIST > box;
00280 NUMBER nboxes=(NUMBER)pow(n,dim);
00281 box.resize(nboxes);
00282 cout <<"\nnow the "<<N<<" spheres have become "<<flush;
00283 cout <<spheres_into_boxes(spheres, all, 0, GRIDSIZE, n, b, box);
00284 cout <<" spheres in "<<nboxes<<" boxes (because some are in several boxes)\n";
00285 cout <<"You want to see, which spheres are in which boxes?\n";
00286 waitanykey();
00287
00288 NUMBER bn;
00289 NUMLIST::iterator sn;
00290 for (bn=0; bn<nboxes;bn++){
00291 cout<<"\nBox"<<bn<<": ";
00292 for (sn=box[bn].begin();sn!=box[bn].end();sn++){
00293 cout <<*sn<<" ";
00294 }
00295 }
00296 cout <<"\ncool, isn't it?\n"<<endl;
00297 }
|
|
|
Definition at line 182 of file boxing.h. References myVector::coord(), maximal_slots_that_can_be_numbered(), NUMBER, put_vector_into_boxes(), and REAL.
00182 {
00183 cout<<"\nvector2boxes\n";
00184
00185 REAL min; REAL max;
00186 NUMBER n; REAL b;
00187 int dim;
00188
00189 cout <<"dimension = ? ";
00190 cin>>dim;
00191 cout<<"# of slots in one direction( <"<<maximal_slots_that_can_be_numbered(dim)<<") = ? ";
00192 cin>>n;
00193 myVector x(dim);
00194 cout<<"coordmin, coordmax = ?,? ";
00195 cin >>min>>max;
00196 cout <<"half size of (linear) slot-egde = ? ";
00197 cin>>b;
00198
00199 NUMLIST boxes; NUMLIST::iterator box; NUMBER nboxes;
00200 do {
00201 cout<<"give coordinates in ["<<min<<";"<<max<<"]^"<<dim<<" (42->END) = ? ";
00202 cin >>x;
00203
00204 boxes.clear();
00205 nboxes=put_vector_into_boxes(x, min, max, n, b, boxes);
00206 if (nboxes==-2) {cout<<"sorry, too many slots (in this dim) for long"<<endl; break;}
00207 if (nboxes==-1) {cout<<"sorry, slot-edge >= slotsize"<<endl;break;}
00208 if (nboxes==0) {cout<<"very sorry, at least one coordinate is not slot-ed";}
00209
00210 cout<<"\nx="<<x<<" is in ";
00211 cout<<nboxes<<" boxes, with the numbers: ";
00212 if (boxes.size()!=0){
00213 for(box=boxes.begin();box!=boxes.end();box++){
00214 cout<<*box<<" ";
00215 }
00216 }
00217 cout <<"\n\n";
00218 } while ( x.coord(0) != 42);
00219 cout <<"Goodbye...\n\n"<<endl;
00220 }
|
| Diploma Thesis Sourcecode
Documentation check out the text and the executable binaries |