| 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 |
/* Free the space used in the bpmatch routines. */ |
| 15 |
static void free2d(double *vals[4][MAXSETS], int *indices[4][MAXSETS]) |
| 16 |
{ |
| 17 |
sfree(vals[0][1]); |
| 18 |
sfree(vals[0][2]); |
| 19 |
sfree(vals[0][3]); |
| 20 |
sfree(vals[1][2]); |
| 21 |
|
| 22 |
sfree(indices[0][1]); |
| 23 |
sfree(indices[0][2]); |
| 24 |
sfree(indices[0][3]); |
| 25 |
sfree(indices[1][2]); |
| 26 |
} |
| 27 |
|
| 28 |
void map2d(struct vtx_data **graph, /* data structure with vertex weights */ |
| 29 |
double **xvecs, /* vectors to partition */ |
| 30 |
int nvtxs, /* number of vertices */ |
| 31 |
int *sets, /* set each vertex gets assigned to */ |
| 32 |
double *goal, /* desired set sizes */ |
| 33 |
int vwgt_max /* largest vertex weight */ |
| 34 |
) |
| 35 |
{ |
| 36 |
extern int DEBUG_BPMATCH; /* turn on debugging for bipartite matching */ |
| 37 |
extern int N_VTX_MOVES; /* total number of vertex moves */ |
| 38 |
extern int N_VTX_CHECKS; /* total number of moves contemplated */ |
| 39 |
double *vals[4][MAXSETS]; /* values in sorted lists */ |
| 40 |
double dist[4]; /* trial separation point */ |
| 41 |
double size[4]; /* sizes of each set being modified */ |
| 42 |
int *indices[4][MAXSETS]; /* indices sorting lists */ |
| 43 |
int startvtx[4][MAXSETS]; /* indices defining separation */ |
| 44 |
int nsection = 2; /* number of xvectors */ |
| 45 |
int nsets = 4; /* number of sets being divided into */ |
| 46 |
|
| 47 |
N_VTX_CHECKS = N_VTX_MOVES = 0; |
| 48 |
|
| 49 |
/* Generate all the lists of values that need to be sorted. */ |
| 50 |
genvals2d(xvecs, vals, nvtxs); |
| 51 |
|
| 52 |
/* Sort the lists of values. */ |
| 53 |
sorts2d(vals, indices, nvtxs); |
| 54 |
|
| 55 |
/* Now initialize dists and assign to sets. */ |
| 56 |
inits2d(graph, xvecs, vals, indices, nvtxs, dist, startvtx, size, sets); |
| 57 |
|
| 58 |
/* Determine the largest and smallest allowed set sizes. */ |
| 59 |
/* (For now, assume all sets must be same size, but can easily change.) */ |
| 60 |
|
| 61 |
if (DEBUG_BPMATCH > 1) { |
| 62 |
printf(" Calling check before movevtxs\n"); |
| 63 |
checkbp(graph, xvecs, sets, dist, nvtxs, nsection); |
| 64 |
} |
| 65 |
|
| 66 |
movevtxs(graph, nvtxs, nsets, dist, indices, vals, startvtx, sets, size, goal, vwgt_max); |
| 67 |
|
| 68 |
if (DEBUG_BPMATCH > 0) { |
| 69 |
printf(" N_VTX_CHECKS = %d, N_VTX_MOVES = %d\n", N_VTX_CHECKS, N_VTX_MOVES); |
| 70 |
checkbp(graph, xvecs, sets, dist, nvtxs, nsection); |
| 71 |
} |
| 72 |
|
| 73 |
free2d(vals, indices); |
| 74 |
} |