### 2 unstable releases

0.2.0 | Aug 8, 2022 |
---|---|

0.1.0 | Aug 8, 2022 |

#**1179** in Algorithms

**MIT**license

**6MB**

**49K**
SLoC

# KaMinPar Rust Wrapper

KaMinPar is a shared-memory parallel tool to heuristically solve the graph partitioning problem:. This code provides a small rust wrapper around the main KaMinPar repostitory here: https://github.com/KaHIP/KaMinPar

This KaMinPar algorithm is described in:

`@`inproceedings`{``DBLP``:`conf`/`esa`/`GottesburenH00S21`,`
author `=` `{`Lars Gottesb`{`\`"`{u}}ren and
Tobias Heuer and
Peter Sanders and
Christian Schulz and
Daniel Seemaier},
title = {Deep Multilevel Graph Partitioning},
booktitle = {29th Annual European Symposium on Algorithms, {ESA} 2021, September
6-8, 2021, Lisbon, Portugal (Virtual Conference)},
series = {LIPIcs},
volume = {204},
pages = {48:1--48:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{`\"`{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.ESA.2021.48},
doi = {10.4230/LIPIcs.ESA.2021.48}
}

Note: This is only a simple wrapper, all credit belongs to the original authors!

# What is KaMinPar (taken from original repo)

KaMinPar is a shared-memory parallel tool to heuristically solve the graph partitioning problem: divide a graph into k disjoint blocks of roughly equal weight while minimizing the number of edges between blocks. Competing algorithms are mostly evaluated for small values of k. If k is large, they often compute highly imbalance solutions, solutions of low quality or suffer excessive running time. KaMinPar substantially mitigates these problems. It computes partitions of comparable quality to other high-quality graph partitioning tools while guaranteeing the balance constraint for unweighted input graphs. Moreover, for large values of k, it is an order of magnitude faster than competing algorithms.

# Requirements

The actual C++ code requires:

- Modern C++-20 ready compiler such as g++ version 10 or higher
- A C++17 port requiring g++ version 7.2.0 or higher is available in branch c++17
- CMake
- Intel Thread Building Blocks library (TBB)

on ubuntu`libnuma-dev`

# Usage

as a library call with a node and edge weighted graph:

`fn` `main``(``)`` ``{`
`let` `mut` graph `=` `petgraph``::``graph``::``UnGraph``::``<``i32`, `i64``>``::`new_undirected`(``)``;`
`let` a `=` graph`.``add_node``(``5``)``;`
`let` b `=` graph`.``add_node``(``1``)``;`
`let` c `=` graph`.``add_node``(``1``)``;`
`let` d `=` graph`.``add_node``(``3``)``;`
`let` e `=` graph`.``add_node``(``3``)``;`
`let` f `=` graph`.``add_node``(``4``)``;`
`let` g `=` graph`.``add_node``(``3``)``;`
graph`.``add_edge``(`a`,` b`,` `1``)``;`
graph`.``add_edge``(`a`,` g`,` `3``)``;`
graph`.``add_edge``(`b`,` c`,` `3``)``;`
graph`.``add_edge``(`b`,` g`,` `1``)``;`
graph`.``add_edge``(`c`,` d`,` `1``)``;`
graph`.``add_edge``(`d`,` g`,` `4``)``;`
graph`.``add_edge``(`d`,` e`,` `1``)``;`
graph`.``add_edge``(`e`,` f`,` `1``)``;`
graph`.``add_edge``(`e`,` g`,` `1``)``;`
graph`.``add_edge``(`f`,` g`,` `6``)``;`
`let` num_partitions`:` `u32` `=` `2``;`
`let` partition `=` `kaminpar``::``PartitionerBuilder``::`with_epsilon`(``0.``03``)`
`.``seed``(``123``)`
`.``threads``(``std``::``num``::``NonZeroUsize``::`new`(``6``)``.``unwrap``(``)``)`
`.``partition_weighted``(``&`graph`,` num_partitions`)``;`
`println!``(``"``{:?}``"``,` partition`)``;`
`}`

or unweighted

`fn` `main``(``)`` ``{`
`let` `mut` graph `=` `petgraph``::``graph``::``UnGraph``::``<``(``)`, `(``)``>``::`new_undirected`(``)``;`
`let` a `=` graph`.``add_node``(``(``)``)``;`
`let` b `=` graph`.``add_node``(``(``)``)``;`
`let` c `=` graph`.``add_node``(``(``)``)``;`
`let` d `=` graph`.``add_node``(``(``)``)``;`
`let` e `=` graph`.``add_node``(``(``)``)``;`
graph`.``add_edge``(`a`,` b`,` `(``)``)``;`
graph`.``add_edge``(`a`,` e`,` `(``)``)``;`
graph`.``add_edge``(`b`,` c`,` `(``)``)``;`
graph`.``add_edge``(`b`,` e`,` `(``)``)``;`
graph`.``add_edge``(`c`,` d`,` `(``)``)``;`
graph`.``add_edge``(`d`,` e`,` `(``)``)``;`
`let` num_partitions`:` `u32` `=` `2``;`
`let` partition `=` `kaminpar``::``PartitionerBuilder``::`with_epsilon`(``0.``03``)`
`.``seed``(``123``)`
`.``threads``(``std``::``num``::``NonZeroUsize``::`new`(``6``)``.``unwrap``(``)``)`
`.``partition``(``&`graph`,` num_partitions`)``;`
`println!``(``"``{:?}``"``,` partition`)``;`
`}`

# License

MIT

#### Dependencies

~2.4–4MB

~61K SLoC