graph-partitioner

A pure Rust reimplementation of the METIS graph partitioning algorithms, generated with the help of an LLM from the original C source code. Produces bit-identical output to C METIS 5.1.0.

Compared to the C original, this crate:

• Is written in safe, idiomatic Rust with no C dependencies

• Fixes a thread-safety issue in the original METIS RNG, which uses global mutable state

• Provides a builder API for ergonomic graph and mesh partitioning

• Documentation

Usage

Add this to your Cargo.toml:

[dependencies]
graph-partitioner = "0.1.0"

Graph partitioning

let mut partition = vec![0i32; num_vertices];
graph_partitioner::Graph::new(1, num_parts, &xadj, &adjacency)
    .unwrap()
    .seed(42)
    .part_kway(&mut partition)
    .unwrap();

Mesh partitioning

let mut epart = vec![0i32; num_elements];
let mut npart = vec![0i32; num_nodes];
graph_partitioner::Mesh::new(num_parts, &element_offsets, &element_indices)
    .unwrap()
    .seed(42)
    .part_dual(&mut epart, &mut npart)
    .unwrap();

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.