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
11 /* Perform KL between two sets. */
kl_refine(graph,subgraph,set_list,vtx_elems,new_assign,set1,set2,glob2loc,loc2glob,sub_assign,old_sub_assign,degrees,using_ewgts,hops,goal,sizes,term_wgts,architecture,mesh_dims)12 int kl_refine(graph, subgraph, set_list, vtx_elems, new_assign,
13 set1, set2, glob2loc, loc2glob, sub_assign, old_sub_assign,
14 degrees, using_ewgts, hops, goal, sizes, term_wgts, architecture,
15 mesh_dims)
16 struct vtx_data **graph; /* graph data structure */
17 struct vtx_data **subgraph; /* space for subgraph to refine */
18 struct bilist *set_list; /* lists of vtxs in each set */
19 struct bilist *vtx_elems; /* start of storage for lists */
20 short *new_assign; /* set assignments for all vertices */
21 int set1, set2; /* two sets being refined */
22 int *glob2loc; /* maps vertices to subgraph vertices */
23 int *loc2glob; /* maps subgraph vertices to vertices */
24 short *sub_assign; /* new assignment for subgraphs */
25 short *old_sub_assign; /* current assignment for subgraphs */
26 short *degrees; /* space for forming subgraphs */
27 int using_ewgts; /* are edge weights being used? */
28 short (*hops)[MAXSETS]; /* KL set preferences */
29 double *goal; /* desired set sizes */
30 int *sizes; /* number of vertices in different sets */
31 float *term_wgts[]; /* space for terminal propagation weights */
32 int architecture; /* 0 => hypercube, d => d-dimensional mesh */
33 int mesh_dims[3]; /* if mesh, how big is it? */
34 {
35 extern int TERM_PROP; /* perform terminal propagation? */
36 extern double KL_IMBALANCE; /* fractional imbalance allowed in KL */
37 struct bilist *ptr; /* element in set_list */
38 double subgoal[2]; /* goal within two subgraphs */
39 double weights[2]; /* weights for each set */
40 double maxdeg; /* largest degree of a vertex */
41 double ratio; /* set sizes / goals */
42 int *null_ptr; /* argument to klspiff */
43 int vwgt_max; /* largest vertex weight */
44 int max_dev; /* largest set deviation allowed in KL */
45 int subnvtxs; /* number of vtxs in subgraph */
46 int vwgt_sum1; /* sum of vertex wgts in first set */
47 int vwgt_sum2; /* sum of vertex wgts in second set */
48 int subnedges; /* number of edges in subgraph */
49 int setA, setB; /* two sets being refined */
50 int nsame; /* number of vertices not moved */
51 int vtx; /* vertex in subgraph */
52 int i; /* loop counter */
53 double find_maxdeg();
54 void make_maps_ref(), make_subgraph(), remake_graph();
55 void klspiff(), make_terms_ref(), count_weights();
56
57 /* Compute all the quantities I'll need. */
58 null_ptr = NULL;
59 make_maps_ref(graph, set_list, vtx_elems, new_assign, sub_assign,
60 set1, set2, glob2loc, loc2glob, &subnvtxs, &vwgt_max,
61 &vwgt_sum1, &vwgt_sum2);
62
63 for (i = 1; i <= subnvtxs; i++)
64 old_sub_assign[i] = sub_assign[i];
65
66 /* Set up goals for this KL invocation. */
67 ratio = (vwgt_sum1 + vwgt_sum2) / (goal[set1] + goal[set2]);
68 subgoal[0] = ratio * goal[set1];
69 subgoal[1] = ratio * goal[set2];
70
71 if (TERM_PROP) {
72 make_terms_ref(graph, using_ewgts, subnvtxs, loc2glob,
73 set1, set2, new_assign, architecture, mesh_dims, term_wgts);
74 }
75
76 /* New_assign has overwritten set2 with set1. */
77 make_subgraph(graph, subgraph, subnvtxs, &subnedges, new_assign, set1,
78 glob2loc, loc2glob, degrees, using_ewgts);
79
80 maxdeg = find_maxdeg(subgraph, subnvtxs, using_ewgts, (float *) NULL);
81
82 count_weights(subgraph, subnvtxs, sub_assign, 2, weights, (vwgt_max != 1));
83
84 max_dev = vwgt_max;
85 ratio = (subgoal[0] + subgoal[1]) * KL_IMBALANCE / 2;
86 if (ratio > max_dev) {
87 max_dev = ratio;
88 }
89
90 klspiff(subgraph, subnvtxs, sub_assign, 2, hops, subgoal,
91 term_wgts, max_dev, maxdeg, using_ewgts, &null_ptr, weights);
92
93 /* Figure out which modification leaves most vertices intact. */
94 nsame = 0;
95 for (i = 1; i <= subnvtxs; i++) {
96 if (old_sub_assign[i] == sub_assign[i])
97 nsame++;
98 }
99 if (2 * nsame > subnvtxs) {
100 setA = set1;
101 setB = set2;
102 }
103 else {
104 setA = set2;
105 setB = set1;
106 }
107
108 /* Now update the assignments. */
109 sizes[setA] = sizes[setB] = 0;
110 for (i = 1; i <= subnvtxs; i++) {
111 vtx = loc2glob[i];
112 /* Update the set_lists. */
113 ptr = &(vtx_elems[vtx]);
114 if (ptr->next != NULL) {
115 ptr->next->prev = ptr->prev;
116 }
117 if (ptr->prev != NULL) {
118 ptr->prev->next = ptr->next;
119 }
120
121 if (sub_assign[i] == 0) {
122 new_assign[vtx] = (short) setA;
123 ++sizes[setA];
124 ptr->next = set_list[setA].next;
125 if (ptr->next != NULL)
126 ptr->next->prev = ptr;
127 ptr->prev = &(set_list[setA]);
128 set_list[setA].next = ptr;
129 }
130 else {
131 new_assign[vtx] = (short) setB;
132 ++sizes[setB];
133 ptr->next = set_list[setB].next;
134 if (ptr->next != NULL)
135 ptr->next->prev = ptr;
136 ptr->prev = &(set_list[setB]);
137 set_list[setB].next = ptr;
138 }
139 }
140
141 remake_graph(subgraph, subnvtxs, loc2glob, degrees, using_ewgts);
142
143 return(nsame != subnvtxs);
144 }
145