1
/* This software was developed by Bruce Hendrickson and Robert Leland *
2
* at Sandia National Laboratories under US Department of Energy *
3
* contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
11
void inits3d(graph, xvecs, vals, indices, nvtxs, dist, startvtx, size, sets)
12
struct vtx_data **graph; /* graph data structure for vertex weights */
13
double **xvecs; /* values to partition with */
14
double *vals[8][MAXSETS]; /* values in sorted lists */
15
int *indices[8][MAXSETS]; /* indices sorting lists */
16
int nvtxs; /* number of vertices */
17
double *dist; /* trial separation point */
18
int startvtx[8][MAXSETS]; /* indices defining separation */
19
double *size; /* size of each set being modified */
20
short *sets; /* set each vertex gets assigned to */
22
double xmid, ymid, zmid; /* median x, y and z values */
23
double val, bestval; /* values for determining set preferences */
24
short bestset; /* set vertex wants to be in */
25
int signx, signy, signz; /* sign values for different target points */
26
int nsets = 8; /* number of different sets */
27
int i, j; /* loop counters */
31
xmid = .25 * (vals[0][1][indices[0][1][nvtxs / 2]] +
32
vals[0][1][indices[0][1][nvtxs / 2 - 1]]);
33
ymid = .25 * (vals[0][2][indices[0][2][nvtxs / 2]] +
34
vals[0][2][indices[0][2][nvtxs / 2 - 1]]);
35
zmid = .25 * (vals[0][4][indices[0][4][nvtxs / 2]] +
36
vals[0][4][indices[0][4][nvtxs / 2 - 1]]);
38
xmid = .5 * vals[0][1][indices[0][1][nvtxs / 2]];
39
ymid = .5 * vals[0][2][indices[0][2][nvtxs / 2]];
40
zmid = .5 * vals[0][4][indices[0][4][nvtxs / 2]];
42
dist[0] = -xmid - ymid - zmid;
43
dist[1] = xmid - ymid - zmid;
44
dist[2] = -xmid + ymid - zmid;
45
dist[3] = xmid + ymid - zmid;
46
dist[4] = -xmid - ymid + zmid;
47
dist[5] = xmid - ymid + zmid;
48
dist[6] = -xmid + ymid + zmid;
49
dist[7] = xmid + ymid + zmid;
51
/* Now initialize startvtxs. */
52
startvtx[0][1] = startvtx[2][3] = startvtx[4][5] = startvtx[6][7] = nvtxs / 2;
53
startvtx[0][2] = startvtx[1][3] = startvtx[4][6] = startvtx[5][7] = nvtxs / 2;
54
startvtx[0][4] = startvtx[1][5] = startvtx[2][6] = startvtx[3][7] = nvtxs / 2;
55
startvtx[0][3] = startvtx[4][7] =
56
findindex(indices[0][3], vals[0][3], dist[3] - dist[0], nvtxs);
57
startvtx[1][2] = startvtx[5][6] =
58
findindex(indices[1][2], vals[1][2], dist[2] - dist[1], nvtxs);
59
startvtx[0][5] = startvtx[2][7] =
60
findindex(indices[0][5], vals[0][5], dist[5] - dist[0], nvtxs);
61
startvtx[1][4] = startvtx[3][6] =
62
findindex(indices[1][4], vals[1][4], dist[4] - dist[1], nvtxs);
63
startvtx[0][6] = startvtx[1][7] =
64
findindex(indices[0][6], vals[0][6], dist[6] - dist[0], nvtxs);
65
startvtx[2][4] = startvtx[3][5] =
66
findindex(indices[2][4], vals[2][4], dist[4] - dist[2], nvtxs);
67
startvtx[0][7] = findindex(indices[0][7], vals[0][7], dist[7] - dist[0], nvtxs);
68
startvtx[1][6] = findindex(indices[1][6], vals[1][6], dist[6] - dist[1], nvtxs);
69
startvtx[2][5] = findindex(indices[2][5], vals[2][5], dist[5] - dist[2], nvtxs);
70
startvtx[3][4] = findindex(indices[3][4], vals[3][4], dist[4] - dist[3], nvtxs);
72
/* Finally, determine the set sizes based on this splitter. */
74
for (i = 0; i < nsets; i++)
77
for (i = 1; i <= nvtxs; i++) {
78
/* Which set is this vertex in? */
79
signx = signy = signz = -1;
81
for (j = 0; j < nsets; j++) {
82
val = -dist[j] + 2 * (signx * xvecs[1][i] + signy * xvecs[2][i] + signz * xvecs[3][i]);
83
if (j == 0 || val < bestval) {
87
if (signx == 1 && signy == 1)
94
size[bestset] += graph[i]->vwgt;