source: inundation/pymetis/metis-4.0/Lib/kwayrefine.c @ 2051

Last change on this file since 2051 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.

File size: 11.7 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * kwayrefine.c
5 *
6 * This file contains the driving routines for multilevel k-way refinement
7 *
8 * Started 7/28/97
9 * George
10 *
11 * $Id: kwayrefine.c,v 1.1 1998/11/27 17:59:17 karypis Exp $
12 */
13
14#include <metis.h>
15
16
17/*************************************************************************
18* This function is the entry point of refinement
19**************************************************************************/
20void RefineKWay(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, int nparts, float *tpwgts, float ubfactor)
21{
22  int i, nlevels, mustfree=0;
23  GraphType *ptr;
24
25  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
26
27  /* Compute the parameters of the coarsest graph */
28  ComputeKWayPartitionParams(ctrl, graph, nparts);
29
30  /* Take care any non-contiguity */
31  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr1));
32  if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
33    EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
34    EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
35    EliminateComponents(ctrl, graph, nparts, tpwgts, 1.25);
36  }
37  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr1));
38
39  /* Determine how many levels are there */
40  for (ptr=graph, nlevels=0; ptr!=orggraph; ptr=ptr->finer, nlevels++); 
41
42  for (i=0; ;i++) {
43    /* PrintSubDomainGraph(graph, nparts, graph->where); */
44    if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN && (i == nlevels/2 || i == nlevels/2+1))
45      EliminateSubDomainEdges(ctrl, graph, nparts, tpwgts);
46
47    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
48
49    if (2*i >= nlevels && !IsBalanced(graph->pwgts, nparts, tpwgts, 1.04*ubfactor)) {
50      ComputeKWayBalanceBoundary(ctrl, graph, nparts);
51      if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN)
52        Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
53      else
54        Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 1); 
55      ComputeKWayBoundary(ctrl, graph, nparts);
56    }
57
58    switch (ctrl->RType) {
59      case RTYPE_KWAYRANDOM:
60        Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
61        break;
62      case RTYPE_KWAYGREEDY:
63        Greedy_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10); 
64        break;
65      case RTYPE_KWAYRANDOM_MCONN:
66        Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 1); 
67        break;
68    }
69    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
70
71    if (graph == orggraph)
72      break;
73
74    GKfree(&graph->gdata, LTERM);  /* Deallocate the graph related arrays */
75
76    graph = graph->finer;
77
78    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
79    if (graph->vwgt == NULL) {
80      graph->vwgt = idxsmalloc(graph->nvtxs, 1, "RefineKWay: graph->vwgt");
81      graph->adjwgt = idxsmalloc(graph->nedges, 1, "RefineKWay: graph->adjwgt");
82      mustfree = 1;
83    }
84    ProjectKWayPartition(ctrl, graph, nparts);
85    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
86  }
87
88  if (!IsBalanced(graph->pwgts, nparts, tpwgts, ubfactor)) {
89    ComputeKWayBalanceBoundary(ctrl, graph, nparts);
90    if (ctrl->RType == RTYPE_KWAYRANDOM_MCONN) {
91      Greedy_KWayEdgeBalanceMConn(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
92      Random_KWayEdgeRefineMConn(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
93    }
94    else {
95      Greedy_KWayEdgeBalance(ctrl, graph, nparts, tpwgts, ubfactor, 8); 
96      Random_KWayEdgeRefine(ctrl, graph, nparts, tpwgts, ubfactor, 10, 0); 
97    }
98  }
99
100  /* Take care any trivial non-contiguity */
101  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->AuxTmr2));
102  EliminateComponents(ctrl, graph, nparts, tpwgts, ubfactor);
103  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->AuxTmr2));
104
105  if (mustfree) 
106    GKfree(&graph->vwgt, &graph->adjwgt, LTERM);
107
108  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
109}
110
111
112/*************************************************************************
113* This function allocates memory for k-way edge refinement
114**************************************************************************/
115void AllocateKWayPartitionMemory(CtrlType *ctrl, GraphType *graph, int nparts)
116{
117  int nvtxs, pad64;
118
119  nvtxs = graph->nvtxs;
120
121  pad64 = (3*nvtxs+nparts)%2;
122
123  graph->rdata = idxmalloc(3*nvtxs+nparts+(sizeof(RInfoType)/sizeof(idxtype))*nvtxs+pad64, "AllocateKWayPartitionMemory: rdata");
124  graph->pwgts          = graph->rdata;
125  graph->where          = graph->rdata + nparts;
126  graph->bndptr         = graph->rdata + nvtxs + nparts;
127  graph->bndind         = graph->rdata + 2*nvtxs + nparts;
128  graph->rinfo          = (RInfoType *)(graph->rdata + 3*nvtxs+nparts + pad64);
129
130/*
131  if (ctrl->wspace.edegrees != NULL)
132    free(ctrl->wspace.edegrees);
133  ctrl->wspace.edegrees = (EDegreeType *)GKmalloc(graph->nedges*sizeof(EDegreeType), "AllocateKWayPartitionMemory: edegrees");
134*/
135}
136
137
138/*************************************************************************
139* This function computes the initial id/ed
140**************************************************************************/
141void ComputeKWayPartitionParams(CtrlType *ctrl, GraphType *graph, int nparts)
142{
143  int i, j, k, l, nvtxs, nbnd, mincut, me, other;
144  idxtype *xadj, *vwgt, *adjncy, *adjwgt, *pwgts, *where, *bndind, *bndptr;
145  RInfoType *rinfo, *myrinfo;
146  EDegreeType *myedegrees;
147
148  nvtxs = graph->nvtxs;
149  xadj = graph->xadj;
150  vwgt = graph->vwgt;
151  adjncy = graph->adjncy;
152  adjwgt = graph->adjwgt;
153
154  where = graph->where;
155  pwgts = idxset(nparts, 0, graph->pwgts);
156  bndind = graph->bndind;
157  bndptr = idxset(nvtxs, -1, graph->bndptr);
158  rinfo = graph->rinfo;
159
160
161  /*------------------------------------------------------------
162  / Compute now the id/ed degrees
163  /------------------------------------------------------------*/
164  ctrl->wspace.cdegree = 0;
165  nbnd = mincut = 0;
166  for (i=0; i<nvtxs; i++) {
167    me = where[i];
168    pwgts[me] += vwgt[i];
169
170    myrinfo = rinfo+i;
171    myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
172    myrinfo->edegrees = NULL;
173
174    for (j=xadj[i]; j<xadj[i+1]; j++) {
175      if (me != where[adjncy[j]])
176        myrinfo->ed += adjwgt[j];
177    }
178    myrinfo->id = graph->adjwgtsum[i] - myrinfo->ed;
179
180    if (myrinfo->ed > 0) 
181      mincut += myrinfo->ed;
182
183    if (myrinfo->ed-myrinfo->id >= 0)
184      BNDInsert(nbnd, bndind, bndptr, i);
185
186    /* Time to compute the particular external degrees */
187    if (myrinfo->ed > 0) { 
188      myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
189      ctrl->wspace.cdegree += xadj[i+1]-xadj[i];
190
191      for (j=xadj[i]; j<xadj[i+1]; j++) {
192        other = where[adjncy[j]];
193        if (me != other) {
194          for (k=0; k<myrinfo->ndegrees; k++) {
195            if (myedegrees[k].pid == other) {
196              myedegrees[k].ed += adjwgt[j];
197              break;
198            }
199          }
200          if (k == myrinfo->ndegrees) {
201            myedegrees[myrinfo->ndegrees].pid = other;
202            myedegrees[myrinfo->ndegrees++].ed = adjwgt[j];
203          }
204        }
205      }
206
207      ASSERT(myrinfo->ndegrees <= xadj[i+1]-xadj[i]);
208    }
209  }
210
211  graph->mincut = mincut/2;
212  graph->nbnd = nbnd;
213
214}
215
216
217
218/*************************************************************************
219* This function projects a partition, and at the same time computes the
220* parameters for refinement.
221**************************************************************************/
222void ProjectKWayPartition(CtrlType *ctrl, GraphType *graph, int nparts)
223{
224  int i, j, k, nvtxs, nbnd, me, other, istart, iend, ndegrees;
225  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
226  idxtype *cmap, *where, *bndptr, *bndind;
227  idxtype *cwhere;
228  GraphType *cgraph;
229  RInfoType *crinfo, *rinfo, *myrinfo;
230  EDegreeType *myedegrees;
231  idxtype *htable;
232
233  cgraph = graph->coarser;
234  cwhere = cgraph->where;
235  crinfo = cgraph->rinfo;
236
237  nvtxs = graph->nvtxs;
238  cmap = graph->cmap;
239  xadj = graph->xadj;
240  adjncy = graph->adjncy;
241  adjwgt = graph->adjwgt;
242  adjwgtsum = graph->adjwgtsum;
243
244  AllocateKWayPartitionMemory(ctrl, graph, nparts);
245  where = graph->where;
246  rinfo = graph->rinfo;
247  bndind = graph->bndind;
248  bndptr = idxset(nvtxs, -1, graph->bndptr);
249
250  /* Go through and project partition and compute id/ed for the nodes */
251  for (i=0; i<nvtxs; i++) {
252    k = cmap[i];
253    where[i] = cwhere[k];
254    cmap[i] = crinfo[k].ed;  /* For optimization */
255  }
256
257  htable = idxset(nparts, -1, idxwspacemalloc(ctrl, nparts));
258
259  ctrl->wspace.cdegree = 0;
260  for (nbnd=0, i=0; i<nvtxs; i++) {
261    me = where[i];
262
263    myrinfo = rinfo+i;
264    myrinfo->id = myrinfo->ed = myrinfo->ndegrees = 0;
265    myrinfo->edegrees = NULL;
266
267    myrinfo->id = adjwgtsum[i];
268
269    if (cmap[i] > 0) { /* If it is an interface node. Note cmap[i] = crinfo[cmap[i]].ed */
270      istart = xadj[i];
271      iend = xadj[i+1];
272
273      myedegrees = myrinfo->edegrees = ctrl->wspace.edegrees+ctrl->wspace.cdegree;
274      ctrl->wspace.cdegree += iend-istart;
275
276      ndegrees = 0;
277      for (j=istart; j<iend; j++) {
278        other = where[adjncy[j]];
279        if (me != other) {
280          myrinfo->ed += adjwgt[j];
281          if ((k = htable[other]) == -1) {
282            htable[other] = ndegrees;
283            myedegrees[ndegrees].pid = other;
284            myedegrees[ndegrees++].ed = adjwgt[j];
285          }
286          else {
287            myedegrees[k].ed += adjwgt[j];
288          }
289        }
290      }
291      myrinfo->id -= myrinfo->ed;
292
293      /* Remove space for edegrees if it was interior */
294      if (myrinfo->ed == 0) { 
295        myrinfo->edegrees = NULL;
296        ctrl->wspace.cdegree -= iend-istart;
297      }
298      else {
299        if (myrinfo->ed-myrinfo->id >= 0) 
300          BNDInsert(nbnd, bndind, bndptr, i); 
301
302        myrinfo->ndegrees = ndegrees;
303
304        for (j=0; j<ndegrees; j++)
305          htable[myedegrees[j].pid] = -1;
306      }
307    }
308  }
309
310  idxcopy(nparts, cgraph->pwgts, graph->pwgts);
311  graph->mincut = cgraph->mincut;
312  graph->nbnd = nbnd;
313
314  FreeGraph(graph->coarser);
315  graph->coarser = NULL;
316
317  idxwspacefree(ctrl, nparts);
318
319  ASSERT(CheckBnd2(graph));
320
321}
322
323
324
325/*************************************************************************
326* This function checks if the partition weights are within the balance
327* contraints
328**************************************************************************/
329int IsBalanced(idxtype *pwgts, int nparts, float *tpwgts, float ubfactor)
330{
331  int i, j, tvwgt;
332
333  tvwgt = idxsum(nparts, pwgts);
334  for (i=0; i<nparts; i++) {
335    if (pwgts[i] > tpwgts[i]*tvwgt*(ubfactor+0.005))
336      return 0;
337  }
338
339  return 1;
340}
341
342
343/*************************************************************************
344* This function computes the boundary definition for balancing
345**************************************************************************/
346void ComputeKWayBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
347{
348  int i, nvtxs, nbnd;
349  idxtype *bndind, *bndptr;
350
351  nvtxs = graph->nvtxs;
352  bndind = graph->bndind;
353  bndptr = idxset(nvtxs, -1, graph->bndptr);
354
355
356  /*------------------------------------------------------------
357  / Compute the new boundary
358  /------------------------------------------------------------*/
359  nbnd = 0;
360  for (i=0; i<nvtxs; i++) {
361    if (graph->rinfo[i].ed-graph->rinfo[i].id >= 0) 
362      BNDInsert(nbnd, bndind, bndptr, i);
363  }
364
365  graph->nbnd = nbnd;
366}
367
368/*************************************************************************
369* This function computes the boundary definition for balancing
370**************************************************************************/
371void ComputeKWayBalanceBoundary(CtrlType *ctrl, GraphType *graph, int nparts)
372{
373  int i, nvtxs, nbnd;
374  idxtype *bndind, *bndptr;
375
376  nvtxs = graph->nvtxs;
377  bndind = graph->bndind;
378  bndptr = idxset(nvtxs, -1, graph->bndptr);
379
380
381  /*------------------------------------------------------------
382  / Compute the new boundary
383  /------------------------------------------------------------*/
384  nbnd = 0;
385  for (i=0; i<nvtxs; i++) {
386    if (graph->rinfo[i].ed > 0) 
387      BNDInsert(nbnd, bndind, bndptr, i);
388  }
389
390  graph->nbnd = nbnd;
391}
392
Note: See TracBrowser for help on using the repository browser.