Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
separator.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * separator.c
5  *
6  * This file contains code for separator extraction
7  *
8  * Started 8/1/97
9  * George
10  *
11  * $Id: separator.c,v 1.1 1998/11/27 17:59:30 karypis Exp $
12  *
13  */
14 
15 #include <metis.h>
16 
17 /*************************************************************************
18 * This function takes a bisection and constructs a minimum weight vertex
19 * separator out of it. It uses the node-based separator refinement for it.
20 **************************************************************************/
21 void ConstructSeparator(CtrlType *ctrl, GraphType *graph, float ubfactor)
22 {
23  int i, j, k, nvtxs, nbnd;
24  idxtype *xadj, *where, *bndind;
25 
26  nvtxs = graph->nvtxs;
27  xadj = graph->xadj;
28  nbnd = graph->nbnd;
29  bndind = graph->bndind;
30 
31  where = idxcopy(nvtxs, graph->where, idxwspacemalloc(ctrl, nvtxs));
32 
33  /* Put the nodes in the boundary into the separator */
34  for (i=0; i<nbnd; i++) {
35  j = bndind[i];
36  if (xadj[j+1]-xadj[j] > 0) /* Ignore islands */
37  where[j] = 2;
38  }
39 
40  GKfree(&graph->rdata, LTERM);
42  idxcopy(nvtxs, where, graph->where);
43  idxwspacefree(ctrl, nvtxs);
44 
45  ASSERT(IsSeparable(graph));
46 
47  Compute2WayNodePartitionParams(ctrl, graph);
48 
50 
51  FM_2WayNodeRefine(ctrl, graph, ubfactor, 8);
52 
53  ASSERT(IsSeparable(graph));
54 }
55 
56 
57 
58 /*************************************************************************
59 * This function takes a bisection and constructs a minimum weight vertex
60 * separator out of it. It uses an unweighted minimum-cover algorithm
61 * followed by node-based separator refinement.
62 **************************************************************************/
63 void ConstructMinCoverSeparator0(CtrlType *ctrl, GraphType *graph, float ubfactor)
64 {
65  int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
66  idxtype *xadj, *adjncy, *bxadj, *badjncy;
67  idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
68 
69 
70  nvtxs = graph->nvtxs;
71  xadj = graph->xadj;
72  adjncy = graph->adjncy;
73 
74  nbnd = graph->nbnd;
75  bndind = graph->bndind;
76  bndptr = graph->bndptr;
77  where = graph->where;
78 
79  vmap = idxwspacemalloc(ctrl, nvtxs);
80  ivmap = idxwspacemalloc(ctrl, nbnd);
81  cover = idxwspacemalloc(ctrl, nbnd);
82 
83  if (nbnd > 0) {
84  /* Go through the boundary and determine the sizes of the bipartite graph */
85  bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
86  for (i=0; i<nbnd; i++) {
87  j = bndind[i];
88  k = where[j];
89  if (xadj[j+1]-xadj[j] > 0) {
90  bnvtxs[k]++;
91  bnedges[k] += xadj[j+1]-xadj[j];
92  }
93  }
94 
95  bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
96  bnvtxs[1] = bnvtxs[0];
97  bnvtxs[0] = 0;
98 
99  bxadj = idxmalloc(bnvtxs[2]+1, "ConstructMinCoverSeparator: bxadj");
100  badjncy = idxmalloc(bnedges[0]+bnedges[1]+1, "ConstructMinCoverSeparator: badjncy");
101 
102  /* Construct the ivmap and vmap */
103  ASSERT(idxset(nvtxs, -1, vmap) == vmap);
104  for (i=0; i<nbnd; i++) {
105  j = bndind[i];
106  k = where[j];
107  if (xadj[j+1]-xadj[j] > 0) {
108  vmap[j] = bnvtxs[k];
109  ivmap[bnvtxs[k]++] = j;
110  }
111  }
112 
113  /* OK, go through and put the vertices of each part starting from 0 */
114  bnvtxs[1] = bnvtxs[0];
115  bnvtxs[0] = 0;
116  bxadj[0] = l = 0;
117  for (k=0; k<2; k++) {
118  for (ii=0; ii<nbnd; ii++) {
119  i = bndind[ii];
120  if (where[i] == k && xadj[i] < xadj[i+1]) {
121  for (j=xadj[i]; j<xadj[i+1]; j++) {
122  jj = adjncy[j];
123  if (where[jj] != k) {
124  ASSERT(bndptr[jj] != -1);
125  ASSERTP(vmap[jj] != -1, ("%d %d %d\n", jj, vmap[jj], graph->bndptr[jj]));
126  badjncy[l++] = vmap[jj];
127  }
128  }
129  bxadj[++bnvtxs[k]] = l;
130  }
131  }
132  }
133 
134  ASSERT(l <= bnedges[0]+bnedges[1]);
135 
136  MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
137 
138  IFSET(ctrl->dbglvl, DBG_SEPINFO,
139  printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
140 
141  for (i=0; i<csize; i++) {
142  j = ivmap[cover[i]];
143  where[j] = 2;
144  }
145 
146  GKfree(&bxadj, &badjncy, LTERM);
147 
148  for (i=0; i<nbnd; i++)
149  bndptr[bndind[i]] = -1;
150  for (nbnd=i=0; i<nvtxs; i++) {
151  if (where[i] == 2) {
152  bndind[nbnd] = i;
153  bndptr[i] = nbnd++;
154  }
155  }
156  }
157  else {
158  IFSET(ctrl->dbglvl, DBG_SEPINFO,
159  printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, 0, 0, 0));
160  }
161 
162  idxwspacefree(ctrl, nvtxs);
163  idxwspacefree(ctrl, graph->nbnd);
164  idxwspacefree(ctrl, graph->nbnd);
165  graph->nbnd = nbnd;
166 
167 
168  ASSERT(IsSeparable(graph));
169 }
170 
171 
172 
173 /*************************************************************************
174 * This function takes a bisection and constructs a minimum weight vertex
175 * separator out of it. It uses an unweighted minimum-cover algorithm
176 * followed by node-based separator refinement.
177 **************************************************************************/
178 void ConstructMinCoverSeparator(CtrlType *ctrl, GraphType *graph, float ubfactor)
179 {
180  int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
181  idxtype *xadj, *adjncy, *bxadj, *badjncy;
182  idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
183 
184 
185  nvtxs = graph->nvtxs;
186  xadj = graph->xadj;
187  adjncy = graph->adjncy;
188 
189  nbnd = graph->nbnd;
190  bndind = graph->bndind;
191  bndptr = graph->bndptr;
192  where = graph->where;
193 
194  vmap = idxwspacemalloc(ctrl, nvtxs);
195  ivmap = idxwspacemalloc(ctrl, nbnd);
196  cover = idxwspacemalloc(ctrl, nbnd);
197 
198  if (nbnd > 0) {
199  /* Go through the boundary and determine the sizes of the bipartite graph */
200  bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
201  for (i=0; i<nbnd; i++) {
202  j = bndind[i];
203  k = where[j];
204  if (xadj[j+1]-xadj[j] > 0) {
205  bnvtxs[k]++;
206  bnedges[k] += xadj[j+1]-xadj[j];
207  }
208  }
209 
210  bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
211  bnvtxs[1] = bnvtxs[0];
212  bnvtxs[0] = 0;
213 
214  bxadj = idxmalloc(bnvtxs[2]+1, "ConstructMinCoverSeparator: bxadj");
215  badjncy = idxmalloc(bnedges[0]+bnedges[1]+1, "ConstructMinCoverSeparator: badjncy");
216 
217  /* Construct the ivmap and vmap */
218  ASSERT(idxset(nvtxs, -1, vmap) == vmap);
219  for (i=0; i<nbnd; i++) {
220  j = bndind[i];
221  k = where[j];
222  if (xadj[j+1]-xadj[j] > 0) {
223  vmap[j] = bnvtxs[k];
224  ivmap[bnvtxs[k]++] = j;
225  }
226  }
227 
228  /* OK, go through and put the vertices of each part starting from 0 */
229  bnvtxs[1] = bnvtxs[0];
230  bnvtxs[0] = 0;
231  bxadj[0] = l = 0;
232  for (k=0; k<2; k++) {
233  for (ii=0; ii<nbnd; ii++) {
234  i = bndind[ii];
235  if (where[i] == k && xadj[i] < xadj[i+1]) {
236  for (j=xadj[i]; j<xadj[i+1]; j++) {
237  jj = adjncy[j];
238  if (where[jj] != k) {
239  ASSERT(bndptr[jj] != -1);
240  ASSERTP(vmap[jj] != -1, ("%d %d %d\n", jj, vmap[jj], graph->bndptr[jj]));
241  badjncy[l++] = vmap[jj];
242  }
243  }
244  bxadj[++bnvtxs[k]] = l;
245  }
246  }
247  }
248 
249  ASSERT(l <= bnedges[0]+bnedges[1]);
250 
251  MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
252 
253  IFSET(ctrl->dbglvl, DBG_SEPINFO,
254  printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
255 
256  for (i=0; i<csize; i++) {
257  j = ivmap[cover[i]];
258  where[j] = 2;
259  }
260 
261  GKfree(&bxadj, &badjncy, LTERM);
262  }
263  else {
264  IFSET(ctrl->dbglvl, DBG_SEPINFO,
265  printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, 0, 0, 0));
266  }
267 
268  /* Prepare to refine the vertex separator */
269  idxcopy(nvtxs, graph->where, vmap);
270  GKfree(&graph->rdata, LTERM);
271 
272  Allocate2WayNodePartitionMemory(ctrl, graph);
273  idxcopy(nvtxs, vmap, graph->where);
274  idxwspacefree(ctrl, nvtxs+2*graph->nbnd);
275 
276  Compute2WayNodePartitionParams(ctrl, graph);
277 
279 
280  FM_2WayNodeRefine_OneSided(ctrl, graph, ubfactor, 6);
281 
282  ASSERT(IsSeparable(graph));
283 }
284 
#define idxwspacefree
Definition: rename.h:165
#define Compute2WayNodePartitionParams
Definition: rename.h:351
#define ConstructMinCoverSeparator
Definition: rename.h:337
idxtype * pwgts
Definition: struct.h:176
int nbnd
Definition: struct.h:177
#define DBG_SEPINFO
Definition: defs.h:161
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
#define CheckNodePartitionParams
Definition: rename.h:48
#define idxwspacemalloc
Definition: rename.h:164
HitTile_Vector graph
#define Allocate2WayNodePartitionMemory
Definition: rename.h:350
idxtype * where
Definition: struct.h:176
#define LTERM
Definition: defs.h:18
int idxtype
Definition: struct.h:19
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define ConstructSeparator
Definition: rename.h:335
#define IsSeparable
Definition: rename.h:49
#define idxset
Definition: rename.h:390
#define idxcopy(n, a, b)
Definition: macros.h:44
void GKfree(void **ptr1,...)
Definition: util.c:121
#define ASSERTP(expr, msg)
Definition: macros.h:142
idxtype * bndind
Definition: struct.h:178
#define FM_2WayNodeRefine_OneSided
Definition: rename.h:343
#define MinCover
Definition: rename.h:196
#define FM_2WayNodeRefine
Definition: rename.h:341
#define ConstructMinCoverSeparator0
Definition: rename.h:336
#define idxmalloc
Definition: rename.h:383
int nvtxs
Definition: struct.h:161
#define ASSERT(expr)
Definition: macros.h:130
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162