goatd 0.1.2

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

use crate::elimination::execution::{ElimSink, ElimStop};
use crate::elimination::graph::EliminationGraph;
use crate::elimination::greedy::min_fill::*;

#[test]
fn path_graph_eliminates_from_endpoints() {
    let mut g = EliminationGraph::from_edges(4, &[(0, 1), (1, 2), (2, 3)]);
    let salt = vec![0u32; 4];
    let mut bags = Vec::new();
    let mut rank = Vec::new();
    let sink = ElimSink::new(&mut bags, &mut rank, 0);
    eliminate_min_fill(&mut g, &salt, sink, ElimStop::default());
    assert_eq!(bags.len(), 4);
    let first = bags[0][0];
    assert!(first == 0 || first == 3);
    assert_eq!(g.num_active, 0);
}

#[test]
fn triangle_eliminates_in_three_steps() {
    let mut g = EliminationGraph::from_edges(3, &[(0, 1), (0, 2), (1, 2)]);
    let salt = vec![0u32; 3];
    let mut bags = Vec::new();
    let mut rank = Vec::new();
    let sink = ElimSink::new(&mut bags, &mut rank, 0);
    eliminate_min_fill(&mut g, &salt, sink, ElimStop::default());
    assert_eq!(bags.len(), 3);
    assert_eq!(bags[0].len(), 3);
}