Debian Codegraph @

packages/seacas/libraries/chaco/bpmatch/map2d.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 "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 }