Go to the documentation of this file.
50 #define RN_TOPOLOGY 0 // Defines Rn topology to be used in graph construction
51 #define TORUS_TOPOLOGY 1 // Defines Torus topology to be used in graph construction
54 #define TRAVERSE_DEPTH_FIRST 0 // Traverse the graph in depth-first order
55 #define TRAVERSE_CYCLES 1 // Traverse only the cycles of the graph
56 #define TRAVERSE_WITHOUT_ORDER 2 // Traverse the graph with no specific order
59 #define INTERSECT_TOL 1e-3 // Threshold to decide whether two boxes intersect
63 boolean BoxesAreNeighboring( Tbox* box1, Tbox* box2, double tolerance, int topology);
64 boolean BoxesIntersect( Tbox* box1, Tbox* box2, double tolerance, int topology);
65 void ConnectFirstBoxInGraphOfBoxes(graph G, double tolerance, int topology);
66 graph GraphOfBoxes( Tlist* boxlist, double tolerance, int topology);
67 status TraverseDepthFirstComponent(graph_vertex root_v, graph_vertex curr_v, Tlist* boxlist);
68 llist TraverseDepthFirstGraphOfBoxes(graph G);
69 llist TraverseCyclesGraphOfBoxes(graph G, int nskip);
70 llist TraverseAllNodesWithoutOrder(graph G);
71 llist TraverseGraphOfBoxes(graph G, int traversal_type);
72 void PrintWalk(FILE* f, llist walk, int stepsize);
96 double i1l, i1u, i2l, i2u;
104 if(i1l <= i1u && i2l <= i2u)
107 if((i1l == 0 && i2u == 2* M_PI) || (i2l == 0 && i1u == 2* M_PI))
120 return(AngleIntervalsIntersect(&a,i2) || AngleIntervalsIntersect(&b,i2));
129 return(AngleIntervalsIntersect(i1,&c) || AngleIntervalsIntersect(i1,&d));
140 boolean BoxesAreNeighboring( Tbox* box1, Tbox* box2, double tolerance, int topology)
142 return(BoxesIntersect(box1,box2,tolerance,topology));
149 boolean BoxesIntersect( Tbox* box1, Tbox* box2, double tolerance, int topology)
154 double i1l, i1u, i2l, i2u;
162 for(i=0;((intersect)&&(i<dim));i++)
182 intersect = NormalIntervalsIntersect(intv1,intv2);
185 intersect = AngleIntervalsIntersect(intv1,intv2);
202 void ConnectFirstBoxInGraphOfBoxes(graph G, double tolerance, int topology)
208 static int edge_count=1;
213 Error( "Error: empty graph in ConnectFirstBox");
215 first_box = ( Tbox*)SPECIFIC_VERTEX_DATA(first_v);
218 for(curr_v=NEXT(first_v); curr_v!=NULL; curr_v=NEXT(curr_v))
220 curr_box = ( Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
221 if(BoxesAreNeighboring(first_box,curr_box,tolerance,topology))
223 add_edge_with_pointers(first_v,curr_v,NULL);
224 printf( "Edge added number %d\n", edge_count);
230 graph GraphOfBoxes( Tlist* boxlist, double tolerance, int topology)
238 if(init_graph(&G)==ERROR)
239 Error( "Error:: init_graph() failed in GraphOfBoxes()");
249 printf( "Adding box %d to the graph\n", boxnumber);
252 if(insert_vertex(&G,boxnumber,( void*)curr_box)==ERROR)
253 Error( "Error in Graph of Boxes: couldn't insert vertex");
256 ConnectFirstBoxInGraphOfBoxes(G,tolerance,topology);
272 status TraverseDepthFirstComponent(graph_vertex root_v,
282 if(root_v==NULL || curr_v==NULL)
295 VISITED(curr_v)= TRUE;
298 curr_box = ( Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
302 for(curr_e=EMANATING(curr_v); curr_e!=NULL; curr_e=NEXT(curr_e))
305 adj_v = VERTEX_POINTER(curr_e);
311 if(TraverseDepthFirstComponent(root_v,adj_v,boxlist)==ERROR)
325 llist TraverseAllNodesWithoutOrder(graph G)
334 Error( "Error in TraverseDepthFirstGraphOfBoxes: empty graph");
337 if(init_list(&walk_list)==ERROR)
338 Error( "Error in TraverseDepthFirstGraphOfBoxes: unable to initialize list");
344 for(curr_v=G; curr_v!=NULL; curr_v=NEXT(curr_v))
346 curr_box = ( Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
351 insert(&walk_list,(generic_ptr)box_list);
367 llist TraverseDepthFirstGraphOfBoxes(graph G)
375 Error( "Error in TraverseDepthFirstGraphOfBoxes: empty graph");
378 if(init_list(&walk_list)==ERROR)
379 Error( "Error in TraverseDepthFirstGraphOfBoxes: unable to initialize list");
382 mark_all_unvisited(G);
383 for(curr_v=G; curr_v!=NULL; curr_v=NEXT(curr_v)) {
384 if(!VISITED(curr_v)) {
388 TraverseDepthFirstComponent(curr_v, curr_v, box_list);
389 insert(&walk_list,(generic_ptr)box_list);
405 llist TraverseCyclesGraphOfBoxes(graph G, int nskip)
419 if(init_list(&walk_list)==ERROR)
420 Error( "Error in TraverseCyclesGraphOfBoxes: unable to initialize list");
423 init_list(&components);
424 if(connected_components(G,&components)==ERROR)
425 Error( "Error in TraverseCyclesGraphOfBoxes: connected_components failed");
427 printf( "Generating list of walks. One walk for each cycle of the graph...\n");
428 printf( "\tNumber of connected components is %d\n", length(components));
431 for(node_comp=components; node_comp!=NULL; node_comp=NEXT(node_comp))
434 root = (llist)(DATA(node_comp));
435 printf( "\tNew component:\n");
439 if(detect_fundamental_cycles(root, &cycles, NULL)==ERROR)
440 Error( "Error in TraverseCyclesGraphOfBoxes: failed to detect fundamental cycles");
441 printf( "\t\tNumber of cycles of this component is %d\n", length(cycles));
444 for(node_cyc = cycles; node_cyc!=NULL; node_cyc=NEXT(node_cyc))
449 for(node_vert=CYC_VERTICES(node_cyc); node_vert!=NULL; node_vert=NEXT(node_vert))
454 curr_box = ( Tbox*)SPECIFIC_VERTEX_DATA(node_vert);
459 while(NEXT(node_vert)!=NULL && i<nskip)
461 node_vert=NEXT(node_vert);
467 append(&walk_list,(generic_ptr)box_list);
471 destroy_list(&cycles,NULL);
475 destroy_list(&components,NULL);
489 llist TraverseGraphOfBoxes(graph G, int traversal_type)
491 llist walk_list=NULL;
494 switch(traversal_type)
496 case TRAVERSE_CYCLES:
498 walk_list = TraverseCyclesGraphOfBoxes(G,0);
500 case TRAVERSE_DEPTH_FIRST:
502 walk_list = TraverseDepthFirstGraphOfBoxes(G);
504 case TRAVERSE_WITHOUT_ORDER:
506 walk_list = TraverseAllNodesWithoutOrder(G);
510 Error( "Error in TraverseGraphOfBoxes: invalid traversal type");
521 void PrintWalk(FILE* f, llist walk, int stepsize)
525 Tlist* walk_box_list;
529 walk_box_list = ( Tlist*)DATA(walk);
543 for(i=0;i<( unsigned int)stepsize;i++)
580 fprintf(stdout, "Use:\n");
581 fprintf(stdout, " cuiksort <basename> <tolerance> <topology> <travmode> <stepsize> \n");
582 fprintf(stdout, "Where:\n");
583 fprintf(stdout, " basename : The basename of the *.sol input file\n");
584 fprintf(stdout, " tolerance: Tolerance when detecting box intersections\n");
585 fprintf(stdout, " topology : May be 'r' (for Rn topology) or 't' (for torus topology)\n");
586 fprintf(stdout, " travmode : May be 'd' (depth 1st) or 'c' (for cycles) or 'u' (for unordered)\n");
587 fprintf(stdout, " stepsize : Stepsize used when printing the boxes of a walk to a file\n");
588 fprintf(stdout, "Examples:\n");
589 fprintf(stdout, " sortboxes ./examples/cyclohexane r d 1\n");
590 fprintf(stdout, " sortboxes ./examples/cycloheptane r d 1\n");
591 fprintf(stdout, " sortboxes ./examples/cycloctane r d 1\n");
600 Tlist* walk_box_list;
601 int traversal_type=0;
614 tolerance = INTERSECT_TOL;
617 tolerance = atof(arg[2]);
620 tolerance = INTERSECT_TOL;
624 topology = RN_TOPOLOGY;
631 topology = RN_TOPOLOGY;
632 printf( "Using Rn topology\n");
635 topology = TORUS_TOPOLOGY;
636 printf( "Using torus topology\n");
642 traversal_type = TRAVERSE_DEPTH_FIRST;
649 traversal_type = TRAVERSE_DEPTH_FIRST;
650 printf( "Walks in depth-first mode\n");
653 traversal_type = TRAVERSE_CYCLES;
654 printf( "Walks in cycles mode\n");
657 traversal_type = TRAVERSE_WITHOUT_ORDER;
658 printf( "Walks in unordered mode\n");
661 Error( "Unknown traversal mode\n");
671 stepsize = ( unsigned int)(atoi(arg[5]));
678 Error( "Couldn't open solutions file\n");
681 G = GraphOfBoxes(&sol_box_list,tolerance,topology);
684 walk_list = TraverseGraphOfBoxes(G,traversal_type);
688 for(curr_walk=walk_list; curr_walk!=NULL; curr_walk=NEXT(curr_walk))
691 walk_box_list = ( Tlist*)DATA(curr_walk);
696 sprintf(suffix, "_%d",walk_number);
701 Error( "Couldn't open output file\n");
704 PrintWalk(fd,curr_walk,stepsize);
718 Error( "Couldn't open file\n");
720 for(curr_v=G; curr_v!=NULL; curr_v = NEXT(curr_v))
722 if(degree(curr_v)==0)
724 curr_box = ( Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
731 printf( "%d isolated boxes.\n",nisol);
737 return(EXIT_SUCCESS);
|
Follow us!