This file contains the top level routines for the multilevel recursive bisection algorithm PMETIS. More...
#include "metislib.h"
Go to the source code of this file.
Functions | |
| int | METIS_PartGraphRecursive (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) |
| Recursive partitioning routine. More... | |
| idx_t | MlevelRecursiveBisection (ctrl_t *ctrl, graph_t *graph, idx_t nparts, idx_t *part, real_t *tpwgts, idx_t fpart) |
| idx_t | MultilevelBisect (ctrl_t *ctrl, graph_t *graph, real_t *tpwgts) |
| void | SplitGraphPart (ctrl_t *ctrl, graph_t *graph, graph_t **r_lgraph, graph_t **r_rgraph) |
Detailed Description
This file contains the top level routines for the multilevel recursive bisection algorithm PMETIS.
- Date
- Started 7/24/1997
- Version
$Id: pmetis.c 10513 2011-07-07 22:06:03Z karypis $
Definition in file pmetis.c.
Function Documentation
| int METIS_PartGraphRecursive | ( | 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 | ||
| ) |
Recursive partitioning routine.
This function computes a partitioning of a graph based on multilevel recursive bisection. It can be used to partition a graph into k parts. The objective of the partitioning is to minimize the edgecut subject to one or more balancing constraints.
- Parameters
-
[in] nvtxs is the number of vertices in the graph. [in] ncon is the number of balancing constraints. For the standard partitioning problem in which each vertex is either unweighted or has a single weight, ncon should be 1. [in] xadj is an array of size nvtxs+1 used to specify the starting positions of the adjacency structure of the vertices in the adjncy array. [in] adjncy is an array of size to the sum of the degrees of the graph that stores for each vertex the set of vertices that is adjancent to. [in] vwgt is an array of size nvtxs*ncon that stores the weights of the vertices for each constraint. The ncon weights for the ith vertex are stored in the ncon consecutive locations starting at vwgt[i*ncon]. When ncon==1, a NULL value can be passed indicating that all the vertices in the graph have the same weight. [in] adjwgt is an array of size equal to adjncy, specifying the weight for each edge (i.e., adjwgt[j] corresponds to the weight of the edge stored in adjncy[j]). A NULL value can be passed indicating that all the edges in the graph have the same weight. [in] nparts is the number of desired partitions. [in] tpwgts is an array of size nparts*ncon that specifies the desired weight for each part and constraint. The {target partition weight} for the ith part and jth constraint is specified at tpwgts[i*ncon+j] (the numbering of i and j starts from 0). For each constraint, the sum of the tpwgts[] entries must be 1.0 (i.e., ![$ \sum_i tpwgts[i*ncon+j] = 1.0 $](form_307.png)
). A NULL value can be passed indicating that the graph should be equally divided among the parts.[in] ubvec is an array of size ncon that specifies the allowed load imbalance tolerance for each constraint. For the ith part and jth constraint the allowed weight is the ubvec[j]*tpwgts[i*ncon+j] fraction of the jth's constraint total weight. The load imbalances must be greater than 1.0. A NULL value can be passed indicating that the load imbalance tolerance for each constraint should be 1.001 (for ncon==1) or 1.01 (for ncon>1).
[in] options is the array for passing additional parameters in order to customize the behaviour of the partitioning algorithm.
[out] edgecut stores the cut of the partitioning.
[out] part is an array of size nvtxs used to store the computed partitioning. The partition number for the ith vertex is stored in part[i]. Based on the numflag parameter, the numbering of the parts starts from either 0 or 1.
- Returns
- Return values
-
METIS_OK indicates that the function returned normally. METIS_ERROR_INPUT indicates an input error. METIS_ERROR_MEMORY indicates that it could not allocate the required memory.