KaHIP (Karlsruhe High Quality Partitioning) is a high-performance C++ library and command-line toolkit for graph partitioning, node ordering, and mapping. It implements multilevel partitioning with advanced refinement techniques including Fiduccia-Mattheyses local search, flow-based min-cut refinement, cycle improvements, and tabu search. The library provides a C API for integration into external applications, along with Python bindings and a Java JNI wrapper. The codebase includes both a sequential version and a distributed-memory parallel version (ParHIP) using MPI, enabling partitioning of large graphs on clusters. Core algorithms are well-structured with modular coarsening, initial partitioning, and uncoarsening/refinement phases, supporting multiple matching strategies (GPA, random, label propagation) and quality/speed trade-offs via preconfigured modes (Strong, Eco, Fast, Social). Despite research-grade complexity and some code duplication between serial and parallel variants, the library is actively maintained and widely used in scientific computing and graph analytics.
PyMetis is a Python wrapper for the METIS graph partitioning library, providing a high-level API for partitioning graphs and meshes, and for computing sparse matrix orderings (nested dissection). The Python package exposes functions such as `part_graph`, `part_mesh`, and `nested_dissection` via pybind11 bindings to the bundled METIS 5.2.1 C source. The build system (meson-python) compiles the METIS library and GKlib utilities from source, producing a self-contained wheel. The repository also includes a comprehensive test suite that validates partitioning of 2D/3D tetrahedral meshes and graph-based partitions with weighted vertices and edges. While the Python API is clean and straightforward, the project's primary value lies in its reliable integration of a well-established, high-performance C library rather than in novel algorithmic contributions. The codebase is actively maintained, with regular releases, CI/CD pipelines for multiple platforms, and support for both PyPI and conda-forge distributions.