separator.c
Go to the documentation of this file.
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 **************************************************************************/
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 
45  icopy(nvtxs, where, graph->where);
46 
47  WCOREPOP;
48 
49  ASSERT(IsSeparable(graph));
50 
51  Compute2WayNodePartitionParams(ctrl, graph);
52 
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 **************************************************************************/
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 
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 {
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 
171 
172  FM_2WayNodeRefine1Sided(ctrl, graph, ctrl->niter);
173 
174  ASSERT(IsSeparable(graph));
175 }
176 
#define FM_2WayNodeRefine2Sided
Definition: rename.h:222
void ConstructSeparator(ctrl_t *ctrl, graph_t *graph)
Definition: separator.c:21
idx_t * bndind
#define Compute2WayNodePartitionParams
Definition: rename.h:229
#define iwspacemalloc
Definition: rename.h:256
idx_t * xadj
idx_t * pwgts
idx_t * bndptr
#define ASSERTP(expr, msg)
Definition: gk_macros.h:131
void ConstructMinCoverSeparator(ctrl_t *ctrl, graph_t *graph)
Definition: separator.c:69
idx_t idx_t * xadj
idx_t * where
#define WCOREPUSH
idx_t nvtxs
mdbglvl_et dbglvl
#define CheckNodePartitionParams
Definition: rename.h:69
NonlinearFactorGraph graph
#define FM_2WayNodeRefine1Sided
Definition: rename.h:223
#define Allocate2WayNodePartitionMemory
Definition: rename.h:228
#define PRIDX
idx_t niter
#define ASSERT(expression)
Definition: ccolamd.c:872
static const Line3 l(Rot3(), 1, 1)
int32_t idx_t
#define IsSeparable
Definition: rename.h:70
idx_t mincut
#define iset
Definition: gklib_rename.h:67
#define icopy
Definition: gklib_rename.h:28
idx_t idx_t idx_t idx_t * where
idx_t * adjncy
#define MinCover
Definition: rename.h:169
idx_t idx_t idx_t * adjncy
#define FreeRData
Definition: rename.h:97
#define WCOREPOP
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
std::ptrdiff_t j


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:35:41