diff options
Diffstat (limited to 'test/ccured_olden/mst/makegraph.c')
-rw-r--r-- | test/ccured_olden/mst/makegraph.c | 93 |
1 files changed, 93 insertions, 0 deletions
diff --git a/test/ccured_olden/mst/makegraph.c b/test/ccured_olden/mst/makegraph.c new file mode 100644 index 00000000..c99fad96 --- /dev/null +++ b/test/ccured_olden/mst/makegraph.c @@ -0,0 +1,93 @@ +/* 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; +} + + |