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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use super::{Xorshift64, fmix64, restart_seed};
use crate::portfolio::SECOND_CANDIDATE_SEED_OFFSET;

#[test]
fn equal_rng_states_produce_equal_streams() {
    let draw = || {
        let mut rng = Xorshift64::from_state(0x1234_5678_9abc_def0);
        (0..16).map(|_| rng.next_u64()).collect::<Vec<_>>()
    };

    assert_eq!(draw(), draw());
}

#[test]
fn next_u32_is_the_low_half_of_the_same_next_u64_draw() {
    let mut wide = Xorshift64::from_state(17);
    let mut narrow = Xorshift64::from_state(17);

    assert_eq!(narrow.next_u32(), wide.next_u64() as u32);
}

#[test]
fn zero_is_the_documented_fixed_point() {
    let mut rng = Xorshift64::from_state(0);

    assert!((0..8).all(|_| rng.next_u64() == 0));
}

#[test]
fn zero_base_seed_uses_the_restart_sequence() {
    assert_eq!(fmix64(0), 0, "the fixed point the invariant rests on");
    for restart in 0..8 {
        let expected = (restart as u64) * 7919 + 42;
        assert_eq!(restart_seed(0, restart), expected, "restart {restart}");
    }
}

#[test]
fn portfolio_candidate_seeds_land_on_different_streams() {
    for base in [1u64, 7, 42, 12_345, u64::MAX / 3] {
        for restart in 0..8 {
            assert_ne!(
                restart_seed(base, restart),
                restart_seed(base.wrapping_add(SECOND_CANDIDATE_SEED_OFFSET), restart),
                "base {base}, restart {restart}",
            );
        }
    }
}

#[test]
fn nonzero_base_seed_changes_every_restart_stream() {
    for base in [1u64, 7, 42, 12_345] {
        for restart in 0..8 {
            assert_ne!(
                restart_seed(base, restart),
                restart_seed(0, restart),
                "base {base}, restart {restart}",
            );
        }
    }
}

// The portfolio hands its two nested-dissection candidates the seed pair
// `(s, s + 42)`. Exercise that pair through both partitioners.

const SEED_A: u64 = 12_345;
const SEED_B: u64 = SEED_A + SECOND_CANDIDATE_SEED_OFFSET;

fn random_graph(n: usize, m: usize) -> Vec<(u32, u32)> {
    let mut rng = Xorshift64::from_state(0x2545_f491_4f6c_dd1d);
    let mut edges: Vec<(u32, u32)> = Vec::with_capacity(m + n);
    for vertex in 0..n {
        edges.push((vertex as u32, ((vertex + 1) % n) as u32));
    }
    while edges.len() < m {
        let u = (rng.next_u64() as usize) % n;
        let v = (rng.next_u64() as usize) % n;
        if u != v {
            edges.push((u.min(v) as u32, u.max(v) as u32));
        }
    }
    edges.sort_unstable();
    edges.dedup();
    edges
}

fn assert_proper_bisection(part: &[u8], n: usize) {
    assert_eq!(part.len(), n, "partition covers every vertex");
    assert!(part.contains(&0), "side 0 non-empty");
    assert!(part.contains(&1), "side 1 non-empty");
}

fn graph_part(seed: u64, edges: &[(u32, u32)], n: usize) -> Vec<u8> {
    let graph = crate::Graph::new(n as u32, edges.iter().copied());
    crate::partition::multilevel_graph_bisect(
        &graph,
        crate::partition::GraphBisectionConfig::new(0.2, seed),
    )
    .unwrap()
    .into_parts()
}

fn hypergraph_part(seed: u64, hyperedges: &[Vec<u32>], n: usize) -> Vec<u8> {
    let hypergraph = crate::partition::Hypergraph::new(n as u32, hyperedges, None).unwrap();
    crate::partition::multilevel_hypergraph_bisect(
        &hypergraph,
        crate::partition::HypergraphBisectionConfig::new(0.03, seed),
    )
    .unwrap()
    .into_parts()
}

#[test]
fn graph_bisect_differs_across_portfolio_seeds() {
    let n = 200;
    let edges = random_graph(n, 800);
    let a = graph_part(SEED_A, &edges, n);
    let b = graph_part(SEED_B, &edges, n);
    assert_proper_bisection(&a, n);
    assert_proper_bisection(&b, n);
    assert_ne!(a, b, "distinct seeds must give distinct partitions");
    assert_eq!(a, graph_part(SEED_A, &edges, n), "deterministic per seed");
}

#[test]
fn hypergraph_bisect_differs_across_portfolio_seeds() {
    let n = 120;
    let hyperedges: Vec<Vec<u32>> = random_graph(n, 480)
        .into_iter()
        .map(|(u, v)| vec![u, v])
        .collect();
    let a = hypergraph_part(SEED_A, &hyperedges, n);
    let b = hypergraph_part(SEED_B, &hyperedges, n);
    assert_proper_bisection(&a, n);
    assert_proper_bisection(&b, n);
    assert_ne!(a, b, "distinct seeds must give distinct partitions");
    assert_eq!(
        a,
        hypergraph_part(SEED_A, &hyperedges, n),
        "deterministic per seed"
    );
}