Skip to main content

faultscope_core/
dem_problem.rs

1use std::collections::{HashMap, HashSet};
2use std::fmt;
3use std::mem;
4
5use crate::dem_canonical::{canonical_id_order, parity_canonicalize, parity_support_len};
6use crate::{DetectorErrorModel, NpError, NpResult};
7
8#[derive(Debug, Clone, PartialEq)]
9pub struct IndexedDemEdge {
10    pub probability: f64,
11    pub weight: f64,
12    pub detectors: Vec<usize>,
13    pub observables: Vec<usize>,
14    pub original_edge_index: usize,
15}
16
17#[derive(Debug, Clone, PartialEq)]
18pub struct IndexedDem {
19    pub detector_ids: Vec<i64>,
20    pub detector_coords: Vec<Vec<f64>>,
21    pub observable_ids: Vec<i64>,
22    pub edges: Vec<IndexedDemEdge>,
23}
24
25#[derive(Debug, Clone, PartialEq)]
26pub struct GraphlikeEdge {
27    pub detectors: Vec<usize>,
28    pub fault_observables: Vec<usize>,
29    pub probability: f64,
30    pub dem_edge_index: usize,
31}
32
33/// One graphlike component used to decompose a canonical DEM edge for decoding.
34///
35/// Detector and observable values are model IDs, not compact problem indices.
36/// All components that originate from the same canonical edge retain that
37/// edge's probability and `dem_edge_index` in the compiled problem.
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct GraphlikeDecompositionComponent {
40    pub detectors: Vec<i64>,
41    pub observables: Vec<i64>,
42}
43
44impl GraphlikeEdge {
45    /// Return the canonical log-likelihood ratio derived from `probability`.
46    pub fn weight(&self) -> f64 {
47        log_likelihood_ratio(self.probability)
48    }
49}
50
51pub const NATIVE_GRAPHLIKE_PROBLEM_ABI_VERSION: u32 = 1;
52pub const NATIVE_GRAPHLIKE_PROBLEM_ABI_NAME: &str = "faultscope.native_graphlike_problem.v1";
53pub const NATIVE_GRAPHLIKE_PROBLEM_CAPSULE_NAME: &str = "faultscope.native_graphlike_problem.v1";
54pub const NATIVE_GRAPHLIKE_PROBLEM_CAPSULE_METHOD: &str =
55    "__faultscope_native_graphlike_problem_capsule__";
56
57/// Compact graphlike edge record shared through the versioned construction ABI.
58///
59/// Detector and observable indices use `u32` to keep the per-edge record small.
60/// The owning problem validates all conversions before storing a record.
61#[doc(hidden)]
62#[repr(C)]
63#[derive(Debug, Clone, Copy, PartialEq)]
64pub struct FaultScopeNativeGraphlikeEdgeV1 {
65    pub dem_edge_index: usize,
66    pub probability: f64,
67    /// Canonical log-likelihood ratio derived from `probability` by the core.
68    pub weight: f64,
69    pub fault_observable_offset: u32,
70    pub fault_observable_count: u32,
71    pub detector0: u32,
72    pub detector1: u32,
73    pub detector_count: u32,
74    pub reserved: u32,
75}
76
77/// Borrowed descriptor exposed by the graphlike construction capsule.
78///
79/// All pointers remain valid only while the capsule that owns the problem is
80/// alive. Consumers must validate `abi_version`, `struct_size`, and
81/// `edge_struct_size` before dereferencing any data pointer.
82#[doc(hidden)]
83#[repr(C)]
84#[derive(Debug, Clone, Copy)]
85pub struct FaultScopeNativeGraphlikeProblemV1 {
86    pub abi_version: u32,
87    pub struct_size: usize,
88    pub edge_struct_size: usize,
89    pub detector_ids: *const i64,
90    pub detector_count: usize,
91    pub observable_ids: *const i64,
92    pub observable_count: usize,
93    pub edges: *const FaultScopeNativeGraphlikeEdgeV1,
94    pub edge_count: usize,
95    pub fault_observables: *const u32,
96    pub fault_observable_count: usize,
97}
98
99/// Borrowed edge view over the compact graphlike representation.
100#[derive(Clone, Copy)]
101pub struct GraphlikeEdgeRef<'a> {
102    edge: &'a FaultScopeNativeGraphlikeEdgeV1,
103    fault_observables: &'a [u32],
104}
105
106impl GraphlikeEdgeRef<'_> {
107    pub fn detector_count(&self) -> usize {
108        self.edge.detector_count as usize
109    }
110
111    pub fn detectors(&self) -> impl ExactSizeIterator<Item = usize> + DoubleEndedIterator + '_ {
112        [self.edge.detector0 as usize, self.edge.detector1 as usize]
113            .into_iter()
114            .take(self.detector_count())
115    }
116
117    pub fn fault_observables(
118        &self,
119    ) -> impl ExactSizeIterator<Item = usize> + DoubleEndedIterator + '_ {
120        self.fault_observables.iter().map(|index| *index as usize)
121    }
122
123    pub fn probability(&self) -> f64 {
124        self.edge.probability
125    }
126
127    pub fn weight(&self) -> f64 {
128        self.edge.weight
129    }
130
131    pub fn dem_edge_index(&self) -> usize {
132        self.edge.dem_edge_index
133    }
134
135    pub fn to_owned(self) -> GraphlikeEdge {
136        GraphlikeEdge {
137            detectors: self.detectors().collect(),
138            fault_observables: self.fault_observables().collect(),
139            probability: self.probability(),
140            dem_edge_index: self.dem_edge_index(),
141        }
142    }
143}
144
145impl fmt::Debug for GraphlikeEdgeRef<'_> {
146    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
147        formatter
148            .debug_struct("GraphlikeEdgeRef")
149            .field("dem_edge_index", &self.dem_edge_index())
150            .field("detectors", &self.detectors().collect::<Vec<_>>())
151            .field(
152                "fault_observables",
153                &self.fault_observables().collect::<Vec<_>>(),
154            )
155            .field("probability", &self.probability())
156            .field("weight", &self.weight())
157            .finish()
158    }
159}
160
161#[derive(Debug, Clone, PartialEq)]
162pub struct GraphlikeDecodingProblem {
163    detector_ids: Vec<i64>,
164    detector_coords: Vec<Vec<f64>>,
165    observable_ids: Vec<i64>,
166    edges: Vec<FaultScopeNativeGraphlikeEdgeV1>,
167    fault_observables: Vec<u32>,
168}
169
170impl GraphlikeDecodingProblem {
171    /// Build a validated compact problem from owned compatibility edge DTOs.
172    pub fn new(
173        detector_ids: Vec<i64>,
174        detector_coords: Vec<Vec<f64>>,
175        observable_ids: Vec<i64>,
176        edges: Vec<GraphlikeEdge>,
177    ) -> NpResult<Self> {
178        let mut builder = GraphlikeProblemBuilder::new(
179            detector_ids,
180            detector_coords,
181            observable_ids,
182            edges.len(),
183        )?;
184        for mut edge in edges {
185            parity_canonicalize(&mut edge.detectors);
186            parity_canonicalize(&mut edge.fault_observables);
187            builder.push_edge(
188                &edge.detectors,
189                &edge.fault_observables,
190                edge.probability,
191                edge.dem_edge_index,
192            )?;
193        }
194        Ok(builder.build())
195    }
196
197    pub fn detector_ids(&self) -> &[i64] {
198        &self.detector_ids
199    }
200
201    pub fn detector_coords(&self) -> &[Vec<f64>] {
202        &self.detector_coords
203    }
204
205    pub fn observable_ids(&self) -> &[i64] {
206        &self.observable_ids
207    }
208
209    pub fn edge_count(&self) -> usize {
210        self.edges.len()
211    }
212
213    pub fn edge(&self, index: usize) -> Option<GraphlikeEdgeRef<'_>> {
214        self.edges.get(index).map(|edge| self.edge_ref(edge))
215    }
216
217    pub fn iter_edges(
218        &self,
219    ) -> impl ExactSizeIterator<Item = GraphlikeEdgeRef<'_>> + DoubleEndedIterator + '_ {
220        self.edges.iter().map(|edge| self.edge_ref(edge))
221    }
222
223    /// Return a zero-copy descriptor for a versioned native construction capsule.
224    #[doc(hidden)]
225    pub fn native_view(&self) -> FaultScopeNativeGraphlikeProblemV1 {
226        FaultScopeNativeGraphlikeProblemV1 {
227            abi_version: NATIVE_GRAPHLIKE_PROBLEM_ABI_VERSION,
228            struct_size: mem::size_of::<FaultScopeNativeGraphlikeProblemV1>(),
229            edge_struct_size: mem::size_of::<FaultScopeNativeGraphlikeEdgeV1>(),
230            detector_ids: self.detector_ids.as_ptr(),
231            detector_count: self.detector_ids.len(),
232            observable_ids: self.observable_ids.as_ptr(),
233            observable_count: self.observable_ids.len(),
234            edges: self.edges.as_ptr(),
235            edge_count: self.edges.len(),
236            fault_observables: self.fault_observables.as_ptr(),
237            fault_observable_count: self.fault_observables.len(),
238        }
239    }
240
241    pub(crate) fn into_ids(self) -> (Vec<i64>, Vec<i64>) {
242        (self.detector_ids, self.observable_ids)
243    }
244
245    fn edge_ref<'a>(&'a self, edge: &'a FaultScopeNativeGraphlikeEdgeV1) -> GraphlikeEdgeRef<'a> {
246        let start = edge.fault_observable_offset as usize;
247        let end = start + edge.fault_observable_count as usize;
248        GraphlikeEdgeRef {
249            edge,
250            fault_observables: &self.fault_observables[start..end],
251        }
252    }
253}
254
255struct GraphlikeProblemBuilder {
256    detector_ids: Vec<i64>,
257    detector_coords: Vec<Vec<f64>>,
258    observable_ids: Vec<i64>,
259    edges: Vec<FaultScopeNativeGraphlikeEdgeV1>,
260    fault_observables: Vec<u32>,
261}
262
263impl GraphlikeProblemBuilder {
264    fn new(
265        detector_ids: Vec<i64>,
266        detector_coords: Vec<Vec<f64>>,
267        observable_ids: Vec<i64>,
268        edge_capacity: usize,
269    ) -> NpResult<Self> {
270        if detector_coords.len() != detector_ids.len() {
271            return Err(NpError::new(format!(
272                "graphlike detector coordinate count {} does not match detector count {}",
273                detector_coords.len(),
274                detector_ids.len()
275            )));
276        }
277        ensure_unique_ids(&detector_ids, "graphlike detector ids must be unique")?;
278        ensure_unique_ids(
279            &observable_ids,
280            "graphlike logical observable ids must be unique",
281        )?;
282        if u32::try_from(detector_ids.len()).is_err() {
283            return Err(NpError::new(
284                "graphlike detector count exceeds the native u32 index capacity",
285            ));
286        }
287        if u32::try_from(observable_ids.len()).is_err() {
288            return Err(NpError::new(
289                "graphlike observable count exceeds the native u32 index capacity",
290            ));
291        }
292        Ok(Self {
293            detector_ids,
294            detector_coords,
295            observable_ids,
296            edges: Vec::with_capacity(edge_capacity),
297            fault_observables: Vec::with_capacity(edge_capacity),
298        })
299    }
300
301    fn push_edge(
302        &mut self,
303        detectors: &[usize],
304        fault_observables: &[usize],
305        probability: f64,
306        dem_edge_index: usize,
307    ) -> NpResult<()> {
308        validate_graphlike_probability(probability)?;
309        let weight = log_likelihood_ratio(probability);
310        if detectors.len() > 2 {
311            return Err(NpError::new(format!(
312                "graphlike decoder requires at most two detectors per edge; edge {dem_edge_index} has {}",
313                detectors.len()
314            )));
315        }
316        if detectors.is_empty() && !fault_observables.is_empty() {
317            return Err(NpError::new(format!(
318                "graphlike decoder cannot use undetectable logical edge {dem_edge_index}; observables={fault_observables:?}"
319            )));
320        }
321        for detector in detectors {
322            if *detector >= self.detector_ids.len() {
323                return Err(NpError::new(format!(
324                    "graphlike edge {dem_edge_index} references detector index {detector} but only {} detectors exist",
325                    self.detector_ids.len()
326                )));
327            }
328        }
329        for observable in fault_observables {
330            if *observable >= self.observable_ids.len() {
331                return Err(NpError::new(format!(
332                    "graphlike edge {dem_edge_index} references observable index {observable} but only {} observables exist",
333                    self.observable_ids.len()
334                )));
335            }
336        }
337
338        let fault_observable_offset = u32::try_from(self.fault_observables.len())
339            .map_err(|_| NpError::new("graphlike observable pool exceeds native u32 capacity"))?;
340        let fault_observable_count = u32::try_from(fault_observables.len()).map_err(|_| {
341            NpError::new(format!(
342                "graphlike edge {dem_edge_index} observable support exceeds native u32 capacity"
343            ))
344        })?;
345        let new_observable_count = self
346            .fault_observables
347            .len()
348            .checked_add(fault_observables.len())
349            .ok_or_else(|| NpError::new("graphlike observable pool length overflow"))?;
350        if u32::try_from(new_observable_count).is_err() {
351            return Err(NpError::new(
352                "graphlike observable pool exceeds native u32 capacity",
353            ));
354        }
355        self.fault_observables.extend(
356            fault_observables
357                .iter()
358                .map(|index| u32::try_from(*index).expect("observable index capacity validated")),
359        );
360
361        self.edges.push(FaultScopeNativeGraphlikeEdgeV1 {
362            dem_edge_index,
363            probability,
364            weight,
365            fault_observable_offset,
366            fault_observable_count,
367            detector0: detectors
368                .first()
369                .map(|index| u32::try_from(*index).expect("detector index capacity validated"))
370                .unwrap_or(0),
371            detector1: detectors
372                .get(1)
373                .map(|index| u32::try_from(*index).expect("detector index capacity validated"))
374                .unwrap_or(0),
375            detector_count: detectors.len() as u32,
376            reserved: 0,
377        });
378        Ok(())
379    }
380
381    fn build(self) -> GraphlikeDecodingProblem {
382        GraphlikeDecodingProblem {
383            detector_ids: self.detector_ids,
384            detector_coords: self.detector_coords,
385            observable_ids: self.observable_ids,
386            edges: self.edges,
387            fault_observables: self.fault_observables,
388        }
389    }
390}
391
392fn ensure_unique_ids(ids: &[i64], message: &'static str) -> NpResult<()> {
393    let mut seen = HashSet::with_capacity(ids.len());
394    if ids.iter().all(|id| seen.insert(*id)) {
395        Ok(())
396    } else {
397        Err(NpError::new(message))
398    }
399}
400
401fn validate_graphlike_probability(probability: f64) -> NpResult<()> {
402    if !(0.0..=1.0).contains(&probability) {
403        return Err(NpError::new(format!(
404            "DEM edge probability must be in [0, 1], got {probability}"
405        )));
406    }
407    Ok(())
408}
409
410#[derive(Clone, Copy)]
411pub(crate) struct GraphlikeSourceEdge<'a> {
412    pub probability: f64,
413    pub detectors: &'a [i64],
414    pub observables: &'a [i64],
415    pub original_edge_index: usize,
416}
417
418pub(crate) fn compile_graphlike_problem_from_edge_views<'a, F, I>(
419    detectors: &'a [crate::Detector],
420    observables: &'a [crate::LogicalObservable],
421    edge_count: usize,
422    edges: F,
423) -> NpResult<GraphlikeDecodingProblem>
424where
425    F: Fn() -> I,
426    I: Iterator<Item = GraphlikeSourceEdge<'a>>,
427{
428    let declared_detector_ids = detectors
429        .iter()
430        .map(|detector| detector.id)
431        .collect::<Vec<_>>();
432    let detector_ids = canonical_id_order(
433        &declared_detector_ids,
434        edges().map(|edge| edge.detectors),
435        "detector ids must be unique",
436    )?;
437    let detector_coords = stable_detector_coords_from_declarations(detectors, &detector_ids);
438    let declared_observable_ids = observables
439        .iter()
440        .map(|observable| observable.id)
441        .collect::<Vec<_>>();
442    let observable_ids = canonical_id_order(
443        &declared_observable_ids,
444        edges().map(|edge| edge.observables),
445        "logical observable ids must be unique",
446    )?;
447    let detector_index = id_index(&detector_ids);
448    let observable_index = id_index(&observable_ids);
449    let mut builder =
450        GraphlikeProblemBuilder::new(detector_ids, detector_coords, observable_ids, edge_count)?;
451
452    for edge in edges() {
453        validate_graphlike_probability(edge.probability)?;
454        let mut detector_indices = edge
455            .detectors
456            .iter()
457            .map(|detector_id| {
458                detector_index.get(detector_id).copied().ok_or_else(|| {
459                    NpError::new(format!("unknown detector id {detector_id} in DEM edge"))
460                })
461            })
462            .collect::<NpResult<Vec<_>>>()?;
463        parity_canonicalize(&mut detector_indices);
464        let mut observable_indices = edge
465            .observables
466            .iter()
467            .map(|observable_id| {
468                observable_index.get(observable_id).copied().ok_or_else(|| {
469                    NpError::new(format!(
470                        "unknown logical observable id {observable_id} in DEM edge"
471                    ))
472                })
473            })
474            .collect::<NpResult<Vec<_>>>()?;
475        parity_canonicalize(&mut observable_indices);
476        builder.push_edge(
477            &detector_indices,
478            &observable_indices,
479            edge.probability,
480            edge.original_edge_index,
481        )?;
482    }
483    Ok(builder.build())
484}
485
486#[derive(Debug, Clone, PartialEq, Eq)]
487pub struct SparseBinaryMatrix {
488    pub row_count: usize,
489    pub col_count: usize,
490    pub entries: Vec<(usize, usize)>,
491}
492
493#[derive(Debug, Clone, PartialEq)]
494pub struct BinaryLinearDecodingProblem {
495    pub detector_ids: Vec<i64>,
496    pub detector_coords: Vec<Vec<f64>>,
497    pub observable_ids: Vec<i64>,
498    pub edge_count: usize,
499    pub h: SparseBinaryMatrix,
500    pub f: SparseBinaryMatrix,
501    pub probabilities: Vec<f64>,
502    pub log_likelihood_ratios: Vec<f64>,
503    pub dem_edge_indices: Vec<usize>,
504}
505
506impl DetectorErrorModel {
507    pub fn compile_indexed(&self) -> NpResult<IndexedDem> {
508        let declared_detector_ids = self
509            .detectors
510            .iter()
511            .map(|detector| detector.id)
512            .collect::<Vec<_>>();
513        let detector_ids = canonical_id_order(
514            &declared_detector_ids,
515            self.edges.iter().map(|edge| edge.detectors.as_slice()),
516            "detector ids must be unique",
517        )?;
518        let detector_coords = stable_detector_coords(self, &detector_ids);
519        let declared_observable_ids = self
520            .observables
521            .iter()
522            .map(|observable| observable.id)
523            .collect::<Vec<_>>();
524        let observable_ids = canonical_id_order(
525            &declared_observable_ids,
526            self.edges.iter().map(|edge| edge.observables.as_slice()),
527            "logical observable ids must be unique",
528        )?;
529        let detector_index = id_index(&detector_ids);
530        let observable_index = id_index(&observable_ids);
531        let mut edges = Vec::with_capacity(self.edges.len());
532
533        for (edge_index, edge) in self.edges.iter().enumerate() {
534            edge.validate()?;
535            let mut detectors = edge
536                .detectors
537                .iter()
538                .map(|detector_id| {
539                    detector_index.get(detector_id).copied().ok_or_else(|| {
540                        NpError::new(format!("unknown detector id {detector_id} in DEM edge"))
541                    })
542                })
543                .collect::<NpResult<Vec<_>>>()?;
544            parity_canonicalize(&mut detectors);
545            let mut observables = edge
546                .observables
547                .iter()
548                .map(|observable_id| {
549                    observable_index.get(observable_id).copied().ok_or_else(|| {
550                        NpError::new(format!(
551                            "unknown logical observable id {observable_id} in DEM edge"
552                        ))
553                    })
554                })
555                .collect::<NpResult<Vec<_>>>()?;
556            parity_canonicalize(&mut observables);
557            edges.push(IndexedDemEdge {
558                probability: edge.probability,
559                weight: log_likelihood_ratio(edge.probability),
560                detectors,
561                observables,
562                original_edge_index: edge_index,
563            });
564        }
565
566        Ok(IndexedDem {
567            detector_ids,
568            detector_coords,
569            observable_ids,
570            edges,
571        })
572    }
573
574    pub fn is_graphlike(&self) -> bool {
575        self.edges.iter().all(|edge| {
576            let detector_count = parity_support_len(&edge.detectors);
577            detector_count <= 2
578                && (detector_count != 0 || parity_support_len(&edge.observables) == 0)
579        })
580    }
581
582    pub fn compile_graphlike_problem(&self) -> NpResult<GraphlikeDecodingProblem> {
583        compile_graphlike_problem_from_edge_views(
584            &self.detectors,
585            &self.observables,
586            self.edges.len(),
587            || {
588                self.edges
589                    .iter()
590                    .enumerate()
591                    .map(|(edge_index, edge)| GraphlikeSourceEdge {
592                        probability: edge.probability,
593                        detectors: &edge.detectors,
594                        observables: &edge.observables,
595                        original_edge_index: edge_index,
596                    })
597            },
598        )
599    }
600
601    /// Compile a graphlike decoder view using per-edge decomposition hints.
602    ///
603    /// The canonical DEM remains unchanged: every component inherits its
604    /// parent edge's probability and original edge index. The decomposition is
605    /// accepted only when the GF(2) XOR of its components exactly reproduces
606    /// the canonical detector and observable support of the parent edge.
607    pub fn compile_graphlike_problem_with_decomposition(
608        &self,
609        decomposition: &HashMap<usize, Vec<GraphlikeDecompositionComponent>>,
610    ) -> NpResult<GraphlikeDecodingProblem> {
611        for edge_index in decomposition.keys() {
612            if *edge_index >= self.edges.len() {
613                return Err(NpError::new(format!(
614                    "graphlike decomposition references DEM edge index {edge_index} but only {} edges exist",
615                    self.edges.len()
616                )));
617            }
618        }
619
620        let indexed = self.compile_indexed()?;
621        let detector_index = id_index(&indexed.detector_ids);
622        let observable_index = id_index(&indexed.observable_ids);
623        let edge_capacity = indexed.edges.iter().try_fold(0usize, |total, edge| {
624            total
625                .checked_add(
626                    decomposition
627                        .get(&edge.original_edge_index)
628                        .map_or(1, Vec::len),
629                )
630                .ok_or_else(|| NpError::new("graphlike decomposition edge count overflow"))
631        })?;
632        let mut builder = GraphlikeProblemBuilder::new(
633            indexed.detector_ids.clone(),
634            indexed.detector_coords.clone(),
635            indexed.observable_ids.clone(),
636            edge_capacity,
637        )?;
638
639        for edge in &indexed.edges {
640            let Some(components) = decomposition.get(&edge.original_edge_index) else {
641                builder.push_edge(
642                    &edge.detectors,
643                    &edge.observables,
644                    edge.probability,
645                    edge.original_edge_index,
646                )?;
647                continue;
648            };
649            if components.is_empty() {
650                return Err(NpError::new(format!(
651                    "graphlike decomposition for DEM edge {} must contain at least one component",
652                    edge.original_edge_index
653                )));
654            }
655
656            let mut compiled_components = Vec::with_capacity(components.len());
657            let mut detector_xor = Vec::new();
658            let mut observable_xor = Vec::new();
659            for (component_index, component) in components.iter().enumerate() {
660                let mut detectors = component
661                    .detectors
662                    .iter()
663                    .map(|detector_id| {
664                        detector_index.get(detector_id).copied().ok_or_else(|| {
665                            NpError::new(format!(
666                                "graphlike decomposition for DEM edge {} component {component_index} references unknown detector id {detector_id}",
667                                edge.original_edge_index
668                            ))
669                        })
670                    })
671                    .collect::<NpResult<Vec<_>>>()?;
672                parity_canonicalize(&mut detectors);
673                let mut observables = component
674                    .observables
675                    .iter()
676                    .map(|observable_id| {
677                        observable_index.get(observable_id).copied().ok_or_else(|| {
678                            NpError::new(format!(
679                                "graphlike decomposition for DEM edge {} component {component_index} references unknown logical observable id {observable_id}",
680                                edge.original_edge_index
681                            ))
682                        })
683                    })
684                    .collect::<NpResult<Vec<_>>>()?;
685                parity_canonicalize(&mut observables);
686
687                if detectors.is_empty() && observables.is_empty() {
688                    return Err(NpError::new(format!(
689                        "graphlike decomposition for DEM edge {} component {component_index} is empty after GF(2) parity reduction",
690                        edge.original_edge_index
691                    )));
692                }
693                if detectors.len() > 2 {
694                    return Err(NpError::new(format!(
695                        "graphlike decomposition for DEM edge {} component {component_index} has {} detectors after GF(2) parity reduction; expected at most two",
696                        edge.original_edge_index,
697                        detectors.len()
698                    )));
699                }
700                if detectors.is_empty() {
701                    return Err(NpError::new(format!(
702                        "graphlike decomposition for DEM edge {} component {component_index} is a pure logical component; at least one detector is required",
703                        edge.original_edge_index
704                    )));
705                }
706
707                detector_xor.extend_from_slice(&detectors);
708                observable_xor.extend_from_slice(&observables);
709                compiled_components.push((detectors, observables));
710            }
711
712            if !gf2_support_equal(&detector_xor, &edge.detectors)
713                || !gf2_support_equal(&observable_xor, &edge.observables)
714            {
715                return Err(NpError::new(format!(
716                    "graphlike decomposition for DEM edge {} does not reproduce the parent detector and observable support under GF(2) XOR",
717                    edge.original_edge_index
718                )));
719            }
720
721            for (detectors, observables) in compiled_components {
722                builder.push_edge(
723                    &detectors,
724                    &observables,
725                    edge.probability,
726                    edge.original_edge_index,
727                )?;
728            }
729        }
730
731        Ok(builder.build())
732    }
733
734    pub fn compile_binary_linear_problem(&self) -> NpResult<BinaryLinearDecodingProblem> {
735        let indexed = self.compile_indexed()?;
736        let mut h_entries = Vec::new();
737        let mut f_entries = Vec::new();
738        let mut probabilities = Vec::with_capacity(indexed.edges.len());
739        let mut log_likelihood_ratios = Vec::with_capacity(indexed.edges.len());
740        let mut dem_edge_indices = Vec::with_capacity(indexed.edges.len());
741
742        for (column, edge) in indexed.edges.iter().enumerate() {
743            for detector in &edge.detectors {
744                h_entries.push((*detector, column));
745            }
746            for observable in &edge.observables {
747                f_entries.push((*observable, column));
748            }
749            probabilities.push(edge.probability);
750            log_likelihood_ratios.push(edge.weight);
751            dem_edge_indices.push(edge.original_edge_index);
752        }
753
754        Ok(BinaryLinearDecodingProblem {
755            detector_ids: indexed.detector_ids.clone(),
756            detector_coords: indexed.detector_coords.clone(),
757            observable_ids: indexed.observable_ids.clone(),
758            edge_count: indexed.edges.len(),
759            h: SparseBinaryMatrix {
760                row_count: indexed.detector_ids.len(),
761                col_count: indexed.edges.len(),
762                entries: h_entries,
763            },
764            f: SparseBinaryMatrix {
765                row_count: indexed.observable_ids.len(),
766                col_count: indexed.edges.len(),
767                entries: f_entries,
768            },
769            probabilities,
770            log_likelihood_ratios,
771            dem_edge_indices,
772        })
773    }
774}
775
776fn stable_detector_coords(dem: &DetectorErrorModel, detector_ids: &[i64]) -> Vec<Vec<f64>> {
777    stable_detector_coords_from_declarations(&dem.detectors, detector_ids)
778}
779
780fn stable_detector_coords_from_declarations(
781    detectors: &[crate::Detector],
782    detector_ids: &[i64],
783) -> Vec<Vec<f64>> {
784    let coords_by_id = detectors
785        .iter()
786        .map(|detector| (detector.id, detector.coords.clone()))
787        .collect::<HashMap<_, _>>();
788    detector_ids
789        .iter()
790        .map(|detector_id| coords_by_id.get(detector_id).cloned().unwrap_or_default())
791        .collect()
792}
793
794fn id_index(ids: &[i64]) -> HashMap<i64, usize> {
795    ids.iter()
796        .copied()
797        .enumerate()
798        .map(|(index, id)| (id, index))
799        .collect()
800}
801
802fn gf2_support_equal(left: &[usize], right: &[usize]) -> bool {
803    let mut left = left.to_vec();
804    let mut right = right.to_vec();
805    parity_canonicalize(&mut left);
806    parity_canonicalize(&mut right);
807    left.sort_unstable();
808    right.sort_unstable();
809    left == right
810}
811
812pub fn log_likelihood_ratio(probability: f64) -> f64 {
813    let p = probability.clamp(1e-15, 1.0 - 1e-15);
814    ((1.0 - p) / p).ln()
815}
816
817#[cfg(test)]
818mod tests {
819    use super::*;
820    use crate::{DemEvent, Detector, DetectorErrorEdge, LogicalObservable};
821
822    fn edge(
823        probability: f64,
824        detectors: Vec<i64>,
825        observables: Vec<i64>,
826        location_id: &str,
827    ) -> DetectorErrorEdge {
828        DetectorErrorEdge {
829            probability,
830            detectors,
831            observables,
832            location_id: location_id.to_string(),
833            event: DemEvent::Pauli("X".to_string()),
834            tags: HashMap::new(),
835        }
836    }
837
838    fn dem() -> DetectorErrorModel {
839        DetectorErrorModel {
840            detectors: vec![
841                Detector {
842                    id: 5,
843                    measurement_keys: Vec::new(),
844                    coords: vec![5.0, 0.0],
845                },
846                Detector {
847                    id: 2,
848                    measurement_keys: Vec::new(),
849                    coords: vec![2.0, 0.0],
850                },
851            ],
852            observables: vec![LogicalObservable {
853                id: 7,
854                measurement_keys: Vec::new(),
855                pauli_qubits: Vec::new(),
856                pauli: String::new(),
857            }],
858            edges: vec![
859                edge(0.1, vec![2, 9], vec![7], "a"),
860                edge(0.2, vec![5], vec![], "b"),
861            ],
862        }
863    }
864
865    #[test]
866    fn indexed_dem_preserves_declared_order_and_appends_edge_ids() {
867        let indexed = dem().compile_indexed().unwrap();
868
869        assert_eq!(indexed.detector_ids, vec![5, 2, 9]);
870        assert_eq!(
871            indexed.detector_coords,
872            vec![vec![5.0, 0.0], vec![2.0, 0.0], Vec::<f64>::new()]
873        );
874        assert_eq!(indexed.observable_ids, vec![7]);
875        assert_eq!(indexed.edges[0].detectors, vec![1, 2]);
876        assert_eq!(indexed.edges[0].observables, vec![0]);
877        assert_eq!(indexed.edges[0].original_edge_index, 0);
878    }
879
880    #[test]
881    fn graphlike_problem_rejects_hyperedges() {
882        let mut dem = dem();
883        dem.edges.push(edge(0.3, vec![1, 2, 3], vec![], "hyper"));
884
885        let err = dem.compile_graphlike_problem().unwrap_err();
886
887        assert!(err.message().contains("at most two detectors"));
888    }
889
890    #[test]
891    fn graphlike_decomposition_accepts_order_independent_support_and_preserves_emission_order() {
892        let dem = DetectorErrorModel {
893            detectors: Vec::new(),
894            observables: Vec::new(),
895            edges: vec![
896                edge(0.125, vec![10, 20, 30], vec![7], "hyper"),
897                edge(0.25, vec![40], vec![], "plain"),
898            ],
899        };
900        let decomposition = HashMap::from([(
901            0,
902            vec![
903                GraphlikeDecompositionComponent {
904                    detectors: vec![30],
905                    observables: vec![],
906                },
907                GraphlikeDecompositionComponent {
908                    detectors: vec![20, 10, 20, 20],
909                    observables: vec![7, 7, 7],
910                },
911            ],
912        )]);
913
914        let problem = dem
915            .compile_graphlike_problem_with_decomposition(&decomposition)
916            .unwrap();
917        let edges = problem
918            .iter_edges()
919            .map(GraphlikeEdgeRef::to_owned)
920            .collect::<Vec<_>>();
921
922        assert_eq!(problem.detector_ids(), &[10, 20, 30, 40]);
923        assert_eq!(problem.observable_ids(), &[7]);
924        assert_eq!(edges.len(), 3);
925        assert_eq!(edges[0].detectors, vec![2]);
926        assert!(edges[0].fault_observables.is_empty());
927        assert_eq!(edges[1].detectors, vec![1, 0]);
928        assert_eq!(edges[1].fault_observables, vec![0]);
929        assert_eq!(edges[2].detectors, vec![3]);
930        assert_eq!(
931            edges
932                .iter()
933                .map(|edge| edge.dem_edge_index)
934                .collect::<Vec<_>>(),
935            vec![0, 0, 1]
936        );
937        assert_eq!(
938            edges
939                .iter()
940                .map(|edge| edge.probability)
941                .collect::<Vec<_>>(),
942            vec![0.125, 0.125, 0.25]
943        );
944    }
945
946    #[test]
947    fn graphlike_decomposition_rejects_invalid_edge_index_and_empty_component_list() {
948        let dem = DetectorErrorModel {
949            detectors: Vec::new(),
950            observables: Vec::new(),
951            edges: vec![edge(0.25, vec![10], vec![], "edge")],
952        };
953
954        let err = dem
955            .compile_graphlike_problem_with_decomposition(&HashMap::from([(1, vec![])]))
956            .unwrap_err();
957        assert!(err.message().contains("index 1"));
958
959        let err = dem
960            .compile_graphlike_problem_with_decomposition(&HashMap::from([(0, vec![])]))
961            .unwrap_err();
962        assert!(err.message().contains("at least one component"));
963    }
964
965    #[test]
966    fn graphlike_decomposition_rejects_invalid_components() {
967        let dem = DetectorErrorModel {
968            detectors: vec![
969                Detector {
970                    id: 10,
971                    measurement_keys: Vec::new(),
972                    coords: Vec::new(),
973                },
974                Detector {
975                    id: 20,
976                    measurement_keys: Vec::new(),
977                    coords: Vec::new(),
978                },
979                Detector {
980                    id: 30,
981                    measurement_keys: Vec::new(),
982                    coords: Vec::new(),
983                },
984            ],
985            observables: vec![LogicalObservable {
986                id: 7,
987                measurement_keys: Vec::new(),
988                pauli_qubits: Vec::new(),
989                pauli: String::new(),
990            }],
991            edges: vec![edge(0.25, vec![10, 20, 30], vec![7], "hyper")],
992        };
993
994        let cases = [
995            (
996                vec![GraphlikeDecompositionComponent {
997                    detectors: vec![10, 10],
998                    observables: vec![],
999                }],
1000                "empty after GF(2)",
1001            ),
1002            (
1003                vec![GraphlikeDecompositionComponent {
1004                    detectors: vec![],
1005                    observables: vec![7],
1006                }],
1007                "pure logical component",
1008            ),
1009            (
1010                vec![GraphlikeDecompositionComponent {
1011                    detectors: vec![10, 20, 30],
1012                    observables: vec![7],
1013                }],
1014                "expected at most two",
1015            ),
1016            (
1017                vec![GraphlikeDecompositionComponent {
1018                    detectors: vec![99],
1019                    observables: vec![],
1020                }],
1021                "unknown detector id 99",
1022            ),
1023            (
1024                vec![GraphlikeDecompositionComponent {
1025                    detectors: vec![10],
1026                    observables: vec![99],
1027                }],
1028                "unknown logical observable id 99",
1029            ),
1030        ];
1031        for (components, expected) in cases {
1032            let err = dem
1033                .compile_graphlike_problem_with_decomposition(&HashMap::from([(0, components)]))
1034                .unwrap_err();
1035            assert!(
1036                err.message().contains(expected),
1037                "expected {expected:?} in {:?}",
1038                err.message()
1039            );
1040        }
1041    }
1042
1043    #[test]
1044    fn graphlike_decomposition_rejects_xor_mismatch() {
1045        let dem = DetectorErrorModel {
1046            detectors: Vec::new(),
1047            observables: Vec::new(),
1048            edges: vec![edge(0.25, vec![10, 20, 30], vec![], "hyper")],
1049        };
1050        let decomposition = HashMap::from([(
1051            0,
1052            vec![
1053                GraphlikeDecompositionComponent {
1054                    detectors: vec![10, 20],
1055                    observables: vec![],
1056                },
1057                GraphlikeDecompositionComponent {
1058                    detectors: vec![20, 30],
1059                    observables: vec![],
1060                },
1061            ],
1062        )]);
1063
1064        let err = dem
1065            .compile_graphlike_problem_with_decomposition(&decomposition)
1066            .unwrap_err();
1067
1068        assert!(err.message().contains("does not reproduce"));
1069    }
1070
1071    #[test]
1072    fn graphlike_problem_preserves_detector_coords() {
1073        let problem = dem().compile_graphlike_problem().unwrap();
1074
1075        assert_eq!(problem.detector_ids(), &[5, 2, 9]);
1076        assert_eq!(
1077            problem.detector_coords(),
1078            &[vec![5.0, 0.0], vec![2.0, 0.0], Vec::<f64>::new()]
1079        );
1080    }
1081
1082    #[test]
1083    fn graphlike_problem_rejects_undetectable_logical_edges() {
1084        let dem = DetectorErrorModel {
1085            detectors: Vec::new(),
1086            observables: vec![LogicalObservable {
1087                id: 0,
1088                measurement_keys: Vec::new(),
1089                pauli_qubits: Vec::new(),
1090                pauli: String::new(),
1091            }],
1092            edges: vec![edge(0.3, vec![], vec![0], "logical")],
1093        };
1094
1095        let err = dem.compile_graphlike_problem().unwrap_err();
1096
1097        assert!(err.message().contains("undetectable logical edge"));
1098    }
1099
1100    #[test]
1101    fn binary_linear_problem_matches_dem_flips() {
1102        let problem = dem().compile_binary_linear_problem().unwrap();
1103
1104        assert_eq!(problem.h.row_count, 3);
1105        assert_eq!(
1106            problem.detector_coords,
1107            vec![vec![5.0, 0.0], vec![2.0, 0.0], Vec::<f64>::new()]
1108        );
1109        assert_eq!(problem.h.col_count, 2);
1110        assert_eq!(problem.h.entries, vec![(1, 0), (2, 0), (0, 1)]);
1111        assert_eq!(problem.f.entries, vec![(0, 0)]);
1112        assert_eq!(problem.probabilities, vec![0.1, 0.2]);
1113        assert_eq!(problem.dem_edge_indices, vec![0, 1]);
1114    }
1115
1116    #[test]
1117    fn canonical_problem_views_reduce_edge_targets_by_parity() {
1118        let dem = DetectorErrorModel {
1119            detectors: Vec::new(),
1120            observables: Vec::new(),
1121            edges: vec![
1122                edge(1.0, vec![1, 1], vec![9, 9], "cancelled"),
1123                edge(0.5, vec![4, 2, 4], vec![8, 8, 7], "odd"),
1124            ],
1125        };
1126
1127        let indexed = dem.compile_indexed().unwrap();
1128        let binary = dem.compile_binary_linear_problem().unwrap();
1129
1130        assert_eq!(indexed.detector_ids, vec![1, 4, 2]);
1131        assert_eq!(indexed.detector_coords, vec![vec![], vec![], vec![]]);
1132        assert_eq!(indexed.observable_ids, vec![9, 8, 7]);
1133        assert!(indexed.edges[0].detectors.is_empty());
1134        assert!(indexed.edges[0].observables.is_empty());
1135        assert_eq!(indexed.edges[1].detectors, vec![2]);
1136        assert_eq!(indexed.edges[1].observables, vec![2]);
1137        assert_eq!(binary.h.entries, vec![(2, 1)]);
1138        assert_eq!(binary.f.entries, vec![(2, 1)]);
1139    }
1140
1141    #[test]
1142    fn graphlike_classification_uses_parity_reduced_support() {
1143        let graphlike = DetectorErrorModel {
1144            detectors: Vec::new(),
1145            observables: Vec::new(),
1146            edges: vec![edge(0.25, vec![1, 2, 3, 2], vec![], "reduced")],
1147        };
1148        let hypergraph = DetectorErrorModel {
1149            detectors: Vec::new(),
1150            observables: Vec::new(),
1151            edges: vec![edge(0.25, vec![1, 2, 3, 2, 4], vec![], "hyper")],
1152        };
1153
1154        assert!(graphlike.is_graphlike());
1155        assert_eq!(
1156            graphlike
1157                .compile_graphlike_problem()
1158                .unwrap()
1159                .edge(0)
1160                .unwrap()
1161                .detectors()
1162                .collect::<Vec<_>>(),
1163            vec![0, 2],
1164        );
1165        assert!(!hypergraph.is_graphlike());
1166        assert!(hypergraph.compile_graphlike_problem().is_err());
1167    }
1168
1169    #[test]
1170    fn compact_graphlike_problem_round_trips_owned_edges_and_native_view() {
1171        let problem = dem().compile_graphlike_problem().unwrap();
1172        let owned = problem
1173            .iter_edges()
1174            .map(GraphlikeEdgeRef::to_owned)
1175            .collect::<Vec<_>>();
1176
1177        assert_eq!(owned.len(), 2);
1178        assert_eq!(owned[0].detectors, vec![1, 2]);
1179        assert_eq!(owned[0].fault_observables, vec![0]);
1180        assert_eq!(
1181            problem.edge(1).unwrap().detectors().collect::<Vec<_>>(),
1182            vec![0]
1183        );
1184
1185        let view = problem.native_view();
1186        assert_eq!(view.abi_version, NATIVE_GRAPHLIKE_PROBLEM_ABI_VERSION);
1187        assert_eq!(
1188            view.struct_size,
1189            mem::size_of::<FaultScopeNativeGraphlikeProblemV1>()
1190        );
1191        assert_eq!(
1192            view.edge_struct_size,
1193            mem::size_of::<FaultScopeNativeGraphlikeEdgeV1>()
1194        );
1195        assert_eq!(view.detector_count, 3);
1196        assert_eq!(view.observable_count, 1);
1197        assert_eq!(view.edge_count, 2);
1198        assert_eq!(view.fault_observable_count, 1);
1199        let native_edges = unsafe { std::slice::from_raw_parts(view.edges, view.edge_count) };
1200        assert_eq!(native_edges[0].detector_count, 2);
1201        assert_eq!(native_edges[0].detector0, 1);
1202        assert_eq!(native_edges[0].detector1, 2);
1203        assert_eq!(native_edges[0].fault_observable_offset, 0);
1204        assert_eq!(native_edges[0].fault_observable_count, 1);
1205    }
1206
1207    #[test]
1208    fn graphlike_constructor_validates_metadata_and_canonicalizes_edge_parity() {
1209        let problem = GraphlikeDecodingProblem::new(
1210            vec![10, 20],
1211            vec![vec![], vec![]],
1212            vec![0, 1],
1213            vec![GraphlikeEdge {
1214                detectors: vec![1, 0, 1],
1215                fault_observables: vec![1, 0, 1],
1216                probability: 0.25,
1217                dem_edge_index: 7,
1218            }],
1219        )
1220        .unwrap();
1221        let edge = problem.edge(0).unwrap();
1222        assert_eq!(edge.detectors().collect::<Vec<_>>(), vec![0]);
1223        assert_eq!(edge.fault_observables().collect::<Vec<_>>(), vec![0]);
1224        assert_eq!(edge.weight(), log_likelihood_ratio(0.25));
1225
1226        let err = GraphlikeDecodingProblem::new(vec![10], vec![], vec![], vec![]).unwrap_err();
1227        assert!(err.message().contains("coordinate count"));
1228
1229        let err = GraphlikeDecodingProblem::new(
1230            vec![10],
1231            vec![vec![]],
1232            vec![],
1233            vec![GraphlikeEdge {
1234                detectors: vec![0],
1235                fault_observables: vec![],
1236                probability: f64::NAN,
1237                dem_edge_index: 9,
1238            }],
1239        )
1240        .unwrap_err();
1241        assert!(err.message().contains("probability must be in [0, 1]"));
1242    }
1243
1244    #[test]
1245    fn compiled_views_reject_duplicate_declarations() {
1246        let mut dem = dem();
1247        dem.detectors.push(dem.detectors[0].clone());
1248
1249        let err = dem.compile_indexed().unwrap_err();
1250
1251        assert_eq!(err.message(), "detector ids must be unique");
1252    }
1253}