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

use crate::elimination::graph::*;

#[test]
fn from_edges_builds_undirected_adjacency() {
    let g = EliminationGraph::from_edges(3, &[(0, 1), (1, 2)]);
    assert_eq!(g.degree(0), 1);
    assert_eq!(g.degree(1), 2);
    assert_eq!(g.degree(2), 1);
    assert!(g.contains_edge(0, 1) && g.contains_edge(1, 0));
}

#[test]
fn eliminate_fills_clique_and_deactivates() {
    let mut g = EliminationGraph::from_edges(3, &[(0, 1), (1, 2)]);
    let bag = g.eliminate(1);
    assert_eq!(bag.len(), 2);
    assert!(g.contains_edge(0, 2));
    assert!(!g.active[1]);
    assert_eq!(g.num_active, 2);
}

#[test]
fn simplicial_detection() {
    let g = EliminationGraph::from_edges(3, &[(0, 1), (0, 2), (1, 2)]);
    assert!(g.is_simplicial(0));
    let g = EliminationGraph::from_edges(3, &[(0, 1), (1, 2)]);
    assert!(!g.is_simplicial(1));
    assert!(g.is_simplicial(0));
}

#[test]
fn from_edges_dedups_repeated_inputs() {
    let g = EliminationGraph::from_edges(2, &[(0, 1), (1, 0), (0, 1)]);
    assert_eq!(g.degree(0), 1);
    assert_eq!(g.degree(1), 1);
}

#[test]
fn edge_query_agrees_with_the_adjacency_lists() {
    let g = EliminationGraph::from_edges(5, &[(0, 1), (1, 2), (2, 3), (3, 4), (0, 4)]);
    assert!(g.bitset_words > 0);
    for u in 0u32..5 {
        for v in 0u32..5 {
            let adj_has = g.adj[u as usize].contains(&v);
            let bs_has = g.contains_edge(u, v);
            assert_eq!(adj_has, bs_has, "u={u} v={v}");
        }
    }
}

#[test]
fn fill_count_is_the_edges_missing_among_the_neighbours() {
    let g = EliminationGraph::from_edges(3, &[(0, 1), (1, 2)]);
    assert_eq!(g.fill_count_of_bs(1), 1);
    assert_eq!(g.fill_count_of_bs(0), 0);
    let g2 = EliminationGraph::from_edges(3, &[(0, 1), (0, 2), (1, 2)]);
    assert_eq!(g2.fill_count_of_bs(0), 0);
    assert_eq!(g2.fill_count_of_bs(1), 0);
}

#[test]
fn promote_bitset_from_sparse_graph() {
    let n = 200u32;
    let edges: Vec<(u32, u32)> = (0..n - 1).map(|v| (v, v + 1)).collect();
    let mut g = EliminationGraph::from_edges(n, &edges);
    assert_eq!(g.bitset_words, 0, "sparse path expected");
    assert!(!g.should_promote_bitset(), "sparse density below threshold");
    g.promote_bitset();
    assert!(g.bitset_words > 0, "bitset populated after promotion");
    for v in 0..n - 1 {
        assert!(g.contains_edge(v, v + 1));
        assert!(g.contains_edge(v + 1, v));
    }
    assert!(!g.contains_edge(0, 5));
}

#[test]
fn should_promote_bitset_triggers_when_dense() {
    // Near-complete graph on 128 vertices, dense enough to cross the
    // promotion threshold.
    let n = 128u32;
    let mut edges = Vec::new();
    for u in 0..n {
        for v in (u + 1)..n {
            edges.push((u, v));
        }
    }
    // Construct sparse (first 10 edges only) then add_edge the rest, so the
    // graph starts adj-only regardless of what from_edges' own threshold does.
    let mut g = EliminationGraph::from_edges(n, &edges[..10]);
    for &(u, v) in &edges[10..] {
        g.add_edge(u, v);
    }
    // n=128 ≤ BITSET_THRESH so from_edges may already have enabled bitset;
    // if not, promotion should fire immediately.
    if g.bitset_words == 0 {
        assert!(g.should_promote_bitset());
    }
}

#[test]
fn eliminating_a_vertex_replaces_its_edges_with_the_fill_edge() {
    let mut g = EliminationGraph::from_edges(3, &[(0, 1), (1, 2)]);
    assert!(g.bitset_words > 0, "should use bitset for n=3");
    g.eliminate(1);
    assert!(g.contains_edge(0, 2));
    assert!(!g.active[1]);
    assert_eq!(g.num_active, 2);
    assert_eq!(g.num_edges, 1);
}