Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
pmetis.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * pmetis.c
5  *
6  * This file contains the top level routines for the multilevel recursive
7  * bisection algorithm PMETIS.
8  *
9  * Started 7/24/97
10  * George
11  *
12  * $Id: pmetis.c,v 1.1 1998/11/27 17:59:28 karypis Exp $
13  *
14  */
15 
16 #include <metis.h>
17 
18 
19 /*************************************************************************
20 * This function is the entry point for PMETIS
21 **************************************************************************/
22 void METIS_PartGraphRecursive(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
23  idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,
24  int *options, int *edgecut, idxtype *part)
25 {
26  int i;
27  float *tpwgts;
28 
29  tpwgts = fmalloc(*nparts, "KMETIS: tpwgts");
30  for (i=0; i<*nparts; i++)
31  tpwgts[i] = 1.0/(1.0*(*nparts));
32 
33  METIS_WPartGraphRecursive(nvtxs, xadj, adjncy, vwgt, adjwgt, wgtflag, numflag, nparts,
34  tpwgts, options, edgecut, part);
35 
36  free(tpwgts);
37 }
38 
39 
40 
41 /*************************************************************************
42 * This function is the entry point for PWMETIS that accepts exact weights
43 * for the target partitions
44 **************************************************************************/
45 void METIS_WPartGraphRecursive(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
46  idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts,
47  float *tpwgts, int *options, int *edgecut, idxtype *part)
48 {
49  int i, j;
51  CtrlType ctrl;
52  float *mytpwgts;
53 
54  if (*numflag == 1)
55  Change2CNumbering(*nvtxs, xadj, adjncy);
56 
57  SetUpGraph(&graph, OP_PMETIS, *nvtxs, 1, xadj, adjncy, vwgt, adjwgt, *wgtflag);
58 
59  if (options[0] == 0) { /* Use the default parameters */
60  ctrl.CType = PMETIS_CTYPE;
61  ctrl.IType = PMETIS_ITYPE;
62  ctrl.RType = PMETIS_RTYPE;
63  ctrl.dbglvl = PMETIS_DBGLVL;
64  }
65  else {
66  ctrl.CType = options[OPTION_CTYPE];
67  ctrl.IType = options[OPTION_ITYPE];
68  ctrl.RType = options[OPTION_RTYPE];
69  ctrl.dbglvl = options[OPTION_DBGLVL];
70  }
71  ctrl.optype = OP_PMETIS;
72  ctrl.CoarsenTo = 20;
73  ctrl.maxvwgt = 1.5*(idxsum(*nvtxs, graph.vwgt)/ctrl.CoarsenTo);
74 
75  mytpwgts = fmalloc(*nparts, "PWMETIS: mytpwgts");
76  for (i=0; i<*nparts; i++)
77  mytpwgts[i] = tpwgts[i];
78 
79  InitRandom(-1);
80 
81  AllocateWorkSpace(&ctrl, &graph, *nparts);
82 
83  IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
84  IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
85 
86  *edgecut = MlevelRecursiveBisection(&ctrl, &graph, *nparts, part, mytpwgts, 1.000, 0);
87 
88  IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
89  IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
90 
91  FreeWorkSpace(&ctrl, &graph);
92  free(mytpwgts);
93 
94  if (*numflag == 1)
95  Change2FNumbering(*nvtxs, xadj, adjncy, part);
96 }
97 
98 
99 
100 /*************************************************************************
101 * This function takes a graph and produces a bisection of it
102 **************************************************************************/
103 int MlevelRecursiveBisection(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, float *tpwgts, float ubfactor, int fpart)
104 {
105  int i, j, nvtxs, cut, tvwgt, tpwgts2[2];
106  idxtype *label, *where;
107  GraphType lgraph, rgraph;
108  float wsum;
109 
110  nvtxs = graph->nvtxs;
111  if (nvtxs == 0) {
112  printf("\t***Cannot bisect a graph with 0 vertices!\n\t***You are trying to partition a graph into too many parts!\n");
113  return 0;
114  }
115 
116  /* Determine the weights of the partitions */
117  tvwgt = idxsum(nvtxs, graph->vwgt);
118  tpwgts2[0] = tvwgt*ssum(nparts/2, tpwgts);
119  tpwgts2[1] = tvwgt-tpwgts2[0];
120 
121  MlevelEdgeBisection(ctrl, graph, tpwgts2, ubfactor);
122  cut = graph->mincut;
123 
124  /* printf("%5d %5d %5d [%5d %f]\n", tpwgts2[0], tpwgts2[1], cut, tvwgt, ssum(nparts/2, tpwgts));*/
125 
126  label = graph->label;
127  where = graph->where;
128  for (i=0; i<nvtxs; i++)
129  part[label[i]] = where[i] + fpart;
130 
131  if (nparts > 2) {
132  SplitGraphPart(ctrl, graph, &lgraph, &rgraph);
133  /* printf("%d %d\n", lgraph.nvtxs, rgraph.nvtxs); */
134  }
135 
136 
137  /* Free the memory of the top level graph */
138  GKfree(&graph->gdata, &graph->rdata, &graph->label, LTERM);
139 
140  /* Scale the fractions in the tpwgts according to the true weight */
141  wsum = ssum(nparts/2, tpwgts);
142  sscale(nparts/2, 1.0/wsum, tpwgts);
143  sscale(nparts-nparts/2, 1.0/(1.0-wsum), tpwgts+nparts/2);
144  /*
145  for (i=0; i<nparts; i++)
146  printf("%5.3f ", tpwgts[i]);
147  printf("[%5.3f]\n", wsum);
148  */
149 
150  /* Do the recursive call */
151  if (nparts > 3) {
152  cut += MlevelRecursiveBisection(ctrl, &lgraph, nparts/2, part, tpwgts, ubfactor, fpart);
153  cut += MlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, tpwgts+nparts/2, ubfactor, fpart+nparts/2);
154  }
155  else if (nparts == 3) {
156  cut += MlevelRecursiveBisection(ctrl, &rgraph, nparts-nparts/2, part, tpwgts+nparts/2, ubfactor, fpart+nparts/2);
157  GKfree(&lgraph.gdata, &lgraph.label, LTERM);
158  }
159 
160  return cut;
161 
162 }
163 
164 
165 /*************************************************************************
166 * This function performs multilevel bisection
167 **************************************************************************/
168 void MlevelEdgeBisection(CtrlType *ctrl, GraphType *graph, int *tpwgts, float ubfactor)
169 {
170  GraphType *cgraph;
171 
172  cgraph = Coarsen2Way(ctrl, graph);
173 
174  Init2WayPartition(ctrl, cgraph, tpwgts, ubfactor);
175 
176  Refine2Way(ctrl, graph, cgraph, tpwgts, ubfactor);
177 
178 /*
179  IsConnectedSubdomain(ctrl, graph, 0);
180  IsConnectedSubdomain(ctrl, graph, 1);
181 */
182 }
183 
184 
185 
186 
187 /*************************************************************************
188 * This function takes a graph and a bisection and splits it into two graphs.
189 **************************************************************************/
190 void SplitGraphPart(CtrlType *ctrl, GraphType *graph, GraphType *lgraph, GraphType *rgraph)
191 {
192  int i, j, k, kk, l, istart, iend, mypart, nvtxs, ncon, snvtxs[2], snedges[2], sum;
193  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *adjwgtsum, *label, *where, *bndptr;
194  idxtype *sxadj[2], *svwgt[2], *sadjncy[2], *sadjwgt[2], *sadjwgtsum[2], *slabel[2];
195  idxtype *rename;
196  idxtype *auxadjncy, *auxadjwgt;
197  float *nvwgt, *snvwgt[2], *npwgts;
198 
199 
200  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->SplitTmr));
201 
202  nvtxs = graph->nvtxs;
203  ncon = graph->ncon;
204  xadj = graph->xadj;
205  vwgt = graph->vwgt;
206  nvwgt = graph->nvwgt;
207  adjncy = graph->adjncy;
208  adjwgt = graph->adjwgt;
209  adjwgtsum = graph->adjwgtsum;
210  label = graph->label;
211  where = graph->where;
212  bndptr = graph->bndptr;
213  npwgts = graph->npwgts;
214 
215  ASSERT(bndptr != NULL);
216 
217  rename = idxwspacemalloc(ctrl, nvtxs);
218 
219  snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
220  for (i=0; i<nvtxs; i++) {
221  k = where[i];
222  rename[i] = snvtxs[k]++;
223  snedges[k] += xadj[i+1]-xadj[i];
224  }
225 
226  SetUpSplitGraph(graph, lgraph, snvtxs[0], snedges[0]);
227  sxadj[0] = lgraph->xadj;
228  svwgt[0] = lgraph->vwgt;
229  snvwgt[0] = lgraph->nvwgt;
230  sadjwgtsum[0] = lgraph->adjwgtsum;
231  sadjncy[0] = lgraph->adjncy;
232  sadjwgt[0] = lgraph->adjwgt;
233  slabel[0] = lgraph->label;
234 
235  SetUpSplitGraph(graph, rgraph, snvtxs[1], snedges[1]);
236  sxadj[1] = rgraph->xadj;
237  svwgt[1] = rgraph->vwgt;
238  snvwgt[1] = rgraph->nvwgt;
239  sadjwgtsum[1] = rgraph->adjwgtsum;
240  sadjncy[1] = rgraph->adjncy;
241  sadjwgt[1] = rgraph->adjwgt;
242  slabel[1] = rgraph->label;
243 
244  snvtxs[0] = snvtxs[1] = snedges[0] = snedges[1] = 0;
245  sxadj[0][0] = sxadj[1][0] = 0;
246  for (i=0; i<nvtxs; i++) {
247  mypart = where[i];
248  sum = adjwgtsum[i];
249 
250  istart = xadj[i];
251  iend = xadj[i+1];
252  if (bndptr[i] == -1) { /* This is an interior vertex */
253  auxadjncy = sadjncy[mypart] + snedges[mypart] - istart;
254  auxadjwgt = sadjwgt[mypart] + snedges[mypart] - istart;
255  for(j=istart; j<iend; j++) {
256  auxadjncy[j] = adjncy[j];
257  auxadjwgt[j] = adjwgt[j];
258  }
259  snedges[mypart] += iend-istart;
260  }
261  else {
262  auxadjncy = sadjncy[mypart];
263  auxadjwgt = sadjwgt[mypart];
264  l = snedges[mypart];
265  for (j=istart; j<iend; j++) {
266  k = adjncy[j];
267  if (where[k] == mypart) {
268  auxadjncy[l] = k;
269  auxadjwgt[l++] = adjwgt[j];
270  }
271  else {
272  sum -= adjwgt[j];
273  }
274  }
275  snedges[mypart] = l;
276  }
277 
278  if (ncon == 1)
279  svwgt[mypart][snvtxs[mypart]] = vwgt[i];
280  else {
281  for (kk=0; kk<ncon; kk++)
282  snvwgt[mypart][snvtxs[mypart]*ncon+kk] = nvwgt[i*ncon+kk]/npwgts[mypart*ncon+kk];
283  }
284 
285  sadjwgtsum[mypart][snvtxs[mypart]] = sum;
286  slabel[mypart][snvtxs[mypart]] = label[i];
287  sxadj[mypart][++snvtxs[mypart]] = snedges[mypart];
288  }
289 
290  for (mypart=0; mypart<2; mypart++) {
291  iend = sxadj[mypart][snvtxs[mypart]];
292  auxadjncy = sadjncy[mypart];
293  for (i=0; i<iend; i++)
294  auxadjncy[i] = rename[auxadjncy[i]];
295  }
296 
297  lgraph->nedges = snedges[0];
298  rgraph->nedges = snedges[1];
299 
300  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->SplitTmr));
301 
302  idxwspacefree(ctrl, nvtxs);
303 }
304 
305 
306 /*************************************************************************
307 * Setup the various arrays for the splitted graph
308 **************************************************************************/
309 void SetUpSplitGraph(GraphType *graph, GraphType *sgraph, int snvtxs, int snedges)
310 {
311  InitGraph(sgraph);
312  sgraph->nvtxs = snvtxs;
313  sgraph->nedges = snedges;
314  sgraph->ncon = graph->ncon;
315 
316  /* Allocate memory for the splitted graph */
317  if (graph->ncon == 1) {
318  sgraph->gdata = idxmalloc(4*snvtxs+1 + 2*snedges, "SetUpSplitGraph: gdata");
319 
320  sgraph->xadj = sgraph->gdata;
321  sgraph->vwgt = sgraph->gdata + snvtxs+1;
322  sgraph->adjwgtsum = sgraph->gdata + 2*snvtxs+1;
323  sgraph->cmap = sgraph->gdata + 3*snvtxs+1;
324  sgraph->adjncy = sgraph->gdata + 4*snvtxs+1;
325  sgraph->adjwgt = sgraph->gdata + 4*snvtxs+1 + snedges;
326  }
327  else {
328  sgraph->gdata = idxmalloc(3*snvtxs+1 + 2*snedges, "SetUpSplitGraph: gdata");
329 
330  sgraph->xadj = sgraph->gdata;
331  sgraph->adjwgtsum = sgraph->gdata + snvtxs+1;
332  sgraph->cmap = sgraph->gdata + 2*snvtxs+1;
333  sgraph->adjncy = sgraph->gdata + 3*snvtxs+1;
334  sgraph->adjwgt = sgraph->gdata + 3*snvtxs+1 + snedges;
335 
336  sgraph->nvwgt = fmalloc(graph->ncon*snvtxs, "SetUpSplitGraph: nvwgt");
337  }
338 
339  sgraph->label = idxmalloc(snvtxs, "SetUpSplitGraph: sgraph->label");
340 }
341 
#define idxwspacefree
Definition: rename.h:165
timer TotalTmr
Definition: struct.h:230
idxtype * cmap
Definition: struct.h:172
idxtype * adjwgtsum
Definition: struct.h:168
int optype
Definition: struct.h:222
#define SplitGraphPart
Definition: rename.h:310
#define SetUpGraph
Definition: rename.h:72
#define fmalloc
Definition: rename.h:384
#define OPTION_CTYPE
Definition: defs.h:30
#define MlevelRecursiveBisection
Definition: rename.h:308
#define Coarsen2Way
Definition: rename.h:34
int IType
Definition: struct.h:218
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
#define idxwspacemalloc
Definition: rename.h:164
#define SetUpSplitGraph
Definition: rename.h:311
#define idxsum
Definition: rename.h:399
#define stoptimer(tmr)
Definition: macros.h:54
HitTile_Vector graph
int CType
Definition: struct.h:217
#define OP_PMETIS
Definition: defs.h:89
idxtype * where
Definition: struct.h:176
#define PMETIS_ITYPE
Definition: defs.h:44
#define LTERM
Definition: defs.h:18
#define Refine2Way
Definition: rename.h:328
float * npwgts
Definition: struct.h:196
int idxtype
Definition: struct.h:19
#define InitRandom
Definition: rename.h:412
#define AllocateWorkSpace
Definition: rename.h:161
#define ssum
Definition: rename.h:404
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define InitTimers
Definition: rename.h:373
void METIS_WPartGraphRecursive(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, float *tpwgts, int *options, int *edgecut, idxtype *part)
Definition: pmetis.c:45
#define Change2CNumbering
Definition: rename.h:62
idxtype * label
Definition: struct.h:170
void METIS_PartGraphRecursive(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, int *options, int *edgecut, idxtype *part)
Definition: pmetis.c:22
#define OPTION_RTYPE
Definition: defs.h:32
idxtype * adjwgt
Definition: struct.h:166
int CoarsenTo
Definition: struct.h:215
void GKfree(void **ptr1,...)
Definition: util.c:121
int ncon
Definition: struct.h:194
#define PMETIS_DBGLVL
Definition: defs.h:46
#define sscale
Definition: rename.h:406
#define PrintTimers
Definition: rename.h:374
timer SplitTmr
Definition: struct.h:230
#define FreeWorkSpace
Definition: rename.h:162
idxtype * vwgt
Definition: struct.h:163
#define DBG_TIME
Definition: defs.h:154
int RType
Definition: struct.h:219
int nedges
Definition: struct.h:161
#define idxmalloc
Definition: rename.h:383
idxtype * gdata
Definition: struct.h:157
int maxvwgt
Definition: struct.h:220
#define OPTION_ITYPE
Definition: defs.h:31
int nvtxs
Definition: struct.h:161
#define ASSERT(expr)
Definition: macros.h:130
#define PMETIS_RTYPE
Definition: defs.h:45
float * nvwgt
Definition: struct.h:195
#define MlevelEdgeBisection
Definition: rename.h:309
#define PMETIS_CTYPE
Definition: defs.h:43
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define Change2FNumbering
Definition: rename.h:63
#define InitGraph
Definition: rename.h:168
#define OPTION_DBGLVL
Definition: defs.h:33
#define starttimer(tmr)
Definition: macros.h:53
#define Init2WayPartition
Definition: rename.h:84