00001 #include "box_list.h"
00002 #include "box.h"
00003 #include "glr.h"
00004 #include "llr.h"
00005 #include "defines.h"
00006 #include "error.h"
00007 #include "filename.h"
00008
00009
00010 #include <string.h>
00011 #include <stdlib.h>
00012
00026
00028
00029
00030 #define RN_TOPOLOGY 0 // Defines Rn topology to be used in graph construction
00031 #define TORUS_TOPOLOGY 1 // Defines Torus topology to be used in graph construction
00032
00033
00034 #define TRAVERSE_DEPTH_FIRST 0 // Traverse the graph in depth-first order
00035 #define TRAVERSE_CYCLES 1 // Traverse only the cycles of the graph
00036 #define TRAVERSE_WITHOUT_ORDER 2 // Traverse the graph with no specific order
00037
00038
00039 #define INTERSECT_TOL 0 // Threshold to decide whether two boxes intersect
00040
00041 boolean NormalIntervalsIntersect(Tinterval *i1, Tinterval *i2);
00042 boolean AngleIntervalsIntersect(Tinterval *i1, Tinterval *i2);
00043 boolean BoxesAreNeighboring(Tbox* box1, Tbox* box2, int topology);
00044 boolean BoxesIntersect(Tbox* box1, Tbox* box2, int topology);
00045 void ConnectFirstBoxInGraphOfBoxes(graph G,int topology);
00046 graph GraphOfBoxes(Tlist* boxlist, int topology);
00047 status TraverseDepthFirstComponent(graph_vertex root_v, graph_vertex curr_v, Tlist* boxlist);
00048 llist TraverseDepthFirstGraphOfBoxes(graph G);
00049 llist TraverseCyclesGraphOfBoxes(graph G, int nskip);
00050 llist TraverseAllNodesWithoutOrder(graph G);
00051 llist TraverseGraphOfBoxes(graph G, int traversal_type);
00052 void PrintWalk(FILE* f, llist walk, int stepsize);
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 boolean NormalIntervalsIntersect(Tinterval *i1, Tinterval *i2)
00063 {
00064 return(Intersect(i1,i2));
00065 }
00066
00067
00068
00069
00070
00071
00072
00073
00074 boolean AngleIntervalsIntersect(Tinterval *i1, Tinterval *i2)
00075 {
00076 double i1l, i1u, i2l, i2u;
00077 Tinterval a, b, c, d;
00078
00079
00080 i1l = i1->lower_limit; i1u = i1->upper_limit;
00081 i2l = i2->lower_limit; i2u = i2->upper_limit;
00082
00083
00084 if(i1l <= i1u && i2l <= i2u)
00085 {
00086
00087 if((i1l == 0 && i2u == 2*M_PI) || (i2l == 0 && i1u == 2*M_PI))
00088 return(TRUE);
00089
00090 else
00091 return(Intersect(i1,i2));
00092 }
00093
00094
00095 if(i1l > i1u)
00096 {
00097
00098 NewInterval(i1l,2*M_PI,&a);
00099 NewInterval(0,i1u,&b);
00100 return(AngleIntervalsIntersect(&a,i2) || AngleIntervalsIntersect(&b,i2));
00101 }
00102
00103
00104 if(i2l > i2u)
00105 {
00106
00107 NewInterval(i2l,2*M_PI,&c);
00108 NewInterval(0,i2u,&d);
00109 return(AngleIntervalsIntersect(i1,&c) || AngleIntervalsIntersect(i1,&d));
00110 }
00111
00112 return(FALSE);
00113 }
00114
00115
00116
00117
00118
00119
00120 boolean BoxesAreNeighboring(Tbox* box1, Tbox* box2, int topology)
00121 {
00122 return(BoxesIntersect(box1,box2,topology));
00123 }
00124
00125
00126
00127
00128
00129 boolean BoxesIntersect(Tbox* box1, Tbox* box2, int topology)
00130 {
00131 Tinterval* intv1;
00132 Tinterval* intv2;
00133 unsigned int i, dim;
00134 boolean boxes_intersect;
00135 double i1l, i1u, i2l, i2u;
00136
00137
00138 dim = GetBoxNIntervals(box1);
00139
00140
00141 for(i=0;i<dim;i++)
00142 {
00143
00144 intv1 = GetBoxInterval(i,box1);
00145 intv2 = GetBoxInterval(i,box2);
00146
00147
00148 i1l = intv1->lower_limit; i1u = intv1->upper_limit;
00149 i2l = intv2->lower_limit; i2u = intv2->upper_limit;
00150
00151
00152 intv1->lower_limit = intv1->lower_limit - INTERSECT_TOL;
00153 intv1->upper_limit = intv1->upper_limit + INTERSECT_TOL;
00154 intv2->lower_limit = intv2->lower_limit - INTERSECT_TOL;
00155 intv2->upper_limit = intv2->upper_limit + INTERSECT_TOL;
00156
00157
00158 switch(topology)
00159 {
00160 case RN_TOPOLOGY:
00161 boxes_intersect = NormalIntervalsIntersect(intv1,intv2);
00162 break;
00163 case TORUS_TOPOLOGY:
00164 boxes_intersect = AngleIntervalsIntersect(intv1,intv2);
00165 break;
00166 }
00167
00168
00169 intv1->lower_limit = i1l; intv1->upper_limit = i1u;
00170 intv2->lower_limit = i2l; intv2->upper_limit = i2u;
00171
00172
00173 if(!boxes_intersect)
00174 return(FALSE);
00175 }
00176
00177
00178 return(TRUE);
00179 }
00180
00181
00182
00183
00184
00185 void ConnectFirstBoxInGraphOfBoxes(graph G,int topology)
00186 {
00187 llist curr_v;
00188 llist first_v;
00189 Tbox* first_box;
00190 Tbox* curr_box;
00191 static int edge_count=1;
00192
00193
00194 first_v = G;
00195 if(first_v==NULL)
00196 Error("Error: empty graph in ConnectFirstBox");
00197
00198 first_box = (Tbox*)SPECIFIC_VERTEX_DATA(first_v);
00199
00200
00201 for(curr_v=NEXT(first_v); curr_v!=NULL; curr_v=NEXT(curr_v))
00202 {
00203 curr_box = (Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
00204 if(BoxesAreNeighboring(first_box,curr_box,topology))
00205 {
00206 add_edge_with_pointers(first_v,curr_v,NULL);
00207 printf("Edge added number %d\n", edge_count);
00208 edge_count++;
00209 }
00210 }
00211 }
00212
00213 graph GraphOfBoxes(Tlist* boxlist, int topology)
00214 {
00215 graph G;
00216 Tbox* curr_box;
00217 Titerator iter;
00218 int boxnumber;
00219
00220
00221 if(init_graph(&G)==ERROR)
00222 Error("Error:: init_graph() failed in GraphOfBoxes()");
00223
00224
00225 InitIterator(&iter,boxlist);
00226 First(&iter);
00227 boxnumber=1;
00228 while(!EndOfList(&iter))
00229 {
00230
00231 curr_box=(Tbox*)GetCurrent(&iter);
00232 printf("Adding box %d to the graph\n", boxnumber);
00233
00234
00235 if(insert_vertex(&G,boxnumber,(void*)curr_box)==ERROR)
00236 Error("Error in Graph of Boxes: couldn't insert vertex");
00237
00238
00239 ConnectFirstBoxInGraphOfBoxes(G,topology);
00240
00241
00242 Advance(&iter);
00243 boxnumber++;
00244 }
00245
00246 return(G);
00247 }
00248
00249
00250
00251
00252
00253
00254
00255 status TraverseDepthFirstComponent(graph_vertex root_v,
00256 graph_vertex curr_v,
00257 Tlist* boxlist)
00258 {
00259 llist curr_e;
00260 llist adj_v;
00261 Tbox* curr_box;
00262
00263
00264
00265 if(root_v==NULL || curr_v==NULL)
00266 return ERROR;
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278 VISITED(curr_v)=TRUE;
00279
00280
00281 curr_box = (Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
00282 AddLastElement((void*)curr_box,boxlist);
00283
00284
00285 for(curr_e=EMANATING(curr_v); curr_e!=NULL; curr_e=NEXT(curr_e))
00286 {
00287
00288 adj_v = VERTEX_POINTER(curr_e);
00289
00290
00291 if(!VISITED(adj_v))
00292 {
00293
00294 if(TraverseDepthFirstComponent(root_v,adj_v,boxlist)==ERROR)
00295 return ERROR;
00296
00297
00298 }
00299 }
00300
00301 return OK;
00302 }
00303
00304
00305
00306
00307
00308 llist TraverseAllNodesWithoutOrder(graph G)
00309 {
00310 llist walk_list;
00311 graph_vertex curr_v;
00312 Tlist* box_list;
00313 Tbox* curr_box;
00314
00315
00316 if(G==NULL)
00317 Error("Error in TraverseDepthFirstGraphOfBoxes: empty graph");
00318
00319
00320 if(init_list(&walk_list)==ERROR)
00321 Error("Error in TraverseDepthFirstGraphOfBoxes: unable to initialize list");
00322
00323
00324 NEW(box_list,1,Tlist);
00325 InitListOfBoxes(box_list);
00326
00327 for(curr_v=G; curr_v!=NULL; curr_v=NEXT(curr_v))
00328 {
00329 curr_box = (Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
00330 AddLastElement((void*)curr_box,box_list);
00331 }
00332
00333
00334 insert(&walk_list,(generic_ptr)box_list);
00335
00336
00337 return(walk_list);
00338 }
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350 llist TraverseDepthFirstGraphOfBoxes(graph G)
00351 {
00352 llist walk_list;
00353 graph_vertex curr_v;
00354 Tlist* box_list;
00355
00356
00357 if(G==NULL)
00358 Error("Error in TraverseDepthFirstGraphOfBoxes: empty graph");
00359
00360
00361 if(init_list(&walk_list)==ERROR)
00362 Error("Error in TraverseDepthFirstGraphOfBoxes: unable to initialize list");
00363
00364
00365 mark_all_unvisited(G);
00366 for(curr_v=G; curr_v!=NULL; curr_v=NEXT(curr_v)) {
00367 if(!VISITED(curr_v)) {
00368
00369 NEW(box_list,1,Tlist);
00370 InitListOfBoxes(box_list);
00371 TraverseDepthFirstComponent(curr_v, curr_v, box_list);
00372 insert(&walk_list,(generic_ptr)box_list);
00373 }
00374 }
00375
00376
00377 return(walk_list);
00378 }
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388 llist TraverseCyclesGraphOfBoxes(graph G, int nskip)
00389 {
00390 llist components;
00391 llist root;
00392 llist cycles;
00393 llist walk_list;
00394 Tlist* box_list;
00395 Tbox* curr_box;
00396 llist node_comp;
00397 llist node_cyc;
00398 llist node_vert;
00399 int i;
00400
00401
00402 if(init_list(&walk_list)==ERROR)
00403 Error("Error in TraverseCyclesGraphOfBoxes: unable to initialize list");
00404
00405
00406 init_list(&components);
00407 if(connected_components(G,&components)==ERROR)
00408 Error("Error in TraverseCyclesGraphOfBoxes: connected_components failed");
00409
00410 printf("Generating list of walks. One walk for each cycle of the graph...\n");
00411 printf("\tNumber of connected components is %d\n", length(components));
00412
00413
00414 for(node_comp=components; node_comp!=NULL; node_comp=NEXT(node_comp))
00415 {
00416
00417 root = (llist)(DATA(node_comp));
00418 printf("\tNew component:\n");
00419
00420
00421 init_list(&cycles);
00422 if(detect_fundamental_cycles(root, &cycles, NULL)==ERROR)
00423 Error("Error in TraverseCyclesGraphOfBoxes: failed to detect fundamental cycles");
00424 printf("\t\tNumber of cycles of this component is %d\n", length(cycles));
00425
00426
00427 for(node_cyc = cycles; node_cyc!=NULL; node_cyc=NEXT(node_cyc))
00428 {
00429
00430 NEW(box_list,1,Tlist);
00431 InitListOfBoxes(box_list);
00432 for(node_vert=CYC_VERTICES(node_cyc); node_vert!=NULL; node_vert=NEXT(node_vert))
00433 {
00434
00435
00436
00437 curr_box = (Tbox*)SPECIFIC_VERTEX_DATA(node_vert);
00438 AddLastElement((void*)curr_box,box_list);
00439
00440
00441 i=0;
00442 while(NEXT(node_vert)!=NULL && i<nskip)
00443 {
00444 node_vert=NEXT(node_vert);
00445 i++;
00446 }
00447 }
00448
00449
00450 append(&walk_list,(generic_ptr)box_list);
00451 }
00452
00453
00454 destroy_list(&cycles,NULL);
00455 }
00456
00457
00458 destroy_list(&components,NULL);
00459
00460 return(walk_list);
00461 }
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472 llist TraverseGraphOfBoxes(graph G, int traversal_type)
00473 {
00474 llist walk_list;
00475
00476
00477 switch(traversal_type)
00478 {
00479 case TRAVERSE_CYCLES:
00480
00481 walk_list = TraverseCyclesGraphOfBoxes(G,0);
00482 break;
00483 case TRAVERSE_DEPTH_FIRST:
00484
00485 walk_list = TraverseDepthFirstGraphOfBoxes(G);
00486 break;
00487 case TRAVERSE_WITHOUT_ORDER:
00488
00489 walk_list = TraverseAllNodesWithoutOrder(G);
00490 break;
00491 default:
00492
00493 Error("Error in TraverseGraphOfBoxes: invalid traversal type");
00494 break;
00495 }
00496
00497 return(walk_list);
00498 }
00499
00500
00501
00502
00503
00504 void PrintWalk(FILE* f, llist walk, int stepsize)
00505 {
00506 Tbox* curr_box;
00507 Titerator iter;
00508 Tlist* walk_box_list;
00509 unsigned int i;
00510
00511
00512 walk_box_list = (Tlist*)DATA(walk);
00513
00514
00515 InitIterator(&iter,walk_box_list);
00516 First(&iter);
00517 while(!EndOfList(&iter))
00518 {
00519
00520 curr_box = (Tbox *)GetCurrent(&iter);
00521
00522
00523 PrintBox(f,curr_box);
00524
00525
00526 for(i=0;i<(unsigned int)stepsize;i++)
00527 Advance(&iter);
00528 }
00529 }
00558 int main(int argc, char **arg)
00559 {
00560 if (argc<2)
00561 {
00562 fprintf(stdout,"Use:\n");
00563 fprintf(stdout," cuiksort <basename> <topology> <travmode> <stepsize> \n");
00564 fprintf(stdout,"Where:\n");
00565 fprintf(stdout," basename: The basename of the *.sol input file\n");
00566 fprintf(stdout," topology: May be 'r' (for Rn topology) or 't' (for torus topology)\n");
00567 fprintf(stdout," travmode: May be 'd' (depth 1st) or 'c' (for cycles) or 'u' (for unordered)\n");
00568 fprintf(stdout," stepsize: Stepsize used when printing the boxes of a walk to a file\n");
00569 fprintf(stdout,"Examples:\n");
00570 fprintf(stdout," sortboxes ./examples/cyclohexane r d 1\n");
00571 fprintf(stdout," sortboxes ./examples/cycloheptane r d 1\n");
00572 fprintf(stdout," sortboxes ./examples/cycloctane r d 1\n");
00573 }
00574 else
00575 {
00576 char suffix[50];
00577 Tlist sol_box_list;
00578 graph G;
00579 llist walk_list;
00580 llist curr_walk;
00581 Tlist* walk_box_list;
00582 int traversal_type;
00583 int walk_number;
00584 int topology;
00585 FILE *fd;
00586 int nisol;
00587 graph_vertex curr_v;
00588 Tbox* curr_box;
00589 int stepsize;
00590 Tfilename fsols,fout;
00591
00592
00593 if (argc<3)
00594 topology = RN_TOPOLOGY;
00595 else
00596 {
00597
00598 switch(arg[2][0])
00599 {
00600 case 'r':
00601 topology = RN_TOPOLOGY;
00602 printf("Using Rn topology\n");
00603 break;
00604 case 't':
00605 topology = TORUS_TOPOLOGY;
00606 printf("Using torus topology\n");
00607 break;
00608 }
00609 }
00610
00611 if (argc<4)
00612 traversal_type = TRAVERSE_DEPTH_FIRST;
00613 else
00614 {
00615
00616 switch(arg[3][0])
00617 {
00618 case 'd':
00619 traversal_type = TRAVERSE_DEPTH_FIRST;
00620 printf("Walks in depth-first mode\n");
00621 break;
00622 case 'c':
00623 traversal_type = TRAVERSE_CYCLES;
00624 printf("Walks in cycles mode\n");
00625 break;
00626 case 'u':
00627 traversal_type = TRAVERSE_WITHOUT_ORDER;
00628 printf("Walks in unordered mode\n");
00629 break;
00630 default:
00631 Error("Unknown traversal mode\n");
00632 break;
00633 }
00634 }
00635
00636 if (argc<5)
00637 stepsize=1;
00638 else
00639 {
00640
00641 stepsize = (unsigned int)(atoi(arg[4]));
00642 }
00643
00644
00645 CreateFileName(NULL,arg[1],NULL,SOL_EXT,&fsols);
00646 ReadListOfBoxes(GetFileFullName(&fsols),&sol_box_list);
00647 if(ListSize(&sol_box_list)==0)
00648 Error("Couldn't open solutions file\n");
00649
00650
00651 G = GraphOfBoxes(&sol_box_list,topology);
00652
00653
00654 walk_list = TraverseGraphOfBoxes(G,traversal_type);
00655
00656
00657 walk_number=1;
00658 for(curr_walk=walk_list; curr_walk!=NULL; curr_walk=NEXT(curr_walk))
00659 {
00660
00661 walk_box_list = (Tlist*)DATA(curr_walk);
00662
00663 if(ListSize(walk_box_list) > 1)
00664 {
00665
00666 sprintf(suffix,"_%d",walk_number);
00667 CreateFileName(NULL,arg[1],suffix,SOL_EXT,&fout);
00668 printf("Generating %s ...",GetFileFullName(&fout));
00669 fd = fopen(GetFileFullName(&fout),"w");
00670 if(fd==NULL)
00671 Error("Couldn't open output file\n");
00672
00673
00674 PrintWalk(fd,curr_walk,stepsize);
00675 fclose(fd);
00676 printf("done.\n");
00677 DeleteFileName(&fout);
00678
00679 walk_number++;
00680 }
00681 }
00682
00683
00684 nisol = 0;
00685 CreateFileName(NULL,arg[1],"_isol",SOL_EXT,&fout);
00686 fd = fopen(GetFileFullName(&fout),"w");
00687 if(fd==NULL)
00688 Error("Couldn't open file\n");
00689 printf("Generating %s ...",GetFileFullName(&fout));
00690 for(curr_v=G; curr_v!=NULL; curr_v = NEXT(curr_v))
00691 {
00692 if(degree(curr_v)==0)
00693 {
00694 curr_box = (Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
00695 PrintBox(fd,curr_box);
00696 nisol ++;
00697 }
00698 }
00699 fclose(fd);
00700 printf("done.\n");
00701 printf("%d isolated boxes.\n",nisol);
00702
00703 DeleteFileName(&fout);
00704 DeleteFileName(&fsols);
00705 }
00706
00707 return(EXIT_SUCCESS);
00708 }
00709