diff options
Diffstat (limited to 'test/ccured_olden/tsp')
| -rw-r--r-- | test/ccured_olden/tsp/.cvsignore | 28 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/CVS/Entries | 8 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/CVS/Repository | 1 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/CVS/Root | 1 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/Makefile | 44 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/README | 22 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/build.c | 124 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/main.c | 101 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/tsp.c | 308 | ||||
| -rw-r--r-- | test/ccured_olden/tsp/tsp.h | 32 |
10 files changed, 0 insertions, 669 deletions
diff --git a/test/ccured_olden/tsp/.cvsignore b/test/ccured_olden/tsp/.cvsignore deleted file mode 100644 index 83a0e7b9..00000000 --- a/test/ccured_olden/tsp/.cvsignore +++ /dev/null @@ -1,28 +0,0 @@ -*.o -*.obj -*.exe -*.pdb -*.ilk -*.cpp -*.i -*.s -*.asm -*cil.c -*.rtl -*box.c -*infer.c -*_ppp.c -*.origi -*.stackdump -*_all.c -changes.out -tsp.cil -tsp.*box -allcfiles -ope.m -ope.m -*cured.c -*.optim.c -*_comb.c -changes -*.browser diff --git a/test/ccured_olden/tsp/CVS/Entries b/test/ccured_olden/tsp/CVS/Entries deleted file mode 100644 index 92dedef2..00000000 --- a/test/ccured_olden/tsp/CVS/Entries +++ /dev/null @@ -1,8 +0,0 @@ -/Makefile/1.4/Sun Jul 8 14:10:47 2001// -/README/1.1/Tue Jun 12 04:31:21 2001// -/tsp.c/1.1/Tue Jun 12 04:31:21 2001// -/tsp.h/1.1/Tue Jun 12 04:31:21 2001// -/main.c/1.5/Mon Mar 18 23:18:46 2002// -/build.c/1.3/Wed May 29 03:29:06 2002// -/.cvsignore/1.11/Wed Jul 31 19:35:08 2002// -D diff --git a/test/ccured_olden/tsp/CVS/Repository b/test/ccured_olden/tsp/CVS/Repository deleted file mode 100644 index feb9fc46..00000000 --- a/test/ccured_olden/tsp/CVS/Repository +++ /dev/null @@ -1 +0,0 @@ -cil/test/olden/tsp diff --git a/test/ccured_olden/tsp/CVS/Root b/test/ccured_olden/tsp/CVS/Root deleted file mode 100644 index 35f411e9..00000000 --- a/test/ccured_olden/tsp/CVS/Root +++ /dev/null @@ -1 +0,0 @@ -/home/cvs-repository diff --git a/test/ccured_olden/tsp/Makefile b/test/ccured_olden/tsp/Makefile deleted file mode 100644 index a27d6db9..00000000 --- a/test/ccured_olden/tsp/Makefile +++ /dev/null @@ -1,44 +0,0 @@ -CC = gcc - -#CFLAGS = -CFLAGS = -O2 - -# sm -PLAIN=1 -all: defaulttarget - -ifdef PLAIN -ifdef _MSVC -EXTOBJ = .obj -OBJOUT = /Fo -EXEOUT = /Fe -CFLAGS = /DPLAIN -CONLY = /c -CC = cl -else -EXTOBJ = .o -OBJOUT = -o -EXEOUT = -o -CFLAGS += -DPLAIN -CONLY = -c -CC = gcc -MATH = -lm -endif - -MYOBJS = tsp$(EXTOBJ) build$(EXTOBJ) main$(EXTOBJ) - -%$(EXTOBJ) : %.c - $(CC) $(CONLY) $(CFLAGS) $< $(OBJOUT)$@ - - -defaulttarget: $(MYOBJS) - $(CC) $(CFLAGS) $(MYOBJS) $(EXTRA_LIBS) $(EXEOUT)tsp.exe $(MATH) -endif - - - -clean: - rm -f $(TARGET) $(OBJS) *.o *.obj *.exe *~ .make.state .nse_depinfo - - - diff --git a/test/ccured_olden/tsp/README b/test/ccured_olden/tsp/README deleted file mode 100644 index 29e34d88..00000000 --- a/test/ccured_olden/tsp/README +++ /dev/null @@ -1,22 +0,0 @@ -/* For copyright information, see olden_v1.01/COPYRIGHT */ -********************** -olden_v1.01/benchmarks/tsp/README -June 1996 -Martin C. Carlisle - -this directory contains the Traveling Salesman benchmark: - -Adapted for Olden from code by J. Muller using algorithm by: - -R. Karp, "Probabilistic analysis of partitioning algorithms for the traveling- -salesman problem in the plane." Mathematics of Operations Research -2(3):209-224, August 1977 - -********************** - -Makefile - use "make tsp" to create executable - -args.c - process command line args -build.c - build cities tree -tsp.[ch] - compute tsp -main.c - main routine diff --git a/test/ccured_olden/tsp/build.c b/test/ccured_olden/tsp/build.c deleted file mode 100644 index 090439bc..00000000 --- a/test/ccured_olden/tsp/build.c +++ /dev/null @@ -1,124 +0,0 @@ -/* build.c - * - * By: Martin C. Carlisle - * Princeton University - * 6/24/94 - * - * builds a two-dimensional tree for TSP - * - * distribution of median is given by modification of exponential to - * be [-1,1] - */ - -#include <stdio.h> - -extern double drand48(); -extern void srand48(long seedval); -extern double exp(double x); -extern double log(double x); -#define M_E 2.7182818284590452354 -#define M_E2 7.3890560989306502274 -#define M_E3 20.08553692318766774179 -#define M_E6 403.42879349273512264299 -#define M_E12 162754.79141900392083592475 -#ifndef NULL -#define NULL 0 -#endif - -#include "tsp.h" -#include <stdlib.h> - -#ifndef PLAIN -#include "mem-ref.h" -#ifdef FUTURES -#include "future-cell.h" -#endif -#endif - -static double median(double min,double max,int n); -static double uniform(double min, double max); - -double drand48(void) { - return (double)rand() / (double)RAND_MAX; -} - -/* Return an estimate of median of n values distributed in [min,max) */ -static double median(double min,double max,int n) { - double t; - double retval; - - t = drand48(); /* in [0.0,1.0) */ - if (t>0.5) { - retval=log(1.0-(2.0*(M_E12-1)*(t-0.5)/M_E12))/12.0; - } - else { - retval=-log(1.0-(2.0*(M_E12-1)*t/M_E12))/12.0; - } - /* We now have something distributed on (-1.0,1.0) */ - retval = (retval+1.0) * (max-min)/2.0; - retval = retval + min; - return retval; -} - -/* Get double uniformly distributed over [min,max) */ -static double uniform(double min, double max) { - double retval; - - retval = drand48(); /* in [0.0,1.0) */ - retval = retval * (max-min); - return retval + min; -} - -/* Builds a 2D tree of n nodes in specified range with dir as primary - axis (0 for x, 1 for y) */ -// post: -// if n!=0, make a node, set its left & right to valid or null, -// set next/prev to null; if n==0 return null -Tree build_tree(int n,int dir,int lo,int num_proc,double min_x, - double max_x,double min_y,double max_y) { - double med; - Tree t; -#ifdef FUTURES - future_cell_int fc; -#endif - - if (n==0) return NULL; - - t = (Tree) malloc(sizeof(*t)); - if (dir) { - dir = !dir; - med = median(min_x,max_x,n); -#ifndef FUTURES - t->left=build_tree(n/2,dir,lo+num_proc/2,num_proc/2,min_x,med,min_y,max_y); - t->right=build_tree(n/2,dir,lo,num_proc/2,med,max_x,min_y,max_y); -#else - FUTURE(n/2,dir,lo+num_proc/2,num_proc/2,min_x,med,min_y,max_y, - build_tree,&fc); - t->right=build_tree(n/2,dir,lo,num_proc/2,med,max_x,min_y,max_y); -#endif - t->x = med; - t->y = uniform(min_y,max_y); - } - else { - dir = !dir; - med = median(min_y,max_y,n); -#ifndef FUTURES - t->left=build_tree(n/2,dir,lo+num_proc/2,num_proc/2,min_x,max_x,min_y,med); - t->right=build_tree(n/2,dir,lo,num_proc/2,min_x,max_x,med,max_y); -#else - FUTURE(n/2,dir,lo+num_proc/2,num_proc/2,min_x,max_x,min_y,med, - build_tree,&fc); - t->right=build_tree(n/2,dir,lo,num_proc/2,min_x,max_x,med,max_y); -#endif - t->y = med; - t->x = uniform(min_x,max_x); - } - t->sz = n; - t->next = NULL; - t->prev = NULL; -#ifdef FUTURES - TOUCH(&fc); - t->left = (Tree) fc.value; -#endif - return t; -} diff --git a/test/ccured_olden/tsp/main.c b/test/ccured_olden/tsp/main.c deleted file mode 100644 index 3bd5679a..00000000 --- a/test/ccured_olden/tsp/main.c +++ /dev/null @@ -1,101 +0,0 @@ -#include "tsp.h" -#include <stdio.h> -#include <stdlib.h> - -#ifndef PLAIN -#include <cm/cmmd.h> -#include "mem-ref.h" -#endif - -#ifdef VERIFY_AFFINITIES -#include "affinity.h" -CHECK2(Tree,left,right,tree) -#endif - -int flag; -int __NumNodes, __NDim; - -int mylog(int num) -{ - int j=0,k=1; - - while(k<num) { k*=2; j++; } - return j; -} - -int dealwithargs(void) -{ - int num; - - flag = 0; - __NumNodes = 4; - - __NDim = mylog(__NumNodes); - - num = 150000; - - return num; -} - -void print_tree(Tree t) -{ - Tree left,right; - double x,y; - - if (!t) return; - x = t->x; y = t->y; - chatting("x=%f,y=%f\n",x,y); - left = t->left; right=t->right; - print_tree(left); - print_tree(right); -} - -void print_list(Tree t) -{ - Tree tmp; - double x,y; - - if (!t) return; - x = t->x; y = t->y; - chatting("%f %f\n",x,y); - for (tmp=t->next; tmp!=t; tmp=tmp->next) - { - x = tmp->x; y = tmp->y; - chatting("%f %f\n",x,y); - } -} - -double wallclock; - -int main() -{ - Tree t; - int num; - - num = dealwithargs(); - - chatting("Building tree of size %d\n",num); - t=build_tree(num,0,0,__NumNodes,0.0,1.0,0.0,1.0); -#ifdef VERIFY_AFFINITIES - Docheck_tree(t); -#endif - if (!flag) chatting("Past build\n"); - if (flag) chatting("newgraph\n"); - if (flag) chatting("newcurve pts\n"); - - - timer_start(0); - tsp(t,150,__NumNodes); - timer_stop(0); - if (flag) print_list(t); - if (flag) chatting("linetype solid\n"); - chatting("Time for TSP = %f\n", timer_elapsed(0)); -#ifdef VERIFY_AFFINITIES - Print_Accumulated_list(); -#endif - -#ifdef FUTURES - __ShutDown(0); -#endif - exit(0); -} diff --git a/test/ccured_olden/tsp/tsp.c b/test/ccured_olden/tsp/tsp.c deleted file mode 100644 index 5f371c86..00000000 --- a/test/ccured_olden/tsp/tsp.c +++ /dev/null @@ -1,308 +0,0 @@ -#include "tsp.h" - -#ifndef PLAIN -#include "mem-ref.h" -#ifdef FUTURES -#include "future-cell.h" -#endif -#endif - -#ifndef PLAIN -#define NULL 0 -#endif - -#ifdef VERIFY_AFFINITIES -#include "affinity.h" -CHECK1_ACCUM(Tree,next,list) -#endif - -static Tree conquer(Tree t); -static Tree merge(Tree a, Tree b, Tree t, int nproc); -static Tree makelist(Tree t); -static void reverse(Tree t); -static double distance(Tree a, Tree b); -extern double sqrt(double a); - -/* Find Euclidean distance from a to b */ -static double distance(Tree a, Tree b) { - double ax,ay,bx,by; - - ax = a->x; ay = a->y; - bx = b->x; by = b->y; - return (sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))); -} - -/* sling tree nodes into a list -- requires root to be tail of list */ -/* only fills in next field, not prev */ -static Tree makelist(Tree t) { - Tree left, right; - Tree tleft,tright; - Tree retval = t; - - if (!t) return NULL; - - /*chatting("makelist\n");*/ - left = makelist(t->left); /* head of left list */ - right = makelist(t->right); /* head of right list */ - - if (right) { retval = right; tright = t->right; tright->next = t; } - if (left) { retval=left; tleft=t->left; tleft->next = (right) ? right : t; } - t->next = NULL; - /*chatting("end makelist\n");*/ - - return retval; -} - -/* reverse orientation of list */ -static void reverse(Tree t) { - Tree prev,back,next,tmp; - - if (!t) return; - /*chatting("REVERSE\n");*/ - /*print_list(t);*/ - prev = t->prev; - prev->next = NULL; - t->prev = NULL; - back = t; - tmp = t; - for (t=t->next; t; back=t,t=next) { - next = t->next; - t->next = back; - back->prev = t; - } - tmp->next = prev; - prev->prev = tmp; - /*printf("REVERSE result\n");*/ - /*print_list(tmp);*/ - /*printf("End REVERSE\n");*/ -} - -/* Use closest-point heuristic from Cormen Leiserson and Rivest */ -static Tree conquer(Tree t) { - Tree cycle,tmp,min,prev,next,donext; - double mindist,test; - double mintonext, mintoprev, ttonext, ttoprev; - - if (!t) return NULL; - t=makelist(t); - - /*printf("CONQUER\n");*/ - /* Create initial cycle */ - cycle = t; - t = t->next; - cycle->next = cycle; - cycle->prev = cycle; - - for (; t; t=donext) { /* loop over remaining points */ - donext = t->next; /* value won't be around later */ - min = cycle; - mindist = distance(t,cycle); - for (tmp=cycle->next; tmp!=cycle; tmp=tmp->next) { - test = distance(tmp,t); - if (test < mindist) { - mindist = test; - min = tmp; - } /* if */ - } /* for tmp... */ - next = min->next; - prev = min->prev; - mintonext = distance(min,next); - mintoprev = distance(min,prev); - ttonext = distance(t,next); - ttoprev = distance(t,prev); - if ((ttoprev - mintoprev) < (ttonext - mintonext)) { - /* insert between min and prev */ - prev->next = t; - t->next = min; - t->prev = prev; - min->prev = t; - } - else { - next->prev = t; - t->next = next; - min->next = t; - t->prev = min; - } - } /* for t... */ - /*print_list(cycle);*/ - /*printf("End CONQUER\n");*/ - return cycle; -} - -/* Merge two cycles as per Karp */ -static Tree merge(Tree a, Tree b, Tree t, int nproc) { - Tree min,next,prev,tmp; - double mindist,test,mintonext,mintoprev,ttonext,ttoprev; - Tree n1,p1,n2,p2; - double tton1,ttop1,tton2,ttop2; - double n1ton2,n1top2,p1ton2,p1top2; - int choice; - int i; - - /* Compute location for first cycle */ - min = a; - mindist = distance(t,a); - tmp = a; -#ifdef VERIFY_AFFINITIES - Accumulate_list(a,a); - Accumulate_list(b,b); -#endif - for (a=a->next; a!=tmp; a=a->next) { - test = distance(a,t); - if (test < mindist) { - mindist = test; - min = a; - } /* if */ - } /* for a... */ - next = min->next; - prev = min->prev; - mintonext = distance(min,next); - mintoprev = distance(min,prev); - ttonext = distance(t,next); - ttoprev = distance(t,prev); - if ((ttoprev - mintoprev) < (ttonext - mintonext)) { - /* would insert between min and prev */ - p1 = prev; - n1 = min; - tton1 = mindist; - ttop1 = ttoprev; - } - else { /* would insert between min and next */ - p1 = min; - n1 = next; - ttop1 = mindist; - tton1 = ttonext; - } - - /* Compute location for second cycle */ - min = b; - mindist = distance(t,b); - tmp = b; - for (b=b->next; b!=tmp; b=b->next) { - test = distance(b,t); - if (test < mindist) { - mindist = test; - min = b; - } /* if */ - } /* for tmp... */ - next = min->next; - prev = min->prev; - mintonext = distance(min,next); - mintoprev = distance(min,prev); - ttonext = distance(t,next); - ttoprev = distance(t,prev); - if ((ttoprev - mintoprev) < (ttonext - mintonext)) { - /* would insert between min and prev */ - p2 = prev; - n2 = min; - tton2 = mindist; - ttop2 = ttoprev; - } - else { /* would insert between min and next */ - p2 = min; - n2 = next; - ttop2 = mindist; - tton2 = ttonext; - } - - /* Now we have 4 choices to complete: - 1:t,p1 t,p2 n1,n2 - 2:t,p1 t,n2 n1,p2 - 3:t,n1 t,p2 p1,n2 - 4:t,n1 t,n2 p1,p2 */ - n1ton2 = distance(n1,n2); - n1top2 = distance(n1,p2); - p1ton2 = distance(p1,n2); - p1top2 = distance(p1,p2); - - mindist = ttop1+ttop2+n1ton2; - choice = 1; - - test = ttop1+tton2+n1top2; - if (test<mindist) { - choice = 2; - mindist = test; - } - - test = tton1+ttop2+p1ton2; - if (test<mindist) { - choice = 3; - mindist = test; - } - - test = tton1+tton2+p1top2; - if (test<mindist) choice = 4; - -/*chatting("p1,n1,t,p2,n2 0x%x,0x%x,0x%x,0x%x,0x%x\n",p1,n1,t,p2,n2);*/ - switch (choice) { - case 1: - /* 1:p1,t t,p2 n2,n1 -- reverse 2!*/ - /*reverse(b);*/ - reverse(n2); - p1->next = t; - t->prev = p1; - t->next = p2; - p2->prev = t; - n2->next = n1; - n1->prev = n2; - break; - case 2: - /* 2:p1,t t,n2 p2,n1 -- OK*/ - p1->next = t; - t->prev = p1; - t->next = n2; - n2->prev = t; - p2->next = n1; - n1->prev = p2; - break; - case 3: - /* 3:p2,t t,n1 p1,n2 -- OK*/ - p2->next = t; - t->prev = p2; - t->next = n1; - n1->prev = t; - p1->next = n2; - n2->prev = p1; - break; - case 4: - /* 4:n1,t t,n2 p2,p1 -- reverse 1!*/ - /*reverse(a);*/ - reverse(n1); - n1->next = t; - t->prev = n1; - t->next = n2; - n2->prev = t; - p2->next = p1; - p1->prev = p2; - break; - } - return t; -} - -/* Compute TSP for the tree t -- use conquer for problems <= sz */ -Tree tsp(Tree t,int sz,int nproc) { - Tree left,right; - Tree leftval; -#ifdef FUTURES - future_cell_pointer fc; -#endif - Tree rightval; - int nproc_2 = nproc/2; - - if (t->sz <= sz) return conquer(t); - - left = t->left; right = t->right; -#ifndef FUTURES - leftval = tsp(left,sz,nproc_2); -#else - FUTURE(left,sz,nproc_2,tsp,&fc); -#endif - rightval = tsp(right,sz,nproc_2); -#ifdef FUTURES - leftval = (Tree) TOUCH(&fc); - leftval = (Tree) fc.value; - return merge(leftval,rightval,t,nproc); -#else - return merge(leftval,rightval,t,nproc); -#endif -} diff --git a/test/ccured_olden/tsp/tsp.h b/test/ccured_olden/tsp/tsp.h deleted file mode 100644 index 8d928891..00000000 --- a/test/ccured_olden/tsp/tsp.h +++ /dev/null @@ -1,32 +0,0 @@ -typedef struct tree { - int sz; - double x,y; - struct tree *left, *right; - /*struct tree *next, *prev;*/ - struct tree *next /*{95}*/, *prev /*{95}*/; -} *Tree; - -/* Builds a 2D tree of n nodes in specified range with dir as primary - axis (0 for x, 1 for y) */ -Tree build_tree(int n,int dir,int lo,int num_proc,double min_x, - double max_x,double min_y,double max_y); -/* Compute TSP for the tree t -- use conquer for problems <= sz */ -Tree tsp(Tree t, int sz, int nproc); - -#ifdef PLAIN -#include <time.h> -#define local -#define mymalloc malloc -#define CMMD_node_timer_clear(x) (void)0 -#define TIMESTART(clk) {clk=(double)clock();} -#define TIMESTOP(clk) {clk=1000000.0 * ((double)clock()-(clk))/CLOCKS_PER_SEC;} -extern double wallclock; -#define timer_start(x) TIMESTART(wallclock) -#define timer_stop(x) TIMESTOP(wallclock) -#define timer_elapsed(x) (wallclock / 1000.0) -#define chatting printf -#define NOTEST() (void)0 -#define RETEST() (void)0 -#define LOCAL(x) x -#define mymalloc malloc -#endif |