aboutsummaryrefslogtreecommitdiffstats
path: root/test/ccured_olden/tsp
diff options
context:
space:
mode:
Diffstat (limited to 'test/ccured_olden/tsp')
-rw-r--r--test/ccured_olden/tsp/.cvsignore28
-rw-r--r--test/ccured_olden/tsp/CVS/Entries8
-rw-r--r--test/ccured_olden/tsp/CVS/Repository1
-rw-r--r--test/ccured_olden/tsp/CVS/Root1
-rw-r--r--test/ccured_olden/tsp/Makefile44
-rw-r--r--test/ccured_olden/tsp/README22
-rw-r--r--test/ccured_olden/tsp/build.c124
-rw-r--r--test/ccured_olden/tsp/main.c101
-rw-r--r--test/ccured_olden/tsp/tsp.c308
-rw-r--r--test/ccured_olden/tsp/tsp.h32
10 files changed, 669 insertions, 0 deletions
diff --git a/test/ccured_olden/tsp/.cvsignore b/test/ccured_olden/tsp/.cvsignore
new file mode 100644
index 00000000..83a0e7b9
--- /dev/null
+++ b/test/ccured_olden/tsp/.cvsignore
@@ -0,0 +1,28 @@
+*.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
new file mode 100644
index 00000000..92dedef2
--- /dev/null
+++ b/test/ccured_olden/tsp/CVS/Entries
@@ -0,0 +1,8 @@
+/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
new file mode 100644
index 00000000..feb9fc46
--- /dev/null
+++ b/test/ccured_olden/tsp/CVS/Repository
@@ -0,0 +1 @@
+cil/test/olden/tsp
diff --git a/test/ccured_olden/tsp/CVS/Root b/test/ccured_olden/tsp/CVS/Root
new file mode 100644
index 00000000..35f411e9
--- /dev/null
+++ b/test/ccured_olden/tsp/CVS/Root
@@ -0,0 +1 @@
+/home/cvs-repository
diff --git a/test/ccured_olden/tsp/Makefile b/test/ccured_olden/tsp/Makefile
new file mode 100644
index 00000000..a27d6db9
--- /dev/null
+++ b/test/ccured_olden/tsp/Makefile
@@ -0,0 +1,44 @@
+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
new file mode 100644
index 00000000..29e34d88
--- /dev/null
+++ b/test/ccured_olden/tsp/README
@@ -0,0 +1,22 @@
+/* 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
new file mode 100644
index 00000000..090439bc
--- /dev/null
+++ b/test/ccured_olden/tsp/build.c
@@ -0,0 +1,124 @@
+/* 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
new file mode 100644
index 00000000..3bd5679a
--- /dev/null
+++ b/test/ccured_olden/tsp/main.c
@@ -0,0 +1,101 @@
+#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
new file mode 100644
index 00000000..5f371c86
--- /dev/null
+++ b/test/ccured_olden/tsp/tsp.c
@@ -0,0 +1,308 @@
+#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
new file mode 100644
index 00000000..8d928891
--- /dev/null
+++ b/test/ccured_olden/tsp/tsp.h
@@ -0,0 +1,32 @@
+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
generated by cgit (git 2.34.1) at 2024-07-06 16:15:02 +0000