use std::collections::{HashMap, HashSet};
use crate::flooder::graph::MatchingGraph;
use crate::flooder::graph_flooder::GraphFlooder;
use crate::matcher::mwpm::Mwpm;
use crate::search::search_graph::SearchGraph;
use crate::types::*;
pub const NUM_DISTINCT_WEIGHTS: Weight = 1 << (std::mem::size_of::<Weight>() * 8 - 8);
#[derive(Debug, Clone)]
pub struct UserEdge {
pub node1: usize,
pub node2: usize,
pub observable_indices: Vec<usize>,
pub weight: f64,
pub error_probability: f64,
}
#[derive(Debug, Clone, Default)]
pub struct UserNode {
pub is_boundary: bool,
}
pub struct UserGraph {
pub nodes: Vec<UserNode>,
pub edges: Vec<UserEdge>,
pub boundary_nodes: HashSet<usize>,
pub num_observables: usize,
mwpm: Option<Mwpm>,
all_edges_have_error_probabilities: bool,
}
impl UserGraph {
pub fn new() -> Self {
UserGraph {
nodes: Vec::new(),
edges: Vec::new(),
boundary_nodes: HashSet::new(),
num_observables: 0,
mwpm: None,
all_edges_have_error_probabilities: true,
}
}
fn ensure_node(&mut self, id: usize) {
if id >= self.nodes.len() {
self.nodes.resize_with(id + 1, UserNode::default);
}
}
fn update_num_observables(&mut self, observables: &[usize]) {
for &obs in observables {
if obs + 1 > self.num_observables {
self.num_observables = obs + 1;
}
}
}
pub(crate) fn declare_observable(&mut self, observable: usize) -> Result<(), String> {
let count = observable
.checked_add(1)
.ok_or_else(|| format!("observable index {observable} is too large"))?;
if count > self.num_observables {
self.num_observables = count;
self.mwpm = None;
}
Ok(())
}
fn record_dem_dimensions(
&mut self,
detectors: &[usize],
observables: &[usize],
) -> Result<(), String> {
if let Some(&max_detector) = detectors.iter().max() {
let required_len = max_detector
.checked_add(1)
.ok_or_else(|| format!("detector index {max_detector} is too large"))?;
if required_len > self.nodes.len() {
let additional = required_len - self.nodes.len();
self.nodes.try_reserve(additional).map_err(|_| {
format!("detector index {max_detector} exceeds supported graph capacity")
})?;
self.nodes.resize_with(required_len, UserNode::default);
self.mwpm = None;
}
}
for &observable in observables {
self.declare_observable(observable)?;
}
Ok(())
}
pub fn add_edge(
&mut self,
node1: usize,
node2: usize,
observables: Vec<usize>,
weight: f64,
error_probability: f64,
) {
self.ensure_node(node1.max(node2));
self.update_num_observables(&observables);
if !(0.0..=1.0).contains(&error_probability) {
self.all_edges_have_error_probabilities = false;
}
self.edges.push(UserEdge {
node1,
node2,
observable_indices: observables,
weight,
error_probability,
});
self.mwpm = None;
}
pub fn add_boundary_edge(
&mut self,
node: usize,
observables: Vec<usize>,
weight: f64,
error_probability: f64,
) {
self.ensure_node(node);
self.update_num_observables(&observables);
if !(0.0..=1.0).contains(&error_probability) {
self.all_edges_have_error_probabilities = false;
}
self.edges.push(UserEdge {
node1: node,
node2: usize::MAX,
observable_indices: observables,
weight,
error_probability,
});
self.mwpm = None;
}
pub fn set_boundary(&mut self, nodes: HashSet<usize>) {
for &n in &self.boundary_nodes {
if n < self.nodes.len() {
self.nodes[n].is_boundary = false;
}
}
self.boundary_nodes = nodes;
let max_boundary = self.boundary_nodes.iter().copied().max();
if let Some(m) = max_boundary {
self.ensure_node(m);
}
for &n in &self.boundary_nodes {
self.nodes[n].is_boundary = true;
}
self.mwpm = None;
}
pub fn is_boundary_node(&self, node_id: usize) -> bool {
node_id == usize::MAX || (node_id < self.nodes.len() && self.nodes[node_id].is_boundary)
}
fn max_abs_weight(&self) -> f64 {
self.edges
.iter()
.map(|e| e.weight.abs())
.fold(0.0f64, f64::max)
}
fn get_edge_weight_normalising_constant(&self, num_distinct_weights: Weight) -> f64 {
let max_abs = self.max_abs_weight();
let all_integral = self.edges.iter().all(|e| e.weight.round() == e.weight);
if all_integral {
1.0
} else {
let max_half: f64 = (num_distinct_weights - 1) as f64;
max_half / max_abs
}
}
fn obs_mask(observables: &[usize]) -> ObsMask {
let mut mask: ObsMask = 0;
for &obs in observables {
mask ^= 1u64 << obs;
}
mask
}
pub fn to_matching_graph(&self, num_distinct_weights: Weight) -> MatchingGraph {
let mut mg = MatchingGraph::new(self.nodes.len(), self.num_observables);
let norm = self.get_edge_weight_normalising_constant(num_distinct_weights);
let num_nodes = self.nodes.len();
let mut has_boundary_edge = vec![false; num_nodes];
let mut boundary_edge_weights: Vec<SignedWeight> = vec![0; num_nodes];
let mut boundary_edge_observables: Vec<Vec<usize>> = vec![Vec::new(); num_nodes];
for e in &self.edges {
let w = (e.weight * norm).round() as SignedWeight * 2;
let n1_boundary = self.is_boundary_node(e.node1);
let n2_boundary = self.is_boundary_node(e.node2);
if n2_boundary && !n1_boundary {
if !has_boundary_edge[e.node1] || boundary_edge_weights[e.node1] > w {
boundary_edge_weights[e.node1] = w;
boundary_edge_observables[e.node1] = e.observable_indices.clone();
has_boundary_edge[e.node1] = true;
}
} else if n1_boundary && !n2_boundary {
if !has_boundary_edge[e.node2] || boundary_edge_weights[e.node2] > w {
boundary_edge_weights[e.node2] = w;
boundary_edge_observables[e.node2] = e.observable_indices.clone();
has_boundary_edge[e.node2] = true;
}
} else if !n1_boundary {
mg.add_edge(e.node1, e.node2, w, &e.observable_indices);
}
}
for i in 0..num_nodes {
if has_boundary_edge[i] {
mg.add_boundary_edge(i, boundary_edge_weights[i], &boundary_edge_observables[i]);
}
}
mg.normalising_constant = norm * 2.0;
if !self.boundary_nodes.is_empty() {
mg.is_user_graph_boundary_node = vec![false; self.nodes.len()];
for &i in &self.boundary_nodes {
mg.is_user_graph_boundary_node[i] = true;
}
}
mg.finalize_derived_state();
mg
}
pub fn to_search_graph(&self, num_distinct_weights: Weight) -> SearchGraph {
let mut sg = SearchGraph::new(self.nodes.len(), self.num_observables);
let norm = self.get_edge_weight_normalising_constant(num_distinct_weights);
let num_nodes = self.nodes.len();
let mut has_boundary_edge = vec![false; num_nodes];
let mut boundary_edge_weights: Vec<SignedWeight> = vec![0; num_nodes];
let mut boundary_edge_obs: Vec<ObsMask> = vec![0; num_nodes];
for e in &self.edges {
let w_signed = (e.weight * norm).round() as SignedWeight * 2;
let obs = Self::obs_mask(&e.observable_indices);
let n1_boundary = self.is_boundary_node(e.node1);
let n2_boundary = self.is_boundary_node(e.node2);
if n2_boundary && !n1_boundary {
if !has_boundary_edge[e.node1] || boundary_edge_weights[e.node1] > w_signed {
boundary_edge_weights[e.node1] = w_signed;
boundary_edge_obs[e.node1] = obs;
has_boundary_edge[e.node1] = true;
}
} else if n1_boundary && !n2_boundary {
if !has_boundary_edge[e.node2] || boundary_edge_weights[e.node2] > w_signed {
boundary_edge_weights[e.node2] = w_signed;
boundary_edge_obs[e.node2] = obs;
has_boundary_edge[e.node2] = true;
}
} else if !n1_boundary {
let w = w_signed.unsigned_abs();
sg.add_edge(e.node1, e.node2, w, obs);
}
}
for i in 0..num_nodes {
if has_boundary_edge[i] {
let w = boundary_edge_weights[i].unsigned_abs();
sg.add_boundary_edge(i, w, boundary_edge_obs[i]);
}
}
sg
}
pub fn to_mwpm(&self) -> Mwpm {
let mg = self.to_matching_graph(NUM_DISTINCT_WEIGHTS);
let flooder = GraphFlooder::new(mg);
Mwpm::new(flooder)
}
pub fn get_mwpm(&mut self) -> &mut Mwpm {
if self.mwpm.is_none() {
self.mwpm = Some(self.to_mwpm());
}
self.mwpm.as_mut().unwrap()
}
pub fn handle_dem_instruction(
&mut self,
p: f64,
detectors: &[usize],
observables: Vec<usize>,
) -> Result<(), String> {
if !p.is_finite() || p < 0.0 || p >= 1.0 {
return Err(format!(
"rmatching requires finite error probabilities in the range 0 <= p < 1, got {p}"
));
}
self.record_dem_dimensions(detectors, &observables)?;
if p == 0.0 {
return Ok(());
}
let weight = ((1.0 - p) / p).ln();
match detectors.len() {
2 => self.add_edge(detectors[0], detectors[1], observables, weight, p),
1 => self.add_boundary_edge(detectors[0], observables, weight, p),
0 => {}
count => {
return Err(format!(
"rmatching requires a graphlike DEM, but an error component has {count} detectors: {detectors:?}"
));
}
}
Ok(())
}
pub(crate) fn merge_parallel_dem_edges(&mut self) {
let mut merged_edges: Vec<UserEdge> = Vec::with_capacity(self.edges.len());
let mut edge_indices: HashMap<(usize, usize), usize> = HashMap::new();
for edge in std::mem::take(&mut self.edges) {
let key = if edge.node1 <= edge.node2 {
(edge.node1, edge.node2)
} else {
(edge.node2, edge.node1)
};
if let Some(&edge_index) = edge_indices.get(&key) {
let merged_edge = &mut merged_edges[edge_index];
let previous_probability = merged_edge.error_probability;
let probability = previous_probability * (1.0 - edge.error_probability)
+ edge.error_probability * (1.0 - previous_probability);
merged_edge.error_probability = probability;
merged_edge.weight = ((1.0 - probability) / probability).ln();
} else {
edge_indices.insert(key, merged_edges.len());
merged_edges.push(edge);
}
}
self.edges = merged_edges;
self.mwpm = None;
}
pub fn get_num_edges(&self) -> usize {
self.edges.len()
}
pub fn get_num_nodes(&self) -> usize {
self.nodes.len()
}
pub fn get_num_detectors(&self) -> usize {
self.nodes.len() - self.boundary_nodes.len()
}
}