|
1.2.4
by Christophe Prud'homme
Import upstream version 2.2.5.dfsg |
1 |
/* This software was developed by Bruce Hendrickson and Robert Leland *
|
2 |
* at Sandia National Laboratories under US Department of Energy *
|
|
3 |
* contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
|
|
4 |
||
5 |
#include <stdio.h> |
|
6 |
#include "Gmsh_printf.h" |
|
7 |
#include "defs.h" |
|
8 |
#include "params.h" |
|
9 |
#include "structs.h" |
|
10 |
||
11 |
||
12 |
static void free2d(); |
|
13 |
||
14 |
void map2d(graph, xvecs, nvtxs, sets, goal, vwgt_max) |
|
15 |
struct vtx_data **graph; /* data structure with vertex weights */ |
|
16 |
double **xvecs; /* vectors to partition */ |
|
17 |
int nvtxs; /* number of vertices */ |
|
18 |
short *sets; /* set each vertex gets assigned to */ |
|
19 |
double *goal; /* desired set sizes */ |
|
20 |
int vwgt_max; /* largest vertex weight */ |
|
21 |
{
|
|
22 |
extern int DEBUG_BPMATCH; /* turn on debuging for bipartite matching */ |
|
23 |
extern int N_VTX_MOVES; /* total number of vertex moves */ |
|
24 |
extern int N_VTX_CHECKS; /* total number of moves contemplated */ |
|
25 |
double *vals[4][MAXSETS]; /* values in sorted lists */ |
|
26 |
double dist[4]; /* trial separation point */ |
|
27 |
double size[4]; /* sizes of each set being modified */ |
|
28 |
int *indices[4][MAXSETS]; /* indices sorting lists */ |
|
29 |
int startvtx[4][MAXSETS]; /* indices defining separation */ |
|
30 |
int nsection = 2; /* number of xvectors */ |
|
31 |
int nsets = 4; /* number of sets being divided into */ |
|
32 |
void genvals2d(), sorts2d(), inits2d(), checkbp(), movevtxs(); |
|
33 |
||
34 |
N_VTX_CHECKS = N_VTX_MOVES = 0; |
|
35 |
||
36 |
/* Generate all the lists of values that need to be sorted. */
|
|
37 |
genvals2d(xvecs, vals, nvtxs); |
|
38 |
||
39 |
/* Sort the lists of values. */
|
|
40 |
sorts2d(vals, indices, nvtxs); |
|
41 |
||
42 |
/* Now initialize dists and assign to sets. */
|
|
43 |
inits2d(graph, xvecs, vals, indices, nvtxs, dist, startvtx, size, sets); |
|
44 |
||
45 |
/* Determine the largest and smallest allowed set sizes. */
|
|
46 |
/* (For now, assume all sets must be same size, but can easily change.) */
|
|
47 |
||
48 |
if (DEBUG_BPMATCH > 1) { |
|
49 |
printf(" Calling check before movevtxs\n"); |
|
50 |
checkbp(graph, xvecs, sets, dist, nvtxs, nsection); |
|
51 |
}
|
|
52 |
||
53 |
movevtxs(graph, nvtxs, nsets, dist, indices, vals, startvtx, sets, size, |
|
54 |
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 |
free2d(vals, indices); |
|
62 |
}
|
|
63 |
||
64 |
||
65 |
/* Free the space used in the bpmatch routines. */
|
|
66 |
static void free2d(vals, indices) |
|
67 |
double *vals[4][MAXSETS]; |
|
68 |
int *indices[4][MAXSETS]; |
|
69 |
{
|
|
70 |
int sfree(); |
|
71 |
||
72 |
sfree((char *) vals[0][1]); |
|
73 |
sfree((char *) vals[0][2]); |
|
74 |
sfree((char *) vals[0][3]); |
|
75 |
sfree((char *) vals[1][2]); |
|
76 |
||
77 |
sfree((char *) indices[0][1]); |
|
78 |
sfree((char *) indices[0][2]); |
|
79 |
sfree((char *) indices[0][3]); |
|
80 |
sfree((char *) indices[1][2]); |
|
81 |
}
|