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#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct GraphlikeDecompositionComponent {
40 pub detectors: Vec<i64>,
41 pub observables: Vec<i64>,
42}
43
44impl GraphlikeEdge {
45 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#[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 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#[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#[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 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 #[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 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}