SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/refine.c
ViewVC logotype

Annotation of /pkg/src/Metis/refine.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (view) (download) (as text)

1 : bates 10 /*
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 2003/12/31 21:32:30 bates Exp $
12 :     */
13 :    
14 :     #include <metis.h>
15 :    
16 :    
17 :     /*************************************************************************
18 :     * This function is the entry point of refinement
19 :     **************************************************************************/
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 :     **************************************************************************/
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 :     **************************************************************************/
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 :     **************************************************************************/
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 :    

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge