KaHIP v3.25 =====

Table of Contents

• About
• What's New
• Installation
• Install via Homebrew
• Downloading KaHIP
• Compiling KaHIP
• Running Programs
• Default Partitioning
• Distributed Memory Parallel Partitioning
• Node Separators
• Node Ordering
• Edge Partitioning
• Process Mapping
• ILP Improvements
• Linking the KaHIP Library
• Linking the ParHIP Library
• Using KaHIP in Python
• Licence
• Contributors

The graph partitioning framework KaHIP -- High Quality Partitioning. Part of the KaHIP organization. KaHIP supports Linux, macOS and Windows.

The graph partitioning problem asks for a division of a graph's node set into k equally sized blocks such that the number of edges that run between the blocks is minimized. KaHIP is a family of graph partitioning programs. It includes KaFFPa (Karlsruhe Fast Flow Partitioner), which is a multilevel graph partitioning algorithm, in its variants Strong, Eco and Fast, KaFFPaE (KaFFPaEvolutionary), which is a parallel evolutionary algorithm that uses KaFFPa to provide combine and mutation operations, as well as KaBaPE which extends the evolutionary algorithm. Moreover, specialized techniques are included to partition road networks (Buffoon), to output a vertex separator from a given partition as well as techniques geared towards the efficient partitioning of social networks. Here is an overview of our framework:

NEW in v3.25:

• Connected Blocks (Experimental): KaFFPa and KaFFPaE now support --connected_blocks (strong preconfiguration only) to produce partitions where each block is a connected subgraph. The input graph must be connected. Connectivity is enforced via checkpoint-based component elimination during uncoarsening, combined with connectivity-aware refinement and greedy rebalancing. When this flag is not used, KaHIP behavior is unchanged.

NEW in v3.24:

• 64-bit Edge Support: The C interface now supports 64-bit edges via a compile-time kahip_idx typedef. Compile with -D64BITMODE=On to enable int64_t for all edge-related arrays and values (xadj, adjncy, adjcwgt, edgecut). Node-related parameters remain int.
• Windows Support: KaHIP now builds on Windows with MSVC. Windows pip wheels are available on PyPI.
• Python 3.13/3.14: Pip wheels now available for Python 3.10-3.14 on Linux, macOS and Windows.
• pkg-config Support: KaHIP and ParHIP are now discoverable via pkg-config.
• ParHIP Example: Added a ParHIP interface usage example (misc/example_parhip_call/).
• Runtime Index Query: Added kahip_sizeof_idx() to query whether the library was compiled with 32-bit or 64-bit indices.

NEW in v3.23:

Homebrew Support: KaHIP can now be installed via Homebrew on macOS and Linux using

brew install KaHIP/kahip/kahip

NEW in v3.21:

KaFFPa can now be used with pip. Simply run

pip install kahip

and use the example Python code below.

NEW in v3.14:

Support for Python: KaHIP can now also be used in Python. See below how to do that.

Hierarchical Partitionings: KaHIP can compute hierarchial partitionings. All you have to do is specify the hierarchy and KaHIP is ready to go and does the multisection as you specified.

Node Ordering Algorithms: Many applications rely on time-intensive matrix operations, such as factorization, which can be sped up significantly for large sparse matrices by interpreting the matrix as a sparse graph and computing a node ordering that minimizes the so-called fill-in. Here, we added new algorithms to compute fill-in reduced orderings in graphs.

ILPs For Even Higher Quality: ILPs typically don't scale to large instances. We adapt them to heuristically improve a given partition. We do so by defining a much smaller model that allows us to use symmetry breaking and other techniques that make the approach scalable. We include ILPs that can be used as a post-processing step to improve high-quality partitions even further. The codes are now included in KaHIP.

TCMalloc: we added the possibility to link against TCMalloc. Depending on your system, this can yield an overall faster algorithm since it provides faster malloc operations.

Faster IO: we added an option to kaffpa (option --mmap_io) that speedsup the IO of text files significantly -- sometimes by an order of magnitude.

Added Support for Vertex and Edge Weights in ParHIP: we extended the IO functionality of ParHIP to read weighted graphs in the METIS format.

Global Multisection Mapping: we added global multisection n-to-1 process mapping algorithms. This computes better process mapping for parallel applications if information about the system hierarchy/architecture is known.

Determinism in ParHIP: we added an option to run ParHIP deterministically, i.e. two runs of ParHIP using the same seed will always return the same result.

Version Flag: we added an option to output the version that you are currently using, use the --version option of the programs.

NEW in v2.10:

ParHIP (Parallel High Quality Partitioning): Our distributed memory parallel partitioning techniques are designed to partition hierarchically structured networks such as web graphs or social networks.

Mapping Algorithms: Our new algorithms to map the blocks onto processors to minimize overall communication time based on hierarchical partitionings of the task graph and fast local search algorithms.

Edge Partitioning Algorithms: Our new algorithms to compute edge partitionings of graphs.

Main org site:

https://github.com/kahip/

Installation Notes

Install via Homebrew

brew install KaHIP/kahip/kahip

If open-mpi fails to build from source (non-standard Homebrew prefix), either install it separately first:

brew install open-mpi
brew install KaHIP/kahip/kahip

or set the compiler explicitly:

export HOMEBREW_CC=gcc-15
export HOMEBREW_CXX=g++-15
brew install KaHIP/kahip/kahip

Downloading KaHIP:

You can download KaHIP with the following command line:

git clone https://github.com/KaHIP/KaHIP

Compiling KaHIP:

Before you can start, you need to install the following software packages:

• if you want to use parallel algorithms contained within the framework (e.g. ParHIP), you need OpenMPI (https://www.open-mpi.org/). If you don't want to run ParHIP, you can easily get rid of this dependency.

Once you installed the packages, just type

./compile_withcmake.sh 

In this case, all binaries, libraries and headers are in the folder ./deploy/

Note that this script detects the amount of available cores on your machine and uses all of them for the compilation process. If you don't want that, set the variable NCORES to the number of cores that you would like to use for compilation.

Alternatively use the standard cmake build process:

mkdir build
cd build 
cmake ../ -DCMAKE_BUILD_TYPE=Release     
make 
cd ..

In this case, the binaries, libraries and headers are in the folder ./build as well as ./build/parallel/parallel_src/

We also provide the option to link against TCMalloc. If you have it installed, run cmake with the additional option -DUSE_TCMALLOC=On.

By default node ordering programs are also compiled. If you have Metis installed, the build script also compiles a faster node ordering program that uses reductions before calling Metis ND. Note that Metis requires GKlib (https://github.com/KarypisLab/GKlib).

If you use the option -DUSE_ILP=On and you have Gurobi installed, the build script compiles the ILP programs to improve a given partition ilp_improve and an exact solver ilp_exact. Alternatively, you can also pass these options to ./compile_withmake.sh for example:

./compile_withcmake -DUSE_ILP=On

We also provide an option to support 64-bit edges. In order to use this, compile KaHIP with the option -D64BITMODE=On. When enabled, the C interface uses kahip_idx (typedef for int64_t) instead of int32_t for all edge-related arrays and values (xadj, adjncy, adjcwgt, edgecut, infinity_edge_weight). Node-related parameters (n, vwgt, nparts, part) remain int. No additional flags are needed; -D64BITMODE=On enables both the internal 64-bit edge types and the public kahip_idx typedef.

Lastly, we provide an option for determinism in ParHIP, e.g. two runs with the same seed will give you the same result. Note however that this option can reduce the quality of partitions, as initial partitioning algorithms do not use sophisticated memetic algorithms, but only multilevel algorithms to compute initial partitionings. ONLY use this option if you use ParHIP as a tool. Do not use this option if you want to make quality comparisons against ParHIP. To make use of this option, run

./compile_withcmake -DDETERMINISTIC_PARHIP=On

Running Programs

For a description of the graph format (and an extensive description of all other programs) please have a look into the manual. We give short examples here.

Overview of Programs and Usecase

Default Partitioning Problem

These programs and configurations take a graph and partition it more or less sequentially. We list here kaffpa and kaffpaE (the evolutionary framework) and their configurations. In general, the configurations are such that you can invest a lot of time into solution quality using the memetic algorithm. The memetic algorithm can also be run in parallel using MPI. In general, the more time and resources you invest, the better will be the quality of your partition. We have a lot of trade-offs, contact us if you are unsure what works best for your application. For a description of the algorithm have a look at the references that we list in the manual.

Use Case	Input	Programs
Graph Format		graphchecker
Evaluate Partitions		evaluator
Fast Partitioning	Meshes	kaffpa preconfiguration set