2 * Copyright 1997, Regents of the University of Minnesota
6 * This file contains top level routines that are used by ParMETIS
11 * $Id: parmetis.c 10481 2011-07-05 18:01:23Z karypis $
18 /*************************************************************************/
19 /*! This function is the entry point for the node ND code for ParMETIS.
20 The difference between this routine and the standard METIS_NodeND are
23 - It performs at least log2(npes) levels of nested dissection.
24 - It stores the size of the log2(npes) top-level separators in the
27 /*************************************************************************/
28 int METIS_NodeNDP(idx_t nvtxs
, idx_t
*xadj
, idx_t
*adjncy
, idx_t
*vwgt
,
29 idx_t npes
, idx_t
*options
, idx_t
*perm
, idx_t
*iperm
, idx_t
*sizes
)
31 idx_t i
, ii
, j
, l
, nnvtxs
=0;
36 ctrl
= SetupCtrl(METIS_OP_OMETIS
, options
, 1, 3, NULL
, NULL
);
37 if (!ctrl
) return METIS_ERROR_INPUT
;
39 IFSET(ctrl
->dbglvl
, METIS_DBG_TIME
, InitTimers(ctrl
));
40 IFSET(ctrl
->dbglvl
, METIS_DBG_TIME
, gk_startcputimer(ctrl
->TotalTmr
));
42 /* compress the graph; not that compression only happens if not prunning
45 cptr
= imalloc(nvtxs
+1, "OMETIS: cptr");
46 cind
= imalloc(nvtxs
, "OMETIS: cind");
48 graph
= CompressGraph(ctrl
, nvtxs
, xadj
, adjncy
, vwgt
, cptr
, cind
);
50 /* if there was no compression, cleanup the compress flag */
51 gk_free((void **)&cptr
, &cind
, LTERM
);
55 nnvtxs
= graph
->nvtxs
;
59 /* if no compression, setup the graph in the normal way. */
60 if (ctrl
->compress
== 0)
61 graph
= SetupGraph(ctrl
, nvtxs
, 1, xadj
, adjncy
, vwgt
, NULL
, NULL
);
64 /* allocate workspace memory */
65 AllocateWorkSpace(ctrl
, graph
);
68 /* do the nested dissection ordering */
69 iset(2*npes
-1, 0, sizes
);
70 MlevelNestedDissectionP(ctrl
, graph
, iperm
, graph
->nvtxs
, npes
, 0, sizes
);
73 /* Uncompress the ordering */
75 /* construct perm from iperm */
76 for (i
=0; i
<nnvtxs
; i
++)
78 for (l
=ii
=0; ii
<nnvtxs
; ii
++) {
80 for (j
=cptr
[i
]; j
<cptr
[i
+1]; j
++)
84 gk_free((void **)&cptr
, &cind
, LTERM
);
88 for (i
=0; i
<nvtxs
; i
++)
91 IFSET(ctrl
->dbglvl
, METIS_DBG_TIME
, gk_stopcputimer(ctrl
->TotalTmr
));
92 IFSET(ctrl
->dbglvl
, METIS_DBG_TIME
, PrintTimers(ctrl
));
101 /*************************************************************************/
102 /*! This function is similar to MlevelNestedDissection with the difference
103 that it also records separator sizes for the top log2(npes) levels */
104 /**************************************************************************/
105 void MlevelNestedDissectionP(ctrl_t
*ctrl
, graph_t
*graph
, idx_t
*order
,
106 idx_t lastvtx
, idx_t npes
, idx_t cpos
, idx_t
*sizes
)
108 idx_t i
, j
, nvtxs
, nbnd
;
109 idx_t
*label
, *bndind
;
110 graph_t
*lgraph
, *rgraph
;
112 nvtxs
= graph
->nvtxs
;
119 MlevelNodeBisectionMultiple(ctrl
, graph
);
121 IFSET(ctrl
->dbglvl
, METIS_DBG_SEPINFO
,
122 printf("Nvtxs: %6"PRIDX
", [%6"PRIDX
" %6"PRIDX
" %6"PRIDX
"]\n",
123 graph
->nvtxs
, graph
->pwgts
[0], graph
->pwgts
[1], graph
->pwgts
[2]));
126 sizes
[2*npes
-2-cpos
] = graph
->pwgts
[2];
127 sizes
[2*npes
-2-(2*cpos
+1)] = graph
->pwgts
[1];
128 sizes
[2*npes
-2-(2*cpos
+2)] = graph
->pwgts
[0];
131 /* Order the nodes in the separator */
133 bndind
= graph
->bndind
;
134 label
= graph
->label
;
135 for (i
=0; i
<nbnd
; i
++)
136 order
[label
[bndind
[i
]]] = --lastvtx
;
138 SplitGraphOrder(ctrl
, graph
, &lgraph
, &rgraph
);
140 /* Free the memory of the top level graph */
143 if ((lgraph
->nvtxs
> MMDSWITCH
|| 2*cpos
+2 < npes
-1) && lgraph
->nedges
> 0)
144 MlevelNestedDissectionP(ctrl
, lgraph
, order
, lastvtx
-rgraph
->nvtxs
, npes
, 2*cpos
+2, sizes
);
146 MMDOrder(ctrl
, lgraph
, order
, lastvtx
-rgraph
->nvtxs
);
149 if ((rgraph
->nvtxs
> MMDSWITCH
|| 2*cpos
+1 < npes
-1) && rgraph
->nedges
> 0)
150 MlevelNestedDissectionP(ctrl
, rgraph
, order
, lastvtx
, npes
, 2*cpos
+1, sizes
);
152 MMDOrder(ctrl
, rgraph
, order
, lastvtx
);
158 /*************************************************************************/
159 /*! This function bisects a graph by computing a vertex separator */
160 /**************************************************************************/
161 int METIS_ComputeVertexSeparator(idx_t
*nvtxs
, idx_t
*xadj
, idx_t
*adjncy
,
162 idx_t
*vwgt
, idx_t
*options
, idx_t
*r_sepsize
, idx_t
*part
)
168 if ((ctrl
= SetupCtrl(METIS_OP_OMETIS
, options
, 1, 3, NULL
, NULL
)) == NULL
)
169 return METIS_ERROR_INPUT
;
171 InitRandom(ctrl
->seed
);
173 graph
= SetupGraph(ctrl
, *nvtxs
, 1, xadj
, adjncy
, vwgt
, NULL
, NULL
);
175 AllocateWorkSpace(ctrl
, graph
);
177 /*============================================================
178 * Perform the bisection
179 *============================================================*/
180 ctrl
->CoarsenTo
= 100;
182 MlevelNodeBisectionMultiple(ctrl
, graph
);
184 *r_sepsize
= graph
->pwgts
[2];
185 icopy(*nvtxs
, graph
->where
, part
);
195 /*************************************************************************/
196 /*! This function is the entry point of a node-based separator refinement
197 of the nodes with an hmarker[] of 0. */
198 /*************************************************************************/
199 int METIS_NodeRefine(idx_t nvtxs
, idx_t
*xadj
, idx_t
*vwgt
, idx_t
*adjncy
,
200 idx_t
*where
, idx_t
*hmarker
, real_t ubfactor
)
205 /* set up the run time parameters */
206 ctrl
= SetupCtrl(METIS_OP_OMETIS
, NULL
, 1, 3, NULL
, NULL
);
207 if (!ctrl
) return METIS_ERROR_INPUT
;
209 /* set up the graph */
210 graph
= SetupGraph(ctrl
, nvtxs
, 1, xadj
, adjncy
, vwgt
, NULL
, NULL
);
212 /* allocate workspace memory */
213 AllocateWorkSpace(ctrl
, graph
);
215 /* set up the memory and the input partition */
216 Allocate2WayNodePartitionMemory(ctrl
, graph
);
217 icopy(nvtxs
, where
, graph
->where
);
219 Compute2WayNodePartitionParams(ctrl
, graph
);
221 FM_2WayNodeRefine1SidedP(ctrl
, graph
, hmarker
, ubfactor
, 10);
222 /* FM_2WayNodeRefine2SidedP(ctrl, graph, hmarker, ubfactor, 10); */
224 icopy(nvtxs
, graph
->where
, where
);
233 /*************************************************************************/
234 /*! This function performs a node-based 1-sided FM refinement that moves
235 only nodes whose hmarker[] == -1. It is used by Parmetis. */
236 /*************************************************************************/
237 void FM_2WayNodeRefine1SidedP(ctrl_t
*ctrl
, graph_t
*graph
,
238 idx_t
*hmarker
, real_t ubfactor
, idx_t npasses
)
240 idx_t i
, ii
, j
, k
, jj
, kk
, nvtxs
, nbnd
, nswaps
, nmind
, nbad
, qsize
;
241 idx_t
*xadj
, *vwgt
, *adjncy
, *where
, *pwgts
, *edegrees
, *bndind
, *bndptr
;
242 idx_t
*mptr
, *mind
, *swaps
, *inqueue
;
245 idx_t higain
, oldgain
, mincut
, initcut
, mincutorder
;
246 idx_t pass
, from
, to
, limit
;
247 idx_t badmaxpwgt
, mindiff
, newdiff
;
251 ASSERT(graph
->mincut
== graph
->pwgts
[2]);
253 nvtxs
= graph
->nvtxs
;
255 adjncy
= graph
->adjncy
;
258 bndind
= graph
->bndind
;
259 bndptr
= graph
->bndptr
;
260 where
= graph
->where
;
261 pwgts
= graph
->pwgts
;
262 rinfo
= graph
->nrinfo
;
264 queue
= rpqCreate(nvtxs
);
266 inqueue
= iset(nvtxs
, -1, iwspacemalloc(ctrl
, nvtxs
));
267 swaps
= iwspacemalloc(ctrl
, nvtxs
);
268 mptr
= iwspacemalloc(ctrl
, nvtxs
+1);
269 mind
= iwspacemalloc(ctrl
, 2*nvtxs
);
271 badmaxpwgt
= (idx_t
)(ubfactor
*gk_max(pwgts
[0], pwgts
[1]));
273 IFSET(ctrl
->dbglvl
, METIS_DBG_REFINE
,
274 printf("Partitions-N1: [%6"PRIDX
" %6"PRIDX
"] Nv-Nb[%6"PRIDX
" %6"PRIDX
"] "
275 "MaxPwgt[%6"PRIDX
"]. ISep: %6"PRIDX
"\n",
276 pwgts
[0], pwgts
[1], graph
->nvtxs
, graph
->nbnd
, badmaxpwgt
,
279 to
= (pwgts
[0] < pwgts
[1] ? 1 : 0);
280 for (pass
=0; pass
<npasses
; pass
++) {
287 initcut
= mincut
= graph
->mincut
;
290 /* use the swaps array in place of the traditional perm array to save memory */
291 irandArrayPermute(nbnd
, swaps
, nbnd
, 1);
292 for (ii
=0; ii
<nbnd
; ii
++) {
293 i
= bndind
[swaps
[ii
]];
294 ASSERT(where
[i
] == 2);
295 if (hmarker
[i
] == -1 || hmarker
[i
] == to
) {
296 rpqInsert(queue
, i
, vwgt
[i
]-rinfo
[i
].edegrees
[from
]);
300 qsize
= rpqLength(queue
);
302 ASSERT(CheckNodeBnd(graph
, nbnd
));
303 ASSERT(CheckNodePartitionParams(graph
));
307 /******************************************************
308 * Get into the FM loop
309 *******************************************************/
310 mptr
[0] = nmind
= nbad
= 0;
311 mindiff
= abs(pwgts
[0]-pwgts
[1]);
312 for (nswaps
=0; nswaps
<nvtxs
; nswaps
++) {
313 if ((higain
= rpqGetTop(queue
)) == -1)
316 ASSERT(bndptr
[higain
] != -1);
318 /* The following check is to ensure we break out if there is a posibility
319 of over-running the mind array. */
320 if (nmind
+ xadj
[higain
+1]-xadj
[higain
] >= 2*nvtxs
-1)
323 inqueue
[higain
] = -1;
325 if (pwgts
[to
]+vwgt
[higain
] > badmaxpwgt
) { /* Skip this vertex */
334 pwgts
[2] -= (vwgt
[higain
]-rinfo
[higain
].edegrees
[from
]);
336 newdiff
= abs(pwgts
[to
]+vwgt
[higain
] - (pwgts
[from
]-rinfo
[higain
].edegrees
[from
]));
337 if (pwgts
[2] < mincut
|| (pwgts
[2] == mincut
&& newdiff
< mindiff
)) {
339 mincutorder
= nswaps
;
344 if (nbad
++ > limit
) {
345 pwgts
[2] += (vwgt
[higain
]-rinfo
[higain
].edegrees
[from
]);
346 break; /* No further improvement, break out */
350 BNDDelete(nbnd
, bndind
, bndptr
, higain
);
351 pwgts
[to
] += vwgt
[higain
];
353 swaps
[nswaps
] = higain
;
356 /**********************************************************
357 * Update the degrees of the affected nodes
358 ***********************************************************/
359 for (j
=xadj
[higain
]; j
<xadj
[higain
+1]; j
++) {
361 if (where
[k
] == 2) { /* For the in-separator vertices modify their edegree[to] */
362 rinfo
[k
].edegrees
[to
] += vwgt
[higain
];
364 else if (where
[k
] == from
) { /* This vertex is pulled into the separator */
365 ASSERTP(bndptr
[k
] == -1, ("%"PRIDX
" %"PRIDX
" %"PRIDX
"\n", k
, bndptr
[k
], where
[k
]));
366 BNDInsert(nbnd
, bndind
, bndptr
, k
);
368 mind
[nmind
++] = k
; /* Keep track for rollback */
370 pwgts
[from
] -= vwgt
[k
];
372 edegrees
= rinfo
[k
].edegrees
;
373 edegrees
[0] = edegrees
[1] = 0;
374 for (jj
=xadj
[k
]; jj
<xadj
[k
+1]; jj
++) {
377 edegrees
[where
[kk
]] += vwgt
[kk
];
379 oldgain
= vwgt
[kk
]-rinfo
[kk
].edegrees
[from
];
380 rinfo
[kk
].edegrees
[from
] -= vwgt
[k
];
382 /* Update the gain of this node if it was not skipped */
383 if (inqueue
[kk
] == pass
)
384 rpqUpdate(queue
, kk
, oldgain
+vwgt
[k
]);
388 /* Insert the new vertex into the priority queue. Safe due to one-sided moves */
389 if (hmarker
[k
] == -1 || hmarker
[k
] == to
) {
390 rpqInsert(queue
, k
, vwgt
[k
]-edegrees
[from
]);
395 mptr
[nswaps
+1] = nmind
;
398 IFSET(ctrl
->dbglvl
, METIS_DBG_MOVEINFO
,
399 printf("Moved %6"PRIDX
" to %3"PRIDX
", Gain: %5"PRIDX
" [%5"PRIDX
"] \t[%5"PRIDX
" %5"PRIDX
" %5"PRIDX
"] [%3"PRIDX
" %2"PRIDX
"]\n",
400 higain
, to
, (vwgt
[higain
]-rinfo
[higain
].edegrees
[from
]),
401 vwgt
[higain
], pwgts
[0], pwgts
[1], pwgts
[2], nswaps
, limit
));
406 /****************************************************************
407 * Roll back computation
408 *****************************************************************/
409 for (nswaps
--; nswaps
>mincutorder
; nswaps
--) {
410 higain
= swaps
[nswaps
];
412 ASSERT(CheckNodePartitionParams(graph
));
413 ASSERT(where
[higain
] == to
);
415 INC_DEC(pwgts
[2], pwgts
[to
], vwgt
[higain
]);
417 BNDInsert(nbnd
, bndind
, bndptr
, higain
);
419 edegrees
= rinfo
[higain
].edegrees
;
420 edegrees
[0] = edegrees
[1] = 0;
421 for (j
=xadj
[higain
]; j
<xadj
[higain
+1]; j
++) {
424 rinfo
[k
].edegrees
[to
] -= vwgt
[higain
];
426 edegrees
[where
[k
]] += vwgt
[k
];
429 /* Push nodes out of the separator */
430 for (j
=mptr
[nswaps
]; j
<mptr
[nswaps
+1]; j
++) {
432 ASSERT(where
[k
] == 2);
434 INC_DEC(pwgts
[from
], pwgts
[2], vwgt
[k
]);
435 BNDDelete(nbnd
, bndind
, bndptr
, k
);
436 for (jj
=xadj
[k
]; jj
<xadj
[k
+1]; jj
++) {
439 rinfo
[kk
].edegrees
[from
] += vwgt
[k
];
444 ASSERT(mincut
== pwgts
[2]);
446 IFSET(ctrl
->dbglvl
, METIS_DBG_REFINE
,
447 printf("\tMinimum sep: %6"PRIDX
" at %5"PRIDX
", PWGTS: [%6"PRIDX
" %6"PRIDX
"], NBND: %6"PRIDX
", QSIZE: %6"PRIDX
"\n",
448 mincut
, mincutorder
, pwgts
[0], pwgts
[1], nbnd
, qsize
));
450 graph
->mincut
= mincut
;
453 if (pass
%2 == 1 && (mincutorder
== -1 || mincut
>= initcut
))
463 /*************************************************************************/
464 /*! This function performs a node-based (two-sided) FM refinement that
465 moves only nodes whose hmarker[] == -1. It is used by Parmetis. */
466 /*************************************************************************/
467 void FM_2WayNodeRefine2SidedP(ctrl_t
*ctrl
, graph_t
*graph
,
468 idx_t
*hmarker
, real_t ubfactor
, idx_t npasses
)
470 idx_t i
, ii
, j
, k
, jj
, kk
, nvtxs
, nbnd
, nswaps
, nmind
;
471 idx_t
*xadj
, *vwgt
, *adjncy
, *where
, *pwgts
, *edegrees
, *bndind
, *bndptr
;
472 idx_t
*mptr
, *mind
, *moved
, *swaps
;
475 idx_t higain
, oldgain
, mincut
, initcut
, mincutorder
;
476 idx_t pass
, to
, other
, limit
;
477 idx_t badmaxpwgt
, mindiff
, newdiff
;
482 nvtxs
= graph
->nvtxs
;
484 adjncy
= graph
->adjncy
;
487 bndind
= graph
->bndind
;
488 bndptr
= graph
->bndptr
;
489 where
= graph
->where
;
490 pwgts
= graph
->pwgts
;
491 rinfo
= graph
->nrinfo
;
493 queues
[0] = rpqCreate(nvtxs
);
494 queues
[1] = rpqCreate(nvtxs
);
496 moved
= iwspacemalloc(ctrl
, nvtxs
);
497 swaps
= iwspacemalloc(ctrl
, nvtxs
);
498 mptr
= iwspacemalloc(ctrl
, nvtxs
+1);
499 mind
= iwspacemalloc(ctrl
, 2*nvtxs
);
501 IFSET(ctrl
->dbglvl
, METIS_DBG_REFINE
,
502 printf("Partitions: [%6"PRIDX
" %6"PRIDX
"] Nv-Nb[%6"PRIDX
" %6"PRIDX
"]. ISep: %6"PRIDX
"\n", pwgts
[0], pwgts
[1], graph
->nvtxs
, graph
->nbnd
, graph
->mincut
));
504 badmaxpwgt
= (idx_t
)(ubfactor
*gk_max(pwgts
[0], pwgts
[1]));
506 for (pass
=0; pass
<npasses
; pass
++) {
507 iset(nvtxs
, -1, moved
);
512 initcut
= mincut
= graph
->mincut
;
515 /* use the swaps array in place of the traditional perm array to save memory */
516 irandArrayPermute(nbnd
, swaps
, nbnd
, 1);
517 for (ii
=0; ii
<nbnd
; ii
++) {
518 i
= bndind
[swaps
[ii
]];
519 ASSERT(where
[i
] == 2);
520 if (hmarker
[i
] == -1) {
521 rpqInsert(queues
[0], i
, vwgt
[i
]-rinfo
[i
].edegrees
[1]);
522 rpqInsert(queues
[1], i
, vwgt
[i
]-rinfo
[i
].edegrees
[0]);
525 else if (hmarker
[i
] != 2) {
526 rpqInsert(queues
[hmarker
[i
]], i
, vwgt
[i
]-rinfo
[i
].edegrees
[(hmarker
[i
]+1)%2]);
527 moved
[i
] = -(10+hmarker
[i
]);
531 ASSERT(CheckNodeBnd(graph
, nbnd
));
532 ASSERT(CheckNodePartitionParams(graph
));
536 /******************************************************
537 * Get into the FM loop
538 *******************************************************/
540 mindiff
= abs(pwgts
[0]-pwgts
[1]);
541 to
= (pwgts
[0] < pwgts
[1] ? 0 : 1);
542 for (nswaps
=0; nswaps
<nvtxs
; nswaps
++) {
543 u
[0] = rpqSeeTopVal(queues
[0]);
544 u
[1] = rpqSeeTopVal(queues
[1]);
545 if (u
[0] != -1 && u
[1] != -1) {
546 g
[0] = vwgt
[u
[0]]-rinfo
[u
[0]].edegrees
[1];
547 g
[1] = vwgt
[u
[1]]-rinfo
[u
[1]].edegrees
[0];
549 to
= (g
[0] > g
[1] ? 0 : (g
[0] < g
[1] ? 1 : pass
%2));
551 if (pwgts
[to
]+vwgt
[u
[to
]] > badmaxpwgt
)
554 else if (u
[0] == -1 && u
[1] == -1) {
557 else if (u
[0] != -1 && pwgts
[0]+vwgt
[u
[0]] <= badmaxpwgt
) {
560 else if (u
[1] != -1 && pwgts
[1]+vwgt
[u
[1]] <= badmaxpwgt
) {
568 higain
= rpqGetTop(queues
[to
]);
570 /* Delete its matching entry in the other queue */
571 if (moved
[higain
] == -5)
572 rpqDelete(queues
[other
], higain
);
574 ASSERT(bndptr
[higain
] != -1);
576 /* The following check is to ensure we break out if there is a posibility
577 of over-running the mind array. */
578 if (nmind
+ xadj
[higain
+1]-xadj
[higain
] >= 2*nvtxs
-1)
581 pwgts
[2] -= (vwgt
[higain
]-rinfo
[higain
].edegrees
[other
]);
583 newdiff
= abs(pwgts
[to
]+vwgt
[higain
] - (pwgts
[other
]-rinfo
[higain
].edegrees
[other
]));
584 if (pwgts
[2] < mincut
|| (pwgts
[2] == mincut
&& newdiff
< mindiff
)) {
586 mincutorder
= nswaps
;
590 if (nswaps
- mincutorder
> limit
) {
591 pwgts
[2] += (vwgt
[higain
]-rinfo
[higain
].edegrees
[other
]);
592 break; /* No further improvement, break out */
596 BNDDelete(nbnd
, bndind
, bndptr
, higain
);
597 pwgts
[to
] += vwgt
[higain
];
599 moved
[higain
] = nswaps
;
600 swaps
[nswaps
] = higain
;
603 /**********************************************************
604 * Update the degrees of the affected nodes
605 ***********************************************************/
606 for (j
=xadj
[higain
]; j
<xadj
[higain
+1]; j
++) {
608 if (where
[k
] == 2) { /* For the in-separator vertices modify their edegree[to] */
609 oldgain
= vwgt
[k
]-rinfo
[k
].edegrees
[to
];
610 rinfo
[k
].edegrees
[to
] += vwgt
[higain
];
611 if (moved
[k
] == -5 || moved
[k
] == -(10+other
))
612 rpqUpdate(queues
[other
], k
, oldgain
-vwgt
[higain
]);
614 else if (where
[k
] == other
) { /* This vertex is pulled into the separator */
615 ASSERTP(bndptr
[k
] == -1, ("%"PRIDX
" %"PRIDX
" %"PRIDX
"\n", k
, bndptr
[k
], where
[k
]));
616 BNDInsert(nbnd
, bndind
, bndptr
, k
);
618 mind
[nmind
++] = k
; /* Keep track for rollback */
620 pwgts
[other
] -= vwgt
[k
];
622 edegrees
= rinfo
[k
].edegrees
;
623 edegrees
[0] = edegrees
[1] = 0;
624 for (jj
=xadj
[k
]; jj
<xadj
[k
+1]; jj
++) {
627 edegrees
[where
[kk
]] += vwgt
[kk
];
629 oldgain
= vwgt
[kk
]-rinfo
[kk
].edegrees
[other
];
630 rinfo
[kk
].edegrees
[other
] -= vwgt
[k
];
631 if (moved
[kk
] == -5 || moved
[kk
] == -(10+to
))
632 rpqUpdate(queues
[to
], kk
, oldgain
+vwgt
[k
]);
636 /* Insert the new vertex into the priority queue (if it has not been moved). */
637 if (moved
[k
] == -1 && (hmarker
[k
] == -1 || hmarker
[k
] == to
)) {
638 rpqInsert(queues
[to
], k
, vwgt
[k
]-edegrees
[other
]);
641 #ifdef FULLMOVES /* this does not work as well as the above partial one */
642 if (moved
[k
] == -1) {
643 if (hmarker
[k
] == -1) {
644 rpqInsert(queues
[0], k
, vwgt
[k
]-edegrees
[1]);
645 rpqInsert(queues
[1], k
, vwgt
[k
]-edegrees
[0]);
648 else if (hmarker
[k
] != 2) {
649 rpqInsert(queues
[hmarker
[k
]], k
, vwgt
[k
]-edegrees
[(hmarker
[k
]+1)%2]);
650 moved
[k
] = -(10+hmarker
[k
]);
656 mptr
[nswaps
+1] = nmind
;
658 IFSET(ctrl
->dbglvl
, METIS_DBG_MOVEINFO
,
659 printf("Moved %6"PRIDX
" to %3"PRIDX
", Gain: %5"PRIDX
" [%5"PRIDX
"] "
660 "[%4"PRIDX
" %4"PRIDX
"] \t[%5"PRIDX
" %5"PRIDX
" %5"PRIDX
"]\n",
661 higain
, to
, g
[to
], g
[other
], vwgt
[u
[to
]], vwgt
[u
[other
]],
662 pwgts
[0], pwgts
[1], pwgts
[2]));
667 /****************************************************************
668 * Roll back computation
669 *****************************************************************/
670 for (nswaps
--; nswaps
>mincutorder
; nswaps
--) {
671 higain
= swaps
[nswaps
];
673 ASSERT(CheckNodePartitionParams(graph
));
677 INC_DEC(pwgts
[2], pwgts
[to
], vwgt
[higain
]);
679 BNDInsert(nbnd
, bndind
, bndptr
, higain
);
681 edegrees
= rinfo
[higain
].edegrees
;
682 edegrees
[0] = edegrees
[1] = 0;
683 for (j
=xadj
[higain
]; j
<xadj
[higain
+1]; j
++) {
686 rinfo
[k
].edegrees
[to
] -= vwgt
[higain
];
688 edegrees
[where
[k
]] += vwgt
[k
];
691 /* Push nodes out of the separator */
692 for (j
=mptr
[nswaps
]; j
<mptr
[nswaps
+1]; j
++) {
694 ASSERT(where
[k
] == 2);
696 INC_DEC(pwgts
[other
], pwgts
[2], vwgt
[k
]);
697 BNDDelete(nbnd
, bndind
, bndptr
, k
);
698 for (jj
=xadj
[k
]; jj
<xadj
[k
+1]; jj
++) {
701 rinfo
[kk
].edegrees
[other
] += vwgt
[k
];
706 ASSERT(mincut
== pwgts
[2]);
708 IFSET(ctrl
->dbglvl
, METIS_DBG_REFINE
,
709 printf("\tMinimum sep: %6"PRIDX
" at %5"PRIDX
", PWGTS: [%6"PRIDX
" %6"PRIDX
"], NBND: %6"PRIDX
"\n", mincut
, mincutorder
, pwgts
[0], pwgts
[1], nbnd
));
711 graph
->mincut
= mincut
;
714 if (mincutorder
== -1 || mincut
>= initcut
)
718 rpqDestroy(queues
[0]);
719 rpqDestroy(queues
[1]);