Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
srefine.c
Go to the documentation of this file.
1 /*
2  * Copyright 1997, Regents of the University of Minnesota
3  *
4  * srefine.c
5  *
6  * This file contains code for the separator refinement algortihms
7  *
8  * Started 8/1/97
9  * George
10  *
11  * $Id: srefine.c,v 1.1 1998/11/27 17:59:30 karypis Exp $
12  *
13  */
14 
15 #include <metis.h>
16 
17 
18 /*************************************************************************
19 * This function is the entry point of the separator refinement
20 **************************************************************************/
21 void Refine2WayNode(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, float ubfactor)
22 {
23 
25 
26  for (;;) {
27  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
28  if (ctrl->RType != 15)
29  FM_2WayNodeBalance(ctrl, graph, ubfactor);
30 
31  switch (ctrl->RType) {
32  case 1:
33  FM_2WayNodeRefine(ctrl, graph, ubfactor, 8);
34  break;
35  case 2:
36  FM_2WayNodeRefine_OneSided(ctrl, graph, ubfactor, 8);
37  break;
38  case 3:
39  FM_2WayNodeRefine(ctrl, graph, ubfactor, 8);
40  FM_2WayNodeRefine_OneSided(ctrl, graph, ubfactor, 8);
41  break;
42  case 4:
43  FM_2WayNodeRefine_OneSided(ctrl, graph, ubfactor, 8);
44  FM_2WayNodeRefine(ctrl, graph, ubfactor, 8);
45  break;
46  case 5:
47  FM_2WayNodeRefineEqWgt(ctrl, graph, 8);
48  break;
49  }
50  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
51 
52  if (graph == orggraph)
53  break;
54 
55  graph = graph->finer;
56  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
57  Project2WayNodePartition(ctrl, graph);
58  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
59  }
60 
61  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
62 }
63 
64 
65 /*************************************************************************
66 * This function allocates memory for 2-way edge refinement
67 **************************************************************************/
69 {
70  int nvtxs, pad64;
71 
72  nvtxs = graph->nvtxs;
73 
74  pad64 = (3*nvtxs+3)%2;
75 
76  graph->rdata = idxmalloc(3*nvtxs+3+(sizeof(NRInfoType)/sizeof(idxtype))*nvtxs+pad64, "Allocate2WayPartitionMemory: rdata");
77  graph->pwgts = graph->rdata;
78  graph->where = graph->rdata + 3;
79  graph->bndptr = graph->rdata + nvtxs + 3;
80  graph->bndind = graph->rdata + 2*nvtxs + 3;
81  graph->nrinfo = (NRInfoType *)(graph->rdata + 3*nvtxs + 3 + pad64);
82 }
83 
84 
85 
86 /*************************************************************************
87 * This function computes the initial id/ed
88 **************************************************************************/
90 {
91  int i, j, k, l, nvtxs, nbnd;
92  idxtype *xadj, *adjncy, *adjwgt, *vwgt;
93  idxtype *where, *pwgts, *bndind, *bndptr, *edegrees;
94  NRInfoType *rinfo;
95  int me, other;
96 
97  nvtxs = graph->nvtxs;
98  xadj = graph->xadj;
99  vwgt = graph->vwgt;
100  adjncy = graph->adjncy;
101  adjwgt = graph->adjwgt;
102 
103  where = graph->where;
104  rinfo = graph->nrinfo;
105  pwgts = idxset(3, 0, graph->pwgts);
106  bndind = graph->bndind;
107  bndptr = idxset(nvtxs, -1, graph->bndptr);
108 
109 
110  /*------------------------------------------------------------
111  / Compute now the separator external degrees
112  /------------------------------------------------------------*/
113  nbnd = 0;
114  for (i=0; i<nvtxs; i++) {
115  me = where[i];
116  pwgts[me] += vwgt[i];
117 
118  ASSERT(me >=0 && me <= 2);
119 
120  if (me == 2) { /* If it is on the separator do some computations */
121  BNDInsert(nbnd, bndind, bndptr, i);
122 
123  edegrees = rinfo[i].edegrees;
124  edegrees[0] = edegrees[1] = 0;
125 
126  for (j=xadj[i]; j<xadj[i+1]; j++) {
127  other = where[adjncy[j]];
128  if (other != 2)
129  edegrees[other] += vwgt[adjncy[j]];
130  }
131  }
132  }
133 
134  ASSERT(CheckNodeBnd(graph, nbnd));
135 
136  graph->mincut = pwgts[2];
137  graph->nbnd = nbnd;
138 }
139 
140 
141 /*************************************************************************
142 * This function computes the initial id/ed
143 **************************************************************************/
145 {
146  int i, j, nvtxs;
147  idxtype *cmap, *where, *cwhere;
148  GraphType *cgraph;
149 
150  cgraph = graph->coarser;
151  cwhere = cgraph->where;
152 
153  nvtxs = graph->nvtxs;
154  cmap = graph->cmap;
155 
156  Allocate2WayNodePartitionMemory(ctrl, graph);
157  where = graph->where;
158 
159  /* Project the partition */
160  for (i=0; i<nvtxs; i++) {
161  where[i] = cwhere[cmap[i]];
162  ASSERTP(where[i] >= 0 && where[i] <= 2, ("%d %d %d %d\n", i, cmap[i], where[i], cwhere[cmap[i]]));
163  }
164 
165  FreeGraph(graph->coarser);
166  graph->coarser = NULL;
167 
168  Compute2WayNodePartitionParams(ctrl, graph);
169 }
NRInfoType * nrinfo
Definition: struct.h:190
timer ProjectTmr
Definition: struct.h:230
timer RefTmr
Definition: struct.h:230
#define Compute2WayNodePartitionParams
Definition: rename.h:351
idxtype * pwgts
Definition: struct.h:176
idxtype * cmap
Definition: struct.h:172
#define CheckNodeBnd
Definition: rename.h:46
int nbnd
Definition: struct.h:177
#define FreeGraph
Definition: rename.h:169
#define BNDInsert(nbnd, bndind, bndptr, vtx)
Definition: macros.h:102
int mincut
Definition: struct.h:175
idxtype * bndptr
Definition: struct.h:178
idxtype * rdata
Definition: struct.h:157
struct graphdef * coarser
Definition: struct.h:198
#define stoptimer(tmr)
Definition: macros.h:54
struct graphdef * finer
Definition: struct.h:198
HitTile_Vector graph
#define Allocate2WayNodePartitionMemory
Definition: rename.h:350
idxtype * where
Definition: struct.h:176
int idxtype
Definition: struct.h:19
#define IFSET(a, flag, cmd)
Definition: macros.h:61
int dbglvl
Definition: struct.h:216
#define Project2WayNodePartition
Definition: rename.h:352
#define Refine2WayNode
Definition: rename.h:349
#define idxset
Definition: rename.h:390
idxtype * adjwgt
Definition: struct.h:166
#define ASSERTP(expr, msg)
Definition: macros.h:142
idxtype * bndind
Definition: struct.h:178
timer UncoarsenTmr
Definition: struct.h:230
#define FM_2WayNodeRefine_OneSided
Definition: rename.h:343
#define FM_2WayNodeRefineEqWgt
Definition: rename.h:342
#define FM_2WayNodeRefine
Definition: rename.h:341
idxtype * vwgt
Definition: struct.h:163
#define FM_2WayNodeBalance
Definition: rename.h:344
#define DBG_TIME
Definition: defs.h:154
int RType
Definition: struct.h:219
#define idxmalloc
Definition: rename.h:383
idxtype edegrees[2]
Definition: struct.h:147
int nvtxs
Definition: struct.h:161
#define ASSERT(expr)
Definition: macros.h:130
idxtype * adjncy
Definition: struct.h:165
idxtype * xadj
Definition: struct.h:162
#define starttimer(tmr)
Definition: macros.h:53