deq_runtime/decoder/
blackbox_util.rs1use crate::decoder::blackbox_decoder::{DecodingHypergraph, ParityFactor};
2use crate::misc::bit_vector::to_sparse_indices;
3use crate::util::BitVector;
4use hashbrown::HashSet;
5
6pub fn active_edge_indices(hypergraph: &DecodingHypergraph) -> Vec<u64> {
13 hypergraph
14 .hyperedges
15 .iter()
16 .enumerate()
17 .filter(|(_, hyperedge)| hyperedge.probability > 0.0)
18 .map(|(index, _)| index as u64)
19 .collect()
20}
21
22pub fn is_parity_factor(
23 decoding_hypergraph: &DecodingHypergraph,
24 parity_factor: &ParityFactor,
25 syndrome: &BitVector,
26) -> bool {
27 let mut selected_edges = HashSet::with_capacity(parity_factor.subgraph.len());
28 let mut flips = HashSet::<u64>::new();
29 for &edge_index in &parity_factor.subgraph {
30 if !selected_edges.insert(edge_index) {
31 return false;
32 }
33 let Ok(edge_index) = usize::try_from(edge_index) else {
34 return false;
35 };
36 let Some(edge) = decoding_hypergraph.hyperedges.get(edge_index) else {
37 return false;
38 };
39 for &vertex in &edge.vertices {
40 if !flips.insert(vertex) {
41 flips.remove(&vertex);
42 }
43 }
44 }
45
46 let syndrome = to_sparse_indices(syndrome);
47 let mut flips: Vec<u64> = flips.into_iter().collect();
48 flips.sort_unstable();
49 syndrome == flips
50}
51
52pub fn assert_parity_factor(decoding_hypergraph: &DecodingHypergraph, parity_factor: &ParityFactor, syndrome: &BitVector) {
53 if !is_parity_factor(decoding_hypergraph, parity_factor, syndrome) {
54 panic!(
55 "the provided parity factor does not match the syndrome: parity factor {parity_factor:?}, syndrome {syndrome:?}"
56 );
57 }
58}
59
60#[cfg(test)]
61mod tests {
62 use super::*;
63
64 fn single_edge_graph() -> DecodingHypergraph {
65 DecodingHypergraph {
66 vertex_num: 1,
67 hyperedges: vec![crate::decoder::blackbox_decoder::Hyperedge {
68 observable_flips: None,
69 vertices: vec![0],
70 probability: 0.1,
71 }],
72 }
73 }
74
75 #[test]
76 fn parity_factor_rejects_invalid_and_duplicate_edges() {
77 let hypergraph = single_edge_graph();
78 let syndrome = crate::misc::bit_vector::from_sparse_indices(1, &[0]);
79
80 assert!(is_parity_factor(&hypergraph, &ParityFactor { subgraph: vec![0] }, &syndrome));
81 assert!(!is_parity_factor(&hypergraph, &ParityFactor { subgraph: vec![1] }, &syndrome));
82 assert!(!is_parity_factor(
83 &hypergraph,
84 &ParityFactor { subgraph: vec![0, 0] },
85 &syndrome
86 ));
87 }
88}