2 unstable releases
0.2.0 | Aug 8, 2022 |
---|---|
0.1.0 | Aug 8, 2022 |
#1179 in Algorithms
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)
libnuma-dev
on ubuntu
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