Documentation Index
Fetch the complete documentation index at: https://mintlify.com/KarypisLab/METIS/llms.txt
Use this file to discover all available pages before exploring further.
METIS ships with both command-line tools and a C library API. The CLI tools let you partition graphs and compute orderings directly from the terminal using the sample graphs included in the repository. The C API gives you full control from your own programs by calling METIS functions directly. This guide covers both approaches using the 4elt.graph finite element mesh included in the graphs/ directory.
CLI usage
After installing METIS, the following programs are available in your <prefix>/bin directory:| Program | Purpose |
|---|
gpmetis | Partition a graph into k parts |
ndmetis | Compute a nested dissection ordering for sparse matrix fill reduction |
mpmetis | Partition a finite element mesh |
m2gmetis | Convert a mesh to a graph |
graphchk | Validate a graph file |
cmpfillin | Compare fill-in of two orderings |
Partition a graph into 4 parts
The gpmetis command takes a graph file and the number of desired partitions:gpmetis graphs/4elt.graph 4
./build/programs/gpmetis graphs/4elt.graph 4
******************************************************************************
METIS 5.2.1 Copyright 1998-2020, Regents of the University of Minnesota
(HEAD: , )
size of idx_t: 32bits, size of real_t: 32bits
Graph Information -----------------------------------------------------------
Name: graphs/4elt.graph, #Vertices: 15606, #Edges: 45878, #Parts: 4
Options Information ---------------------------------------------------------
ptype=kway, objtype=cut, ctype=shem, iptype=grow, rtype=greedy
dbglvl=0, ufactor=1.030, minconn=0, contig=0, nooutput=0
seed=-1, niter=10, ncuts=1
Direct k-way Partitioning --------------------------------------------------
...
- Edgecut: 716, communication volume: 641
Timing Information ---------------------------------------------------------
I/O: 0.001 sec
Partitioning: 0.018 sec (METIS time)
Total: 0.019 sec
Completed.
******************************************************************************
<graphfile>.part.<k> (here: graphs/4elt.graph.part.4). Each line i contains the partition number (0-indexed) assigned to vertex i.Compute a sparse matrix ordering
The ndmetis command computes a nested dissection ordering that reduces fill-in when factoring a sparse matrix:ndmetis graphs/4elt.graph
./build/programs/ndmetis graphs/4elt.graph
graphs/4elt.graph.iperm — the inverse permutation (node → reordered position)graphs/4elt.graph.perm — the forward permutation (reordered position → original node)
Validate a graph file
Before partitioning, you can check that a graph file is well-formed:graphchk graphs/4elt.graph
C API usage
The METIS C API lets you partition graphs directly from your own programs. All public functions return a status code, and options are configured through an integer array initialized by METIS_SetDefaultOptions.Function signature
The primary graph partitioning function is METIS_PartGraphKway, which performs direct k-way partitioning:int METIS_PartGraphKway(
idx_t *nvtxs, /* number of vertices */
idx_t *ncon, /* number of balancing constraints */
idx_t *xadj, /* adjacency structure: row pointers (CSR) */
idx_t *adjncy, /* adjacency structure: column indices (CSR) */
idx_t *vwgt, /* vertex weights (NULL = unweighted) */
idx_t *vsize, /* vertex communication sizes (NULL = ignore) */
idx_t *adjwgt, /* edge weights (NULL = unweighted) */
idx_t *nparts, /* number of desired partitions */
real_t *tpwgts, /* target partition weights (NULL = equal) */
real_t *ubvec, /* imbalance tolerance per constraint (NULL = default 1.03) */
idx_t *options, /* options array (NULL = all defaults) */
idx_t *edgecut, /* output: number of edges cut */
idx_t *part /* output: partition assignment per vertex */
);
xadj has nvtxs + 1 entries; xadj[i] is the index into adjncy where vertex i’s neighbors begin.adjncy lists all neighbors consecutively.
Complete example
The following program partitions a simple 6-vertex graph into 2 parts:#include <stdio.h>
#include <stdlib.h>
#include "metis.h"
int main(void) {
/*
* A simple undirected graph with 6 vertices and 7 edges:
*
* 0 -- 1 -- 2
* | |
* 3 -- 4 -- 5
*
* Stored in CSR format.
*/
idx_t nvtxs = 6; /* number of vertices */
idx_t ncon = 1; /* number of balancing constraints */
idx_t nparts = 2; /* partition into 2 parts */
/* xadj[i] to xadj[i+1] gives the range of neighbors for vertex i */
idx_t xadj[7] = { 0, 2, 4, 6, 8, 10, 12 };
idx_t adjncy[12] = { 1, 3, /* neighbors of vertex 0 */
0, 2, /* neighbors of vertex 1 */
1, 5, /* neighbors of vertex 2 */
0, 4, /* neighbors of vertex 3 */
3, 5, /* neighbors of vertex 4 */
4, 2 }; /* neighbors of vertex 5 */
idx_t part[6]; /* output: partition assignment per vertex */
idx_t edgecut; /* output: number of edges crossing partitions */
/* Initialize options array to defaults */
idx_t options[METIS_NOPTIONS];
METIS_SetDefaultOptions(options);
int ret = METIS_PartGraphKway(
&nvtxs, &ncon,
xadj, adjncy,
NULL, /* no vertex weights */
NULL, /* no vertex communication sizes */
NULL, /* no edge weights */
&nparts,
NULL, /* equal target partition weights */
NULL, /* default imbalance tolerance */
options,
&edgecut,
part
);
if (ret != METIS_OK) {
fprintf(stderr, "METIS_PartGraphKway failed with code %d\n", ret);
return 1;
}
printf("Edge cut: %d\n", (int)edgecut);
for (idx_t i = 0; i < nvtxs; i++) {
printf(" vertex %d -> partition %d\n", (int)i, (int)part[i]);
}
return 0;
}
Compiling and linking
Compile the program and link against libmetis. Make sure the compiler can find the METIS header and library under your install prefix (default ~/local):gcc -o partition partition.c \
-I~/local/include \
-L~/local/lib \
-lmetis
gcc -o partition partition.c \
-I~/local/include \
-L~/local/lib \
-lmetis -lGKlib -lm
Return codes
All METIS API functions return one of four status codes. Always check the return value before using the output arrays.| Code | Value | Meaning |
|---|
METIS_OK | 1 | Completed successfully |
METIS_ERROR_INPUT | -2 | Bad input arguments or options |
METIS_ERROR_MEMORY | -3 | Could not allocate required memory |
METIS_ERROR | -4 | An unspecified internal error occurred |
Setting options
METIS_SetDefaultOptions initializes the entire options array to -1, which causes each option to use its built-in default. Override individual options using the METIS_OPTION_* enum constants, for example:idx_t options[METIS_NOPTIONS];
METIS_SetDefaultOptions(options);
/* Request contiguous partitions */
options[METIS_OPTION_CONTIG] = 1;
/* Set a fixed random seed for reproducibility */
options[METIS_OPTION_SEED] = 42;
