hpart 0.1.1

A hypergraph partitioning library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#![feature(let_chains)]
mod bipartite;
mod coarsen;
mod initial;
mod uncoarsen;

use rand::prelude::*;

use bipartite::{Bipartite, Bipartition, Index};
use coarsen::coarsen;
use initial::initial_partitioning;
use uncoarsen::uncoarsen;

pub fn bipartition(
    capacities: &[f32],
    weights: &[f32],
    nets: &[&[Index]],
    epsilon: f32,
) -> (Bipartition, (f32, f32)) {
    let mut h = Bipartite::new(capacities, weights, nets);
    let size_constraint = h.size_constraint(epsilon);
    let mementos = coarsen(&mut h);
    let mut bipart = initial_partitioning(&h, epsilon);
    uncoarsen(&mut h, size_constraint, mementos, &mut bipart);
    let eval = h.evaluate_bipartition(&bipart);
    (bipart, eval)
}

#[cfg(test)]
mod tests {
    use std::collections::BTreeSet;

    use ordered_float::OrderedFloat;
    use rayon::prelude::*;

    use super::*;

    #[test]
    fn bipartition_random_hypergraph() {
        let num_v = 2000;
        let num_e = 500;
        let max_net_size = 4;

        let capacities: Vec<_> = (0..num_v).map(|_| random::<f32>()).collect();
        let weights: Vec<_> = (0..num_e).map(|_| random::<f32>()).collect();
        let nets: Vec<Vec<_>> = (0..num_e)
            .map(|_| {
                let pins: BTreeSet<_> = (0..max_net_size)
                    .map(|_| random::<Index>() % num_v)
                    .collect();
                pins.into_iter().collect()
            })
            .collect();
        let nets_ref: Vec<&[_]> = nets.iter().map(|vec| &**vec).collect();
        let best_eval = (0..16)
            .into_par_iter()
            .map(|_| bipartition(&capacities, &weights, &nets_ref, 0.1).1)
            .min_by_key(|(_, cost)| OrderedFloat(*cost))
            .unwrap();
        println!(
            "{:?} {:?} {:?} {:?}",
            best_eval,
            capacities.iter().sum::<f32>(),
            weights.iter().sum::<f32>(),
            best_eval.1 / weights.iter().sum::<f32>(),
        );
    }
}