Debian Codegraph @

packages/seacas/libraries/chaco/bpmatch/inits2d.c

raw
1 /*
2 * Copyright(C) 1999-2020 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 int findindex(int *indices, /* indices sorting values */
13 double *vals, /* values sorted by indices */
14 double target, /* target value */
15 int nvals /* number of values */
16 )
17 {
18 double ratio; /* interpolation parameter */
19 double vlow, vhigh; /* values at limits of search range */
20 int low, high; /* range left to search */
21 int new; /* new index limit */
22
23 if (target <= vals[indices[0]]) {
24 return (0);
25 }
26 if (target >= vals[indices[nvals - 1]]) {
27 return (nvals - 1);
28 }
29
30 low = 0;
31 high = nvals - 1;
32
33 while (high - low > 1) {
34 vlow = vals[indices[low]];
35 vhigh = vals[indices[high]];
36 if (vlow == vhigh) {
37 return ((vlow + vhigh) / 2);
38 }
39
40 ratio = (target - vlow) / (vhigh - vlow);
41 new = low + ratio *(high - low);
42 if (new == low) {
43 ++new;
44 }
45 else if (new == high) {
46 --new;
47 }
48
49 if (vals[indices[new]] < target) {
50 low = new;
51 }
52 else {
53 high = new;
54 }
55 }
56
57 if (target == vals[indices[high]]) {
58 return (high);
59 }
60
61 return (low);
62 }
63
64 void inits2d(struct vtx_data **graph, /* graph data structure for vertex weights */
65 double **xvecs, /* values to partition with */
66 double *vals[4][MAXSETS], /* values in sorted lists */
67 int *indices[4][MAXSETS], /* indices sorting lists */
68 int nvtxs, /* number of vertices */
69 double *dist, /* trial separation point */
70 int startvtx[4][MAXSETS], /* indices defining separation */
71 double *size, /* size of each set being modified */
72 int *sets /* set each vertex gets assigned to */
73 )
74 {
75 double xmid, ymid; /* median x and y values */
76 double val, bestval; /* values for determining set preferences */
77 int bestset = 0; /* set vertex wants to be in */
78 int signx, signy; /* sign values for different target points */
79 int nsets = 4; /* number of different sets */
80 int i, j; /* loop counters */
81
82 /*
83 xmid = .25 * (vals[0][1][indices[0][1][nvtxs / 2]] +
84 vals[0][1][indices[0][1][nvtxs / 2 - 1]]);
85 ymid = .25 * (vals[0][2][indices[0][2][nvtxs / 2]] +
86 vals[0][2][indices[0][2][nvtxs / 2 - 1]]);
87 */
88 xmid = .5 * vals[0][1][indices[0][1][nvtxs / 2]];
89 ymid = .5 * vals[0][2][indices[0][2][nvtxs / 2]];
90
91 dist[0] = -xmid - ymid;
92 dist[1] = xmid - ymid;
93 dist[2] = -xmid + ymid;
94 dist[3] = xmid + ymid;
95
96 /* Now initialize startvtx. */
97 startvtx[0][1] = startvtx[2][3] = nvtxs / 2;
98 startvtx[0][2] = startvtx[1][3] = nvtxs / 2;
99 startvtx[1][2] = findindex(indices[1][2], vals[1][2], dist[2] - dist[1], nvtxs);
100 startvtx[0][3] = findindex(indices[0][3], vals[0][3], dist[3] - dist[0], nvtxs);
101
102 for (i = 0; i < nsets; i++) {
103 size[i] = 0;
104 }
105
106 for (i = 1; i <= nvtxs; i++) {
107 /* Which set is this vertex in? */
108 signx = signy = -1;
109 bestval = 0;
110 for (j = 0; j < nsets; j++) {
111 val = -dist[j] + 2 * (signx * xvecs[1][i] + signy * xvecs[2][i]);
112 if (j == 0 || val < bestval) {
113 bestval = val;
114 bestset = j;
115 }
116 if (signx == 1) {
117 signy *= -1;
118 }
119 signx *= -1;
120 }
121 sets[i] = bestset;
122 size[bestset] += graph[i]->vwgt;
123 }
124 }