1 /*!
2 \file
3 \brief The top-level routines for multilevel k-way partitioning that minimizes
4 the edge cut.
5
6 \date Started 7/28/1997
7 \author George
8 \author Copyright 1997-2011, Regents of the University of Minnesota
9 \version\verbatim $Id: kmetis.c 13905 2013-03-25 13:21:20Z karypis $ \endverbatim
10 */
11
12 #include "metislib.h"
13
14
15 /*************************************************************************/
16 /*! This function is the entry point for MCKMETIS */
17 /*************************************************************************/
METIS_PartGraphKway(idx_t * nvtxs,idx_t * ncon,idx_t * xadj,idx_t * adjncy,idx_t * vwgt,idx_t * vsize,idx_t * adjwgt,idx_t * nparts,real_t * tpwgts,real_t * ubvec,idx_t * options,idx_t * objval,idx_t * part)18 int METIS_PartGraphKway(idx_t *nvtxs, idx_t *ncon, idx_t *xadj, idx_t *adjncy,
19 idx_t *vwgt, idx_t *vsize, idx_t *adjwgt, idx_t *nparts,
20 real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *objval,
21 idx_t *part)
22 {
23 int sigrval=0, renumber=0;
24 graph_t *graph;
25 ctrl_t *ctrl;
26
27 /* set up malloc cleaning code and signal catchers */
28 if (!gk_malloc_init())
29 return METIS_ERROR_MEMORY;
30
31 gk_sigtrap();
32
33 if ((sigrval = gk_sigcatch()) != 0)
34 goto SIGTHROW;
35
36
37 /* set up the run parameters */
38 ctrl = SetupCtrl(METIS_OP_KMETIS, options, *ncon, *nparts, tpwgts, ubvec);
39 if (!ctrl) {
40 gk_siguntrap();
41 return METIS_ERROR_INPUT;
42 }
43
44 /* if required, change the numbering to 0 */
45 if (ctrl->numflag == 1) {
46 Change2CNumbering(*nvtxs, xadj, adjncy);
47 renumber = 1;
48 }
49
50 /* set up the graph */
51 graph = SetupGraph(ctrl, *nvtxs, *ncon, xadj, adjncy, vwgt, vsize, adjwgt);
52
53 /* set up multipliers for making balance computations easier */
54 SetupKWayBalMultipliers(ctrl, graph);
55
56 /* set various run parameters that depend on the graph */
57 ctrl->CoarsenTo = gk_max((*nvtxs)/(20*gk_log2(*nparts)), 30*(*nparts));
58 ctrl->nIparts = (ctrl->CoarsenTo == 30*(*nparts) ? 4 : 5);
59
60 /* take care contiguity requests for disconnected graphs */
61 if (ctrl->contig && !IsConnected(graph, 0))
62 gk_errexit(SIGERR, "METIS Error: A contiguous partition is requested for a non-contiguous input graph.\n");
63
64 /* allocate workspace memory */
65 AllocateWorkSpace(ctrl, graph);
66
67 /* start the partitioning */
68 IFSET(ctrl->dbglvl, METIS_DBG_TIME, InitTimers(ctrl));
69 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->TotalTmr));
70
71 *objval = MlevelKWayPartitioning(ctrl, graph, part);
72
73 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->TotalTmr));
74 IFSET(ctrl->dbglvl, METIS_DBG_TIME, PrintTimers(ctrl));
75
76 /* clean up */
77 FreeCtrl(&ctrl);
78
79 SIGTHROW:
80 /* if required, change the numbering back to 1 */
81 if (renumber)
82 Change2FNumbering(*nvtxs, xadj, adjncy, part);
83
84 gk_siguntrap();
85 gk_malloc_cleanup(0);
86
87 return metis_rcode(sigrval);
88 }
89
90
91 /*************************************************************************/
92 /*! This function computes a k-way partitioning of a graph that minimizes
93 the specified objective function.
94
95 \param ctrl is the control structure
96 \param graph is the graph to be partitioned
97 \param part is the vector that on return will store the partitioning
98
99 \returns the objective value of the partitoning. The partitioning
100 itself is stored in the part vector.
101 */
102 /*************************************************************************/
MlevelKWayPartitioning(ctrl_t * ctrl,graph_t * graph,idx_t * part)103 idx_t MlevelKWayPartitioning(ctrl_t *ctrl, graph_t *graph, idx_t *part)
104 {
105 idx_t i, j, objval=0, curobj=0, bestobj=0;
106 real_t curbal=0.0, bestbal=0.0;
107 graph_t *cgraph;
108 int status;
109
110
111 for (i=0; i<ctrl->ncuts; i++) {
112 cgraph = CoarsenGraph(ctrl, graph);
113
114 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_startcputimer(ctrl->InitPartTmr));
115 AllocateKWayPartitionMemory(ctrl, cgraph);
116
117 /* Release the work space */
118 FreeWorkSpace(ctrl);
119
120 /* Compute the initial partitioning */
121 InitKWayPartitioning(ctrl, cgraph);
122
123 /* Re-allocate the work space */
124 AllocateWorkSpace(ctrl, graph);
125 AllocateRefinementWorkSpace(ctrl, 2*cgraph->nedges);
126
127 IFSET(ctrl->dbglvl, METIS_DBG_TIME, gk_stopcputimer(ctrl->InitPartTmr));
128 IFSET(ctrl->dbglvl, METIS_DBG_IPART,
129 printf("Initial %"PRIDX"-way partitioning cut: %"PRIDX"\n", ctrl->nparts, objval));
130
131 RefineKWay(ctrl, graph, cgraph);
132
133 switch (ctrl->objtype) {
134 case METIS_OBJTYPE_CUT:
135 curobj = graph->mincut;
136 break;
137
138 case METIS_OBJTYPE_VOL:
139 curobj = graph->minvol;
140 break;
141
142 default:
143 gk_errexit(SIGERR, "Unknown objtype: %d\n", ctrl->objtype);
144 }
145
146 curbal = ComputeLoadImbalanceDiff(graph, ctrl->nparts, ctrl->pijbm, ctrl->ubfactors);
147
148 if (i == 0
149 || (curbal <= 0.0005 && bestobj > curobj)
150 || (bestbal > 0.0005 && curbal < bestbal)) {
151 icopy(graph->nvtxs, graph->where, part);
152 bestobj = curobj;
153 bestbal = curbal;
154 }
155
156 FreeRData(graph);
157
158 if (bestobj == 0)
159 break;
160 }
161
162 FreeGraph(&graph);
163
164 return bestobj;
165 }
166
167
168 /*************************************************************************/
169 /*! This function computes the initial k-way partitioning using PMETIS
170 */
171 /*************************************************************************/
InitKWayPartitioning(ctrl_t * ctrl,graph_t * graph)172 void InitKWayPartitioning(ctrl_t *ctrl, graph_t *graph)
173 {
174 idx_t i, ntrials, options[METIS_NOPTIONS], curobj=0, bestobj=0;
175 idx_t *bestwhere=NULL;
176 real_t *ubvec=NULL;
177 int status;
178
179 METIS_SetDefaultOptions(options);
180 options[METIS_OPTION_NITER] = 10;
181 options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
182 options[METIS_OPTION_NO2HOP] = ctrl->no2hop;
183
184
185 ubvec = rmalloc(graph->ncon, "InitKWayPartitioning: ubvec");
186 for (i=0; i<graph->ncon; i++)
187 ubvec[i] = (real_t)pow(ctrl->ubfactors[i], 1.0/log(ctrl->nparts));
188
189
190 switch (ctrl->objtype) {
191 case METIS_OBJTYPE_CUT:
192 case METIS_OBJTYPE_VOL:
193 options[METIS_OPTION_NCUTS] = ctrl->nIparts;
194 status = METIS_PartGraphRecursive(&graph->nvtxs, &graph->ncon,
195 graph->xadj, graph->adjncy, graph->vwgt, graph->vsize,
196 graph->adjwgt, &ctrl->nparts, ctrl->tpwgts, ubvec,
197 options, &curobj, graph->where);
198
199 if (status != METIS_OK)
200 gk_errexit(SIGERR, "Failed during initial partitioning\n");
201
202 break;
203
204 #ifdef XXX /* This does not seem to help */
205 case METIS_OBJTYPE_VOL:
206 bestwhere = imalloc(graph->nvtxs, "InitKWayPartitioning: bestwhere");
207 options[METIS_OPTION_NCUTS] = 2;
208
209 ntrials = (ctrl->nIparts+1)/2;
210 for (i=0; i<ntrials; i++) {
211 status = METIS_PartGraphRecursive(&graph->nvtxs, &graph->ncon,
212 graph->xadj, graph->adjncy, graph->vwgt, graph->vsize,
213 graph->adjwgt, &ctrl->nparts, ctrl->tpwgts, ubvec,
214 options, &curobj, graph->where);
215 if (status != METIS_OK)
216 gk_errexit(SIGERR, "Failed during initial partitioning\n");
217
218 curobj = ComputeVolume(graph, graph->where);
219
220 if (i == 0 || bestobj > curobj) {
221 bestobj = curobj;
222 if (i < ntrials-1)
223 icopy(graph->nvtxs, graph->where, bestwhere);
224 }
225
226 if (bestobj == 0)
227 break;
228 }
229 if (bestobj != curobj)
230 icopy(graph->nvtxs, bestwhere, graph->where);
231
232 break;
233 #endif
234
235 default:
236 gk_errexit(SIGERR, "Unknown objtype: %d\n", ctrl->objtype);
237 }
238
239 gk_free((void **)&ubvec, &bestwhere, LTERM);
240
241 }
242
243
244