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

use super::*;
use crate::tests::td_fixture::make_td;
use crate::{Graph, TreeDecomposition};

fn trivial_td(num_vertices: u32) -> TreeDecomposition {
    make_td(vec![(0..num_vertices).collect()], Vec::new())
}

#[test]
fn refine_noop_on_tiny_subproblem() {
    // Under the min-side-size threshold: should return unchanged.
    let td = trivial_td(4);
    let edges: Vec<(u32, u32)> = vec![(0, 1), (1, 2), (2, 3)];
    let graph = Graph::new(4, edges);
    let out = refine_with_flowcutter(td.clone(), &graph, None).unwrap();
    assert_eq!(out.bags.len(), td.bags.len());
    assert_eq!(out.treewidth(), td.treewidth());
}

#[test]
fn refine_preserves_coverage_and_rip_on_path() {
    // 32-vertex path graph.  FlowCutter should cut it cleanly.
    let num_vertices = 32u32;
    let edges: Vec<(u32, u32)> = (0..num_vertices - 1).map(|i| (i, i + 1)).collect();
    let graph = Graph::new(num_vertices, edges);

    // Start from a deliberately bad TD: one giant bag containing every vertex.
    let td = trivial_td(num_vertices);

    let out = refine_with_flowcutter(td.clone(), &graph, None).unwrap();

    out.validate(&graph)
        .expect("refinement preserves the decomposition contract");
}