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) |
This file contains the top level routines for the multilevel recursive bisection algorithm PMETIS.
$Id: pmetis.c 10513 2011-07-07 22:06:03Z karypis $
Definition in file pmetis.c.
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.
[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., ). 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). |
\params[in] options is the array for passing additional parameters in order to customize the behaviour of the partitioning algorithm.
\params[out] edgecut stores the cut of the partitioning.
\params[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.
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. |