Mt-KaHyPar - Multi-Threaded Karlsruhe Graph and Hypergraph Partitioner

License	Linux, MacOS & Windows Build	Code Coverage	Zenodo

About Mt-KaHyPar
Features
Installing Mt-KaHyPar
Building Mt-KaHyPar from Source
Running Mt-KaHyPar
The C Library
The Python Library
Supported Objective Functions
Improving Compile Times
Licensing

About Mt-KaHyPar

Mt-KaHyPar is a shared-memory algorithm for partitioning graphs and hypergraphs. The balanced (hyper)graph partitioning problem asks for a partition of the node set of a (hyper)graph into k disjoint blocks of roughly the same size (usually a small imbalance is allowed by at most 1 + ε times the average block weight), while simultaneously minimizing an objective function defined on the (hyper)edges. Mt-KaHyPar can optimize the cut-net, connectivity, sum-of-external-degrees, and Steiner tree metric (see Supported Objective Functions).

alt text

The highest-quality configuration of Mt-KaHyPar computes partitions that are on par with those produced by the best sequential partitioning algorithms, while being almost an order of magnitude faster with only ten threads (e.g., when compared to KaFFPa or KaHyPar). Besides our high-quality configuration, we provide several other faster configurations that are already able to outperform most of the existing partitioning algorithms with regard to solution quality and running time. The figure below summarizes the time-quality trade-off of different hypergraph (left, connectivity metric) and graph partitioning algorithms (right, cut-net metric). The plot is based on an experiment with over 800 graphs and hypergraphs and relates the average solution quality and running time of each algorithm to the best achievable results. Points on the lower-left are considered better. Partially transparent markers indicate solvers producing more than 15% infeasible partitions (either imbalanced or timeout). For more details, we refer the reader to our publications.

time_quality_trade_off

Features

Besides its fast and high-quality partitioning algorithm, Mt-KaHyPar provides many other useful features:

Scalability: Mt-KaHyPar has excellent scaling behaviour (up to 25 with 64 threads), while increasing the number of threads does not adversely affect the solution quality.
Deterministic Partitioning: Mt-KaHyPar offers a high-quality deterministic partitioning algorithm, ensuring consistent solutions for the same input and random seed.
Large K Partitioning: We provide a partitioning configuration for partitioning (hyper)graphs into a large number of blocks (e.g., k > 1024).
Graph Partitioning: Mt-KaHyPar includes optimized data structures for graph partitioning, achieving a speedup by a factor of two for plain graphs.
Objective Functions: Mt-KaHyPar can optimize the cut-net, connectivity, and sum-of-external-degrees metric (for more details, see Supported Objective Functions)
Mapping (Hyper)Graphs Onto Graphs: In many applications (e.g., distributed computation), the partition is assigned to a communication network that can be represented as a graph. However, conventional objective functions do not consider the topology of the target graph. We therefore provide a mode that maps the nodes of a (hyper)graph onto a target graph via the Steiner tree metric.
Fixed Vertices: Fixed vertices are nodes that are preassigned to a particular block and are not allowed to change their block during partitioning.

Installing Mt-KaHyPar

For Linux and MacOS, the Mt-KaHyPar Python package can be installed via pip:

pip install mtkahypar

We also provide Debian packages that contain the CLI application and the C library interface for the latest release.

Building Mt-KaHyPar from Source

Mt-KaHyPar requires:

A 64-bit Linux, MacOS, or Windows operating system.
A modern, C++17-ready compiler such as g++ version 7 or higher, clang version 11.0.3 or higher, or MinGW compiler on Windows.
The cmake build system (>= 3.26).
The Intel Thread Building Blocks library (TBB, minimum required version is OneTBB 2021.5.0). If you don't want to install TBB by yourself, you can add the -DKAHYPAR_DOWNLOAD_TBB=On flag to the cmake command to download oneTBB and extract the necessary dependencies automatically.
The Portable Hardware Locality library (hwloc). This dependency is not strictly necessary, you can add the -DKAHYPAR_DISABLE_HWLOC=On flag to remove it.

Linux

The following command will install most of the required dependencies on a Ubuntu machine:

sudo apt-get install libtbb-dev libhwloc-dev

MacOS

The following command will install most of the required dependencies on a MacOS machine:

brew install tbb hwloc

Windows

The following instructions set up the environment used to build Mt-KaHyPar on Windows machines:

Download and install MSYS2 from the official website (https://www.msys2.org/).
Launch the MSYS2 MinGW x64 terminal.
Update the package manager database by running the following command:

pacman -Syu

The following command will then install all required dependencies:

pacman -S make mingw-w64-x86_64-cmake mingw-w64-x86_64-gcc mingw-w64-x86_64-python3 mingw-w64-x86_64-tbb

Build Commands

To build Mt-KaHyPar, use the following commands:

Clone the repository including submodules:

git clone https://github.com/kahypar/mt-kahypar.git
Create a build directory: mkdir build && cd build
Only on Windows machines: export CMAKE_GENERATOR="MSYS Makefiles"
Run cmake: cmake .. --preset=<default/python/dev>
Run make: make MtKaHyPar -j4

The build produces the executable MtKaHyPar, which can be found in build/mt-kahypar/application/.

As a user of Mt-KaHyPar, the default cmake preset is appropriate (or python for installing the Python interface). If you work on Mt-KaHyPar or want to run benchmarks, use the dev preset.

Please note that Mt-KaHyPar was primarily tested and evaluated on Linux machines. While a Windows build has been provided and tested on MSYS2 using pacman to install the required dependencies, we cannot provide any performance guarantees or ensure that the Windows version is free of bugs. We are happy to accept contributions to improve Windows support.

Running Mt-KaHyPar

To partition a hypergraph with our default configuration, use the following command:

./mt-kahypar/application/MtKaHyPar -h <path-to-hgr> --preset-type=default -t <# threads> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1

Available options are described in more detail below. You can also use --help to print a summary of the most important options.

Partitioning Configurations

Mt-KaHyPar provides several partitioning configurations with different time-quality trade-offs. The configurations are stored in ini files located in the config folder. However, we recommend using the --preset-type parameter:

--preset-type=<default/quality/highest_quality/deterministic/deterministic_quality/large_k>

default: computes good partitions very fast
quality: computes high-quality partitions (uses flow-based refinement)
highest_quality: highest-quality configuration (uses n-level coarsening and flow-based refinement)
deterministic: fast deterministic partitioning
deterministic_quality: high-quality deterministic partitioning (uses flow-based refinement)
large_k: configuration for partitioning (hyper)graphs into a large number of blocks (e.g. >= 1024 blocks)

The presets can be ranked from lowest quality to highest quality as follows: large_k, default, deterministic, quality, deterministic_quality, and highest_quality (the quality of the matching deterministic and non-deterministic configurations is roughly equivalent). We recommend using the default configuration to compute good partitions very fast and the quality configuration to compute high-quality solutions. The highest_quality configuration computes better partitions than our quality configuration by 0.5% on average at the cost of a two times longer running time for medium-sized instances (up to 100 million pins). When you have to partition a (hyper)graph into a large number of blocks (e.g., >= 1024 blocks), you can use our large_k configuration. However, we only recommend using this if you experience high running times with one of our other configurations as this can significantly worsen the partitioning quality.

Objective Functions

Mt-KaHyPar can optimize the cut-net, connectivity, and sum-of-external-degrees metric (see Supported Objective Functions).

-o <cut/km1/soed>

Mapping (Hyper)Graphs onto Graphs

To map a (hyper)graph onto a target graph, use the following parameters:

-g <path-to-target-graph> -o steiner_tree

The target graph is expected to be in Metis format. The nodes of the (hyper)graph are then mapped onto the nodes of the target graph, while optimizing the Steiner tree metric (see Supported Objective Functions).

Graph Partitioning

To partition a graph in Metis format, use the following parameters:

-h <path-to-graph> --file-format=metis -o cut

Mt-KaHyPar uses optimized data structures for graph partitioning, which speeds up the partitioning time by a factor of two in comparison to hypergraphs. For graphs in hMetis format, the optimized data structures can be enabled with --instance-type=graph.

Fixed Vertices

Fixed vertices are nodes that are preassigned to particular block and are not allowed to change their block during partitioning. Mt-KaHyPar reads fixed vertices from a file in the hMetis fix file format, which can be provided via the following command line parameter:

-f <path-to-fixed-vertex-file>

Individual Target Block Weights

Per default, Mt-KaHyPar enforces that the weight of each block must be smaller than the average block weight (weight of the hypergraph divided by the number of blocks) times (1 + ε). However, you can provide individual target block weights for each block via

--part-weights=weight_of_block_0 weight_of_block_1 ... weight_of_block_k

Note that the sum of all individual target block weights must be larger than the total weight of all nodes.

Write Partition to Output File

To enable writing the partition to a file after partitioning, you can add the following command line parameters to the partitioning call:

--write-partition-file --partition-output-folder=<path/to/folder>

The partition file name is generated automatically based on parameters such as k, imbalance, seed and the input file name and will be located in the folder specified by --partition-output-folder. If you do not provide a partition output folder, the partition file will be placed in the same folder as the input hypergraph file.

Display Options

There are several useful options to control which output is shown:

-q/--quiet: Disable partitioning output
-v/--verbose: Displays more detailed information on the partitioning process
--show-detailed-timings: Shows detailed sub-timings of each phase of the algorithm at the end of partitioning
--enable-progress-bar: Shows a progress bar during the coarsening and refinement phase

For changing other configuration parameters manually, please run --help -v for a detailed description of the program options.

The C Library

We provide a simple C interface to use Mt-KaHyPar as a library. The C libary is available from the debian package provided with the latest release. Alternatively, the library can be installed via

make install-mtkahypar  # use sudo (Linux & MacOS) or run shell as an administrator (Windows) to install system-wide

Note: When installing locally, the build will exit with an error due to missing permissions. However, the library is still built successfully and is available in the build folder.

To remove the library from your system use the provided uninstall target:

make uninstall-mtkahypar

Integration via Cmake

If possible, the best way to integrate the C library is directly via cmake using the MtKaHyPar::mtkahypar target.

If the library is installed on the system, it can be used via find_package:

find_package(MtKaHyPar)
if(MtKaHyPar_FOUND)
  add_executable(example example.cc)
  target_link_libraries(example MtKaHyPar::mtkahypar)
endif()

Alternatively, you can use Mt-KaHyPar directly via FetchContent:

FetchContent_Declare(
  MtKaHyPar EXCLUDE_FROM_ALL
  GIT_REPOSITORY https://github.com/kahypar/mt-kahypar
  GIT_TAG        v1.5
)
FetchContent_MakeAvailable(MtKaHyPar)

add_executable(example example.cc)
target_link_libraries(example MtKaHyPar::mtkahypar)

When including Mt-KaHyPar directly, it is also possible to control static versus dynamic linking with the BUILD_SHARED_LIBS and KAHYPAR_STATIC_LINK_DEPENDENCIES cmake options (note that static linking support is still experimental and not available for the installed library).

The C Library Interface

The library interface can be found in include/mtkahypar.h with a detailed documentation. We also provide several examples that show how to use the library.

Here is a short example of how you can partition a hypergraph using our library interface:

#include <cassert>
#include <memory>
#include <vector>
#include <iostream>
#include <thread>

#include <mtkahypar.h>

int main(int argc, char* argv[]) {
  mt_kahypar_error_t error{};

  // Initialize
  mt_kahypar_initialize(
    std::thread::hardware_concurrency() /* use all available cores */,
    true /* activate interleaved NUMA allocation policy */ );

  // Setup partitioning context
  mt_kahypar_context_t* context = mt_kahypar_context_from_preset(DEFAULT);
  // In the following, we partition a hypergraph into two blocks
  // with an allowed imbalance of 3% and optimize the connective metric (KM1)
  mt_kahypar_set_partitioning_parameters(context,
    2 /* number of blocks */, 0.03 /* imbalance parameter */,
    KM1 /* objective function */);
  mt_kahypar_set_seed(42 /* seed */);
  // Enable logging
  mt_kahypar_status_t status =
    mt_kahypar_set_context_parameter(context, VERBOSE, "1", &error);
  assert(status == SUCCESS);

  // Load Hypergraph for DEFAULT preset
  mt_kahypar_hypergraph_t hypergraph =
    mt_kahypar_read_hypergraph_from_file("path/to/hypergraph/file",
      context, HMETIS /* file format */, &error);
  if (hypergraph.hypergraph == nullptr) {
    std::cout << error.msg << std::endl; std::exit(1);
  }

  // Partition Hypergraph
  mt_kahypar_partitioned_hypergraph_t partitioned_hg =
    mt_kahypar_partition(hypergraph, context, &error);
  if (partitioned_hg.partitioned_hg == nullptr) {
    std::cout << error.msg << std::endl; std::exit(1);
  }

  // Extract Partition
  auto partition = std::make_unique<mt_kahypar_partition_id_t[]>(
    mt_kahypar_num_hypernodes(hypergraph));
  mt_kahypar_get_partition(partitioned_hg, partition.get());

  // Extract Block Weights
  auto block_weights = std::make_unique<mt_kahypar_hypernode_weight_t[]>(2);
  mt_kahypar_get_block_weights(partitioned_hg, block_weights.get());

  // Compute Metrics
  const double imbalance = mt_kahypar_imbalance(partitioned_hg, context);
  const int km1 = mt_kahypar_km1(partitioned_hg);

  // Output Results
  std::cout << "Partitioning Results:" << std::endl;
  std::cout << "Imbalance         = " << imbalance << std::endl;
  std::cout << "Km1               = " << km1 << std::endl;
  std::cout << "Weight of Block 0 = " << block_weights[0] << std::endl;
  std::cout << "Weight of Block 1 = " << block_weights[1] << std::endl;

  mt_kahypar_free_context(context);
  mt_kahypar_free_hypergraph(hypergraph);
  mt_kahypar_free_partitioned_hypergraph(partitioned_hg);
}

We recommend integrating the library via cmake into your project, to manage compiling and linking automatically.

However, it is also possible to directly compile the program using g++:

g++ -std=c++17 -DNDEBUG -O3 your_program.cc -o your_program -lmtkahypar

To execute the produced binary, you need to ensure that the installation directory (probably /usr/local/lib on Linux and C:\Program Files (x86)\MtKaHyPar\bin on Windows) is included in the dynamic library path (LD_LIBRARY_PATH on Linux, PATH on Windows).

Note that we internally use different data structures to represent a (hyper)graph based on the corresponding configuration (mt_kahypar_preset_type_t). The mt_kahypar_hypergraph_t structure stores a pointer to this data structure and also a type description. Therefore, you can not partition a (hyper)graph with all available configurations once it is loaded or constructed. However, you can check the compatibility of a hypergraph with a configuration with the following code:

mt_kahypar_context_t* context = mt_kahypar_context_from_preset(QUALITY);
// Check if the hypergraph is compatible with the QUALITY preset
if ( mt_kahypar_check_compatibility(hypergraph, QUALITY) ) {
  mt_kahypar_partitioned_hypergraph_t partitioned_hg =
    mt_kahypar_partition(hypergraph, context, &error);
}

The Python Library

We provide a Python library for Mt-KaHyPar, which is available on pypi (see installation). Alternatively, the Python library can be installed via

make mtkahypar_python

This will create a shared library in the build/python folder (mtkahypar.so on Linux and mtkahypar.pyd on Windows). Copy the libary to your Python project directory to import Mt-KaHyPar as a Python module.

A documentation of the Python module can be found by importing the module (import mtkahypar) and calling help(mtkahypar) in Python. We also provide several examples that show how to use the Python interface.

Here is a short example of how you can partition a hypergraph using our Python interface:

import multiprocessing
import mtkahypar

# Initialize
mtk = mtkahypar.initialize(multiprocessing.cpu_count()) # use all available cores

# Setup partitioning context
context = mtk.context_from_preset(mtkahypar.PresetType.DEFAULT)
# In the following, we partition a hypergraph into two blocks
# with an allowed imbalance of 3% and optimize the connectivity metric
context.set_partitioning_parameters(
  2,                       # number of blocks
  0.03,                    # imbalance parameter
  mtkahypar.Objective.KM1) # objective function
mtkahypar.set_seed(42)     # seed
context.logging = True

# Load hypergraph from file (assumes hMetis file format per default)
hypergraph = mtk.hypergraph_from_file("path/to/hypergraph/file", context)

# Partition hypergraph
partitioned_hg = hypergraph.partition(context)

# Output metrics
print("Partition Stats:")
print("Imbalance = " + str(partitioned_hg.imbalance(context)))
print("km1       = " + str(partitioned_hg.km1()))
print("Block Weights:")
for i in partitioned_hg.blocks():
  print(f"Weight of Block {i} = {partitioned_hg.block_weight(i)}")

We also provide an optimized graph data structure for partitioning plain graphs. The following example loads and partitions a graph:

# Load graph from file (assumes Metis file format per default)
graph = mtkahypar.graph_from_file("path/to/graph/file", context)

# Partition graph
partitioned_graph = graph.partition(context)

Note that we internally use different data structures to represent a (hyper)graph based on the corresponding configuration (PresetType). Therefore, you can not partition a (hyper)graph with all available configurations once it is loaded or constructed. However, you can check the compatibility of a hypergraph with a configuration with the following code:

context = mtk.context_from_preset(mtkahypar.PresetType.QUALITY)
# Check if the hypergraph is compatible with the QUALITY preset
if hypergraph.is_compatible(context.preset):
   partitioned_hg = hypergraph.partition(context)

Supported Objective Functions

Mt-KaHyPar can optimize several objective functions which we explain in the following in more detail.

Cut-Net Metric

cut_net

The cut-net metric is defined as total weight of all nets spanning more than one block of the partition Π (also called cut nets).

Connectivity Metric

connectivity

The connectivity metric additionally multiplies the weight of each cut net with the number of blocks λ(e) spanned by that net minus one. Thus, the connectivity metric tries to minimize the number of blocks connected by each net.

Sum-of-external-Degrees Metric

soed

The sum-of-external-degrees metric is similar to the connectivity metric, but does not subtract one from the number of blocks λ(e) spanned by a net. A peculiarity of this objective function is that removing a net from the cut reduces the metric by 2ω(e), while reducing the connectivity by one reduces the metric only by ω(e). Thus, the objective function prefers removing nets from the cut, while as a secondary criterion, it tries to reduce the connectivity of the nets.

Steiner Tree Metric

steiner_tree

The Steiner tree metric is the most versatile metric that we provide at the moment. A Steiner tree is a tree with minimal weight that connects a subset of the nodes on a graph (a more detailed definition can be found here). For a subset with exactly two nodes, finding a Steiner tree reverts to computing the shortest path between the two nodes. When optimizing the Steiner tree metric, we map the node set of a hypergraph H onto the nodes of a target graph G. The objective is to minimize the total weight of all Steiner trees induced by the nets of H on G. For a net e, dist(Λ(e)) is the weight of the minimal Steiner tree connecting the blocks Λ(e) spanned by net e on G. The Steiner tree metric can be used to accurately model wire-lengths in VLSI design or communication costs in distributed systems when some processors do not communicate with each other directly or with different speeds.

Note that finding a Steiner tree is an NP-hard problem. We therefore enforce a strict upper bound on the number of nodes of the target graph G, which is 64 nodes at the moment. If you want to map a hypergraph onto larger target graphs, you can use recursive partitioning. For example, if you want to map a hypergraph onto a graph with 4096 nodes, you can first partition the hypergraph into 64 blocks, and then map each block of the partition onto a subgraph of the target graph with 64 nodes.

Custom Objective Functions

Our implementation uses a common interface for all gain computation techniques that we use in our refinement algorithms. This enables us to extend Mt-KaHyPar with new objective functions without having to modify the internal implementation of the refinement algorithms. A step-by-step guide on how you can implement your own objective function can be found here.

Improving Compile Times

Mt-KaHyPar implements several graph and hypergraph data structures, and supports different objective functions. In the hot parts of the algorithm, each combination of (hyper)graph data structure and objective function is compiled separately, which notably increases the compile time. We therefore provide the cmake preset minimal to disable some of the features of Mt-KaHyPar for faster compilation.

With this, only the deterministic, deterministic_quality, default, and quality configurations are available in combination with the cut-net or connectivity metric. Using a disabled feature will throw an error. Note that you can only disable the features in our binary, not in the C and Python interface.

For more fine-grained control, you can directly use the corresponding cmake flags:

-DKAHYPAR_ENABLE_GRAPH_PARTITIONING_FEATURES=On/Off # enables/disables graph partitioning features
-DKAHYPAR_ENABLE_HIGHEST_QUALITY_FEATURES=On/Off # enables/disables our highest-quality configuration
-DKAHYPAR_ENABLE_LARGE_K_PARTITIONING_FEATURES=On/Off # enables/distables large k partitioning features
-DKAHYPAR_ENABLE_SOED_METRIC=On/Off # enables/disables sum-of-external-degrees metric
-DKAHYPAR_ENABLE_STEINER_TREE_METRIC=On/Off # enables/disables Steiner tree metric

Bug Reports

We encourage you to report any problems with Mt-KaHyPar via the github issue tracking system of the project.

Licensing

Mt-KaHyPar is a free software provided under the MIT License. For more information see the LICENSE file. We distribute this framework freely to foster the use and development of hypergraph partitioning tools. If you use Mt-KaHyPar in an academic setting please cite the appropriate papers.

// Mt-KaHyPar-D
@inproceedings{MT-KAHYPAR-D,
  title     = {Scalable Shared-Memory Hypergraph Partitioning},
  author    = {Gottesbüren, Lars and
               Heuer, Tobias and
               Sanders, Peter and
               Schlag, Sebastian},
  booktitle = {23rd Workshop on Algorithm Engineering and Experiments (ALENEX 2021)},
  pages     = {16--30},
  year      = {2021},
  publisher = {SIAM},
  doi       = {10.1137/1.9781611976472.2},
}

// Mt-KaHyPar-Q
@inproceedings{MT-KAHYPAR-Q,
  title     = {Shared-Memory $n$-level Hypergraph Partitioning},
  author    = {Lars Gottesb{\"{u}}ren and
               Tobias Heuer and
               Peter Sanders and
               Sebastian Schlag},
  booktitle = {24th Workshop on Algorithm Engineering and Experiments (ALENEX 2022)},
  year      = {2022},
  publisher = {SIAM},
  month     = {01},
  doi       = {10.1137/1.9781611977042.11}
}

// Mt-KaHyPar-Q-F
@inproceedings{MT-KaHyPar-Q-F,
  title       =	{Parallel Flow-Based Hypergraph Partitioning},
  author      =	{Lars Gottesb\"{u}ren and
                 Tobias Heuer and
                 Peter Sanders},
  booktitle   =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages       =	{5:1--5:21},
  year        =	{2022},
  volume      =	{233},
  publisher   =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi         =	{10.4230/LIPIcs.SEA.2022.5}
}

// Deterministic Partitioning
@inproceedings{MT-KAHYPAR-SDET,
  author    = {Lars Gottesb{\"{u}}ren and
               Michael Hamann},
  title     = {Deterministic Parallel Hypergraph Partitioning},
  booktitle = {European Conference on Parallel Processing (Euro-Par)},
  volume    = {13440},
  pages     = {301--316},
  publisher = {Springer},
  year      = {2022},
  doi       = {10.1007/978-3-031-12597-3\_19},
}

// Unconstrained Refinement
@inproceedings{MT-KAHYPAR-UNCONSTRAINED,
  author       = {Nikolai Maas and
                  Lars Gottesb{\"{u}}ren and
                  Daniel Seemaier},
  editor       = {Rezaul Chowdhury and
                  Solon P. Pissis},
  title        = {Parallel Unconstrained Local Search for Partitioning Irregular Graphs},
  booktitle    = {Symposium on Algorithm Engineering and Experiments (ALENEX 2024)},
  pages        = {32--45},
  publisher    = {{SIAM}},
  year         = {2024},
  doi          = {10.1137/1.9781611977929.3},
}

// Steiner Tree Objective
@inproceedings{MT-KAHYPAR-STEINER-TREES,
  author       = {Tobias Heuer},
  editor       = {Rezaul Chowdhury and
                  Solon P. Pissis},
  title        = {A Direct \emph{k-}Way Hypergraph Partitioning Algorithm for Optimizing
                  the Steiner Tree Metric},
  booktitle    = {Symposium on Algorithm Engineering and Experiments (ALENEX 2024)},
  pages        = {15--31},
  publisher    = {{SIAM}},
  year         = {2024},
  doi          = {10.1137/1.9781611977929.2}
}

// Dissertation of Lars Gottesbüren
@phdthesis{MT-KAHYPAR-DIS-GOTTESBUEREN,
  author         = {Lars Gottesb\"{u}ren},
  year           = {2023},
  title          = {Parallel and Flow-Based High-Quality Hypergraph Partitioning},
  doi            = {10.5445/IR/1000157894},
  pagetotal      = {256},
  school         = {Karlsruhe Institute of Technology}
}

// Dissertation of Tobias Heuer
@phdthesis{MT-KAHYPAR-DIS-HEUER,
    author       = {Heuer, Tobias},
    year         = {2022},
    title        = {Scalable High-Quality Graph and Hypergraph Partitioning},
    doi          = {10.5445/IR/1000152872},
    pagetotal    = {242},
    school       = {Karlsruhe Institute of Technology}
}

// Mt-KaHyPar Journal Paper
@article{MT-KAHYPAR-JOURNAL,
  author       = {Lars Gottesb{\"{u}}ren and
                  Tobias Heuer and
                  Nikolai Maas and
                  Peter Sanders and
                  Sebastian Schlag},
  title        = {Scalable High-Quality Hypergraph Partitioning},
  journal      = {{ACM} Transactions on Algorithms},
  volume       = {20},
  number       = {1},
  pages        = {9:1--9:54},
  year         = {2024},
  doi          = {10.1145/3626527},
}

Contributing

If you are interested in contributing to the Mt-KaHyPar framework feel free to contact us or create an issue on the issue tracking system.

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

mtkahypar-1.6.2.tar.gz (3.1 MB view details)

Uploaded Jul 28, 2026 Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

The dropdown lists show the available interpreters, ABIs, and platforms. Enable javascript to be able to filter the list of wheel files.

mtkahypar-1.6.2-cp314-cp314t-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (6.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.14tmanylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

mtkahypar-1.6.2-cp314-cp314t-manylinux_2_26_aarch64.manylinux_2_28_aarch64.whl (6.1 MB view details)

Uploaded Jul 28, 2026 CPython 3.14tmanylinux: glibc 2.26+ ARM64manylinux: glibc 2.28+ ARM64

mtkahypar-1.6.2-cp314-cp314t-macosx_11_0_arm64.whl (4.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.14tmacOS 11.0+ ARM64

mtkahypar-1.6.2-cp314-cp314t-macosx_10_15_x86_64.whl (5.4 MB view details)

Uploaded Jul 28, 2026 CPython 3.14tmacOS 10.15+ x86-64

mtkahypar-1.6.2-cp314-cp314-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (6.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.14manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

mtkahypar-1.6.2-cp314-cp314-manylinux_2_26_aarch64.manylinux_2_28_aarch64.whl (6.1 MB view details)

Uploaded Jul 28, 2026 CPython 3.14manylinux: glibc 2.26+ ARM64manylinux: glibc 2.28+ ARM64

mtkahypar-1.6.2-cp314-cp314-macosx_11_0_arm64.whl (4.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.14macOS 11.0+ ARM64

mtkahypar-1.6.2-cp314-cp314-macosx_10_15_x86_64.whl (5.4 MB view details)

Uploaded Jul 28, 2026 CPython 3.14macOS 10.15+ x86-64

mtkahypar-1.6.2-cp313-cp313-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (6.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.13manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

mtkahypar-1.6.2-cp313-cp313-manylinux_2_26_aarch64.manylinux_2_28_aarch64.whl (6.1 MB view details)

Uploaded Jul 28, 2026 CPython 3.13manylinux: glibc 2.26+ ARM64manylinux: glibc 2.28+ ARM64

mtkahypar-1.6.2-cp313-cp313-macosx_11_0_arm64.whl (4.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.13macOS 11.0+ ARM64

mtkahypar-1.6.2-cp313-cp313-macosx_10_13_x86_64.whl (5.4 MB view details)

Uploaded Jul 28, 2026 CPython 3.13macOS 10.13+ x86-64

mtkahypar-1.6.2-cp312-cp312-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (6.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.12manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

mtkahypar-1.6.2-cp312-cp312-manylinux_2_26_aarch64.manylinux_2_28_aarch64.whl (6.1 MB view details)

Uploaded Jul 28, 2026 CPython 3.12manylinux: glibc 2.26+ ARM64manylinux: glibc 2.28+ ARM64

mtkahypar-1.6.2-cp312-cp312-macosx_11_0_arm64.whl (4.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.12macOS 11.0+ ARM64

mtkahypar-1.6.2-cp312-cp312-macosx_10_13_x86_64.whl (5.4 MB view details)

Uploaded Jul 28, 2026 CPython 3.12macOS 10.13+ x86-64

mtkahypar-1.6.2-cp311-cp311-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (6.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.11manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

mtkahypar-1.6.2-cp311-cp311-manylinux_2_26_aarch64.manylinux_2_28_aarch64.whl (6.1 MB view details)

Uploaded Jul 28, 2026 CPython 3.11manylinux: glibc 2.26+ ARM64manylinux: glibc 2.28+ ARM64

mtkahypar-1.6.2-cp311-cp311-macosx_11_0_arm64.whl (4.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.11macOS 11.0+ ARM64

mtkahypar-1.6.2-cp311-cp311-macosx_10_13_x86_64.whl (5.4 MB view details)

Uploaded Jul 28, 2026 CPython 3.11macOS 10.13+ x86-64

mtkahypar-1.6.2-cp310-cp310-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (6.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.10manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

mtkahypar-1.6.2-cp310-cp310-manylinux_2_26_aarch64.manylinux_2_28_aarch64.whl (6.1 MB view details)

Uploaded Jul 28, 2026 CPython 3.10manylinux: glibc 2.26+ ARM64manylinux: glibc 2.28+ ARM64

mtkahypar-1.6.2-cp310-cp310-macosx_11_0_arm64.whl (4.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.10macOS 11.0+ ARM64

mtkahypar-1.6.2-cp310-cp310-macosx_10_13_x86_64.whl (5.4 MB view details)

Uploaded Jul 28, 2026 CPython 3.10macOS 10.13+ x86-64

mtkahypar-1.6.2-cp39-cp39-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl (6.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.9manylinux: glibc 2.27+ x86-64manylinux: glibc 2.28+ x86-64

mtkahypar-1.6.2-cp39-cp39-manylinux_2_26_aarch64.manylinux_2_28_aarch64.whl (6.1 MB view details)

Uploaded Jul 28, 2026 CPython 3.9manylinux: glibc 2.26+ ARM64manylinux: glibc 2.28+ ARM64

mtkahypar-1.6.2-cp39-cp39-macosx_11_0_arm64.whl (4.3 MB view details)

Uploaded Jul 28, 2026 CPython 3.9macOS 11.0+ ARM64

mtkahypar-1.6.2-cp39-cp39-macosx_10_13_x86_64.whl (5.4 MB view details)

Uploaded Jul 28, 2026 CPython 3.9macOS 10.13+ x86-64

File details

Details for the file mtkahypar-1.6.2.tar.gz.

File metadata

Download URL: mtkahypar-1.6.2.tar.gz
Upload date: Jul 28, 2026
Size: 3.1 MB
Tags: Source
Uploaded using Trusted Publishing? Yes
Uploaded via: twine/6.1.0 CPython/3.13.14

File hashes

Hashes for mtkahypar-1.6.2.tar.gz
Algorithm	Hash digest
SHA256	`657130d049d3f81e1e3a5e429532d9819632b9e571d2595aa4e2036e6cebe295`
MD5	`26410dc7f8c0a2ac63acc046575b68f1`
BLAKE2b-256	`1a55a6dd0fd73d1e820babaf77e12bd74614de573d0fe997f6835023725a4c23`

Algorithm	Hash digest
SHA256	`d744d9b57e90ddfe9743f5ed67616a70d377536875978d38df378e120458e037`
MD5	`fa4453cbcee16d3880a90ce609eed7e3`
BLAKE2b-256	`d89dad3cc335d0a0bf01ce79de2c35bfa37f3db88d6cef4c7007659a33f69203`

Algorithm	Hash digest
SHA256	`79ff14a151aa49a30a69b94c3641649de029ea099edbbc1aa3186441f6eda962`
MD5	`f2401d466c4f0141bad1c34aab4e97c8`
BLAKE2b-256	`2cde8275dd4a5923838f04d95b27af4a4f9a31984be6596bbf4454b3eac81553`

Algorithm	Hash digest
SHA256	`c1ca1d5da960dfe3550abb9e7c053e64163bd2a7ade87be6a7a97a7aa388146b`
MD5	`bb7b056401fa2e8a7ecca7c038627407`
BLAKE2b-256	`46b61150d69aea026b6d1234d1565683da876e465dc65f2da624eef13dc1c906`

Algorithm	Hash digest
SHA256	`9e03eae9479e5a9da31fbfc2879a77d97b3496f007a33a96876c02a2e5d11fe3`
MD5	`14c10f8c735c1dfadcb9df6a3f5f6826`
BLAKE2b-256	`368ec8039b336e31a792819c3f310b399f9346005e4134884534e8f7f3cf0659`

Algorithm	Hash digest
SHA256	`1c7f66e5ee1f4a710b05908420d225159b9ee5c158357437591607ae4f173863`
MD5	`fcefb21cee83022ed27488b17ec61577`
BLAKE2b-256	`01b90a194df6f72ea068bf4731d849634bacc6aa2e838fed144e03f187083fe9`

Algorithm	Hash digest
SHA256	`f0036c126ed9cc4a5751b3c060811ff6fdc1bf7a7ece877332536971b2482a35`
MD5	`9fe9262c4597e8546b5ab2fe96c20a11`
BLAKE2b-256	`171847c97aeae579d3564c7a8efe035913e709612ca06341d0ac18e3db7eb91a`

Algorithm	Hash digest
SHA256	`9891d69c74daafe0013c0f08978254b6ebca5fcd53579f3ea49510a70ae6d874`
MD5	`c98f08e64c75491108c8980f46a34eb8`
BLAKE2b-256	`80fa8435a56c6efb52c05e1990d2dc489da2736c27a5a4caf5ef87a4f86303ca`

Algorithm	Hash digest
SHA256	`fbac66ef0bde0cf9539a5c5f967c6f1e14337ecc6c854fcf2a80e80bcab46518`
MD5	`0160de5e3220e3d87be9b638ec84b02f`
BLAKE2b-256	`132fab741c569dc12e03d33c7d92e115ab7cc54d76f2ee0b574a8388c20b125c`

Algorithm	Hash digest
SHA256	`a72cb8a3cfd3f3a0f2b8ce037df17aa4229ea32743d0a7e6c1063a316eb5956e`
MD5	`19c8173a0845a9066512b792ea8233d4`
BLAKE2b-256	`66b3ebdf17fd1ef2fcb169cb8349ca117349ddd7db95881b31afa0582e3ca46f`

Algorithm	Hash digest
SHA256	`bd5c4af9efa3888737ddf730834816f9a00b843d0711cdf86fabc762d02308ff`
MD5	`6c34924f499dbd37a5850a5207cf7a2f`
BLAKE2b-256	`609c1357a70196232d14232458b7bc9d475aa2a718a735d6003ebe76b63e8f54`

Algorithm	Hash digest
SHA256	`b610580d94b84c9f3736bc87964516538271c0f3470c5d19ce8a1484a9bf6efc`
MD5	`7ba90c5bbea576d9258aad710acebb20`
BLAKE2b-256	`78b41ff83d2d61e42ffa70e004d698620dc43c98c72cccff127389b5166e838d`

Algorithm	Hash digest
SHA256	`5f051d7e80cf0b280effa07016820be6664e2a6f44cf9c03a6b999c3942a9460`
MD5	`7f146b09f972f9f47c052bd549cb1afe`
BLAKE2b-256	`2fe2e8658bf559de827960edb5a885c2bc072d5ab60e99927c0d66792e5d3364`

Algorithm	Hash digest
SHA256	`2bd05fd32c7d791ff1bd3cfc5335c4b198fc47fbf0ef7bd3a845546525a7c303`
MD5	`442021cbd5535029de3981715a747a9e`
BLAKE2b-256	`f2771cc89e2b50a4dd95d82b1ad6595855412664dd833c34d1719c3674e9556a`

Algorithm	Hash digest
SHA256	`921a5490b3ba3dde09cbbb375831e41fc7d7851bfe7062fde9d6a81c3b318336`
MD5	`cc8ef7ca8b5b1e81cc18d6d63b65e527`
BLAKE2b-256	`472b7762a709af6f38767830ad311043f677a497f85c06287eede0d2be603257`

Algorithm	Hash digest
SHA256	`fa607dbb7d5bd72de418ee192f573e4cce07f594b6a8e0dad8c6e33535f8a5be`
MD5	`96f9bea0626e7a621b7327afbd0518a6`
BLAKE2b-256	`8994e47f91583d5158d28cb6ef241f1ddd4fd8e27f585ff3662c7515daff081a`

Algorithm	Hash digest
SHA256	`9e78aef82d5c56c29411b0944b10c3f62cb8c48dce63fe7c08cf8626f502924c`
MD5	`d9184b022ebb7a07124c107cca9e09f9`
BLAKE2b-256	`dce34a8a9c35f52f005fe5f63d688c26a6527bea48fb71047eb61f9abcb6a671`

Algorithm	Hash digest
SHA256	`cdd18cb8de1ccf962d46bac0ccc3b05418bb692beb4c1a60f49d6a3a3b0b1b32`
MD5	`6cde27522681c9543e98362bc285a476`
BLAKE2b-256	`db9baffee7409f97ad2e3870ed0a807651995d22cadd3eb3b6bfcd2eff400012`

Algorithm	Hash digest
SHA256	`0f0d81d3b70706fcdcace022f89718ffb924d36b826f4e9854e90e5df5f8a904`
MD5	`00474b7c9b8aeb6b3683c47bb4000e73`
BLAKE2b-256	`5b9b4c0429c1625f013bf8953dcf886147d1be9c23e0abd3a11a6ebdb9130939`

Algorithm	Hash digest
SHA256	`4be0745be8b81b10f4fc944634ae84b28001a50ba27a5f84ecf6395f1be8d416`
MD5	`7c8f68be2a1bd259a3b16781d9c571d6`
BLAKE2b-256	`d5c2e9ef6f43703826cf77a356645a8c75ddf59e449c35f3361d4c4ed9e09e0c`

Algorithm	Hash digest
SHA256	`67026269e66d179c4a3f7ce57a519bf25d87708fb4fd5ffc943849d405d86f08`
MD5	`8b394c4dff9fbfa7093b2ce8e3203d6c`
BLAKE2b-256	`e7cb81a03d3a1cb5090e0436c00dd5d77bede1e948daa97a0308178b67011ca4`

mtkahypar 1.6.2

Mt-KaHyPar - Multi-Threaded Karlsruhe Graph and Hypergraph Partitioner

Table of Contents

About Mt-KaHyPar

Features

Installing Mt-KaHyPar

Building Mt-KaHyPar from Source

Linux

MacOS

Windows

Build Commands

Running Mt-KaHyPar

Partitioning Configurations

Objective Functions

Mapping (Hyper)Graphs onto Graphs

Graph Partitioning

Fixed Vertices

Individual Target Block Weights

Write Partition to Output File

Display Options

The C Library

Integration via Cmake

The C Library Interface

The Python Library

Supported Objective Functions

Cut-Net Metric

Connectivity Metric

Sum-of-external-Degrees Metric

Steiner Tree Metric

Custom Objective Functions

Improving Compile Times

Bug Reports

Licensing

Contributing

Project links

Key dates

1 maintainer

Credits

GitHub Statistics

License

Requires

Classifiers

Download files

Source Distribution

Built Distributions

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Algorithm	Hash digest
SHA256	`34ad1d7b1a8093e42a466b5302db4f8aca039e854311aedaee3045bfc6013795`
MD5	`37aaa10a78723b31a8f2e2c912af636e`
BLAKE2b-256	`e1bc6c4c57b50527f3882ac985f2c720cb9feebb088e9e93c4f01f4896ed86a3`

Algorithm	Hash digest
SHA256	`82c41e15a6224ef36fb1c53c8632043e89893aaff46edd707e61dd148beb530b`
MD5	`56d4b122127935251290d33c1bce87bd`
BLAKE2b-256	`014e74b633a52831b23740db4f51afb1c7c14c977ec5641e0fbe449e6180831c`

Algorithm	Hash digest
SHA256	`ee6f8c55704ede5576eb02be173859b4d48f1fa06c9aef023dd858376f5389eb`
MD5	`ad0640ad60d31b98a0a07f01d7b84984`
BLAKE2b-256	`ecbd2b6bc2b5580e7cd2bd6cb9f329d416e01ca012192db33857bc00aac523de`

Algorithm	Hash digest
SHA256	`dca1250d6ef971aa408ce25dbb1f1a6422bebf8bf3609e774c541f92fb3d77b8`
MD5	`756ca7fd5eb69a641386c77612b72322`
BLAKE2b-256	`7cd638c3e67620f5b91d1eaeb57d9612c69af7a4ba5caa05d8dfa810e49c3a1c`

Algorithm	Hash digest
SHA256	`cc8c41437a32132c4f9b38fc09d06503343aaaa538bbdf16e8d992730125d13c`
MD5	`de69e3aae04d2152ae97d51f7ad4b7c5`
BLAKE2b-256	`ea727dc8a51b683420776b326f85aeb609de3e33014b0951c159adc0f328a5ea`

Algorithm	Hash digest
SHA256	`dc16314e157fe8ac0bc8f43894eef26e552677b9292690f268e967e4a13bb3be`
MD5	`ad1e6e1a3d6facc1bd960f4a64b5bf99`
BLAKE2b-256	`80553a07fd37b9412cce4964ccfdccbce11bec6c07089498e6bbeb255dac3225`

Algorithm	Hash digest
SHA256	`926c6c7065f6179cbc05b9eb6dc6b6470392e9a2abaf21c9067bd09ce1728576`
MD5	`983c4b064795377a4813f0adffe1133c`
BLAKE2b-256	`5575229266447dc02c8824dae26be2347ff73adbfa0660f80e30cb8c075f938b`

Algorithm	Hash digest
SHA256	`445023cb65e0c29deed4d2e1c9f1699486e7cbfdb0608b9ff37659c9c628dbc6`
MD5	`e46e6031f46253f053f2925363213398`
BLAKE2b-256	`e681e87e5615a6d4853ec673979902e1646894152bd816a19d46f57fe86da91e`