KaHyPar - Karlsruhe Hypergraph Partitioning

Travis-CI Status: ![Travis-CI Status] (https://travis-ci.com/SebastianSchlag/kahypar.svg?token=ZcLRsjUs4Yprny1FyfPy&branch=master) Appveyor Status: Coverity Status:

Requirements:

The Karlsruhe Hypergraph Partitioning Framework requires:

A 64-bit operating system. Linux, Mac OS X and Windows are currently supported.
A modern, C++11 ready compiler such as g++ version 4.9 or higher or clang version 3.2 or higher.
The cmake build system.
The Boost.Program_options library.

Building KaHyPar:

Clone the repository including submodules: git clone --recursive git@github.com:SebastianSchlag/kahypar.git
Create a build directory: mkdir build && cd build
Run cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
Run make: make

Testing and Profiling:

Tests are automatically executed while project is built. Additionally a test target is provided. End-to-end integration tests can be started with: make integration_tests. Profiling can be enabled via cmake flag: -DENABLE_PROFILE=ON.

Running KaHyPar:

The binary is located at: build/kahypar/application/.

KaHyPar has several configuration parameters. For a list of all possible parameters please run: ./KaHyPar --help. We use the hMetis format for the input hypergraph file as well as the partition output file.

Currently we provide two different presets that correspond to the configuration used in the ALENEX'16 submission and the ALENEX'17 submission.

To start KaHyPar in recursive bisection mode (KaHyPar-R) optimizing the cut-net objective run:

./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rb_alenex16.ini

To start KaHyPar in direct k-way mode (KaHyPar-K) optimizing the (connectivity - 1) objective run:

./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_direct_kway_alenex17.ini

All preset parameters can be overwritten by using the corresponding command line options.

Bug Reports:

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

Licensing:

KaHyPar is free software provided under the GNU General Public License (GPLv3). For more information see the COPYING file.

We distribute this framework freely to foster the use and development of hypergraph partitioning tools. If you use KaHyPar-R in an academic setting please cite the following paper:

@inproceedings{shhmss2016alenex,
 author    = {Sebastian Schlag and
              Vitali Henne and
              Tobias Heuer and
              Henning Meyerhenke and
              Peter Sanders and
              Christian Schulz},
 title     = {\emph{k}-way Hypergraph Partitioning via \emph{n}-Level Recursive
              Bisection},
 booktitle = {18th Workshop on Algorithm Engineering and Experiments, (ALENEX 2016)},
 pages     = {53--67},
 year      = {2016},
}

A preliminary version is available here on arxiv.

If you use KaHyPar-K in an academic setting please cite the following paper:

@inproceedings{ahss2017alenex,
 author    = {Yaroslav Akhremtsev and
              Tobias Heuer and
              Peter Sanders and
              Sebastian Schlag},
 title     = {Engineering a direct \emph{k}-way Hypergraph Partitioning Algorithm},
 booktitle = {19th Workshop on Algorithm Engineering and Experiments, (ALENEX 2017)},
 pages     = {tba},
 year      = {2017},
}

Contributing:

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

kittobi1992/kahypar-louvain