Skip to main content

deq_runtime/decoder/
test_problems.rs

1//! Standard decoding test problems
2//!
3//! A small curated set of decoding problems used by the standard decoder test
4//! harness. The library carries **no policy** about which problems each decoder
5//! should solve correctly — that is up to each caller (integration tests, CLI)
6//! to specify.
7
8use crate::decoder::blackbox_decoder::{DecodingHypergraph, Hyperedge};
9use crate::misc::bit_vector::from_sparse_indices;
10use crate::util::BitVector;
11
12/// One standard test problem: a hypergraph plus a list of syndrome inputs.
13#[derive(Clone, Debug)]
14pub struct StandardTestProblem {
15    pub name: &'static str,
16    pub hypergraph: DecodingHypergraph,
17    pub cases: Vec<TestCase>,
18}
19
20/// A single syndrome input for a standard problem.
21#[derive(Clone, Debug)]
22pub struct TestCase {
23    pub name: &'static str,
24    pub syndrome: BitVector,
25}
26
27/// Format the identifier of a (problem, case) pair as `"problem/case"`.
28pub fn case_id(problem: &str, case: &str) -> String {
29    format!("{problem}/{case}")
30}
31
32fn edge(vertices: &[u64], probability: f64) -> Hyperedge {
33    Hyperedge {
34        observable_flips: None,
35        vertices: vertices.to_vec(),
36        probability,
37    }
38}
39
40fn case(name: &'static str, vertex_num: u64, defect_indices: &[u64]) -> TestCase {
41    TestCase {
42        name,
43        syndrome: from_sparse_indices(vertex_num, defect_indices),
44    }
45}
46
47/// Return the standard list of decoding problems exercised by the harness.
48///
49/// The set is intentionally small and well-defined so every decoder can be
50/// reasoned about case-by-case.
51pub fn standard_test_problems() -> Vec<StandardTestProblem> {
52    vec![
53        StandardTestProblem {
54            name: "empty_graph",
55            hypergraph: DecodingHypergraph {
56                vertex_num: 0,
57                hyperedges: vec![],
58            },
59            cases: vec![case("zero", 0, &[])],
60        },
61        StandardTestProblem {
62            name: "no_edges",
63            hypergraph: DecodingHypergraph {
64                vertex_num: 3,
65                hyperedges: vec![],
66            },
67            cases: vec![case("zero", 3, &[])],
68        },
69        StandardTestProblem {
70            name: "single_vertex_boundary",
71            hypergraph: DecodingHypergraph {
72                vertex_num: 1,
73                hyperedges: vec![edge(&[0], 0.1)],
74            },
75            cases: vec![case("zero", 1, &[]), case("vertex_0", 1, &[0])],
76        },
77        StandardTestProblem {
78            name: "simple_edge",
79            hypergraph: DecodingHypergraph {
80                vertex_num: 2,
81                hyperedges: vec![edge(&[0, 1], 0.1)],
82            },
83            cases: vec![case("zero", 2, &[]), case("both", 2, &[0, 1])],
84        },
85        StandardTestProblem {
86            name: "single_hyperedge_3",
87            hypergraph: DecodingHypergraph {
88                vertex_num: 3,
89                hyperedges: vec![edge(&[0, 1, 2], 0.1)],
90            },
91            cases: vec![case("zero", 3, &[]), case("all", 3, &[0, 1, 2])],
92        },
93        StandardTestProblem {
94            name: "line_chain_3",
95            hypergraph: DecodingHypergraph {
96                vertex_num: 3,
97                hyperedges: vec![edge(&[0, 1], 0.1), edge(&[1, 2], 0.1)],
98            },
99            cases: vec![
100                case("zero", 3, &[]),
101                case("left", 3, &[0, 1]),
102                case("right", 3, &[1, 2]),
103                case("ends", 3, &[0, 2]),
104            ],
105        },
106        StandardTestProblem {
107            name: "triangle",
108            hypergraph: DecodingHypergraph {
109                vertex_num: 3,
110                hyperedges: vec![edge(&[0, 1], 0.1), edge(&[1, 2], 0.1), edge(&[0, 2], 0.1)],
111            },
112            cases: vec![
113                case("zero", 3, &[]),
114                case("v01", 3, &[0, 1]),
115                case("v12", 3, &[1, 2]),
116                case("v02", 3, &[0, 2]),
117            ],
118        },
119    ]
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125
126    #[test]
127    fn problems_are_well_formed() {
128        for problem in standard_test_problems() {
129            assert!(!problem.cases.is_empty(), "problem {} has no cases", problem.name);
130            for case in &problem.cases {
131                assert_eq!(
132                    case.syndrome.size, problem.hypergraph.vertex_num,
133                    "case {}/{} syndrome size mismatch",
134                    problem.name, case.name
135                );
136            }
137        }
138    }
139
140    #[test]
141    fn case_id_formats_as_problem_slash_case() {
142        assert_eq!(case_id("simple_edge", "both"), "simple_edge/both");
143    }
144}