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 | |
---|
24 | IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr)); |
---|
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 | **************************************************************************/ |
---|
68 | void Allocate2WayNodePartitionMemory(CtrlType *ctrl, GraphType *graph) |
---|
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 | **************************************************************************/ |
---|
89 | void Compute2WayNodePartitionParams(CtrlType *ctrl, GraphType *graph) |
---|
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 | **************************************************************************/ |
---|
144 | void Project2WayNodePartition(CtrlType *ctrl, GraphType *graph) |
---|
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 | } |
---|