1 /*
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 10481 2011-07-05 18:01:23Z karypis $
12 *
13 */
14
15 #include "metislib.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 **************************************************************************/
ConstructSeparator(ctrl_t * ctrl,graph_t * graph)21 void ConstructSeparator(ctrl_t *ctrl, graph_t *graph)
22 {
23 idx_t i, j, k, nvtxs, nbnd;
24 idx_t *xadj, *where, *bndind;
25
26 WCOREPUSH;
27
28 nvtxs = graph->nvtxs;
29 xadj = graph->xadj;
30 nbnd = graph->nbnd;
31 bndind = graph->bndind;
32
33 where = icopy(nvtxs, graph->where, iwspacemalloc(ctrl, nvtxs));
34
35 /* Put the nodes in the boundary into the separator */
36 for (i=0; i<nbnd; i++) {
37 j = bndind[i];
38 if (xadj[j+1]-xadj[j] > 0) /* Ignore islands */
39 where[j] = 2;
40 }
41
42 FreeRData(graph);
43
44 Allocate2WayNodePartitionMemory(ctrl, graph);
45 icopy(nvtxs, where, graph->where);
46
47 WCOREPOP;
48
49 ASSERT(IsSeparable(graph));
50
51 Compute2WayNodePartitionParams(ctrl, graph);
52
53 ASSERT(CheckNodePartitionParams(graph));
54
55 FM_2WayNodeRefine2Sided(ctrl, graph, 1);
56 FM_2WayNodeRefine1Sided(ctrl, graph, 4);
57
58 ASSERT(IsSeparable(graph));
59
60 }
61
62
63
64 /*************************************************************************
65 * This function takes a bisection and constructs a minimum weight vertex
66 * separator out of it. It uses an unweighted minimum-cover algorithm
67 * followed by node-based separator refinement.
68 **************************************************************************/
ConstructMinCoverSeparator(ctrl_t * ctrl,graph_t * graph)69 void ConstructMinCoverSeparator(ctrl_t *ctrl, graph_t *graph)
70 {
71 idx_t i, ii, j, jj, k, l, nvtxs, nbnd, bnvtxs[3], bnedges[2], csize;
72 idx_t *xadj, *adjncy, *bxadj, *badjncy;
73 idx_t *where, *bndind, *bndptr, *vmap, *ivmap, *cover;
74
75 WCOREPUSH;
76
77 nvtxs = graph->nvtxs;
78 xadj = graph->xadj;
79 adjncy = graph->adjncy;
80
81 nbnd = graph->nbnd;
82 bndind = graph->bndind;
83 bndptr = graph->bndptr;
84 where = graph->where;
85
86 vmap = iwspacemalloc(ctrl, nvtxs);
87 ivmap = iwspacemalloc(ctrl, nbnd);
88 cover = iwspacemalloc(ctrl, nbnd);
89
90 if (nbnd > 0) {
91 /* Go through the boundary and determine the sizes of the bipartite graph */
92 bnvtxs[0] = bnvtxs[1] = bnedges[0] = bnedges[1] = 0;
93 for (i=0; i<nbnd; i++) {
94 j = bndind[i];
95 k = where[j];
96 if (xadj[j+1]-xadj[j] > 0) {
97 bnvtxs[k]++;
98 bnedges[k] += xadj[j+1]-xadj[j];
99 }
100 }
101
102 bnvtxs[2] = bnvtxs[0]+bnvtxs[1];
103 bnvtxs[1] = bnvtxs[0];
104 bnvtxs[0] = 0;
105
106 bxadj = iwspacemalloc(ctrl, bnvtxs[2]+1);
107 badjncy = iwspacemalloc(ctrl, bnedges[0]+bnedges[1]+1);
108
109 /* Construct the ivmap and vmap */
110 ASSERT(iset(nvtxs, -1, vmap) == vmap);
111 for (i=0; i<nbnd; i++) {
112 j = bndind[i];
113 k = where[j];
114 if (xadj[j+1]-xadj[j] > 0) {
115 vmap[j] = bnvtxs[k];
116 ivmap[bnvtxs[k]++] = j;
117 }
118 }
119
120 /* OK, go through and put the vertices of each part starting from 0 */
121 bnvtxs[1] = bnvtxs[0];
122 bnvtxs[0] = 0;
123 bxadj[0] = l = 0;
124 for (k=0; k<2; k++) {
125 for (ii=0; ii<nbnd; ii++) {
126 i = bndind[ii];
127 if (where[i] == k && xadj[i] < xadj[i+1]) {
128 for (j=xadj[i]; j<xadj[i+1]; j++) {
129 jj = adjncy[j];
130 if (where[jj] != k) {
131 ASSERT(bndptr[jj] != -1);
132 ASSERTP(vmap[jj] != -1, ("%"PRIDX" %"PRIDX" %"PRIDX"\n", jj, vmap[jj], graph->bndptr[jj]));
133 badjncy[l++] = vmap[jj];
134 }
135 }
136 bxadj[++bnvtxs[k]] = l;
137 }
138 }
139 }
140
141 ASSERT(l <= bnedges[0]+bnedges[1]);
142
143 MinCover(bxadj, badjncy, bnvtxs[0], bnvtxs[1], cover, &csize);
144
145 IFSET(ctrl->dbglvl, METIS_DBG_SEPINFO,
146 printf("Nvtxs: %6"PRIDX", [%5"PRIDX" %5"PRIDX"], Cut: %6"PRIDX", SS: [%6"PRIDX" %6"PRIDX"], Cover: %6"PRIDX"\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, bnvtxs[0], bnvtxs[1]-bnvtxs[0], csize));
147
148 for (i=0; i<csize; i++) {
149 j = ivmap[cover[i]];
150 where[j] = 2;
151 }
152 }
153 else {
154 IFSET(ctrl->dbglvl, METIS_DBG_SEPINFO,
155 printf("Nvtxs: %6"PRIDX", [%5"PRIDX" %5"PRIDX"], Cut: %6"PRIDX", SS: [%6"PRIDX" %6"PRIDX"], Cover: %6"PRIDX"\n", nvtxs, graph->pwgts[0], graph->pwgts[1], graph->mincut, (idx_t)0, (idx_t)0, (idx_t)0));
156 }
157
158 /* Prepare to refine the vertex separator */
159 icopy(nvtxs, graph->where, vmap);
160
161 FreeRData(graph);
162
163 Allocate2WayNodePartitionMemory(ctrl, graph);
164 icopy(nvtxs, vmap, graph->where);
165
166 WCOREPOP;
167
168 Compute2WayNodePartitionParams(ctrl, graph);
169
170 ASSERT(CheckNodePartitionParams(graph));
171
172 FM_2WayNodeRefine1Sided(ctrl, graph, ctrl->niter);
173
174 ASSERT(IsSeparable(graph));
175 }
176
177