| 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 |
} |