use ndarray::ArrayView2;
use crate::types::{CheckMatrixOptions, EdgeData, MergeStrategy, StoredBinaryMatrix};
use crate::{Matching, MatchingError, Result};
impl Matching {
pub fn from_check_matrix(
check_matrix: ArrayView2<'_, u8>,
options: CheckMatrixOptions,
) -> Result<Self> {
let mut matching = Self::default();
matching.load_check_matrix(check_matrix, options)?;
Ok(matching)
}
pub fn load_check_matrix(
&mut self,
check_matrix: ArrayView2<'_, u8>,
options: CheckMatrixOptions,
) -> Result<()> {
validate_binary_matrix("check_matrix", check_matrix)?;
let mut column_supports = Vec::with_capacity(check_matrix.ncols());
for col in 0..check_matrix.ncols() {
column_supports.push(nonzero_rows(check_matrix, col)?);
}
self.load_check_matrix_from_column_supports(
check_matrix.nrows(),
check_matrix.ncols(),
column_supports,
options,
)
}
pub(crate) fn load_check_matrix_from_column_supports(
&mut self,
num_rows: usize,
num_cols: usize,
column_supports: Vec<Vec<usize>>,
options: CheckMatrixOptions,
) -> Result<()> {
if column_supports.len() != num_cols {
return Err(MatchingError::InvalidInput(
"column_supports length must match the number of check-matrix columns",
));
}
let resolved = ResolvedCheckMatrixOptions::new(num_rows, num_cols, options)?;
build_matching_from_column_supports(self, num_rows, &column_supports, &resolved)
}
}
#[derive(Debug, Clone)]
struct ResolvedCheckMatrixOptions {
weights: Vec<f64>,
error_probabilities: Vec<f64>,
fault_id_source: FaultIdSource,
merge_strategy: MergeStrategy,
repetitions: usize,
timelike_weights: Option<Vec<f64>>,
measurement_error_probabilities: Option<Vec<f64>>,
use_virtual_boundary_node: bool,
num_fault_ids: usize,
}
impl ResolvedCheckMatrixOptions {
fn new(num_rows: usize, num_cols: usize, options: CheckMatrixOptions) -> Result<Self> {
let CheckMatrixOptions {
weights,
error_probabilities,
faults_matrix,
merge_strategy,
repetitions,
timelike_weights,
measurement_error_probabilities,
use_virtual_boundary_node,
} = options;
if repetitions == 0 {
return Err(MatchingError::Upstream(
"repetitions must be at least 1".to_string(),
));
}
let explicit_error_probabilities = error_probabilities.is_some();
let weights = resolve_values(
weights,
num_cols,
1.0,
"weights length must match the number of check-matrix columns",
)?;
let error_probabilities = resolve_values(
error_probabilities,
num_cols,
-1.0,
"error_probabilities length must match the number of check-matrix columns",
)?;
if explicit_error_probabilities {
validate_explicit_probabilities(&error_probabilities)?;
}
let (fault_id_source, num_fault_ids) = match faults_matrix {
Some(matrix) => {
validate_stored_binary_matrix("faults_matrix", &matrix)?;
if matrix.ncols() != num_cols {
return Err(MatchingError::Upstream(
"faults_matrix column count must match the check matrix".to_string(),
));
}
let rows = matrix.nrows();
(FaultIdSource::Explicit(matrix), rows)
}
None => (FaultIdSource::Identity, num_cols),
};
let timelike_weights = if repetitions > 1 {
Some(resolve_values(
timelike_weights,
num_rows,
1.0,
"timelike_weights length must match the number of check-matrix rows",
)?)
} else {
None
};
let explicit_measurement_error_probabilities = measurement_error_probabilities.is_some();
let measurement_error_probabilities = if repetitions > 1 {
let resolved = resolve_values(
measurement_error_probabilities,
num_rows,
-1.0,
"measurement_error_probabilities length must match the number of check-matrix rows",
)?;
if explicit_measurement_error_probabilities {
validate_explicit_probabilities(&resolved)?;
}
Some(resolved)
} else {
None
};
Ok(Self {
weights,
error_probabilities,
fault_id_source,
merge_strategy,
repetitions,
timelike_weights,
measurement_error_probabilities,
use_virtual_boundary_node,
num_fault_ids,
})
}
fn fault_ids_for_column(&self, col: usize) -> Vec<usize> {
match &self.fault_id_source {
FaultIdSource::Identity => vec![col],
FaultIdSource::Explicit(matrix) => {
let mut fault_ids = Vec::new();
for row in 0..matrix.nrows() {
if matrix.get(row, col) == 1 {
fault_ids.push(row);
}
}
fault_ids
}
}
}
}
#[derive(Debug, Clone)]
enum FaultIdSource {
Identity,
Explicit(StoredBinaryMatrix),
}
fn build_matching_from_column_supports(
matching: &mut Matching,
num_rows: usize,
column_supports: &[Vec<usize>],
resolved: &ResolvedCheckMatrixOptions,
) -> Result<()> {
let mut staged = Matching::default();
staged.ensure_num_fault_ids(resolved.num_fault_ids);
let num_detectors = num_rows * resolved.repetitions;
let mut has_boundary_node = false;
for rep in 0..resolved.repetitions {
for (col, detectors) in column_supports.iter().enumerate() {
let edge = EdgeData {
fault_ids: resolved.fault_ids_for_column(col),
weight: resolved.weights[col],
error_probability: edge_error_probability(resolved.error_probabilities[col]),
};
match detectors.as_slice() {
[node1, node2] => {
staged.insert_edge_with_strategy(
node1 + num_rows * rep,
node2 + num_rows * rep,
edge,
resolved.merge_strategy,
)?;
}
[node] => {
if resolved.use_virtual_boundary_node {
staged.insert_boundary_edge_with_strategy(
node + num_rows * rep,
edge,
resolved.merge_strategy,
)?;
} else {
has_boundary_node = true;
staged.insert_edge_with_strategy(
node + num_rows * rep,
num_detectors,
edge,
resolved.merge_strategy,
)?;
}
}
[] => {}
_ => unreachable!("column supports validate the maximum count"),
}
}
}
if resolved.repetitions > 1 {
let timelike_weights = resolved
.timelike_weights
.as_ref()
.expect("timelike weights are always resolved for repetitions > 1");
let measurement_error_probabilities = resolved
.measurement_error_probabilities
.as_ref()
.expect("measurement error probabilities are always resolved for repetitions > 1");
for rep in 0..(resolved.repetitions - 1) {
for row in 0..num_rows {
staged.insert_edge_with_strategy(
row + rep * num_rows,
row + (rep + 1) * num_rows,
EdgeData {
fault_ids: Vec::new(),
weight: timelike_weights[row],
error_probability: edge_error_probability(
measurement_error_probabilities[row],
),
},
resolved.merge_strategy,
)?;
}
}
}
if has_boundary_node {
staged.set_boundary_nodes([num_detectors]);
}
staged.ensure_num_fault_ids(resolved.num_fault_ids);
staged.refresh_edge_cache();
*matching = staged;
Ok(())
}
fn validate_binary_matrix(name: &str, matrix: ArrayView2<'_, u8>) -> Result<()> {
if matrix.iter().all(|&value| value <= 1) {
Ok(())
} else {
Err(MatchingError::Upstream(format!(
"{name} must contain only binary values"
)))
}
}
fn validate_stored_binary_matrix(name: &str, matrix: &StoredBinaryMatrix) -> Result<()> {
for row in 0..matrix.nrows() {
for col in 0..matrix.ncols() {
if matrix.get(row, col) > 1 {
return Err(MatchingError::Upstream(format!(
"{name} must contain only binary values"
)));
}
}
}
Ok(())
}
fn resolve_values(
values: Option<Vec<f64>>,
expected_len: usize,
default_value: f64,
length_error: &'static str,
) -> Result<Vec<f64>> {
let resolved = values.unwrap_or_else(|| vec![default_value; expected_len]);
if resolved.len() == expected_len {
Ok(resolved)
} else {
Err(MatchingError::Upstream(length_error.to_string()))
}
}
fn validate_explicit_probabilities(probabilities: &[f64]) -> Result<()> {
for &probability in probabilities {
if !(0.0..=1.0).contains(&probability) {
return Err(MatchingError::InvalidProbability { probability });
}
}
Ok(())
}
fn nonzero_rows(check_matrix: ArrayView2<'_, u8>, col: usize) -> Result<Vec<usize>> {
let mut rows = Vec::with_capacity(2);
for row in 0..check_matrix.nrows() {
match check_matrix[(row, col)] {
0 => {}
1 => rows.push(row),
_ => unreachable!("check_matrix is validated before reading"),
}
}
if rows.len() > 2 {
Err(MatchingError::Upstream(format!(
"check_matrix column {col} contains more than two ones"
)))
} else {
Ok(rows)
}
}
fn edge_error_probability(raw: f64) -> Option<f64> {
(0.0..=1.0).contains(&raw).then_some(raw)
}