btf_chain/
btf_chain.rs

1//! Worked example for PR 4 of issue #53 — Tarjan SCC + block
2//! triangular form on the square sub-graph.
3//!
4//! 4 equality rows × 4 variables with a chain dependency structure:
5//!
6//! ```text
7//! row 0 ↔ col 0
8//! row 1 ↔ col 1, uses col 0
9//! row 2 ↔ col 2, uses col 1
10//! row 3 ↔ col 3, uses col 2
11//! ```
12//!
13//! The dependency DAG is 3 → 2 → 1 → 0, so the BTF emits 4
14//! size-1 blocks in order [0], [1], [2], [3].
15//!
16//! Run with:
17//! ```bash
18//! cargo run -p pounce-presolve --example btf_chain
19//! ```
20
21#![allow(clippy::expect_used, clippy::unwrap_used)]
22
23use pounce_presolve::btf::BlockTriangularForm;
24use pounce_presolve::components::SquareComponents;
25use pounce_presolve::dulmage_mendelsohn::DulmageMendelsohnPartition;
26use pounce_presolve::incidence::{EqualityIncidence, ProbeView};
27use pounce_presolve::matching::hopcroft_karp;
28
29fn main() {
30    let irow: [i32; 7] = [0, 1, 1, 2, 2, 3, 3];
31    let jcol: [i32; 7] = [0, 0, 1, 1, 2, 2, 3];
32    let g = [0.0; 4];
33
34    let probe = ProbeView {
35        n_vars: 4,
36        m_rows: 4,
37        jac_irow: &irow,
38        jac_jcol: &jcol,
39        jac_values: None,
40        g_l: &g,
41        g_u: &g,
42        linearity: None,
43        one_based: false,
44        eq_tol: 1e-12,
45        excluded_vars: None,
46        excluded_rows: None,
47    };
48    let inc = EqualityIncidence::from_probe(&probe);
49    let m = hopcroft_karp(&inc);
50    let dm = DulmageMendelsohnPartition::from_matching(&inc, &m);
51    let comps = SquareComponents::of_square_part(&inc, &m, &dm);
52
53    println!("btf_chain example — PR 4 of pounce#53");
54    println!("matching size: {}", m.size);
55    println!("square components: {}", comps.components.len());
56    assert_eq!(
57        comps.components.len(),
58        1,
59        "expected one connected component"
60    );
61
62    let btf = BlockTriangularForm::of_component(&inc, &m, &comps.components[0]);
63    println!("BTF blocks (elimination order):");
64    for (i, b) in btf.blocks.iter().enumerate() {
65        println!("  block {i}: rows={:?}, cols={:?}", b.eq_rows, b.cols);
66    }
67    assert_eq!(btf.blocks.len(), 4, "chain expands to 4 size-1 blocks");
68    for (i, b) in btf.blocks.iter().enumerate() {
69        assert_eq!(b.eq_rows, vec![i]);
70        assert_eq!(b.cols, vec![i]);
71    }
72}
btf_chain/btf_chain.rs

btf_chain/
btf_chain.rs
