SCM

SCM Repository

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

Annotation of /pkg/src/Metis/separator.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 :     * separator.c
5 :     *
6 :     * This file contains code for separator extraction
7 :     *
8 :     * Started 8/1/97
9 :     * George
10 :     *
11 :     * $Id: separator.c,v 1.1 2003/12/31 21:32:30 bates Exp $
12 :     *
13 :     */
14 :    
15 :     #include <metis.h>
16 :    
17 :     /*************************************************************************
18 :     * This function takes a bisection and constructs a minimum weight vertex
19 :     * separator out of it. It uses the node-based separator refinement for it.
20 :     **************************************************************************/
21 :     void ConstructSeparator(CtrlType *ctrl, GraphType *graph, float ubfactor)
22 :     {
23 :     int i, j, k, nvtxs, nbnd;
24 :     idxtype *xadj, *where, *bndind;
25 :    
26 :     nvtxs = graph->nvtxs;
27 :     xadj = graph->xadj;
28 :     nbnd = graph->nbnd;
29 :     bndind = graph->bndind;
30 :    
31 :     where = idxcopy(nvtxs, graph->where, idxwspacemalloc(ctrl, nvtxs));
32 :    
33 :     /* Put the nodes in the boundary into the separator */
34 :     for (i=0; i<nbnd; i++) {
35 :     j = bndind[i];
36 :     if (xadj[j+1]-xadj[j] > 0) /* Ignore islands */
37 :     where[j] = 2;
38 :     }
39 :    
40 :     GKfree(&graph->rdata, LTERM);
41 :     Allocate2WayNodePartitionMemory(ctrl, graph);
42 :     idxcopy(nvtxs, where, graph->where);
43 :     idxwspacefree(ctrl, nvtxs);
44 :    
45 :     ASSERT(IsSeparable(graph));
46 :    
47 :     Compute2WayNodePartitionParams(ctrl, graph);
48 :    
49 :     ASSERT(CheckNodePartitionParams(graph));
50 :    
51 :     FM_2WayNodeRefine(ctrl, graph, ubfactor, 8);
52 :    
53 :     ASSERT(IsSeparable(graph));
54 :     }
55 :    
56 :    
57 :    
58 :     /*************************************************************************
59 :     * This function takes a bisection and constructs a minimum weight vertex
60 :     * separator out of it. It uses an unweighted minimum-cover algorithm
61 :     * followed by node-based separator refinement.
62 :     **************************************************************************/
63 :     void ConstructMinCoverSeparator0(CtrlType *ctrl, GraphType *graph, float ubfactor)
64 :     {
65 :     int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
66 :     idxtype *xadj, *adjncy, *bxadj, *badjncy;
67 :     idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
68 :    
69 :    
70 :     nvtxs = graph->nvtxs;
71 :     xadj = graph->xadj;
72 :     adjncy = graph->adjncy;
73 :    
74 :     nbnd = graph->nbnd;
75 :     bndind = graph->bndind;
76 :     bndptr = graph->bndptr;
77 :     where = graph->where;
78 :    
79 :     vmap = idxwspacemalloc(ctrl, nvtxs);
80 :     ivmap = idxwspacemalloc(ctrl, nbnd);
81 :     cover = idxwspacemalloc(ctrl, nbnd);
82 :    
83 :     if (nbnd > 0) {
84 :     /* Go through the boundary and determine the sizes of the bipartite graph */
85 :     bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
86 :     for (i=0; i<nbnd; i++) {
87 :     j = bndind[i];
88 :     k = where[j];
89 :     if (xadj[j+1]-xadj[j] > 0) {
90 :     bnvtxs[k]++;
91 :     bnedges[k] += xadj[j+1]-xadj[j];
92 :     }
93 :     }
94 :    
95 :     bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
96 :     bnvtxs[1] = bnvtxs[0];
97 :     bnvtxs[0] = 0;
98 :    
99 :     bxadj = idxmalloc(bnvtxs[2]+1, "ConstructMinCoverSeparator: bxadj");
100 :     badjncy = idxmalloc(bnedges[0]+bnedges[1]+1, "ConstructMinCoverSeparator: badjncy");
101 :    
102 :     /* Construct the ivmap and vmap */
103 :     ASSERT(idxset(nvtxs, -1, vmap) == vmap);
104 :     for (i=0; i<nbnd; i++) {
105 :     j = bndind[i];
106 :     k = where[j];
107 :     if (xadj[j+1]-xadj[j] > 0) {
108 :     vmap[j] = bnvtxs[k];
109 :     ivmap[bnvtxs[k]++] = j;
110 :     }
111 :     }
112 :    
113 :     /* OK, go through and put the vertices of each part starting from 0 */
114 :     bnvtxs[1] = bnvtxs[0];
115 :     bnvtxs[0] = 0;
116 :     bxadj[0] = l = 0;
117 :     for (k=0; k<2; k++) {
118 :     for (ii=0; ii<nbnd; ii++) {
119 :     i = bndind[ii];
120 :     if (where[i] == k && xadj[i] < xadj[i+1]) {
121 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
122 :     jj = adjncy[j];
123 :     if (where[jj] != k) {
124 :     ASSERT(bndptr[jj] != -1);
125 :     ASSERTP(vmap[jj] != -1, ("%d %d %d\n", jj, vmap[jj], graph->bndptr[jj]));
126 :     badjncy[l++] = vmap[jj];
127 :     }
128 :     }
129 :     bxadj[++bnvtxs[k]] = l;
130 :     }
131 :     }
132 :     }
133 :    
134 :     ASSERT(l <= bnedges[0]+bnedges[1]);
135 :    
136 :     MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
137 :    
138 :     IFSET(ctrl->dbglvl, DBG_SEPINFO,
139 :     printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
140 :    
141 :     for (i=0; i<csize; i++) {
142 :     j = ivmap[cover[i]];
143 :     where[j] = 2;
144 :     }
145 :    
146 :     GKfree(&bxadj, &badjncy, LTERM);
147 :    
148 :     for (i=0; i<nbnd; i++)
149 :     bndptr[bndind[i]] = -1;
150 :     for (nbnd=i=0; i<nvtxs; i++) {
151 :     if (where[i] == 2) {
152 :     bndind[nbnd] = i;
153 :     bndptr[i] = nbnd++;
154 :     }
155 :     }
156 :     }
157 :     else {
158 :     IFSET(ctrl->dbglvl, DBG_SEPINFO,
159 :     printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, 0, 0, 0));
160 :     }
161 :    
162 :     idxwspacefree(ctrl, nvtxs);
163 :     idxwspacefree(ctrl, graph->nbnd);
164 :     idxwspacefree(ctrl, graph->nbnd);
165 :     graph->nbnd = nbnd;
166 :    
167 :    
168 :     ASSERT(IsSeparable(graph));
169 :     }
170 :    
171 :    
172 :    
173 :     /*************************************************************************
174 :     * This function takes a bisection and constructs a minimum weight vertex
175 :     * separator out of it. It uses an unweighted minimum-cover algorithm
176 :     * followed by node-based separator refinement.
177 :     **************************************************************************/
178 :     void ConstructMinCoverSeparator(CtrlType *ctrl, GraphType *graph, float ubfactor)
179 :     {
180 :     int i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
181 :     idxtype *xadj, *adjncy, *bxadj, *badjncy;
182 :     idxtype *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
183 :    
184 :    
185 :     nvtxs = graph->nvtxs;
186 :     xadj = graph->xadj;
187 :     adjncy = graph->adjncy;
188 :    
189 :     nbnd = graph->nbnd;
190 :     bndind = graph->bndind;
191 :     bndptr = graph->bndptr;
192 :     where = graph->where;
193 :    
194 :     vmap = idxwspacemalloc(ctrl, nvtxs);
195 :     ivmap = idxwspacemalloc(ctrl, nbnd);
196 :     cover = idxwspacemalloc(ctrl, nbnd);
197 :    
198 :     if (nbnd > 0) {
199 :     /* Go through the boundary and determine the sizes of the bipartite graph */
200 :     bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
201 :     for (i=0; i<nbnd; i++) {
202 :     j = bndind[i];
203 :     k = where[j];
204 :     if (xadj[j+1]-xadj[j] > 0) {
205 :     bnvtxs[k]++;
206 :     bnedges[k] += xadj[j+1]-xadj[j];
207 :     }
208 :     }
209 :    
210 :     bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
211 :     bnvtxs[1] = bnvtxs[0];
212 :     bnvtxs[0] = 0;
213 :    
214 :     bxadj = idxmalloc(bnvtxs[2]+1, "ConstructMinCoverSeparator: bxadj");
215 :     badjncy = idxmalloc(bnedges[0]+bnedges[1]+1, "ConstructMinCoverSeparator: badjncy");
216 :    
217 :     /* Construct the ivmap and vmap */
218 :     ASSERT(idxset(nvtxs, -1, vmap) == vmap);
219 :     for (i=0; i<nbnd; i++) {
220 :     j = bndind[i];
221 :     k = where[j];
222 :     if (xadj[j+1]-xadj[j] > 0) {
223 :     vmap[j] = bnvtxs[k];
224 :     ivmap[bnvtxs[k]++] = j;
225 :     }
226 :     }
227 :    
228 :     /* OK, go through and put the vertices of each part starting from 0 */
229 :     bnvtxs[1] = bnvtxs[0];
230 :     bnvtxs[0] = 0;
231 :     bxadj[0] = l = 0;
232 :     for (k=0; k<2; k++) {
233 :     for (ii=0; ii<nbnd; ii++) {
234 :     i = bndind[ii];
235 :     if (where[i] == k && xadj[i] < xadj[i+1]) {
236 :     for (j=xadj[i]; j<xadj[i+1]; j++) {
237 :     jj = adjncy[j];
238 :     if (where[jj] != k) {
239 :     ASSERT(bndptr[jj] != -1);
240 :     ASSERTP(vmap[jj] != -1, ("%d %d %d\n", jj, vmap[jj], graph->bndptr[jj]));
241 :     badjncy[l++] = vmap[jj];
242 :     }
243 :     }
244 :     bxadj[++bnvtxs[k]] = l;
245 :     }
246 :     }
247 :     }
248 :    
249 :     ASSERT(l <= bnedges[0]+bnedges[1]);
250 :    
251 :     MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
252 :    
253 :     IFSET(ctrl->dbglvl, DBG_SEPINFO,
254 :     printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
255 :    
256 :     for (i=0; i<csize; i++) {
257 :     j = ivmap[cover[i]];
258 :     where[j] = 2;
259 :     }
260 :    
261 :     GKfree(&bxadj, &badjncy, LTERM);
262 :     }
263 :     else {
264 :     IFSET(ctrl->dbglvl, DBG_SEPINFO,
265 :     printf("Nvtxs: %6d, [%5d %5d], Cut: %6d, SS: [%6d %6d], Cover: %6d\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, 0, 0, 0));
266 :     }
267 :    
268 :     /* Prepare to refine the vertex separator */
269 :     idxcopy(nvtxs, graph->where, vmap);
270 :     GKfree(&graph->rdata, LTERM);
271 :    
272 :     Allocate2WayNodePartitionMemory(ctrl, graph);
273 :     idxcopy(nvtxs, vmap, graph->where);
274 :     idxwspacefree(ctrl, nvtxs+2*graph->nbnd);
275 :    
276 :     Compute2WayNodePartitionParams(ctrl, graph);
277 :    
278 :     ASSERT(CheckNodePartitionParams(graph));
279 :    
280 :     FM_2WayNodeRefine_OneSided(ctrl, graph, ubfactor, 6);
281 :    
282 :     ASSERT(IsSeparable(graph));
283 :     }
284 :    

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