KaMinPar Rust包装器

KaMinPar是一个用于启发式解决图划分问题的共享内存并行工具。此代码提供了一个小的Rust包装器，围绕主要的KaMinPar仓库： https://github.com/KaHIP/KaMinPar

此KaMinPar算法在以下文档中描述

@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}
}

注意：这只是一个简单的包装器，所有荣誉都归功于原始作者！

什么是KaMinPar（摘自原始仓库）

KaMinPar是一个用于启发式解决图划分问题的共享内存并行工具：将图划分为k个大约相等权重的互斥块，同时最小化块之间的边数。竞争算法主要针对k值较小的情况进行评估。如果k值较大，它们通常计算高度不平衡的解决方案，低质量的解决方案或运行时间过长。KaMinPar在很大程度上缓解了这些问题。它计算出的划分质量与其他高质量的图划分工具相当，同时保证了无权输入图的平衡约束。此外，对于较大的k值，它比竞争算法快一个数量级。

需求

实际的C++代码需要

• 现代C++-20编译器，如g++版本10或更高版本
• 在c++17分支中有一个C++17端口，需要g++版本7.2.0或更高版本
• CMake
• Intel线程构建块库（TBB）
• libnuma-dev在ubuntu上

使用

作为库调用，带有节点和边权重的图

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);
}

或无权

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);
}

许可证

MIT