The graph partitioning framework mt-KaHIP -- Multi-Threaded Karlsruhe High Quality Partitioning.
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. Here, we separately release the shared-memory parallel multilevel version of KaHIP which is due to Yaroslav Akhremtsev. Here is an overview of KaHIP:
You can download mt-KaHIP with the following command line:
git clone https://github.com/KaHIP/mt-KaHIPBefore you can start you need to install the following software packages:
- TBB (https://www.threadingbuildingblocks.org/)
- OpenMP
- CMake
- GCC != 10.1 (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94087#c16)
Once you installed the packages, just type
./compile_withcmake.sh. In this case, all binaries, libraries and headers are in the folder ./deploy/
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
For a description of the graph format (and an extensive description of all other programs) please have a look into the manual. We give a short examples here.
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 ressources 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 | mtkahip preconfiguration set to socialparallel | |
| Good Partitioning | mtkahip preconfiguration set to multitrysocialparallel |
./deploy/graphchecker ./examples/rgg_n_2_15_s0.graph ./deploy/mtkahip ./examples/rgg_n_2_15_s0.graph --k 4 --preconfiguration=socialparallel --num_threads=4mt-KaHIP also offers libaries and interfaces to link the algorithms directly to your code. We explain the details of the interface in the manual. Below we list an example program that links the kahip library. This example can also be found in misc/example_library_call/. The program will also be compiled when running the cmake process from above (see CMakeLists.txt file for necessary libraries etc...).
#include <iostream>
#include <sstream>
#include "mtkahip_interface.h"
int main(int argn, char **argv) {
std::cout << "partitioning graph from the manual" << std::endl;
int n = 5;
int* xadj = new int[6];
xadj[0] = 0; xadj[1] = 2; xadj[2] = 5; xadj[3] = 7; xadj[4] = 9; xadj[5] = 12;
int* adjncy = new int[12];
adjncy[0] = 1; adjncy[1] = 4; adjncy[2] = 0; adjncy[3] = 2; adjncy[4] = 4; adjncy[5] = 1;
adjncy[6] = 3; adjncy[7] = 2; adjncy[8] = 4; adjncy[9] = 0; adjncy[10] = 1; adjncy[11] = 3;
double imbalance = 0.03;
int* part = new int[n];
int edge_cut = 0;
int nparts = 2;
int numthreads = 4;
int* vwgt = NULL;
int* adjcwgt = NULL;
mtkahip(&n, vwgt, xadj, adjcwgt, adjncy, &nparts, &imbalance, false, 0, FASTSOCIALMULTITRY_PARALLEL, numthreads, & edge_cut, part);
std::cout << "edge cut " << edge_cut << std::endl;
}The program is licenced under MIT licence. If you publish results using our algorithms, please acknowledge our work by quoting the following paper:
@article{DBLP:journals/tpds/AkhremtsevSS20,
author = {Yaroslav Akhremtsev and
Peter Sanders and
Christian Schulz},
title = {High-Quality Shared-Memory Graph Partitioning},
journal = {{IEEE} Trans. Parallel Distributed Syst.},
volume = {31},
number = {11},
pages = {2710--2722},
year = {2020},
url = {https://doi.org/10.1109/TPDS.2020.3001645},
doi = {10.1109/TPDS.2020.3001645},
timestamp = {Fri, 02 Oct 2020 14:40:05 +0200},
biburl = {https://dblp.org/rec/journals/tpds/AkhremtsevSS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
Yaroslav Akhremtsev
Peter Sanders
Christian Schulz