| 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 "smalloc.h" // for sfree |
| 11 |
#include "structs.h" |
| 12 |
#include <stdio.h> // for printf |
| 13 |
|
| 14 |
static void free3d(double *vals[8][MAXSETS], int *indices[8][MAXSETS]); |
| 15 |
|
| 16 |
void map3d(struct vtx_data **graph, /* graph data structure */ |
| 17 |
double **xvecs, /* vectors to partition */ |
| 18 |
int nvtxs, /* number of vertices */ |
| 19 |
int *sets, /* set each vertex gets assigned to */ |
| 20 |
double *goal, /* desired set sizes */ |
| 21 |
int vwgt_max /* largest vertex weight */ |
| 22 |
) |
| 23 |
{ |
| 24 |
extern int DEBUG_BPMATCH; /* debug flag for bipartite matching */ |
| 25 |
extern int N_VTX_MOVES; /* number of vertices moved between sets */ |
| 26 |
extern int N_VTX_CHECKS; /* number of vertex moves considered */ |
| 27 |
double *vals[8][MAXSETS]; /* values in sorted lists */ |
| 28 |
double dist[8]; /* trial separation point */ |
| 29 |
double size[8]; /* sizes of each set being modified */ |
| 30 |
int *indices[8][MAXSETS]; /* indices sorting lists */ |
| 31 |
int startvtx[8][MAXSETS]; /* indices defining separation */ |
| 32 |
int nsection = 3; /* number of xvectors */ |
| 33 |
int nsets = 8; /* number of sets being divided into */ |
| 34 |
|
| 35 |
N_VTX_CHECKS = N_VTX_MOVES = 0; |
| 36 |
|
| 37 |
/* Generate all the lists of values that need to be sorted. */ |
| 38 |
genvals3d(xvecs, vals, nvtxs); |
| 39 |
|
| 40 |
/* Sort the lists of values. */ |
| 41 |
sorts3d(vals, indices, nvtxs); |
| 42 |
|
| 43 |
/* Now initialize distances using median values, and assign to sets. */ |
| 44 |
inits3d(graph, xvecs, vals, indices, nvtxs, dist, startvtx, size, sets); |
| 45 |
|
| 46 |
/* Determine largest and smallest allowed sizes for each set. */ |
| 47 |
/* (For now all are the same, but easily changed.) */ |
| 48 |
|
| 49 |
if (DEBUG_BPMATCH > 1) { |
| 50 |
printf(" Calling check before movevtxs\n"); |
| 51 |
checkbp(graph, xvecs, sets, dist, nvtxs, nsection); |
| 52 |
} |
| 53 |
|
| 54 |
movevtxs(graph, nvtxs, nsets, dist, indices, vals, startvtx, sets, size, goal, vwgt_max); |
| 55 |
|
| 56 |
if (DEBUG_BPMATCH > 0) { |
| 57 |
printf(" N_VTX_CHECKS = %d, N_VTX_MOVES = %d\n", N_VTX_CHECKS, N_VTX_MOVES); |
| 58 |
checkbp(graph, xvecs, sets, dist, nvtxs, nsection); |
| 59 |
} |
| 60 |
|
| 61 |
free3d(vals, indices); |
| 62 |
} |
| 63 |
|
| 64 |
static void free3d(double *vals[8][MAXSETS], int *indices[8][MAXSETS]) |
| 65 |
{ |
| 66 |
|
| 67 |
sfree(vals[0][1]); |
| 68 |
sfree(vals[0][2]); |
| 69 |
sfree(vals[0][4]); |
| 70 |
sfree(vals[0][3]); |
| 71 |
sfree(vals[1][2]); |
| 72 |
sfree(vals[0][5]); |
| 73 |
sfree(vals[1][4]); |
| 74 |
sfree(vals[0][6]); |
| 75 |
sfree(vals[2][4]); |
| 76 |
sfree(vals[0][7]); |
| 77 |
sfree(vals[1][6]); |
| 78 |
sfree(vals[2][5]); |
| 79 |
sfree(vals[3][4]); |
| 80 |
|
| 81 |
sfree(indices[0][1]); |
| 82 |
sfree(indices[0][2]); |
| 83 |
sfree(indices[0][4]); |
| 84 |
sfree(indices[0][3]); |
| 85 |
sfree(indices[1][2]); |
| 86 |
sfree(indices[0][5]); |
| 87 |
sfree(indices[1][4]); |
| 88 |
sfree(indices[0][6]); |
| 89 |
sfree(indices[2][4]); |
| 90 |
sfree(indices[0][7]); |
| 91 |
sfree(indices[1][6]); |
| 92 |
sfree(indices[2][5]); |
| 93 |
sfree(indices[3][4]); |
| 94 |
} |