source: inundation/pymetis/metis-4.0/Lib/mrefine.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: 5.7 KB
Line 
1/*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * refine.c
5 *
6 * This file contains the driving routines for multilevel refinement
7 *
8 * Started 7/24/97
9 * George
10 *
11 * $Id: mrefine.c,v 1.2 1998/11/27 18:25:09 karypis Exp $
12 */
13
14#include <metis.h>
15
16
17/*************************************************************************
18* This function is the entry point of refinement
19**************************************************************************/
20void MocRefine2Way(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, float *tpwgts, float ubfactor)
21{
22  int i;
23  float tubvec[MAXNCON];
24
25  for (i=0; i<graph->ncon; i++)
26    tubvec[i] = 1.0;
27
28  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
29
30  /* Compute the parameters of the coarsest graph */
31  MocCompute2WayPartitionParams(ctrl, graph);
32
33  for (;;) {
34    ASSERT(CheckBnd(graph));
35
36    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
37    switch (ctrl->RType) {
38      case RTYPE_FM:
39        MocBalance2Way(ctrl, graph, tpwgts, 1.03);
40        MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 8); 
41        break;
42      case 2:
43        MocBalance2Way(ctrl, graph, tpwgts, 1.03);
44        MocFM_2WayEdgeRefine2(ctrl, graph, tpwgts, tubvec, 8); 
45        break;
46      default:
47        errexit("Unknown refinement type: %d\n", ctrl->RType);
48    }
49    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
50
51    if (graph == orggraph)
52      break;
53
54    graph = graph->finer;
55    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
56    MocProject2WayPartition(ctrl, graph);
57    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
58  }
59
60  MocBalance2Way(ctrl, graph, tpwgts, 1.01);
61  MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 8); 
62
63  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
64}
65
66
67/*************************************************************************
68* This function allocates memory for 2-way edge refinement
69**************************************************************************/
70void MocAllocate2WayPartitionMemory(CtrlType *ctrl, GraphType *graph)
71{
72  int nvtxs, ncon;
73
74  nvtxs = graph->nvtxs;
75  ncon = graph->ncon;
76
77  graph->rdata = idxmalloc(5*nvtxs, "Allocate2WayPartitionMemory: rdata");
78  graph->where          = graph->rdata;
79  graph->id             = graph->rdata + nvtxs;
80  graph->ed             = graph->rdata + 2*nvtxs;
81  graph->bndptr         = graph->rdata + 3*nvtxs;
82  graph->bndind         = graph->rdata + 4*nvtxs;
83
84  graph->npwgts         = fmalloc(2*ncon, "npwgts");
85}
86
87
88/*************************************************************************
89* This function computes the initial id/ed
90**************************************************************************/
91void MocCompute2WayPartitionParams(CtrlType *ctrl, GraphType *graph)
92{
93  int i, j, k, l, nvtxs, ncon, nbnd, mincut;
94  idxtype *xadj, *adjncy, *adjwgt;
95  float *nvwgt, *npwgts;
96  idxtype *id, *ed, *where;
97  idxtype *bndptr, *bndind;
98  int me, other;
99
100  nvtxs = graph->nvtxs;
101  ncon = graph->ncon;
102  xadj = graph->xadj;
103  nvwgt = graph->nvwgt;
104  adjncy = graph->adjncy;
105  adjwgt = graph->adjwgt;
106
107  where = graph->where;
108  npwgts = sset(2*ncon, 0.0, graph->npwgts);
109  id = idxset(nvtxs, 0, graph->id);
110  ed = idxset(nvtxs, 0, graph->ed);
111  bndptr = idxset(nvtxs, -1, graph->bndptr);
112  bndind = graph->bndind;
113
114
115  /*------------------------------------------------------------
116  / Compute now the id/ed degrees
117  /------------------------------------------------------------*/
118  nbnd = mincut = 0;
119  for (i=0; i<nvtxs; i++) {
120    ASSERT(where[i] >= 0 && where[i] <= 1);
121    me = where[i];
122    saxpy(ncon, 1.0, nvwgt+i*ncon, 1, npwgts+me*ncon, 1);
123
124    for (j=xadj[i]; j<xadj[i+1]; j++) {
125      if (me == where[adjncy[j]])
126        id[i] += adjwgt[j];
127      else
128        ed[i] += adjwgt[j];
129    }
130
131    if (ed[i] > 0 || xadj[i] == xadj[i+1]) {
132      mincut += ed[i];
133      bndptr[i] = nbnd;
134      bndind[nbnd++] = i;
135    }
136  }
137
138  graph->mincut = mincut/2;
139  graph->nbnd = nbnd;
140
141}
142
143
144
145/*************************************************************************
146* This function projects a partition, and at the same time computes the
147* parameters for refinement.
148**************************************************************************/
149void MocProject2WayPartition(CtrlType *ctrl, GraphType *graph)
150{
151  int i, j, k, nvtxs, nbnd, me;
152  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
153  idxtype *cmap, *where, *id, *ed, *bndptr, *bndind;
154  idxtype *cwhere, *cid, *ced, *cbndptr;
155  GraphType *cgraph;
156
157  cgraph = graph->coarser;
158  cwhere = cgraph->where;
159  cid = cgraph->id;
160  ced = cgraph->ed;
161  cbndptr = cgraph->bndptr;
162
163  nvtxs = graph->nvtxs;
164  cmap = graph->cmap;
165  xadj = graph->xadj;
166  adjncy = graph->adjncy;
167  adjwgt = graph->adjwgt;
168  adjwgtsum = graph->adjwgtsum;
169
170  MocAllocate2WayPartitionMemory(ctrl, graph);
171
172  where = graph->where;
173  id = idxset(nvtxs, 0, graph->id);
174  ed = idxset(nvtxs, 0, graph->ed);
175  bndptr = idxset(nvtxs, -1, graph->bndptr);
176  bndind = graph->bndind;
177
178
179  /* Go through and project partition and compute id/ed for the nodes */
180  for (i=0; i<nvtxs; i++) {
181    k = cmap[i];
182    where[i] = cwhere[k];
183    cmap[i] = cbndptr[k];
184  }
185
186  for (nbnd=0, i=0; i<nvtxs; i++) {
187    me = where[i];
188
189    id[i] = adjwgtsum[i];
190
191    if (xadj[i] == xadj[i+1]) {
192      bndptr[i] = nbnd;
193      bndind[nbnd++] = i;
194    }
195    else {
196      if (cmap[i] != -1) { /* If it is an interface node. Note that cmap[i] = cbndptr[cmap[i]] */
197        for (j=xadj[i]; j<xadj[i+1]; j++) {
198          if (me != where[adjncy[j]])
199            ed[i] += adjwgt[j];
200        }
201        id[i] -= ed[i];
202
203        if (ed[i] > 0 || xadj[i] == xadj[i+1]) {
204          bndptr[i] = nbnd;
205          bndind[nbnd++] = i;
206        }
207      }
208    }
209  }
210
211  graph->mincut = cgraph->mincut;
212  graph->nbnd = nbnd;
213  scopy(2*graph->ncon, cgraph->npwgts, graph->npwgts);
214
215  FreeGraph(graph->coarser);
216  graph->coarser = NULL;
217
218}
219
Note: See TracBrowser for help on using the repository browser.