goatd 0.1.1

Greatest Of All Tree Decompositions: tree decompositions of graphs — elimination orders, FlowCutter, multilevel bisection — with PACE .gr/.td I/O and a command-line solver.
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

use crate::elimination::nested_dissection::*;

/// The parameters every test here runs under, varying only the base-case
/// threshold: no deadline, seed 0, and the balance tolerance the production
/// caller passes.
fn params<'a>(salt: &'a [u32], base_case_size: usize) -> NestedDissectionParams<'a> {
    NestedDissectionParams {
        salt,
        base_case_size,
        max_imbalance: 0.2,
        hard_deadline: None,
        base_seed: 0,
    }
}

#[test]
fn empty_graph_returns_empty_order() {
    let order = nested_dissection_order(&[], &[], &params(&[], 32), 0);
    assert!(order.is_empty());
}

#[test]
fn small_graph_falls_through_to_base_case() {
    let active = vec![0, 1, 2];
    let edges = vec![(0, 1), (0, 2), (1, 2)];
    let salt = vec![7, 3, 11];
    let order = nested_dissection_order(&active, &edges, &params(&salt, 32), 0);
    assert_eq!(order.len(), 3);
    let mut s: Vec<u32> = order.clone();
    s.sort();
    assert_eq!(s, vec![0, 1, 2]);
}

#[test]
fn grid_10x10_produces_full_order() {
    let mut edges = Vec::new();
    for r in 0..10u32 {
        for c in 0..10u32 {
            let v = r * 10 + c;
            if c + 1 < 10 {
                edges.push((v, v + 1));
            }
            if r + 1 < 10 {
                edges.push((v, v + 10));
            }
        }
    }
    let active: Vec<u32> = (0..100).collect();
    let salt: Vec<u32> = (0..100)
        .map(|i| (i as u32).wrapping_mul(2_654_435_761))
        .collect();
    let order = nested_dissection_order(&active, &edges, &params(&salt, 8), 0);
    assert_eq!(order.len(), 100);
    let mut s = order.clone();
    s.sort();
    assert_eq!(s, (0..100).collect::<Vec<u32>>());
}