dm_partition/
dm_partition.rs

1//! Worked example for PR 3 of issue #53 — Dulmage-Mendelsohn
2//! partition + connected components of the square sub-graph.
3//!
4//! Builds a 5 equality-row × 5 variable problem that decomposes into
5//! three independent square blocks:
6//!
7//! ```text
8//! block A: row 0 ↔ col 0
9//! block B: rows 1, 2 share cols 1, 2
10//! block C: rows 3, 4 share cols 3, 4
11//! ```
12//!
13//! Runs Hopcroft-Karp, builds the DM partition, then asks for
14//! connected components.
15//!
16//! Run with:
17//! ```bash
18//! cargo run -p pounce-presolve --example dm_partition
19//! ```
20
21#![allow(clippy::expect_used, clippy::unwrap_used)]
22
23use pounce_presolve::components::SquareComponents;
24use pounce_presolve::dulmage_mendelsohn::DulmageMendelsohnPartition;
25use pounce_presolve::incidence::{EqualityIncidence, ProbeView};
26use pounce_presolve::matching::hopcroft_karp;
27
28fn main() {
29    let irow: [i32; 9] = [0, 1, 1, 2, 2, 3, 3, 4, 4];
30    let jcol: [i32; 9] = [0, 1, 2, 1, 2, 3, 4, 3, 4];
31    let g = [0.0; 5];
32
33    let probe = ProbeView {
34        n_vars: 5,
35        m_rows: 5,
36        jac_irow: &irow,
37        jac_jcol: &jcol,
38        jac_values: None,
39        g_l: &g,
40        g_u: &g,
41        linearity: None,
42        one_based: false,
43        eq_tol: 1e-12,
44        excluded_vars: None,
45        excluded_rows: None,
46    };
47    let inc = EqualityIncidence::from_probe(&probe);
48    let m = hopcroft_karp(&inc);
49    let dm = DulmageMendelsohnPartition::from_matching(&inc, &m);
50
51    println!("dm_partition example — PR 3 of pounce#53");
52    println!("matching size:    {}", m.size);
53    println!("over rows: {:?}, cols: {:?}", dm.over_rows, dm.over_cols);
54    println!(
55        "square rows: {:?}, cols: {:?}",
56        dm.square_rows, dm.square_cols
57    );
58    println!("under rows: {:?}, cols: {:?}", dm.under_rows, dm.under_cols);
59
60    let comps = SquareComponents::of_square_part(&inc, &m, &dm);
61    println!("square components: {}", comps.components.len());
62    for (i, c) in comps.components.iter().enumerate() {
63        println!("  component {i}: rows={:?}, cols={:?}", c.eq_rows, c.cols);
64    }
65
66    assert_eq!(comps.components.len(), 3, "expected 3 independent blocks");
67}
dm_partition/dm_partition.rs

dm_partition/
dm_partition.rs
