| 1 |
/* |
| 2 |
* Copyright(C) 1999-2020, 2023 National Technology & Engineering Solutions |
| 3 |
* of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with |
| 4 |
* NTESS, the U.S. Government retains certain rights in this software. |
| 5 |
* |
| 6 |
* See packages/seacas/LICENSE for details |
| 7 |
*/ |
| 8 |
|
| 9 |
#include "params.h" // for MAXSETS |
| 10 |
#include "structs.h" // for vtx_data |
| 11 |
|
| 12 |
void inits3d(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 |
int *sets /* set each vertex gets assigned to */ |
| 21 |
) |
| 22 |
{ |
| 23 |
double xmid, ymid, zmid; /* median x, y and z values */ |
| 24 |
double val, bestval; /* values for determining set preferences */ |
| 25 |
int bestset = 0; /* set vertex wants to be in */ |
| 26 |
int signx, signy, signz; /* sign values for different target points */ |
| 27 |
int nsets = 8; /* number of different sets */ |
| 28 |
int i, j; /* loop counters */ |
| 29 |
|
| 30 |
/* |
| 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]]); |
| 37 |
*/ |
| 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]]; |
| 41 |
|
| 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; |
| 50 |
|
| 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] = findindex(indices[0][3], vals[0][3], dist[3] - dist[0], nvtxs); |
| 56 |
startvtx[1][2] = startvtx[5][6] = findindex(indices[1][2], vals[1][2], dist[2] - dist[1], nvtxs); |
| 57 |
startvtx[0][5] = startvtx[2][7] = findindex(indices[0][5], vals[0][5], dist[5] - dist[0], nvtxs); |
| 58 |
startvtx[1][4] = startvtx[3][6] = findindex(indices[1][4], vals[1][4], dist[4] - dist[1], nvtxs); |
| 59 |
startvtx[0][6] = startvtx[1][7] = findindex(indices[0][6], vals[0][6], dist[6] - dist[0], nvtxs); |
| 60 |
startvtx[2][4] = startvtx[3][5] = findindex(indices[2][4], vals[2][4], dist[4] - dist[2], nvtxs); |
| 61 |
startvtx[0][7] = findindex(indices[0][7], vals[0][7], dist[7] - dist[0], nvtxs); |
| 62 |
startvtx[1][6] = findindex(indices[1][6], vals[1][6], dist[6] - dist[1], nvtxs); |
| 63 |
startvtx[2][5] = findindex(indices[2][5], vals[2][5], dist[5] - dist[2], nvtxs); |
| 64 |
startvtx[3][4] = findindex(indices[3][4], vals[3][4], dist[4] - dist[3], nvtxs); |
| 65 |
|
| 66 |
/* Finally, determine the set sizes based on this splitter. */ |
| 67 |
|
| 68 |
for (i = 0; i < nsets; i++) { |
| 69 |
size[i] = 0; |
| 70 |
} |
| 71 |
|
| 72 |
for (i = 1; i <= nvtxs; i++) { |
| 73 |
/* Which set is this vertex in? */ |
| 74 |
signx = signy = signz = -1; |
| 75 |
bestval = 0; |
| 76 |
for (j = 0; j < nsets; j++) { |
| 77 |
val = -dist[j] + 2 * (signx * xvecs[1][i] + signy * xvecs[2][i] + signz * xvecs[3][i]); |
| 78 |
if (j == 0 || val < bestval) { |
| 79 |
bestval = val; |
| 80 |
bestset = j; |
| 81 |
} |
| 82 |
if (signx == 1 && signy == 1) { |
| 83 |
signz *= -1; |
| 84 |
} |
| 85 |
if (signx == 1) { |
| 86 |
signy *= -1; |
| 87 |
} |
| 88 |
signx *= -1; |
| 89 |
} |
| 90 |
sets[i] = bestset; |
| 91 |
size[bestset] += graph[i]->vwgt; |
| 92 |
} |
| 93 |
} |