use rmatching::flooder::graph::MatchingGraph;
use rmatching::flooder::graph_flooder::GraphFlooder;
use rmatching::interop::{CompressedEdge, MwpmEvent};
use rmatching::matcher::alt_tree::{unstable_erase_by_node, AltTreeEdge, AltTreeNode};
use rmatching::matcher::mwpm::Mwpm;
use rmatching::types::*;
use rmatching::Matching;
#[test]
fn graph_self_loop_is_skipped() {
let mut g = MatchingGraph::new(3, 1);
g.add_edge(0, 0, 10, &[0]);
g.add_edge(0, 1, 10, &[0]);
assert_eq!(g.nodes[0].neighbors.len(), 1);
assert_eq!(g.nodes[0].neighbors[0], NodeIdx(1));
}
#[test]
fn graph_negative_weight_boundary_edge() {
let mut g = MatchingGraph::new(2, 2);
g.add_boundary_edge(0, -5, &[0, 1]);
assert!(g.negative_weight_detection_events_set.contains(&0));
assert!(g.negative_weight_observables_set.contains(&0));
assert!(g.negative_weight_observables_set.contains(&1));
assert_eq!(g.negative_weight_sum, -5);
assert_eq!(g.nodes[0].neighbor_weights[0], 5);
}
#[test]
fn graph_negative_weight_boundary_toggle() {
let mut g = MatchingGraph::new(2, 1);
g.add_boundary_edge(0, -3, &[0]);
assert!(g.negative_weight_detection_events_set.contains(&0));
assert!(g.negative_weight_observables_set.contains(&0));
g.add_boundary_edge(0, -2, &[0]);
assert!(!g.negative_weight_detection_events_set.contains(&0));
assert!(!g.negative_weight_observables_set.contains(&0));
assert_eq!(g.negative_weight_sum, -5);
}
#[test]
fn alt_tree_edge_empty() {
let e = AltTreeEdge::empty();
assert!(e.is_empty());
assert_eq!(e.alt_tree_node, AltTreeIdx(u32::MAX));
let real = AltTreeEdge::new(AltTreeIdx(0), CompressedEdge::empty());
assert!(!real.is_empty());
}
#[test]
fn alt_tree_add_child_sets_parent() {
use rmatching::util::arena::Arena;
let mut arena: Arena<AltTreeNode> = Arena::new();
let root_idx = AltTreeIdx(arena.alloc());
arena[root_idx.0] = AltTreeNode::new_root(RegionIdx(0));
let child_idx = AltTreeIdx(arena.alloc());
let edge = CompressedEdge {
loc_from: Some(NodeIdx(0)),
loc_to: Some(NodeIdx(1)),
obs_mask: 0,
};
arena[child_idx.0] = AltTreeNode::new_pair(RegionIdx(1), RegionIdx(2), edge);
let child_edge = AltTreeEdge::new(child_idx, edge);
let reversed_edge = child_edge.edge.reversed();
arena[root_idx.0].children.push(child_edge);
arena[child_idx.0].parent = Some(AltTreeEdge::new(root_idx, reversed_edge));
assert!(arena[child_idx.0].parent.is_some());
assert_eq!(
arena[child_idx.0].parent.as_ref().unwrap().alt_tree_node,
root_idx
);
assert_eq!(arena[root_idx.0].children.len(), 1);
}
#[test]
fn unstable_erase_not_found() {
let mut vec = vec![AltTreeEdge::new(AltTreeIdx(0), CompressedEdge::empty())];
let found = unstable_erase_by_node(&mut vec, AltTreeIdx(99));
assert!(!found);
assert_eq!(vec.len(), 1);
}
#[test]
fn unstable_erase_swap_path() {
let mut vec = vec![
AltTreeEdge::new(AltTreeIdx(0), CompressedEdge::empty()),
AltTreeEdge::new(AltTreeIdx(1), CompressedEdge::empty()),
AltTreeEdge::new(AltTreeIdx(2), CompressedEdge::empty()),
];
let found = unstable_erase_by_node(&mut vec, AltTreeIdx(0));
assert!(found);
assert_eq!(vec.len(), 2);
}
#[test]
fn tree_hitting_match_chain_4() {
let mut m = Matching::new();
m.add_edge(0, 1, 1.0, &[0], 0.1);
m.add_edge(1, 2, 3.0, &[], 0.1); m.add_edge(2, 3, 1.0, &[], 0.1);
m.add_boundary_edge(0, 5.0, &[], 0.05);
m.add_boundary_edge(3, 5.0, &[], 0.05);
let pred = m.decode(&[1, 1, 1, 1]);
assert_eq!(pred.len(), 1);
assert!(pred[0] == 0 || pred[0] == 1);
}
#[test]
fn tree_hitting_match_asymmetric_chain() {
let mut g = MatchingGraph::new(3, 1);
g.add_edge(0, 1, 2, &[0]); g.add_edge(1, 2, 8, &[]); g.add_boundary_edge(0, 20, &[]);
g.add_boundary_edge(2, 20, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
let mut event_count = 0;
let mut event_types = Vec::new();
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
event_types.push(format!("{:?}", &event));
mwpm.process_event(event);
event_count += 1;
if event_count > 30 {
break;
}
}
assert!(event_count >= 2, "Expected at least 2 events, got {}: {:?}", event_count, event_types);
}
#[test]
fn tree_hitting_boundary_match() {
let mut m = Matching::new();
m.add_boundary_edge(0, 0.5, &[0], 0.3);
m.add_edge(0, 1, 3.0, &[], 0.1);
m.add_boundary_edge(1, 10.0, &[], 0.05);
let pred = m.decode(&[1, 1]);
assert_eq!(pred.len(), 1);
assert!(pred[0] == 0 || pred[0] == 1);
}
#[test]
fn blossom_formation_triangle_plus_one() {
let mut g = MatchingGraph::new(4, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(0, 2, 10, &[]);
g.add_edge(2, 3, 20, &[]);
g.add_boundary_edge(0, 50, &[]);
g.add_boundary_edge(3, 50, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
mwpm.create_detection_event(NodeIdx(3));
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 2, "Expected at least 2 events, got {}", event_count);
}
#[test]
fn blossom_formation_triangle_four_events() {
let mut g = MatchingGraph::new(4, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(0, 2, 10, &[]);
g.add_edge(2, 3, 10, &[]);
g.add_edge(1, 3, 10, &[]);
g.add_boundary_edge(0, 50, &[]);
g.add_boundary_edge(3, 50, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
mwpm.create_detection_event(NodeIdx(3));
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 2, "Expected at least 2 events, got {}", event_count);
}
#[test]
fn handle_blossom_shattering_direct() {
let mut g = MatchingGraph::new(5, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(0, 2, 10, &[]);
g.add_edge(0, 3, 20, &[]);
g.add_edge(2, 4, 20, &[]);
g.add_boundary_edge(3, 30, &[]);
g.add_boundary_edge(4, 30, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
mwpm.create_detection_event(NodeIdx(3));
mwpm.create_detection_event(NodeIdx(4));
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 3, "Expected at least 3 events, got {}", event_count);
}
#[test]
fn dem_parse_comments_and_blank_lines() {
let dem = "\
# This is a comment
error(0.1) D0 D1 L0
# Another comment
error(0.1) D0
";
let m = Matching::from_dem(dem);
assert!(m.is_ok());
let mut m = m.unwrap();
let pred = m.decode(&[1, 1]);
assert_eq!(pred, vec![1]);
}
#[test]
fn dem_parse_detector_only_line() {
let dem = "\
error(0.1) D0 D1 L0
detector D0
detector D1
detector D2
";
let m = Matching::from_dem(dem);
assert!(m.is_ok());
}
#[test]
fn dem_parse_no_detector_in_detector_line() {
let dem = "\
error(0.1) D0 D1 L0
detector (0, 0, 0)
";
let m = Matching::from_dem(dem);
assert!(m.is_ok());
}
#[test]
fn user_graph_boundary_node_routing() {
use rmatching::driver::user_graph::{UserGraph, NUM_DISTINCT_WEIGHTS};
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![0], 1.0, 0.1);
g.add_edge(1, 2, vec![], 1.0, 0.1);
let boundary: std::collections::HashSet<usize> = [2].into_iter().collect();
g.set_boundary(boundary);
let mg = g.to_matching_graph(NUM_DISTINCT_WEIGHTS);
assert!(!mg.is_user_graph_boundary_node.is_empty());
assert!(mg.is_user_graph_boundary_node[2]);
}
#[test]
fn user_graph_boundary_search_graph() {
use rmatching::driver::user_graph::{UserGraph, NUM_DISTINCT_WEIGHTS};
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![0], 1.0, 0.1);
g.add_edge(1, 2, vec![], 1.0, 0.1);
let boundary: std::collections::HashSet<usize> = [2].into_iter().collect();
g.set_boundary(boundary);
let sg = g.to_search_graph(NUM_DISTINCT_WEIGHTS);
assert!(sg.nodes[1].neighbors.len() >= 1);
}
#[test]
fn user_graph_set_boundary_clears_old() {
use rmatching::driver::user_graph::UserGraph;
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![], 1.0, 0.1);
g.add_edge(1, 2, vec![], 1.0, 0.1);
g.add_edge(2, 3, vec![], 1.0, 0.1);
let b1: std::collections::HashSet<usize> = [2].into_iter().collect();
g.set_boundary(b1);
assert!(g.is_boundary_node(2));
assert!(!g.is_boundary_node(3));
let b2: std::collections::HashSet<usize> = [3].into_iter().collect();
g.set_boundary(b2);
assert!(!g.is_boundary_node(2));
assert!(g.is_boundary_node(3));
}
#[test]
fn user_graph_invalid_error_probability() {
use rmatching::driver::user_graph::UserGraph;
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![0], 1.0, -1.0);
g.add_boundary_edge(0, vec![], 0.5, 2.0);
}
#[test]
fn user_graph_get_num_detectors_with_boundary() {
use rmatching::driver::user_graph::UserGraph;
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![], 1.0, 0.1);
g.add_edge(1, 2, vec![], 1.0, 0.1);
g.add_edge(2, 3, vec![], 1.0, 0.1);
assert_eq!(g.get_num_detectors(), 4);
let boundary: std::collections::HashSet<usize> = [3].into_iter().collect();
g.set_boundary(boundary);
assert_eq!(g.get_num_detectors(), 3);
}
#[test]
fn user_graph_dem_instruction_zero_detectors() {
use rmatching::driver::user_graph::UserGraph;
let mut g = UserGraph::new();
g.handle_dem_instruction(0.1, &[], vec![0]).unwrap();
assert_eq!(g.get_num_edges(), 0);
let error = g
.handle_dem_instruction(0.1, &[0, 1, 2], vec![0])
.unwrap_err();
assert!(error.contains("requires a graphlike DEM"));
assert!(error.contains("3 detectors"));
assert_eq!(g.get_num_edges(), 0);
}
#[test]
fn matching_set_boundary() {
let mut m = Matching::new();
m.add_edge(0, 1, 1.0, &[0], 0.1);
m.add_edge(1, 2, 1.0, &[], 0.1);
m.set_boundary(&[2]);
let pred = m.decode(&[1, 1, 0]);
assert_eq!(pred.len(), 1);
}
#[test]
fn decode_out_of_range_detection_event() {
let mut m = Matching::new();
m.add_edge(0, 1, 1.0, &[0], 0.1);
m.add_boundary_edge(0, 2.0, &[], 0.1);
m.add_boundary_edge(1, 2.0, &[], 0.1);
let pred = m.decode(&[1, 1, 1, 1, 1]);
assert_eq!(pred.len(), 1);
}
#[test]
fn prune_upward_path_back_false() {
use rmatching::util::arena::Arena;
let mut arena: Arena<AltTreeNode> = Arena::new();
let e = CompressedEdge {
loc_from: Some(NodeIdx(0)),
loc_to: Some(NodeIdx(1)),
obs_mask: 0,
};
let root = AltTreeIdx(arena.alloc());
arena[root.0] = AltTreeNode::new_root(RegionIdx(0));
let child = AltTreeIdx(arena.alloc());
arena[child.0] = AltTreeNode::new_pair(RegionIdx(1), RegionIdx(2), e);
arena[root.0].children.push(AltTreeEdge::new(child, e));
arena[child.0].parent = Some(AltTreeEdge::new(root, e.reversed()));
let result = AltTreeNode::prune_upward_path_stopping_before(
child,
&mut arena,
root,
false,
);
assert_eq!(result.pruned_path_region_edges.len(), 2);
assert_eq!(result.pruned_path_region_edges[0].region, RegionIdx(2));
assert_eq!(result.pruned_path_region_edges[1].region, RegionIdx(1));
}
#[test]
fn surface_code_d5_complex_matching() {
let dem = "\
error(0.1) D0 D1
error(0.1) D1 D2
error(0.1) D2 D3
error(0.1) D3 D4
error(0.1) D0 D5
error(0.1) D1 D6
error(0.1) D2 D7
error(0.1) D3 D8
error(0.1) D4 D9
error(0.1) D5 D6
error(0.1) D6 D7
error(0.1) D7 D8
error(0.1) D8 D9
error(0.1) D0 D6 L0
error(0.05) D0
error(0.05) D4
error(0.05) D5
error(0.05) D9
";
let mut m = Matching::from_dem(dem).unwrap();
assert_eq!(m.decode(&[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), vec![0]);
let pred = m.decode(&[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]);
assert_eq!(pred.len(), 1);
let pred = m.decode(&[1, 0, 1, 0, 0, 0, 1, 0, 1, 0]);
assert_eq!(pred.len(), 1);
let pred = m.decode(&[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]);
assert_eq!(pred.len(), 1);
}
#[test]
fn multiple_decode_calls_reset() {
let mut m = Matching::new();
m.add_edge(0, 1, 1.0, &[0], 0.1);
m.add_edge(1, 2, 1.0, &[], 0.1);
m.add_boundary_edge(0, 2.0, &[], 0.1);
m.add_boundary_edge(2, 2.0, &[], 0.1);
for _ in 0..5 {
let pred = m.decode(&[1, 1, 0]);
assert_eq!(pred.len(), 1);
assert_eq!(pred[0], 1);
}
for _ in 0..5 {
let pred = m.decode(&[0, 0, 0]);
assert_eq!(pred, vec![0]);
}
}
#[test]
fn negative_weight_full_pipeline_boundary() {
let dem = "\
error(0.8) D0 L0
error(0.1) D0 D1
error(0.1) D1
";
let mut m = Matching::from_dem(dem).unwrap();
let pred = m.decode(&[0, 0]);
assert_eq!(pred.len(), 1);
let pred = m.decode(&[1, 0]);
assert_eq!(pred.len(), 1);
let pred = m.decode(&[1, 1]);
assert_eq!(pred.len(), 1);
}
#[test]
fn user_graph_node1_is_boundary() {
use rmatching::driver::user_graph::{UserGraph, NUM_DISTINCT_WEIGHTS};
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![0], 1.0, 0.1);
g.add_edge(1, 2, vec![], 1.0, 0.1);
let boundary: std::collections::HashSet<usize> = [0].into_iter().collect();
g.set_boundary(boundary);
let mg = g.to_matching_graph(NUM_DISTINCT_WEIGHTS);
assert!(mg.is_user_graph_boundary_node[0]);
}
#[test]
fn dem_parse_correlated_error() {
let dem = "\
error(0.1) D0 D1 L0 ^ error(0.1) D2 D3
error(0.1) D0
error(0.1) D1
";
let m = Matching::from_dem(dem);
assert!(m.is_ok());
let mut m = m.unwrap();
let pred = m.decode(&[1, 1]);
assert_eq!(pred, vec![1]);
}
#[test]
fn blossom_pentagon_five_events() {
let mut g = MatchingGraph::new(5, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(2, 3, 10, &[]);
g.add_edge(3, 4, 10, &[]);
g.add_edge(4, 0, 10, &[]);
g.add_boundary_edge(0, 30, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
for i in 0..5 {
mwpm.create_detection_event(NodeIdx(i));
}
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 3, "Expected at least 3 events, got {}", event_count);
}
#[test]
fn direct_blossom_shatter_event() {
let mut g = MatchingGraph::new(5, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(0, 2, 10, &[]);
g.add_edge(2, 3, 20, &[]);
g.add_boundary_edge(3, 30, &[]);
g.add_boundary_edge(0, 30, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
mwpm.create_detection_event(NodeIdx(3));
let mut events = Vec::new();
let mut count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
let _is_blossom_shatter = matches!(&event, MwpmEvent::BlossomShatter { .. });
events.push(format!("{:?}", &event));
mwpm.process_event(event);
count += 1;
if count > 50 {
break;
}
}
assert!(count >= 2, "Expected at least 2 events, got {}: {:?}", count, events);
}
#[test]
fn decode_to_edges_boundary() {
let mut m = Matching::new();
m.add_boundary_edge(0, 1.0, &[0], 0.1);
m.add_edge(0, 1, 5.0, &[], 0.1);
m.add_boundary_edge(1, 5.0, &[], 0.1);
let edges = m.decode_to_edges(&[1, 0]);
assert_eq!(edges.len(), 1);
let (a, b) = edges[0];
assert!(a == 0 || b == 0);
assert!(a == -1 || b == -1);
}
#[test]
fn decode_batch_consistency() {
let dem = "\
error(0.1) D0 D1 L0
error(0.1) D1 D2
error(0.05) D0
error(0.05) D2
";
let mut m = Matching::from_dem(dem).unwrap();
let syndromes = vec![
vec![1u8, 1, 0],
vec![0, 0, 0],
vec![1, 0, 0],
vec![0, 1, 1],
];
let batch = m.decode_batch(&syndromes);
assert_eq!(batch.len(), 4);
for pred in &batch {
assert_eq!(pred.len(), 1);
}
}
#[test]
fn mwpm_make_child_exercises_add_child() {
let mut g = MatchingGraph::new(4, 1);
g.add_edge(0, 1, 4, &[0]); g.add_edge(1, 2, 12, &[]); g.add_edge(2, 3, 4, &[]); g.add_boundary_edge(0, 40, &[]);
g.add_boundary_edge(3, 40, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
mwpm.create_detection_event(NodeIdx(3));
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 30 {
break;
}
}
assert!(event_count >= 2);
}
#[test]
fn alt_tree_mrca_deep_tree() {
use rmatching::util::arena::Arena;
let mut arena: Arena<AltTreeNode> = Arena::new();
let e = CompressedEdge::empty();
let root = AltTreeIdx(arena.alloc());
arena[root.0] = AltTreeNode::new_root(RegionIdx(0));
let c1 = AltTreeIdx(arena.alloc());
arena[c1.0] = AltTreeNode::new_pair(RegionIdx(1), RegionIdx(2), e);
arena[root.0].children.push(AltTreeEdge::new(c1, e));
arena[c1.0].parent = Some(AltTreeEdge::new(root, e));
let c2 = AltTreeIdx(arena.alloc());
arena[c2.0] = AltTreeNode::new_pair(RegionIdx(3), RegionIdx(4), e);
arena[root.0].children.push(AltTreeEdge::new(c2, e));
arena[c2.0].parent = Some(AltTreeEdge::new(root, e));
let c3 = AltTreeIdx(arena.alloc());
arena[c3.0] = AltTreeNode::new_pair(RegionIdx(5), RegionIdx(6), e);
arena[c1.0].children.push(AltTreeEdge::new(c3, e));
arena[c3.0].parent = Some(AltTreeEdge::new(c1, e));
let c4 = AltTreeIdx(arena.alloc());
arena[c4.0] = AltTreeNode::new_pair(RegionIdx(7), RegionIdx(8), e);
arena[c2.0].children.push(AltTreeEdge::new(c4, e));
arena[c4.0].parent = Some(AltTreeEdge::new(c2, e));
let lca = AltTreeNode::most_recent_common_ancestor(c3, c4, &mut arena);
assert_eq!(lca, Some(root));
for idx in [root, c1, c2, c3, c4] {
arena[idx.0].visited = false;
}
let lca2 = AltTreeNode::most_recent_common_ancestor(c3, c1, &mut arena);
assert_eq!(lca2, Some(c1));
}
#[test]
fn alt_tree_mrca_different_trees() {
use rmatching::util::arena::Arena;
let mut arena: Arena<AltTreeNode> = Arena::new();
let root1 = AltTreeIdx(arena.alloc());
arena[root1.0] = AltTreeNode::new_root(RegionIdx(0));
let root2 = AltTreeIdx(arena.alloc());
arena[root2.0] = AltTreeNode::new_root(RegionIdx(1));
let lca = AltTreeNode::most_recent_common_ancestor(root1, root2, &mut arena);
assert_eq!(lca, None);
}
#[test]
fn user_graph_search_graph_node1_boundary() {
use rmatching::driver::user_graph::{UserGraph, NUM_DISTINCT_WEIGHTS};
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![0], 1.0, 0.1);
g.add_edge(1, 2, vec![], 1.0, 0.1);
let boundary: std::collections::HashSet<usize> = [0].into_iter().collect();
g.set_boundary(boundary);
let sg = g.to_search_graph(NUM_DISTINCT_WEIGHTS);
assert!(sg.nodes[1].neighbors.len() >= 2);
}
#[test]
fn dem_parse_repeat_no_shift_detectors() {
let dem = "\
repeat 2 {
error(0.1) D0 D1 L0
}";
let m = Matching::from_dem(dem);
assert!(m.is_ok());
}
#[test]
fn mwpm_tree_hitting_boundary_match_direct() {
let mut g = MatchingGraph::new(2, 1);
g.add_boundary_edge(0, 2, &[0]); g.add_edge(0, 1, 8, &[]); g.add_boundary_edge(1, 20, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
let mut event_count = 0;
let mut event_types = Vec::new();
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
event_types.push(format!("{:?}", &event));
mwpm.process_event(event);
event_count += 1;
if event_count > 20 {
break;
}
}
assert!(event_count >= 2, "Expected at least 2 events, got {}: {:?}", event_count, event_types);
}
#[test]
fn user_graph_both_nodes_boundary() {
use rmatching::driver::user_graph::{UserGraph, NUM_DISTINCT_WEIGHTS};
let mut g = UserGraph::new();
g.add_edge(0, 1, vec![0], 1.0, 0.1);
g.add_edge(1, 2, vec![], 1.0, 0.1);
g.add_edge(2, 3, vec![], 1.0, 0.1);
let boundary: std::collections::HashSet<usize> = [2, 3].into_iter().collect();
g.set_boundary(boundary);
let mg = g.to_matching_graph(NUM_DISTINCT_WEIGHTS);
assert_eq!(mg.nodes[0].neighbors.len(), 1);
}
#[test]
fn blossom_formation_full_decode_pipeline() {
let mut g = MatchingGraph::new(4, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(0, 2, 10, &[]);
g.add_edge(0, 3, 20, &[]);
g.add_boundary_edge(3, 40, &[]);
g.add_boundary_edge(2, 40, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
mwpm.create_detection_event(NodeIdx(3));
let mut event_count = 0;
let mut saw_same_tree = false;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
if matches!(&event, MwpmEvent::RegionHitRegion { .. }) {
if let MwpmEvent::RegionHitRegion { region1, region2, .. } = &event {
let an1 = mwpm.flooder.region_arena[region1.0].alt_tree_node;
let an2 = mwpm.flooder.region_arena[region2.0].alt_tree_node;
if an1.is_some() && an2.is_some() {
saw_same_tree = true;
}
}
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 2, "Expected at least 2 events, got {}", event_count);
}
#[test]
fn blossom_five_node_mwpm() {
let mut g = MatchingGraph::new(5, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(2, 3, 10, &[]);
g.add_edge(3, 4, 10, &[]);
g.add_edge(4, 0, 10, &[]);
g.add_boundary_edge(0, 30, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
for i in 0..5 {
mwpm.create_detection_event(NodeIdx(i));
}
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 3, "Expected at least 3 events, got {}", event_count);
}
#[test]
fn tree_absorb_then_blossom_orphan_reparenting() {
let mut g = MatchingGraph::new(6, 1);
g.add_edge(0, 1, 4, &[0]); g.add_edge(1, 2, 12, &[]); g.add_edge(2, 3, 12, &[]); g.add_edge(0, 3, 24, &[]); g.add_edge(2, 4, 40, &[]); g.add_edge(4, 5, 4, &[]); g.add_boundary_edge(0, 60, &[]);
g.add_boundary_edge(5, 60, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
for i in 0..6 {
mwpm.create_detection_event(NodeIdx(i));
}
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 3, "Expected at least 3 events, got {}", event_count);
}
#[test]
fn alt_tree_mrca_asymmetric_depth() {
use rmatching::util::arena::Arena;
let mut arena: Arena<AltTreeNode> = Arena::new();
let e = CompressedEdge::empty();
let gp = AltTreeIdx(arena.alloc());
arena[gp.0] = AltTreeNode::new_root(RegionIdx(0));
let p = AltTreeIdx(arena.alloc());
arena[p.0] = AltTreeNode::new_pair(RegionIdx(1), RegionIdx(2), e);
arena[gp.0].children.push(AltTreeEdge::new(p, e));
arena[p.0].parent = Some(AltTreeEdge::new(gp, e));
let c1 = AltTreeIdx(arena.alloc());
arena[c1.0] = AltTreeNode::new_pair(RegionIdx(3), RegionIdx(4), e);
arena[p.0].children.push(AltTreeEdge::new(c1, e));
arena[c1.0].parent = Some(AltTreeEdge::new(p, e));
let c2 = AltTreeIdx(arena.alloc());
arena[c2.0] = AltTreeNode::new_pair(RegionIdx(5), RegionIdx(6), e);
arena[p.0].children.push(AltTreeEdge::new(c2, e));
arena[c2.0].parent = Some(AltTreeEdge::new(p, e));
let c3 = AltTreeIdx(arena.alloc());
arena[c3.0] = AltTreeNode::new_pair(RegionIdx(7), RegionIdx(8), e);
arena[c2.0].children.push(AltTreeEdge::new(c3, e));
arena[c3.0].parent = Some(AltTreeEdge::new(c2, e));
let c4 = AltTreeIdx(arena.alloc());
arena[c4.0] = AltTreeNode::new_pair(RegionIdx(9), RegionIdx(10), e);
arena[c3.0].children.push(AltTreeEdge::new(c4, e));
arena[c4.0].parent = Some(AltTreeEdge::new(c3, e));
let lca = AltTreeNode::most_recent_common_ancestor(c1, c4, &mut arena);
assert_eq!(lca, Some(p));
assert!(!arena[gp.0].visited);
assert!(!arena[p.0].visited);
}
#[test]
fn alt_tree_mrca_ancestor_descendant() {
use rmatching::util::arena::Arena;
let mut arena: Arena<AltTreeNode> = Arena::new();
let e = CompressedEdge::empty();
let root = AltTreeIdx(arena.alloc());
arena[root.0] = AltTreeNode::new_root(RegionIdx(0));
let c1 = AltTreeIdx(arena.alloc());
arena[c1.0] = AltTreeNode::new_pair(RegionIdx(1), RegionIdx(2), e);
arena[root.0].children.push(AltTreeEdge::new(c1, e));
arena[c1.0].parent = Some(AltTreeEdge::new(root, e));
let c2 = AltTreeIdx(arena.alloc());
arena[c2.0] = AltTreeNode::new_pair(RegionIdx(3), RegionIdx(4), e);
arena[c1.0].children.push(AltTreeEdge::new(c2, e));
arena[c2.0].parent = Some(AltTreeEdge::new(c1, e));
let lca = AltTreeNode::most_recent_common_ancestor(root, c2, &mut arena);
assert_eq!(lca, Some(root));
}
#[test]
fn graph_negative_weight_edge() {
let mut g = MatchingGraph::new(3, 2);
g.add_edge(0, 1, -5, &[0, 1]);
assert!(g.negative_weight_detection_events_set.contains(&0));
assert!(g.negative_weight_detection_events_set.contains(&1));
assert!(g.negative_weight_observables_set.contains(&0));
assert!(g.negative_weight_observables_set.contains(&1));
assert_eq!(g.negative_weight_sum, -5);
assert_eq!(g.nodes[0].neighbor_weights[0], 5);
assert_eq!(g.nodes[1].neighbor_weights[0], 5);
}
#[test]
fn dem_parse_repeat_with_shift_detectors() {
let dem = "\
repeat 3 {
error(0.1) D0 D1 L0
shift_detectors 2
}";
let m = Matching::from_dem(dem);
assert!(m.is_ok());
let mut m = m.unwrap();
let pred = m.decode(&[1, 1, 0, 0, 0, 0]);
assert_eq!(pred, vec![1]);
}
#[test]
fn dem_parse_unknown_instruction() {
let dem = "\
error(0.1) D0 D1 L0
logical_observable L0
some_unknown_thing
error(0.1) D0
";
let m = Matching::from_dem(dem);
assert!(m.is_ok());
}
#[test]
fn blossom_triangle_boundary_mwpm() {
let mut g = MatchingGraph::new(3, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(0, 2, 10, &[]);
g.add_boundary_edge(0, 20, &[]);
g.add_boundary_edge(1, 20, &[]);
g.add_boundary_edge(2, 20, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(1));
mwpm.create_detection_event(NodeIdx(2));
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 2, "Expected at least 2 events, got {}", event_count);
mwpm.reset();
mwpm.create_detection_event(NodeIdx(0));
mwpm.create_detection_event(NodeIdx(2));
let mut event_count2 = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count2 += 1;
if event_count2 > 50 {
break;
}
}
assert!(event_count2 >= 1);
}
#[test]
fn complex_graph_multiple_triangles_mwpm() {
let mut g = MatchingGraph::new(6, 1);
g.add_edge(0, 1, 10, &[0]);
g.add_edge(1, 2, 10, &[]);
g.add_edge(0, 2, 10, &[]);
g.add_edge(2, 3, 20, &[]);
g.add_edge(3, 4, 10, &[]);
g.add_edge(4, 5, 10, &[]);
g.add_edge(3, 5, 10, &[]);
g.add_boundary_edge(0, 30, &[]);
g.add_boundary_edge(5, 30, &[]);
let mut mwpm = Mwpm::new(GraphFlooder::new(g));
for i in 0..6 {
mwpm.create_detection_event(NodeIdx(i));
}
let mut event_count = 0;
loop {
let event = mwpm.flooder.run_until_next_mwpm_notification();
if event.is_no_event() {
break;
}
mwpm.process_event(event);
event_count += 1;
if event_count > 50 {
break;
}
}
assert!(event_count >= 3, "Expected at least 3 events, got {}", event_count);
}
#[test]
fn decode_to_edges_chain_four() {
let mut m = Matching::new();
m.add_edge(0, 1, 1.0, &[0], 0.1);
m.add_edge(1, 2, 1.0, &[], 0.1);
m.add_edge(2, 3, 1.0, &[], 0.1);
m.add_boundary_edge(0, 3.0, &[], 0.05);
m.add_boundary_edge(3, 3.0, &[], 0.05);
let edges = m.decode_to_edges(&[1, 1, 1, 1]);
assert!(edges.len() >= 1);
}
#[test]
fn negative_weight_edge_decode() {
let mut m = Matching::new();
m.add_edge(0, 1, -1.0, &[0], 0.9);
m.add_boundary_edge(0, 2.0, &[], 0.1);
m.add_boundary_edge(1, 2.0, &[], 0.1);
let pred = m.decode(&[0, 0]);
assert_eq!(pred.len(), 1);
let pred = m.decode(&[1, 1]);
assert_eq!(pred.len(), 1);
let pred = m.decode(&[1, 0]);
assert_eq!(pred.len(), 1);
}
#[test]
fn matching_set_boundary_decode() {
let mut m = Matching::new();
m.add_edge(0, 1, 1.0, &[0], 0.1);
m.add_edge(1, 2, 1.0, &[], 0.1);
m.add_edge(2, 3, 1.0, &[], 0.1);
m.set_boundary(&[3]);
let pred = m.decode(&[1, 1, 0, 0]);
assert_eq!(pred.len(), 1);
assert_eq!(pred[0], 1);
let pred = m.decode(&[0, 0, 1, 0]);
assert_eq!(pred.len(), 1);
}