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