Debian Codegraph @

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

raw
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 "defs.h"
10 #include "params.h"
11 #include "structs.h"
12 #include <math.h>
13 #include <stdio.h>
14
15 /* Confirm that the bipartite match algorithm did the right thing. */
16 void checkbp(struct vtx_data **graph, /* graph data structure for vertex weights */
17 double **xvecs, /* values to partition */
18 int *sets, /* set assignments returned */
19 double *dists, /* distances that separate sets */
20 int nvtxs, /* number of vertices */
21 int ndims /* number of dimensions for division */
22 )
23 {
24 int signs[MAXDIMS]; /* signs for coordinates of target points */
25 int sizes[MAXSETS]; /* size of each set */
26 int weights[MAXSETS]; /* size of each set */
27 double setval = 0.0; /* value from assigned set */
28 double val, bestval = 0.0; /* value to decide set assignment */
29 double tol = 1.0e-8; /* numerical tolerance */
30 int error = FALSE; /* are errors encountered? */
31 int nsets; /* number of sets */
32 int bestset = -1; /* set vtx should be assigned to */
33 int i, j, k; /* loop counter */
34
35 nsets = 1 << ndims;
36
37 for (i = 0; i < nsets; i++) {
38 sizes[i] = 0;
39 weights[i] = 0;
40 }
41
42 for (i = 1; i <= nvtxs; i++) {
43 /* Is vertex closest to the set it is assigned to? */
44 for (j = 0; j < MAXDIMS; j++) {
45 signs[j] = -1;
46 }
47 bestval = 0;
48 for (j = 0; j < nsets; j++) {
49 val = -dists[j];
50 for (k = 1; k <= ndims; k++) {
51 val += 2 * signs[k - 1] * xvecs[k][i];
52 }
53 if (j == sets[i]) {
54 setval = val;
55 }
56 if (j == 0 || val < bestval) {
57 bestval = val;
58 bestset = j;
59 }
60 if (signs[0] == 1 && signs[1] == 1) {
61 signs[2] *= -1;
62 }
63 if (signs[0] == 1) {
64 signs[1] *= -1;
65 }
66 signs[0] *= -1;
67 }
68 if (fabs(setval - bestval) >= tol * (fabs(setval) + fabs(bestval))) {
69 printf(" Vtx %d in set %d (%e), but should be in %d (%e)\n", i, sets[i], setval, bestset,
70 bestval);
71 error = TRUE;
72 }
73 ++sizes[sets[i]];
74 weights[sets[i]] += graph[i]->vwgt;
75 }
76
77 printf(" Sizes:");
78 for (i = 0; i < nsets; i++) {
79 printf(" %d(%d)", sizes[i], weights[i]);
80 }
81 printf("\n");
82
83 if (error) {
84 checkpnt("ERROR in checkbp");
85 }
86 }