diff options
Diffstat (limited to 'test/ccured_olden/mst/makegraph.c')
-rw-r--r-- | test/ccured_olden/mst/makegraph.c | 93 |
1 files changed, 0 insertions, 93 deletions
diff --git a/test/ccured_olden/mst/makegraph.c b/test/ccured_olden/mst/makegraph.c deleted file mode 100644 index c99fad96..00000000 --- a/test/ccured_olden/mst/makegraph.c +++ /dev/null @@ -1,93 +0,0 @@ -/* For copyright information, see olden_v1.0/COPYRIGHT */ - -#include "mst.h" -#include "ssplain.h" - -#define CONST_m1 10000 -#define CONST_b 31415821 -#define RANGE 2048 -static int HashRange; - -static int mult(int p, int q) -{ - int p1, p0, q1, q0; - - p1=p/CONST_m1; p0=p%CONST_m1; - q1=q/CONST_m1; q0=q%CONST_m1; - return (((p0*q1+p1*q0) % CONST_m1)*CONST_m1+p0*q0); -} - -static int mst_random(int seed) -{ - int tmp; - tmp = (mult(seed,CONST_b)+1); - return tmp; -} - -static int compute_dist(int i,int j, int numvert) -{ - int less, gt; - if (i<j) {less = i; gt = j;} else {less = j; gt = i;} - return (mst_random(less*numvert+gt) % RANGE)+1; -} - -static int hashfunc(unsigned int key) -{ - return ((key>>4) % HashRange); -} - -static void AddEdges(Graph retval, int numvert) -{ - Vertex src, dest; - Hash hash; - int i, j, dist, num_inserted = 0; - - for (j = 0; j < numvert; j++) - { - src = &(retval->vlist[j]); - hash = src->edgehash; - - for (i=0; i<numvert; i++) - { - if (i!=j) - { - dist = compute_dist(i,j,numvert); - dest = &(retval->vlist[i]); - HashInsert((void *) dist,(unsigned int) dest,hash); - num_inserted++; - } - } /* for i */ - } /* for j */ - - chatting("%d edges inserted\n", num_inserted); -} - -Graph MakeGraph(int numvert) -{ - int i; - Vertex vf, vt; - Graph retval; - - retval = (Graph) malloc (sizeof(*retval)); - - chatting("Make phase 1: Creating hash tables\n"); - retval->vlist = (Vertex) malloc (numvert*(sizeof(*vf))); - vt = NULL; - - for (i = numvert - 1; i >= 0; i--) - { - vf = &(retval->vlist[i]); - HashRange = numvert/4; - vf->mindist = 9999999; - vf->edgehash = MakeHash(HashRange,hashfunc); - vf->next = vt; - vt=vf; - } - - chatting("Make phase 3: Creating graph\n"); - AddEdges(retval, numvert); - chatting("Make returning\n"); - return retval; -} - - |