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 "structs.h"
7 #include "params.h"
8 #include "defs.h"
9
10 /* Improve (weighted) vertex separator. Two sets are 0/1; separator = 2. */
11
12 int VERTEX_SEPARATOR = FALSE;
13
14 static void free_klv();
15
klvspiff(graph,nvtxs,sets,goal,max_dev,bndy_list,weights)16 void klvspiff(graph, nvtxs, sets, goal, max_dev,
17 bndy_list, weights)
18 struct vtx_data **graph; /* list of graph info for each vertex */
19 int nvtxs; /* number of vertices in graph */
20 short *sets; /* local partitioning of vtxs */
21 double *goal; /* desired set sizes */
22 int max_dev; /* largest deviation from balance allowed */
23 int **bndy_list; /* list of vertices on boundary (0 ends) */
24 double *weights; /* vertex weights in each set */
25 {
26 extern FILE *Output_File; /* output file or null */
27 extern int DEBUG_TRACE; /* debug flag for Kernighan-Lin */
28 extern int DEBUG_KL; /* debug flag for Kernighan-Lin */
29 extern double kl_total_time;
30 extern double kl_init_time;
31 extern double nway_kl_time;
32 struct bilist **lbuckets; /* space for bucket sorts for left moves */
33 struct bilist **rbuckets; /* space for bucket sorts for right moves */
34 struct bilist *llistspace; /* space for all left bidirectional elements */
35 struct bilist *rlistspace; /* space for all right bidirectional elements */
36 int *ldvals; /* change in penalty for each possible move */
37 int *rdvals; /* change in penalty for each possible move */
38 int *edges; /* loops through neighbor lists */
39 double time, time1; /* timing variables */
40 int dval; /* largest transition cost for a vertex */
41 int maxdval; /* largest transition cost for all vertices */
42 int error; /* out of space? */
43 int i, j; /* loop counters */
44 double seconds();
45 int klv_init(), nway_klv();
46 void countup_vtx_sep();
47
48 time = seconds();
49
50 if (DEBUG_TRACE > 0) {
51 printf("<Entering klvspiff, nvtxs = %d>\n", nvtxs);
52 }
53
54 /* Find largest possible change. */
55 maxdval = 0;
56 for (i = 1; i <= nvtxs; i++) {
57 if (graph[i]->vwgt > maxdval) maxdval = graph[i]->vwgt;
58 dval = -graph[i]->vwgt;
59 edges = graph[i]->edges;
60 for (j = graph[i]->nedges - 1; j; j--) {
61 dval += graph[*(++edges)]->vwgt;
62 }
63 if (dval > maxdval) maxdval = dval;
64 }
65
66 /* Allocate a bunch of space for KLV. */
67 time1 = seconds();
68 error = klv_init(&lbuckets, &rbuckets, &llistspace, &rlistspace,
69 &ldvals, &rdvals, nvtxs, maxdval);
70 kl_init_time += seconds() - time1;
71
72 if (!error) {
73 if (DEBUG_KL > 0) {
74 printf(" Before KLV: ");
75 countup_vtx_sep(graph, nvtxs, sets);
76 }
77
78 time1 = seconds();
79 error = nway_klv(graph, nvtxs, lbuckets, rbuckets, llistspace,
80 rlistspace, ldvals, rdvals, sets,
81 maxdval, goal, max_dev, bndy_list, weights);
82 nway_kl_time += seconds() - time1;
83
84 if (DEBUG_KL > 1) {
85 printf(" After KLV: ");
86 countup_vtx_sep(graph, nvtxs, sets);
87 }
88 }
89
90 if (error) {
91 printf("\nWARNING: No space to perform KLV on graph with %d vertices.\n",
92 nvtxs);
93 printf(" NO LOCAL REFINEMENT PERFORMED.\n\n");
94
95 if (Output_File != NULL) {
96 fprintf(Output_File,
97 "\nWARNING: No space to perform KLV on graph with %d vertices.\n",
98 nvtxs);
99 fprintf(Output_File, " LOCAL REFINEMENT NOT PERFORMED.\n\n");
100 }
101 }
102
103 free_klv(lbuckets, rbuckets, llistspace, rlistspace, ldvals, rdvals);
104
105 kl_total_time += seconds() - time;
106 }
107
108
free_klv(lbuckets,rbuckets,llistspace,rlistspace,ldvals,rdvals)109 static void free_klv(lbuckets, rbuckets, llistspace, rlistspace, ldvals, rdvals)
110 /* Free everything malloc'd for KLV. */
111 struct bilist **lbuckets; /* space for bucket sorts */
112 struct bilist **rbuckets; /* space for bucket sorts */
113 struct bilist *llistspace; /* space for all bidirectional elements */
114 struct bilist *rlistspace; /* space for all bidirectional elements */
115 int *ldvals; /* change in penalty for each possible move */
116 int *rdvals; /* change in penalty for each possible move */
117 {
118 int sfree();
119
120 sfree((char *) rlistspace);
121 sfree((char *) llistspace);
122 sfree((char *) rdvals);
123 sfree((char *) ldvals);
124 sfree((char *) rbuckets);
125 sfree((char *) lbuckets);
126 }
127