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,
int topology);
64 boolean BoxesIntersect(
Tbox* box1,
Tbox* box2,
int topology);
65 void ConnectFirstBoxInGraphOfBoxes(graph G,
int topology);
66 graph GraphOfBoxes(
Tlist* boxlist,
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,
int topology)
142 return(BoxesIntersect(box1,box2,topology));
149 boolean BoxesIntersect(
Tbox* box1,
Tbox* box2,
int topology)
154 boolean boxes_intersect;
155 double i1l, i1u, i2l, i2u;
181 boxes_intersect = NormalIntervalsIntersect(intv1,intv2);
184 boxes_intersect = AngleIntervalsIntersect(intv1,intv2);
205 void ConnectFirstBoxInGraphOfBoxes(graph G,
int topology)
211 static int edge_count=1;
216 Error(
"Error: empty graph in ConnectFirstBox");
218 first_box = (
Tbox*)SPECIFIC_VERTEX_DATA(first_v);
221 for(curr_v=NEXT(first_v); curr_v!=NULL; curr_v=NEXT(curr_v))
223 curr_box = (
Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
224 if(BoxesAreNeighboring(first_box,curr_box,topology))
226 add_edge_with_pointers(first_v,curr_v,NULL);
227 printf(
"Edge added number %d\n", edge_count);
233 graph GraphOfBoxes(
Tlist* boxlist,
int topology)
241 if(init_graph(&G)==ERROR)
242 Error(
"Error:: init_graph() failed in GraphOfBoxes()");
252 printf(
"Adding box %d to the graph\n", boxnumber);
255 if(insert_vertex(&G,boxnumber,(
void*)curr_box)==ERROR)
256 Error(
"Error in Graph of Boxes: couldn't insert vertex");
259 ConnectFirstBoxInGraphOfBoxes(G,topology);
275 status TraverseDepthFirstComponent(graph_vertex root_v,
285 if(root_v==NULL || curr_v==NULL)
298 VISITED(curr_v)=
TRUE;
301 curr_box = (
Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
305 for(curr_e=EMANATING(curr_v); curr_e!=NULL; curr_e=NEXT(curr_e))
308 adj_v = VERTEX_POINTER(curr_e);
314 if(TraverseDepthFirstComponent(root_v,adj_v,boxlist)==ERROR)
328 llist TraverseAllNodesWithoutOrder(graph G)
337 Error(
"Error in TraverseDepthFirstGraphOfBoxes: empty graph");
340 if(init_list(&walk_list)==ERROR)
341 Error(
"Error in TraverseDepthFirstGraphOfBoxes: unable to initialize list");
347 for(curr_v=G; curr_v!=NULL; curr_v=NEXT(curr_v))
349 curr_box = (
Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
354 insert(&walk_list,(generic_ptr)box_list);
370 llist TraverseDepthFirstGraphOfBoxes(graph G)
378 Error(
"Error in TraverseDepthFirstGraphOfBoxes: empty graph");
381 if(init_list(&walk_list)==ERROR)
382 Error(
"Error in TraverseDepthFirstGraphOfBoxes: unable to initialize list");
385 mark_all_unvisited(G);
386 for(curr_v=G; curr_v!=NULL; curr_v=NEXT(curr_v)) {
387 if(!VISITED(curr_v)) {
391 TraverseDepthFirstComponent(curr_v, curr_v, box_list);
392 insert(&walk_list,(generic_ptr)box_list);
408 llist TraverseCyclesGraphOfBoxes(graph G,
int nskip)
422 if(init_list(&walk_list)==ERROR)
423 Error(
"Error in TraverseCyclesGraphOfBoxes: unable to initialize list");
426 init_list(&components);
427 if(connected_components(G,&components)==ERROR)
428 Error(
"Error in TraverseCyclesGraphOfBoxes: connected_components failed");
430 printf(
"Generating list of walks. One walk for each cycle of the graph...\n");
431 printf(
"\tNumber of connected components is %d\n", length(components));
434 for(node_comp=components; node_comp!=NULL; node_comp=NEXT(node_comp))
437 root = (llist)(DATA(node_comp));
438 printf(
"\tNew component:\n");
442 if(detect_fundamental_cycles(root, &cycles, NULL)==ERROR)
443 Error(
"Error in TraverseCyclesGraphOfBoxes: failed to detect fundamental cycles");
444 printf(
"\t\tNumber of cycles of this component is %d\n", length(cycles));
447 for(node_cyc = cycles; node_cyc!=NULL; node_cyc=NEXT(node_cyc))
452 for(node_vert=CYC_VERTICES(node_cyc); node_vert!=NULL; node_vert=NEXT(node_vert))
457 curr_box = (
Tbox*)SPECIFIC_VERTEX_DATA(node_vert);
462 while(NEXT(node_vert)!=NULL && i<nskip)
464 node_vert=NEXT(node_vert);
470 append(&walk_list,(generic_ptr)box_list);
474 destroy_list(&cycles,NULL);
478 destroy_list(&components,NULL);
492 llist TraverseGraphOfBoxes(graph G,
int traversal_type)
494 llist walk_list=NULL;
497 switch(traversal_type)
499 case TRAVERSE_CYCLES:
501 walk_list = TraverseCyclesGraphOfBoxes(G,0);
503 case TRAVERSE_DEPTH_FIRST:
505 walk_list = TraverseDepthFirstGraphOfBoxes(G);
507 case TRAVERSE_WITHOUT_ORDER:
509 walk_list = TraverseAllNodesWithoutOrder(G);
513 Error(
"Error in TraverseGraphOfBoxes: invalid traversal type");
524 void PrintWalk(FILE* f, llist walk,
int stepsize)
528 Tlist* walk_box_list;
532 walk_box_list = (
Tlist*)DATA(walk);
546 for(i=0;i<(
unsigned int)stepsize;i++)
582 fprintf(stdout,
"Use:\n");
583 fprintf(stdout,
" cuiksort <basename> <topology> <travmode> <stepsize> \n");
584 fprintf(stdout,
"Where:\n");
585 fprintf(stdout,
" basename: The basename of the *.sol input file\n");
586 fprintf(stdout,
" topology: May be 'r' (for Rn topology) or 't' (for torus topology)\n");
587 fprintf(stdout,
" travmode: May be 'd' (depth 1st) or 'c' (for cycles) or 'u' (for unordered)\n");
588 fprintf(stdout,
" stepsize: Stepsize used when printing the boxes of a walk to a file\n");
589 fprintf(stdout,
"Examples:\n");
590 fprintf(stdout,
" sortboxes ./examples/cyclohexane r d 1\n");
591 fprintf(stdout,
" sortboxes ./examples/cycloheptane r d 1\n");
592 fprintf(stdout,
" sortboxes ./examples/cycloctane r d 1\n");
601 Tlist* walk_box_list;
602 int traversal_type=0;
614 topology = RN_TOPOLOGY;
621 topology = RN_TOPOLOGY;
622 printf(
"Using Rn topology\n");
625 topology = TORUS_TOPOLOGY;
626 printf(
"Using torus topology\n");
632 traversal_type = TRAVERSE_DEPTH_FIRST;
639 traversal_type = TRAVERSE_DEPTH_FIRST;
640 printf(
"Walks in depth-first mode\n");
643 traversal_type = TRAVERSE_CYCLES;
644 printf(
"Walks in cycles mode\n");
647 traversal_type = TRAVERSE_WITHOUT_ORDER;
648 printf(
"Walks in unordered mode\n");
651 Error(
"Unknown traversal mode\n");
661 stepsize = (
unsigned int)(atoi(arg[4]));
668 Error(
"Couldn't open solutions file\n");
671 G = GraphOfBoxes(&sol_box_list,topology);
674 walk_list = TraverseGraphOfBoxes(G,traversal_type);
678 for(curr_walk=walk_list; curr_walk!=NULL; curr_walk=NEXT(curr_walk))
681 walk_box_list = (
Tlist*)DATA(curr_walk);
686 sprintf(suffix,
"_%d",walk_number);
691 Error(
"Couldn't open output file\n");
694 PrintWalk(fd,curr_walk,stepsize);
708 Error(
"Couldn't open file\n");
710 for(curr_v=G; curr_v!=NULL; curr_v = NEXT(curr_v))
712 if(degree(curr_v)==0)
714 curr_box = (
Tbox*)SPECIFIC_VERTEX_DATA(curr_v);
721 printf(
"%d isolated boxes.\n",nisol);
727 return(EXIT_SUCCESS);
void First(Titerator *i)
Moves an iterator to the first position of its associated list.
Tinterval * GetBoxInterval(unsigned int n, Tbox *b)
Returns a pointer to one of the intervals defining the box.
boolean Intersect(Tinterval *i1, Tinterval *i2)
Checks is a two intervals intersect.
#define NEW(_var, _n, _type)
Allocates memory space.
Data structure to hold the information about the name of a file.
Definition of the Tfilename type and the associated functions.
void Error(const char *s)
General error function.
boolean ReadListOfBoxes(char *filename, Tlist *l)
Reads a list of boxes from a file.
Collection of methods to work on Tlist of boxes.
unsigned int GetBoxNIntervals(Tbox *b)
Box dimensionality.
Error and warning functions.
void DeleteFileName(Tfilename *fn)
Destructor.
void AddLastElement(void *Info, Tlist *list)
Adds an element at the tail of the list.
boolean EndOfList(Titerator *i)
Checks if an iterator is pointing at the end of the list.
Definition of the Tbox type and the associated functions.
Definitions of constants and macros used in several parts of the cuik library.
void InitIterator(Titerator *i, Tlist *list)
Constructor.
void CreateFileName(char *path, char *name, char *suffix, char *ext, Tfilename *fn)
Constructor.
char * GetFileFullName(Tfilename *fn)
Gets the file full name (paht+name+extension).
#define SOL_EXT
File extension for solution files.
int main(int argc, char **arg)
Main body of the cuiksort application.
void InitListOfBoxes(Tlist *l)
Constructor.
void * GetCurrent(Titerator *i)
Gets the element pointed by the iterator.
void NewInterval(double lower, double upper, Tinterval *i)
Constructor.
void PrintBox(FILE *f, Tbox *b)
Prints a box.
unsigned int ListSize(Tlist *list)
Gets the number of elements in the list.
boolean Advance(Titerator *i)
Moves an iterator to the next position of its associated list.
Follow us!