Functions
pmetis.c File Reference

This file contains the top level routines for the multilevel recursive bisection algorithm PMETIS. More...

#include "metislib.h"
Include dependency graph for pmetis.c:

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
Author
George
Copyright 1997-2009, Regents of the University of Minnesota
Version
$Id: pmetis.c 10513 2011-07-07 22:06:03Z karypis $ 

Definition in file pmetis.c.

Function Documentation

◆ METIS_PartGraphRecursive()

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]nvtxsis the number of vertices in the graph.
[in]nconis 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]xadjis an array of size nvtxs+1 used to specify the starting positions of the adjacency structure of the vertices in the adjncy array.
[in]adjncyis 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]vwgtis 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]adjwgtis 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]npartsis the number of desired partitions.
[in]tpwgtsis 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 $). A NULL value can be passed indicating that the graph should be equally divided among the parts.
[in]ubvecis 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.

Returns
Return values
METIS_OKindicates that the function returned normally.
METIS_ERROR_INPUTindicates an input error.
METIS_ERROR_MEMORYindicates that it could not allocate the required memory.

Definition at line 91 of file pmetis.c.

◆ MlevelRecursiveBisection()

idx_t MlevelRecursiveBisection ( ctrl_t ctrl,
graph_t graph,
idx_t  nparts,
idx_t part,
real_t tpwgts,
idx_t  fpart 
)

This function is the top-level driver of the recursive bisection routine.

Definition at line 157 of file pmetis.c.

◆ MultilevelBisect()

idx_t MultilevelBisect ( ctrl_t ctrl,
graph_t graph,
real_t tpwgts 
)

This function performs a multilevel bisection

Definition at line 226 of file pmetis.c.

◆ SplitGraphPart()

void SplitGraphPart ( ctrl_t ctrl,
graph_t graph,
graph_t **  r_lgraph,
graph_t **  r_rgraph 
)

This function splits a graph into two based on its bisection

Definition at line 280 of file pmetis.c.



gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:43:20