Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/KarypisLab/ParMETIS/llms.txt

Use this file to discover all available pages before exploring further.

ParMETIS_V3_RefineKway improves an existing partition of a distributed graph by applying multilevel k-way refinement. Unlike the full partitioning routines, it takes the current partition assignment as its starting point and optimizes it locally, which is faster but may not escape poor initial configurations. This function is well suited for situations where a valid partition already exists and only incremental improvement is needed. The part array serves as both input (the initial partition) and output (the refined partition). 
int ParMETIS_V3_RefineKway(
    idx_t *vtxdist, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
    idx_t *adjwgt, idx_t *wgtflag, idx_t *numflag, idx_t *ncon, idx_t *nparts,
    real_t *tpwgts, real_t *ubvec, idx_t *options, idx_t *edgecut,
    idx_t *part, MPI_Comm *comm);

​
Parameters

​
vtxdist
idx_t*
Distribution of vertices across processes. vtxdist[i] is the global index of the first vertex on process i. Size npes + 1; must be identical on all processes.
​
xadj
idx_t*
Local adjacency row pointers in CSR format. Size local_nvtxs + 1.
​
adjncy
idx_t*
Local adjacency column indices in CSR format. Size xadj[local_nvtxs].
​
vwgt
idx_t*
Vertex weights. ncon values per vertex in interleaved order. May be NULL when bit 1 of wgtflag is 0.
​
adjwgt
idx_t*
Edge weights, one value per entry in adjncy. May be NULL when bit 0 of wgtflag is 0.
​
wgtflag
idx_t*
Bitmask controlling which weights are used. 0 = no weights, 1 = edge weights only, 2 = vertex weights only, 3 = both.
​
numflag
idx_t*
Indexing convention. 0 for C-style 0-based indexing; 1 for Fortran-style 1-based indexing.
​
ncon
idx_t*
Number of balancing constraints per vertex.
​
nparts
idx_t*
Number of partitions. Should match the number of distinct partition IDs already present in part.
​
tpwgts
real_t*
Target partition weights. Array of nparts * ncon values. Values for each constraint must sum to 1.0. Pass NULL for equal-weight partitions.
​
ubvec
real_t*
Per-constraint imbalance tolerance. Array of ncon values greater than 1.0.
​
options
idx_t*
Algorithm options. If options[0] = 0, all defaults are used. If options[0] = 1, options[PMV3_OPTION_DBGLVL] (index 1) sets the debug level, options[PMV3_OPTION_SEED] (index 2) sets the random seed, and options[PMV3_OPTION_PSR] (index 3) controls partition-to-process coupling: PARMETIS_PSR_COUPLED (1) when the number of partitions equals the number of processes, PARMETIS_PSR_UNCOUPLED (2) otherwise.
​
edgecut
idx_t*
Output. Total weight of edges crossing partition boundaries after refinement.
​
part
idx_t*
Input and output. On entry, contains the initial partition assignment for each local vertex. On return, contains the refined partition assignment. Caller must allocate at least local_nvtxs elements.
​
comm
MPI_Comm*
Pointer to the MPI communicator covering all participating processes.

​
Return value

Returns METIS_OK (1) on success. Any other value indicates an error.

​
Usage example

#include <parmetis.h>

int main(int argc, char *argv[]) {
    MPI_Init(&argc, &argv);
    MPI_Comm comm = MPI_COMM_WORLD;

    int npes, rank;
    MPI_Comm_size(comm, &npes);
    MPI_Comm_rank(comm, &rank);

    idx_t local_nvtxs = 10;
    idx_t vtxdist[npes + 1];
    for (int i = 0; i <= npes; i++) vtxdist[i] = i * local_nvtxs;

    idx_t xadj[local_nvtxs + 1];
    idx_t adjncy[/* nnz */];

    /* part[] must be pre-populated with an existing partition */
    idx_t part[local_nvtxs]; /* pre-existing partition */

    idx_t wgtflag = 0;
    idx_t numflag = 0;
    idx_t ncon    = 1;
    idx_t nparts  = npes;
    real_t tpwgts[nparts];
    for (int i = 0; i < nparts; i++) tpwgts[i] = 1.0f / nparts;
    real_t ubvec  = 1.05f;

    /* Use coupled mode: nparts == npes */
    idx_t options[4] = {1, 0, 0, PARMETIS_PSR_COUPLED};
    idx_t edgecut;

    int ret = ParMETIS_V3_RefineKway(
        vtxdist, xadj, adjncy,
        NULL, NULL,
        &wgtflag, &numflag, &ncon, &nparts,
        tpwgts, &ubvec, options,
        &edgecut, part, &comm);

    if (ret != METIS_OK) { /* handle error */ }

    MPI_Finalize();
    return 0;
}

Build docs developers (and LLMs) love

Get started for freeTalk to us