1 /*****************************************************************************
2 /
3 / SPACE (SPArse Cholesky Elimination) Library: gbisect.c
4 /
5 / author J"urgen Schulze, University of Paderborn
6 / created 00dec29
7 /
8 / This file contains functions dealing with the graph bisection object
9 /
10 ******************************************************************************
11
12 Data type: struct gbisect
13 graph_t *G; pointer to graph that will be partitioned
14 int *color; color of node (GRAY, BLACK, or WHITE)
15 int cwght[3]; weights of GRAY, BLACK, WHITE partitions
16 Comments:
17 o Structure used to compute the bisection of a graph. Structure does not
18 own graph object => it will not be freed.
19 Methods in lib/gbisect.c:
20 - Gbisect = newGbisect(graph_t *G);
21 o Initial: cwght[GRAY] = cwght[BLACK] = cwght[WHITE] = 0
22 - void freeGbisect(gbisect_t *Gbisect);
23 - void printGbisect(gbisect_t *Gbisect);
24 - void checkSeparator(gbisect_t *Gbisect);
25 - void constructSeparator(gbisect_t *Gbisect, options_t *options,
26 timings_t *cpus);
27 o constructs a vertex separator by applying the new multilevel approach;
28 it first constructs an initial domain decomposition for Gbisect->G
29 by calling constructDomainDecomposition; the dd is then coarsed by
30 several calls to shrinkDomainDecomposition; the last dd is colored
31 by a call to initialDDSep; this coloring is refined during the
32 uncoarsening phase by several calls to improveDDSep
33 o used options:
34 OPTION_MSGLVL, OPTION_NODE_SELECTION3
35 returned timings:
36 TIME_INITDOMDEC, TIME_COARSEDOMDEC, TIME_INITSEP, TIME_REFINESEP
37 - int smoothBy2Layers(gbisect_t *Gbisect, int *bipartvertex, int *pnX,
38 int black, int white);
39 o on start, bipartvertex contains the nodes of the separator; the
40 separator is then paired with eiter the black or the white partition
41 so that the nodes in bipartvertex induce a bipartite graph; this
42 graph is constructed by setupBipartiteGraph; a Dulmage-Mendelsohn
43 decomposition is computed and the separator is smoothed; the
44 vertices of the smoothed separator are returned in bipartvertex
45 - void smoothSeparator(gbisect_t *Gbisect, options_t *options);
46 o smoothes a given separator by repeatedly calling smoothBy2Layers
47 o used options: OPTION_MSGLVL
48
49 ******************************************************************************/
50
51 #include <space.h>
52 /* #define DEBUG */
53 /* #define BE_CAUTIOUS */
54
55
56 /*****************************************************************************
57 ******************************************************************************/
58 gbisect_t*
newGbisect(graph_t * G)59 newGbisect(graph_t *G)
60 { gbisect_t *Gbisect;
61
62 mymalloc(Gbisect, 1, gbisect_t);
63 mymalloc(Gbisect->color, G->nvtx, PORD_INT);
64
65 Gbisect->G = G;
66 Gbisect->cwght[GRAY] = 0;
67 Gbisect->cwght[BLACK] = 0;
68 Gbisect->cwght[WHITE] = 0;
69
70 return(Gbisect);
71 }
72
73
74 /*****************************************************************************
75 ******************************************************************************/
76 void
freeGbisect(gbisect_t * Gbisect)77 freeGbisect(gbisect_t *Gbisect)
78 {
79 free(Gbisect->color);
80 free(Gbisect);
81 }
82
83
84 /*****************************************************************************
85 ******************************************************************************/
86 void
printGbisect(gbisect_t * Gbisect)87 printGbisect(gbisect_t *Gbisect)
88 { graph_t *G;
89 PORD_INT count, u, v, i, istart, istop;
90
91 G = Gbisect->G;
92 printf("\n#nodes %d, #edges %d, totvwght %d\n", G->nvtx, G->nedges >> 1,
93 G->totvwght);
94 printf("partition weights: S %d, B %d, W %d\n", Gbisect->cwght[GRAY],
95 Gbisect->cwght[BLACK], Gbisect->cwght[WHITE]);
96 for (u = 0; u < G->nvtx; u++)
97 { count = 0;
98 printf("--- adjacency list of node %d (weight %d, color %d)\n", u,
99 G->vwght[u], Gbisect->color[u]);
100 istart = G->xadj[u];
101 istop = G->xadj[u+1];
102 for (i = istart; i < istop; i++)
103 { v = G->adjncy[i];
104 printf("%5d (color %2d)", v, Gbisect->color[v]);
105 if ((++count % 4) == 0)
106 printf("\n");
107 }
108 if ((count % 4) != 0)
109 printf("\n");
110 }
111 }
112
113
114 /*****************************************************************************
115 ******************************************************************************/
116 void
checkSeparator(gbisect_t * Gbisect)117 checkSeparator(gbisect_t *Gbisect)
118 { PORD_INT *xadj, *adjncy, *vwght, *color, *cwght;
119 PORD_INT nvtx, err, checkS, checkB, checkW, a, b, u, v, i, istart, istop;
120
121 nvtx = Gbisect->G->nvtx;
122 xadj = Gbisect->G->xadj;
123 adjncy = Gbisect->G->adjncy;
124 vwght = Gbisect->G->vwght;
125 color = Gbisect->color;
126 cwght = Gbisect->cwght;
127
128 err = FALSE;
129 printf("checking separator of induced subgraph (S %d, B %d, W %d)\n",
130 cwght[GRAY], cwght[BLACK], cwght[WHITE]);
131
132 checkS = checkB = checkW = 0;
133 for (u = 0; u < nvtx; u++)
134 { istart = xadj[u];
135 istop = xadj[u+1];
136 switch(color[u])
137 { case GRAY: /* is it a minimal separator? */
138 checkS += vwght[u];
139 a = b = FALSE;
140 for (i = istart; i < istop; i++)
141 { v = adjncy[i];
142 if (color[v] == WHITE) a = TRUE;
143 if (color[v] == BLACK) b = TRUE;
144 }
145 if (!((a) && (b)))
146 printf("WARNING: not a minimal separator (node %d)\n", u);
147 break;
148 case BLACK: /* is it realy a separator? */
149 checkB += vwght[u];
150 for (i = istart; i < istop; i++)
151 { v = adjncy[i];
152 if (color[v] == WHITE)
153 { printf("ERROR: white node %d adjacent to black node %d\n", u,v);
154 err = TRUE;
155 }
156 }
157 break;
158 case WHITE:
159 checkW += vwght[u];
160 break;
161 default:
162 printf("ERROR: node %d has unrecognized color %d\n", u, color[u]);
163 err = TRUE;
164 }
165 }
166
167 /* check cwght[GRAY], cwght[BLACK], cwght[WHITE] */
168 if ((checkS != cwght[GRAY]) || (checkB != cwght[BLACK])
169 || (checkW != cwght[WHITE]))
170 { printf("ERROR in partitioning: checkS %d (S %d), checkB %d (B %d), "
171 "checkW %d (W %d)\n", checkS, cwght[GRAY], checkB, cwght[BLACK],
172 checkW, cwght[WHITE]);
173 err = TRUE;
174 }
175 if (err) quit();
176 }
177
178
179 /*****************************************************************************
180 ******************************************************************************/
181 void
constructSeparator(gbisect_t * Gbisect,options_t * options,timings_t * cpus)182 constructSeparator(gbisect_t *Gbisect, options_t *options, timings_t *cpus)
183 { domdec_t *dd, *dd2;
184 PORD_INT *color, *cwght, *map, nvtx, u, i;
185
186 nvtx = Gbisect->G->nvtx;
187 color = Gbisect->color;
188 cwght = Gbisect->cwght;
189
190 /* --------------------------------------------------------------
191 map vector identifies vertices of Gbisect->G in domain decomp.
192 -------------------------------------------------------------- */
193 mymalloc(map, nvtx, PORD_INT);
194
195 /* --------------------------------------
196 construct initial domain decomposition
197 -------------------------------------- */
198 pord_starttimer(cpus[TIME_INITDOMDEC]);
199 dd = constructDomainDecomposition(Gbisect->G, map);
200
201 #ifdef BE_CAUTIOUS
202 checkDomainDecomposition(dd);
203 #endif
204
205 if (options[OPTION_MSGLVL] > 2)
206 printf("\t 0. dom.dec.: #nodes %d (#domains %d, weight %d), #edges %d\n",
207 dd->G->nvtx, dd->ndom, dd->domwght, dd->G->nedges >> 1);
208 pord_stoptimer(cpus[TIME_INITDOMDEC]);
209
210 /* ---------------------------------------------------
211 construct sequence of coarser domain decompositions
212 --------------------------------------------------- */
213 pord_starttimer(cpus[TIME_COARSEDOMDEC]);
214 i = 0;
215 while ((dd->ndom > MIN_DOMAINS) && (i < MAX_COARSENING_STEPS)
216 && ((dd->G->nedges >> 1) > dd->G->nvtx))
217 { shrinkDomainDecomposition(dd, options[OPTION_NODE_SELECTION3]);
218 dd = dd->next; i++;
219
220 #ifdef BE_CAUTIOUS
221 checkDomainDecomposition(dd);
222 #endif
223
224 if (options[OPTION_MSGLVL] > 2)
225 printf("\t %2d. dom.dec.: #nodes %d (#domains %d, weight %d), #edges %d"
226 "\n", i, dd->G->nvtx, dd->ndom, dd->domwght, dd->G->nedges >> 1);
227 }
228 pord_stoptimer(cpus[TIME_COARSEDOMDEC]);
229
230 /* -----------------------------------------------
231 determine coloring of last domain decomposition
232 ------------------------------------------------ */
233 pord_starttimer(cpus[TIME_INITSEP]);
234 initialDDSep(dd);
235 if (dd->cwght[GRAY] > 0)
236 improveDDSep(dd);
237
238 #ifdef BE_CAUTIOUS
239 checkDDSep(dd);
240 #endif
241
242 if (options[OPTION_MSGLVL] > 2)
243 printf("\t %2d. dom.dec. sep.: S %d, B %d, W %d [cost %7.2f]\n",
244 i, dd->cwght[GRAY], dd->cwght[BLACK], dd->cwght[WHITE],
245 F(dd->cwght[GRAY], dd->cwght[BLACK], dd->cwght[WHITE]));
246 pord_stoptimer(cpus[TIME_INITSEP]);
247
248 /* --------------
249 refine coloring
250 --------------- */
251
252 pord_starttimer(cpus[TIME_REFINESEP]);
253 while (dd->prev != NULL)
254 { dd2 = dd->prev;
255 dd2->cwght[GRAY] = dd->cwght[GRAY];
256 dd2->cwght[BLACK] = dd->cwght[BLACK];
257 dd2->cwght[WHITE] = dd->cwght[WHITE];
258 for (u = 0; u < dd2->G->nvtx; u++)
259 dd2->color[u] = dd->color[dd2->map[u]];
260 freeDomainDecomposition(dd);
261 if (dd2->cwght[GRAY] > 0)
262 improveDDSep(dd2);
263
264 #ifdef BE_CAUTIOUS
265 checkDDSep(dd2);
266 #endif
267
268 dd = dd2;
269 i--;
270 if (options[OPTION_MSGLVL] > 2)
271 printf("\t %2d. dom.dec. sep.: S %d, B %d, W %d [cost %7.2f]\n",
272 i, dd->cwght[GRAY], dd->cwght[BLACK], dd->cwght[WHITE],
273 F(dd->cwght[GRAY], dd->cwght[BLACK], dd->cwght[WHITE]));
274 }
275 pord_stoptimer(cpus[TIME_REFINESEP]);
276
277 /* ---------------------------------
278 copy coloring to subgraph Gbisect
279 --------------------------------- */
280 cwght[GRAY] = dd->cwght[GRAY];
281 cwght[BLACK] = dd->cwght[BLACK];
282 cwght[WHITE] = dd->cwght[WHITE];
283 for (u = 0; u < nvtx; u++)
284 color[u] = dd->color[map[u]];
285 freeDomainDecomposition(dd);
286 free(map);
287 }
288
289
290 /*****************************************************************************
291 ******************************************************************************/
292 PORD_INT
smoothBy2Layers(gbisect_t * Gbisect,PORD_INT * bipartvertex,PORD_INT * pnX,PORD_INT black,PORD_INT white)293 smoothBy2Layers(gbisect_t *Gbisect, PORD_INT *bipartvertex, PORD_INT *pnX,
294 PORD_INT black, PORD_INT white)
295 { gbipart_t *Gbipart;
296 PORD_INT *xadj, *adjncy, *color, *cwght, *map;
297 PORD_INT *flow, *rc, *matching, *dmflag, dmwght[6];
298 PORD_INT nvtx, smoothed, nX, nX2, nY, x, y, u, i, j, jstart, jstop;
299
300 nvtx = Gbisect->G->nvtx;
301 xadj = Gbisect->G->xadj;
302 adjncy = Gbisect->G->adjncy;
303 color = Gbisect->color;
304 cwght = Gbisect->cwght;
305 nX = *pnX;
306
307 /* ----------------------------------------------------
308 map vector identifies vertices of Gbisect in Gbipart
309 ---------------------------------------------------- */
310 mymalloc(map, nvtx, PORD_INT);
311
312 /* ----------------------------------
313 construct set Y of bipartite graph
314 ---------------------------------- */
315 nY = 0;
316 for (i = 0; i < nX; i++)
317 { x = bipartvertex[i];
318 jstart = xadj[x];
319 jstop = xadj[x+1];
320 for (j = jstart; j < jstop; j++)
321 { y = adjncy[j];
322 if (color[y] == black)
323 { bipartvertex[nX+nY++] = y;
324 color[y] = GRAY;
325 }
326 }
327 }
328 for (i = nX; i < nX+nY; i++)
329 { y = bipartvertex[i];
330 color[y] = black;
331 }
332
333 /* --------------------------------------------
334 compute the Dulmage-Mendelsohn decomposition
335 -------------------------------------------- */
336 Gbipart = setupBipartiteGraph(Gbisect->G, bipartvertex, nX, nY, map);
337
338 mymalloc(dmflag, (nX+nY), PORD_INT);
339 switch(Gbipart->G->type)
340 { case UNWEIGHTED:
341 mymalloc(matching, (nX+nY), PORD_INT);
342 maximumMatching(Gbipart, matching);
343 DMviaMatching(Gbipart, matching, dmflag, dmwght);
344 free(matching);
345 break;
346 case WEIGHTED:
347 mymalloc(flow, Gbipart->G->nedges, PORD_INT);
348 mymalloc(rc, (nX+nY), PORD_INT);
349 maximumFlow(Gbipart, flow, rc);
350 DMviaFlow(Gbipart, flow, rc, dmflag, dmwght);
351 free(flow);
352 free(rc);
353 break;
354 default:
355 fprintf(stderr, "\nError in function smoothSeparator\n"
356 " unrecognized bipartite graph type %d\n", Gbipart->G->type);
357 quit();
358 }
359
360 #ifdef DEBUG
361 printf("Dulmage-Mendelsohn decomp. computed\n"
362 "SI %d, SX %d, SR %d, BI %d, BX %d, BR %d\n", dmwght[SI], dmwght[SX],
363 dmwght[SR], dmwght[BI], dmwght[BX], dmwght[BR]);
364 #endif
365
366 /* -----------------------------------------------------------------------
367 1st TEST: try to exchange SI with BX, i.e. nodes in SI are moved from
368 the separator into white (white grows), and nodes in BX are moved from
369 black into the separator (black shrinks)
370 ----------------------------------------------------------------------- */
371 smoothed = FALSE;
372 if (F(cwght[GRAY]-dmwght[SI]+dmwght[BX], cwght[black]-dmwght[BX],
373 cwght[white]+dmwght[SI]) + EPS < F(cwght[GRAY], cwght[black],
374 cwght[white]))
375 { smoothed = TRUE;
376
377 #ifdef DEBUG
378 printf("exchange SI with BX\n");
379 #endif
380
381 cwght[white] += dmwght[SI]; cwght[GRAY] -= dmwght[SI];
382 cwght[black] -= dmwght[BX]; cwght[GRAY] += dmwght[BX];
383 for (i = 0; i < nX+nY; i++)
384 { u = bipartvertex[i];
385 if (dmflag[map[u]] == SI)
386 color[u] = white;
387 if (dmflag[map[u]] == BX)
388 color[u] = GRAY;
389 }
390 }
391
392 /* -----------------------------------------------------------------------
393 2nd TEST: try to exchange SR with BR, i.e. nodes in SR are moved from
394 the separator into white (white grows), and nodes in BR are moved from
395 black into the separator (black shrinks)
396 NOTE: SR is allowed to be exchanged with BR only if SI = BX = 0 or if
397 SI has been exchanged with BX (Adj(SR) is a subset of BX u BR)
398 ----------------------------------------------------------------------- */
399 if ((F(cwght[GRAY]-dmwght[SR]+dmwght[BR], cwght[black]-dmwght[BR],
400 cwght[white]+dmwght[SR]) + EPS < F(cwght[GRAY], cwght[black],
401 cwght[white]))
402 && ((smoothed) || (dmwght[SI] == 0)))
403 { smoothed = TRUE;
404
405 #ifdef DEBUG
406 printf("exchange SR with BR\n");
407 #endif
408
409 cwght[white] += dmwght[SR]; cwght[GRAY] -= dmwght[SR];
410 cwght[black] -= dmwght[BR]; cwght[GRAY] += dmwght[BR];
411 for (i = 0; i < nX+nY; i++)
412 { u = bipartvertex[i];
413 if (dmflag[map[u]] == SR)
414 color[u] = white;
415 if (dmflag[map[u]] == BR)
416 color[u] = GRAY;
417 }
418 }
419
420 /* -----------------------------------------------------
421 fill bipartvertex with the nodes of the new separator
422 ----------------------------------------------------- */
423 nX2 = 0;
424 for (i = 0; i < nX+nY; i++)
425 { u = bipartvertex[i];
426 if (color[u] == GRAY)
427 bipartvertex[nX2++] = u;
428 }
429 *pnX = nX2;
430
431 /* -------------------------------
432 free working storage and return
433 ------------------------------- */
434 free(map); free(dmflag);
435 freeBipartiteGraph(Gbipart);
436 return(smoothed);
437 }
438
439
440 /*****************************************************************************
441 ******************************************************************************/
442 void
smoothSeparator(gbisect_t * Gbisect,options_t * options)443 smoothSeparator(gbisect_t *Gbisect, options_t *options)
444 { PORD_INT *xadj, *adjncy, *vwght, *color, *cwght, *bipartvertex;
445 PORD_INT nvtx, nX, nX2, u, x, y, a, b, i, j, jstart, jstop;
446
447 nvtx = Gbisect->G->nvtx;
448 xadj = Gbisect->G->xadj;
449 adjncy = Gbisect->G->adjncy;
450 vwght = Gbisect->G->vwght;
451 color = Gbisect->color;
452 cwght = Gbisect->cwght;
453
454 mymalloc(bipartvertex, nvtx, PORD_INT);
455
456 /* ----------------------------------------------------------
457 extract the separator (store its vertices in bipartvertex)
458 ---------------------------------------------------------- */
459 nX = 0;
460 for (u = 0; u < nvtx; u++)
461 if (color[u] == GRAY)
462 bipartvertex[nX++] = u;
463
464 do
465 { /* ---------------------------------------------------------------
466 minimize the separator (i.e. minimize set X of bipartite graph)
467 --------------------------------------------------------------- */
468 cwght[GRAY] = nX2 = 0;
469 for (i = 0; i < nX; i++)
470 { x = bipartvertex[i];
471 a = b = FALSE;
472 jstart = xadj[x];
473 jstop = xadj[x+1];
474 for (j = jstart; j < jstop; j++)
475 { y = adjncy[j];
476 if (color[y] == WHITE) a = TRUE;
477 if (color[y] == BLACK) b = TRUE;
478 }
479 if ((a) && (!b))
480 { color[x] = WHITE; cwght[WHITE] += vwght[x]; }
481 else if ((!a) && (b))
482 { color[x] = BLACK; cwght[BLACK] += vwght[x]; }
483 else
484 { bipartvertex[nX2++] = x; cwght[GRAY] += vwght[x]; }
485 }
486 nX = nX2;
487
488 #ifdef BE_CAUTIOUS
489 checkSeparator(Gbisect);
490 #endif
491
492 /* ------------------------------------------------------------------
493 smooth the unweighted/weighted separator
494 first pair it with the larger set; if unsuccessful try the smaller
495 ------------------------------------------------------------------ */
496 if (cwght[BLACK] >= cwght[WHITE])
497 { a = smoothBy2Layers(Gbisect, bipartvertex, &nX, BLACK, WHITE);
498 if (!a)
499 a = smoothBy2Layers(Gbisect, bipartvertex, &nX, WHITE, BLACK);
500 }
501 else
502 { a = smoothBy2Layers(Gbisect, bipartvertex, &nX, WHITE, BLACK);
503 if (!a)
504 a = smoothBy2Layers(Gbisect, bipartvertex, &nX, BLACK, WHITE);
505 }
506 if ((options[OPTION_MSGLVL] > 2) && (a))
507 printf("\t separator smoothed: S %d, B %d, W %d [cost %7.2f]\n",
508 cwght[GRAY], cwght[BLACK], cwght[WHITE],
509 F(cwght[GRAY], cwght[BLACK], cwght[WHITE]));
510 } while (a);
511
512 free(bipartvertex);
513 }
514
515