METIS

METIS is a set of serial C programs and callable library routines for partitioning graphs, partitioning finite-element meshes, and computing fill-reducing orderings for sparse matrices. It was developed by George Karypis and the Karypis Lab at the University of Minnesota, first released in the late 1990s and still maintained (current version 5.1.0) on GitHub. The package comprises over 35,000 lines of ANSI C and is the reference implementation of multilevel graph partitioning, an approach that coarsens a graph into successively smaller graphs, partitions the smallest, and then projects and refines the partition back up to the original.

The command-line tools expose distinct tasks: gpmetis partitions a graph (via multilevel recursive bisection or direct multilevel k-way partitioning), ndmetis computes nested-dissection fill-reducing orderings for sparse-matrix factorization, and mpmetis, m2gmetis, and related utilities handle meshes. METIS optimizes objectives such as minimizing edge cut or total communication volume while keeping partitions balanced, and supports multi-constraint (multi-weight) balancing.

METIS defines its own compact plain-text graph format, format:metis, which the catalog also knows as the Chaco format (format:chaco) used by tool:chaco. A file has n+1 lines: a header giving the vertex count, edge count, and an optional fmt flag plus a constraint count ncon; each following line is the 1-indexed adjacency list for one vertex, optionally interleaved with vertex weights and edge weights. Because it stores only integer adjacency and weights with no attribute or layout metadata, it is a natural fit for the sparse-matrix formats used in scientific computing, such as format:matrix-market and format:harwell-boeing.

Within the graph-tooling ecosystem METIS is the de-facto partitioning backend rather than a general analysis or format-conversion tool. Its parallel siblings ParMETIS (MPI, distributed memory) and mt-METIS (OpenMP, shared memory) scale it to large simulations, while hMETIS handles hypergraph and VLSI circuit partitioning. Bindings such as networkx-metis wrap it for tool:networkx, and it is widely used from tool:igraph, tool:graph-tool, and PDE/finite-element solvers.

Strengths are fast, high-quality, reproducible partitions on very large sparse graphs, a stable interface, and broad adoption. Limitations: the file format carries no node labels, coordinates, or typed attributes, so it is lossy for richer graph exchange; the core is serial; and the ParMETIS and hMETIS binaries are restricted to non-commercial and government use, unlike the more permissively licensed core METIS.