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