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 
43 
45  icopy(nvtxs, where, graph->where);
46 
47  WCOREPOP;
48 
50 
52 
54 
55  FM_2WayNodeRefine2Sided(ctrl, graph, 1);
56  FM_2WayNodeRefine1Sided(ctrl, graph, 4);
57 
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 
164  icopy(nvtxs, vmap, graph->where);
165 
166  WCOREPOP;
167 
169 
171 
172  FM_2WayNodeRefine1Sided(ctrl, graph, ctrl->niter);
173 
175 }
176 
FM_2WayNodeRefine2Sided
#define FM_2WayNodeRefine2Sided
Definition: rename.h:222
ctrl_t
Definition: libmetis/struct.h:139
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
IsSeparable
#define IsSeparable
Definition: rename.h:70
IFSET
#define IFSET(a, flag, cmd)
Definition: gk_macros.h:45
CheckNodePartitionParams
#define CheckNodePartitionParams
Definition: rename.h:69
ConstructSeparator
void ConstructSeparator(ctrl_t *ctrl, graph_t *graph)
Definition: separator.c:21
Compute2WayNodePartitionParams
#define Compute2WayNodePartitionParams
Definition: rename.h:229
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
l
static const Line3 l(Rot3(), 1, 1)
WCOREPUSH
#define WCOREPUSH
Definition: metis/libmetis/macros.h:38
FreeRData
#define FreeRData
Definition: rename.h:97
METIS_DBG_SEPINFO
@ METIS_DBG_SEPINFO
Definition: include/metis.h:346
ASSERTP
#define ASSERTP(expr, msg)
Definition: gk_macros.h:131
ASSERT
#define ASSERT(expression)
Definition: ccolamd.c:872
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
iset
#define iset
Definition: gklib_rename.h:67
FM_2WayNodeRefine1Sided
#define FM_2WayNodeRefine1Sided
Definition: rename.h:223
PRIDX
#define PRIDX
Definition: include/metis.h:107
ctrl_t::niter
idx_t niter
Definition: libmetis/struct.h:158
ctrl_t::dbglvl
mdbglvl_et dbglvl
Definition: libmetis/struct.h:142
metislib.h
WCOREPOP
#define WCOREPOP
Definition: metis/libmetis/macros.h:39
where
idx_t idx_t idx_t idx_t * where
Definition: include/metis.h:240
icopy
#define icopy
Definition: gklib_rename.h:28
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
ConstructMinCoverSeparator
void ConstructMinCoverSeparator(ctrl_t *ctrl, graph_t *graph)
Definition: separator.c:69
iwspacemalloc
#define iwspacemalloc
Definition: rename.h:256
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
Allocate2WayNodePartitionMemory
#define Allocate2WayNodePartitionMemory
Definition: rename.h:228
graph_t
Definition: libmetis/struct.h:82
idx_t
int32_t idx_t
Definition: include/metis.h:101
MinCover
#define MinCover
Definition: rename.h:169


gtsam
Author(s):
autogenerated on Sat Nov 16 2024 04:04:10