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 10515 2011-07-08 15:46:18Z karypis $
12 *
13 */
14
15 #include "metislib.h"
16
17
18 /*************************************************************************/
19 /*! This function is the entry point of the separator refinement.
20 It does not perform any refinement on graph, but it starts by first
21 projecting it to the next level finer graph and proceeds from there. */
22 /*************************************************************************/
Refine2WayNode(ctrl_t * ctrl,graph_t * orggraph,graph_t * graph)23 void Refine2WayNode(ctrl_t *ctrl, graph_t *orggraph, graph_t *graph)
24 {
25
26 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->UncoarsenTmr));
27
28 if (graph == orggraph) {
29 Compute2WayNodePartitionParams(ctrl, graph);
30 }
31 else {
32 do {
33 graph = graph->finer;
34
35 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->ProjectTmr));
36 Project2WayNodePartition(ctrl, graph);
37 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->ProjectTmr));
38
39 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->RefTmr));
40 FM_2WayNodeBalance(ctrl, graph);
41
42 ASSERT(CheckNodePartitionParams(graph));
43
44 switch (ctrl->rtype) {
45 case METIS_RTYPE_SEP2SIDED:
46 FM_2WayNodeRefine2Sided(ctrl, graph, ctrl->niter);
47 break;
48 case METIS_RTYPE_SEP1SIDED:
49 FM_2WayNodeRefine1Sided(ctrl, graph, ctrl->niter);
50 break;
51 default:
52 gk_errexit(SIGERR, "Unknown rtype of %d\n", ctrl->rtype);
53 }
54 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->RefTmr));
55
56 } while (graph != orggraph);
57 }
58
59 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->UncoarsenTmr));
60 }
61
62
63 /*************************************************************************/
64 /*! This function allocates memory for 2-way node-based refinement */
65 /**************************************************************************/
Allocate2WayNodePartitionMemory(ctrl_t * ctrl,graph_t * graph)66 void Allocate2WayNodePartitionMemory(ctrl_t *ctrl, graph_t *graph)
67 {
68 idx_t nvtxs;
69
70 nvtxs = graph->nvtxs;
71
72 graph->pwgts = imalloc(3, "Allocate2WayNodePartitionMemory: pwgts");
73 graph->where = imalloc(nvtxs, "Allocate2WayNodePartitionMemory: where");
74 graph->bndptr = imalloc(nvtxs, "Allocate2WayNodePartitionMemory: bndptr");
75 graph->bndind = imalloc(nvtxs, "Allocate2WayNodePartitionMemory: bndind");
76 graph->nrinfo = (nrinfo_t *)gk_malloc(nvtxs*sizeof(nrinfo_t), "Allocate2WayNodePartitionMemory: nrinfo");
77 }
78
79
80 /*************************************************************************/
81 /*! This function computes the edegrees[] to the left & right sides */
82 /*************************************************************************/
Compute2WayNodePartitionParams(ctrl_t * ctrl,graph_t * graph)83 void Compute2WayNodePartitionParams(ctrl_t *ctrl, graph_t *graph)
84 {
85 idx_t i, j, nvtxs, nbnd;
86 idx_t *xadj, *adjncy, *vwgt;
87 idx_t *where, *pwgts, *bndind, *bndptr, *edegrees;
88 nrinfo_t *rinfo;
89 idx_t me, other;
90
91 nvtxs = graph->nvtxs;
92 xadj = graph->xadj;
93 vwgt = graph->vwgt;
94 adjncy = graph->adjncy;
95
96 where = graph->where;
97 rinfo = graph->nrinfo;
98 pwgts = iset(3, 0, graph->pwgts);
99 bndind = graph->bndind;
100 bndptr = iset(nvtxs, -1, graph->bndptr);
101
102
103 /*------------------------------------------------------------
104 / Compute now the separator external degrees
105 /------------------------------------------------------------*/
106 nbnd = 0;
107 for (i=0; i<nvtxs; i++) {
108 me = where[i];
109 pwgts[me] += vwgt[i];
110
111 ASSERT(me >=0 && me <= 2);
112
113 if (me == 2) { /* If it is on the separator do some computations */
114 BNDInsert(nbnd, bndind, bndptr, i);
115
116 edegrees = rinfo[i].edegrees;
117 edegrees[0] = edegrees[1] = 0;
118
119 for (j=xadj[i]; j<xadj[i+1]; j++) {
120 other = where[adjncy[j]];
121 if (other != 2)
122 edegrees[other] += vwgt[adjncy[j]];
123 }
124 }
125 }
126
127 ASSERT(CheckNodeBnd(graph, nbnd));
128
129 graph->mincut = pwgts[2];
130 graph->nbnd = nbnd;
131 }
132
133
134 /*************************************************************************/
135 /*! This function projects the node-based bisection */
136 /*************************************************************************/
Project2WayNodePartition(ctrl_t * ctrl,graph_t * graph)137 void Project2WayNodePartition(ctrl_t *ctrl, graph_t *graph)
138 {
139 idx_t i, j, nvtxs;
140 idx_t *cmap, *where, *cwhere;
141 graph_t *cgraph;
142
143 cgraph = graph->coarser;
144 cwhere = cgraph->where;
145
146 nvtxs = graph->nvtxs;
147 cmap = graph->cmap;
148
149 Allocate2WayNodePartitionMemory(ctrl, graph);
150 where = graph->where;
151
152 /* Project the partition */
153 for (i=0; i<nvtxs; i++) {
154 where[i] = cwhere[cmap[i]];
155 ASSERTP(where[i] >= 0 && where[i] <= 2, ("%"PRIDX" %"PRIDX" %"PRIDX" %"PRIDX"\n",
156 i, cmap[i], where[i], cwhere[cmap[i]]));
157 }
158
159 FreeGraph(&graph->coarser);
160 graph->coarser = NULL;
161
162 Compute2WayNodePartitionParams(ctrl, graph);
163 }
164