use super::util::*;
use crate::derivative::Derivative;
use super::dual_module::*;
use super::visualize::*;
use std::collections::HashMap;
use crate::weak_table::PtrWeakKeyHashMap;
use super::pointers::*;
pub struct DualModuleSerial {
pub vertices: Vec<VertexPtr>,
pub nodes: Vec<Option<DualNodeInternalPtr>>,
pub nodes_length: usize,
pub edges: Vec<EdgePtr>,
pub active_timestamp: FastClearTimestamp,
pub vertex_num: VertexNum,
pub edge_num: usize,
pub owning_range: VertexRange,
pub unit_module_info: Option<UnitModuleInfo>,
pub active_list: Vec<DualNodeInternalWeak>,
current_cycle: usize,
pub edge_modifier: EdgeWeightModifier,
pub edge_dedup_timestamp: FastClearTimestamp,
pub sync_requests: Vec<SyncRequest>,
updated_boundary: Vec<(bool, EdgeWeak)>,
propagating_vertices: Vec<(VertexWeak, Option<DualNodeInternalWeak>)>,
}
#[derive(Derivative)]
#[derivative(Debug)]
pub struct UnitModuleInfo {
pub unit_index: usize,
pub mirrored_vertices: HashMap<VertexIndex, VertexIndex>,
pub owning_dual_range: NodeRange,
pub dual_node_pointers: PtrWeakKeyHashMap<DualNodeWeak, usize>,
}
pub type DualModuleSerialPtr = ArcManualSafeLock<DualModuleSerial>;
pub type DualModuleSerialWeak = WeakManualSafeLock<DualModuleSerial>;
#[derive(Derivative)]
#[derivative(Debug)]
pub struct DualNodeInternal {
pub origin: DualNodeWeak,
index: NodeIndex,
pub dual_variable: Weight,
pub boundary: Vec<(bool, EdgeWeak)>,
pub overgrown_stack: Vec<(VertexWeak, Weight)>,
last_visit_cycle: usize,
}
pub type DualNodeInternalPtr = ArcManualSafeLock<DualNodeInternal>;
pub type DualNodeInternalWeak = WeakManualSafeLock<DualNodeInternal>;
impl std::fmt::Debug for DualNodeInternalPtr {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
let dual_node_internal = self.read_recursive();
write!(f, "{}", dual_node_internal.index)
}
}
impl std::fmt::Debug for DualNodeInternalWeak {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
self.upgrade_force().fmt(f)
}
}
#[derive(Derivative)]
#[derivative(Debug)]
pub struct Vertex {
pub vertex_index: VertexIndex,
pub is_virtual: bool,
pub is_defect: bool,
pub mirror_unit: Option<PartitionUnitWeak>,
#[derivative(Debug="ignore")]
pub edges: Vec<EdgeWeak>,
pub propagated_dual_node: Option<DualNodeInternalWeak>,
pub propagated_grandson_dual_node: Option<DualNodeInternalWeak>,
pub timestamp: FastClearTimestamp,
}
pub type VertexPtr = FastClearArcManualSafeLockDangerous<Vertex>;
pub type VertexWeak = FastClearWeakManualSafeLockDangerous<Vertex>;
impl std::fmt::Debug for VertexPtr {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
let vertex = self.read_recursive_force();
write!(f, "{}", vertex.vertex_index)
}
}
impl std::fmt::Debug for VertexWeak {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
let vertex_ptr = self.upgrade_force();
let vertex = vertex_ptr.read_recursive_force();
write!(f, "{}", vertex.vertex_index)
}
}
#[derive(Derivative)]
#[derivative(Debug)]
pub struct Edge {
pub edge_index: EdgeIndex,
pub weight: Weight,
#[derivative(Debug="ignore")]
pub left: VertexWeak,
#[derivative(Debug="ignore")]
pub right: VertexWeak,
pub left_growth: Weight,
pub right_growth: Weight,
pub left_dual_node: Option<DualNodeInternalWeak>,
pub left_grandson_dual_node: Option<DualNodeInternalWeak>,
pub right_dual_node: Option<DualNodeInternalWeak>,
pub right_grandson_dual_node: Option<DualNodeInternalWeak>,
pub timestamp: FastClearTimestamp,
pub dedup_timestamp: (FastClearTimestamp, FastClearTimestamp),
}
pub type EdgePtr = FastClearArcManualSafeLockDangerous<Edge>;
pub type EdgeWeak = FastClearWeakManualSafeLockDangerous<Edge>;
impl std::fmt::Debug for EdgePtr {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
let edge = self.read_recursive_force();
write!(f, "{}", edge.edge_index)
}
}
impl std::fmt::Debug for EdgeWeak {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
let edge_ptr = self.upgrade_force();
let edge = edge_ptr.read_recursive_force();
write!(f, "{}", edge.edge_index)
}
}
impl DualModuleImpl for DualModuleSerial {
fn new_empty(initializer: &SolverInitializer) -> Self {
let active_timestamp = 0;
let vertices: Vec<VertexPtr> = (0..initializer.vertex_num).map(|vertex_index| VertexPtr::new_value(Vertex {
vertex_index,
is_virtual: false,
is_defect: false,
mirror_unit: None,
edges: Vec::new(),
propagated_dual_node: None,
propagated_grandson_dual_node: None,
timestamp: active_timestamp,
})).collect();
for &virtual_vertex in initializer.virtual_vertices.iter() {
let mut vertex = vertices[virtual_vertex as usize].write(active_timestamp);
vertex.is_virtual = true;
}
let mut edges = Vec::<EdgePtr>::new();
for &(i, j, weight) in initializer.weighted_edges.iter() {
assert_ne!(i, j, "invalid edge from and to the same vertex {}", i);
assert!(weight % 2 == 0, "edge ({}, {}) has odd weight value; weight should be even", i, j);
assert!(weight >= 0, "edge ({}, {}) is negative-weighted", i, j);
assert!(i < initializer.vertex_num, "edge ({}, {}) connected to an invalid vertex {}", i, j, i);
assert!(j < initializer.vertex_num, "edge ({}, {}) connected to an invalid vertex {}", i, j, j);
let left = VertexIndex::min(i, j);
let right = VertexIndex::max(i, j);
let edge_ptr = EdgePtr::new_value(Edge {
edge_index: edges.len() as EdgeIndex,
weight,
left: vertices[left as usize].downgrade(),
right: vertices[right as usize].downgrade(),
left_growth: 0,
right_growth: 0,
left_dual_node: None,
left_grandson_dual_node: None,
right_dual_node: None,
right_grandson_dual_node: None,
timestamp: 0,
dedup_timestamp: (0, 0),
});
for (a, b) in [(i, j), (j, i)] {
lock_write!(vertex, vertices[a as usize], active_timestamp);
debug_assert!({ let mut no_duplicate = true;
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
let edge = edge_ptr.read_recursive(active_timestamp);
if edge.left == vertices[b as usize].downgrade() || edge.right == vertices[b as usize].downgrade() {
no_duplicate = false;
eprintln!("duplicated edge between {} and {} with weight w1 = {} and w2 = {}, consider merge them into a single edge", i, j, weight, edge.weight);
break
}
}
no_duplicate
});
vertex.edges.push(edge_ptr.downgrade());
}
edges.push(edge_ptr);
}
Self {
vertices,
nodes: vec![],
nodes_length: 0,
edges,
active_timestamp: 0,
vertex_num: initializer.vertex_num,
edge_num: initializer.weighted_edges.len(),
owning_range: VertexRange::new(0, initializer.vertex_num),
unit_module_info: None, active_list: vec![],
current_cycle: 0,
edge_modifier: EdgeWeightModifier::new(),
edge_dedup_timestamp: 0,
sync_requests: vec![],
updated_boundary: vec![],
propagating_vertices: vec![],
}
}
fn clear(&mut self) {
while self.edge_modifier.has_modified_edges() {
let (edge_index, original_weight) = self.edge_modifier.pop_modified_edge();
let edge_ptr = &self.edges[edge_index as usize];
let mut edge = edge_ptr.write(self.active_timestamp);
edge.weight = original_weight;
}
self.clear_graph();
self.nodes_length = 0; if let Some(unit_module_info) = self.unit_module_info.as_mut() {
unit_module_info.owning_dual_range = VertexRange::new(0, 0);
unit_module_info.dual_node_pointers = PtrWeakKeyHashMap::<DualNodeWeak, usize>::new();
}
self.active_list.clear();
}
fn add_dual_node(&mut self, dual_node_ptr: &DualNodePtr) {
self.register_dual_node_ptr(dual_node_ptr);
let active_timestamp = self.active_timestamp;
let node = dual_node_ptr.read_recursive();
let node_index = self.nodes_length as NodeIndex;
let node_internal_ptr = if node_index < self.nodes.len() as NodeIndex && self.nodes[node_index as usize].is_some() {
let node_ptr = self.nodes[node_index as usize].take().unwrap();
let mut node = node_ptr.write();
node.origin = dual_node_ptr.downgrade();
node.index = node_index;
node.dual_variable = 0;
node.boundary.clear();
node.overgrown_stack.clear();
node.last_visit_cycle = 0;
drop(node);
node_ptr
} else {
DualNodeInternalPtr::new_value(DualNodeInternal {
origin: dual_node_ptr.downgrade(),
index: node_index,
dual_variable: 0,
boundary: Vec::new(),
overgrown_stack: Vec::new(),
last_visit_cycle: 0,
})
};
{
let boundary = &mut node_internal_ptr.write().boundary;
match &node.class {
DualNodeClass::Blossom { nodes_circle, .. } => {
for dual_node_weak in nodes_circle.iter() {
let dual_node_ptr = dual_node_weak.upgrade_force();
if self.unit_module_info.is_none() { self.prepare_dual_node_growth(&dual_node_ptr, false); }
if let Some(dual_node_internal_ptr) = self.get_dual_node_internal_ptr_optional(&dual_node_ptr) {
let dual_node_internal = dual_node_internal_ptr.read_recursive();
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
boundary.push((*is_left, edge_weak.clone()));
let mut edge = edge_ptr.write(active_timestamp);
debug_assert!(if *is_left { edge.left_dual_node.is_some() } else { edge.right_dual_node.is_some() }, "dual node of edge should be some");
debug_assert!(if *is_left { edge.left_dual_node == Some(dual_node_internal_ptr.downgrade())
} else { edge.right_dual_node == Some(dual_node_internal_ptr.downgrade()) }, "edge belonging");
if *is_left {
edge.left_dual_node = Some(node_internal_ptr.downgrade());
} else {
edge.right_dual_node = Some(node_internal_ptr.downgrade());
}
}
} else {
debug_assert!(self.unit_module_info.is_some(), "only partitioned could ignore some of its children");
}
}
},
DualNodeClass::DefectVertex { defect_index } => {
let vertex_index = self.get_vertex_index(*defect_index).expect("syndrome not belonging to this dual module");
let vertex_ptr = &self.vertices[vertex_index];
vertex_ptr.dynamic_clear(active_timestamp);
let mut vertex = vertex_ptr.write(active_timestamp);
vertex.propagated_dual_node = Some(node_internal_ptr.downgrade());
vertex.propagated_grandson_dual_node = Some(node_internal_ptr.downgrade());
vertex.is_defect = true;
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
edge_ptr.dynamic_clear(active_timestamp);
let mut edge = edge_ptr.write(active_timestamp);
let is_left = vertex_ptr.downgrade() == edge.left;
debug_assert!(if is_left { edge.left_dual_node.is_none() } else { edge.right_dual_node.is_none() }, "dual node of edge should be none");
if is_left {
edge.left_dual_node = Some(node_internal_ptr.downgrade());
edge.left_grandson_dual_node = Some(node_internal_ptr.downgrade());
} else {
edge.right_dual_node = Some(node_internal_ptr.downgrade());
edge.right_grandson_dual_node = Some(node_internal_ptr.downgrade());
}
boundary.push((is_left, edge_weak.clone()));
}
},
}
}
self.active_list.push(node_internal_ptr.downgrade());
self.nodes_length += 1;
if self.nodes.len() < self.nodes_length {
self.nodes.push(None);
}
self.nodes[node_index as usize] = Some(node_internal_ptr);
}
fn remove_blossom(&mut self, dual_node_ptr: DualNodePtr) {
let active_timestamp = self.active_timestamp;
self.prepare_dual_node_growth(&dual_node_ptr, false); let node = dual_node_ptr.read_recursive();
let dual_node_internal_ptr = self.get_dual_node_internal_ptr(&dual_node_ptr);
let dual_node_internal = dual_node_internal_ptr.read_recursive();
debug_assert_eq!(dual_node_internal.dual_variable, 0, "only blossom with dual variable = 0 can be safely removed");
debug_assert!(dual_node_internal.overgrown_stack.is_empty(), "removing a blossom with non-empty overgrown stack forbidden");
let node_idx = dual_node_internal.index;
debug_assert!(self.nodes[node_idx as usize].is_some(), "blossom may have already been removed, do not call twice");
debug_assert!(self.nodes[node_idx as usize].as_ref().unwrap() == &dual_node_internal_ptr, "the blossom doesn't belong to this DualModuleInterface");
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let mut edge = edge_ptr.write(active_timestamp);
debug_assert!(if *is_left { edge.left_dual_node.is_some() } else { edge.right_dual_node.is_some() }, "dual node of edge should be some");
if *is_left {
edge.left_dual_node = None;
} else {
edge.right_dual_node = None;
}
}
if let DualNodeClass::Blossom{ nodes_circle, .. } = &node.class {
for circle_dual_node_weak in nodes_circle.iter() {
let circle_dual_node_ptr = circle_dual_node_weak.upgrade_force();
if let Some(circle_dual_node_internal_ptr) = self.get_dual_node_internal_ptr_optional(&circle_dual_node_ptr) {
let circle_dual_node_internal = circle_dual_node_internal_ptr.read_recursive();
for (is_left, edge_weak) in circle_dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let mut edge = edge_ptr.write(active_timestamp);
debug_assert!(if *is_left { edge.left_dual_node.is_none() } else { edge.right_dual_node.is_none() }, "dual node of edge should be none");
if *is_left {
edge.left_dual_node = Some(circle_dual_node_internal_ptr.downgrade());
} else {
edge.right_dual_node = Some(circle_dual_node_internal_ptr.downgrade());
}
}
} else {
debug_assert!(self.unit_module_info.is_some(), "only happens if partitioned");
}
}
} else {
unreachable!()
}
self.nodes[node_idx as usize] = None; }
fn set_grow_state(&mut self, dual_node_ptr: &DualNodePtr, grow_state: DualNodeGrowState) {
let dual_node = dual_node_ptr.read_recursive();
if dual_node.grow_state == DualNodeGrowState::Stay && grow_state != DualNodeGrowState::Stay {
let dual_node_internal_ptr = self.get_dual_node_internal_ptr(dual_node_ptr);
self.active_list.push(dual_node_internal_ptr.downgrade())
}
}
#[allow(clippy::collapsible_else_if)]
fn compute_maximum_update_length_dual_node(&mut self, dual_node_ptr: &DualNodePtr, is_grow: bool, simultaneous_update: bool) -> MaxUpdateLength {
let active_timestamp = self.active_timestamp;
if !simultaneous_update {
self.prepare_dual_node_growth(dual_node_ptr, is_grow);
}
let mut max_length_abs = Weight::MAX;
let dual_node_internal_ptr = self.get_dual_node_internal_ptr(dual_node_ptr);
let dual_node_internal = dual_node_internal_ptr.read_recursive();
if !is_grow {
if dual_node_internal.dual_variable == 0 {
let dual_node = dual_node_ptr.read_recursive();
match dual_node.class {
DualNodeClass::Blossom { .. } => { return MaxUpdateLength::BlossomNeedExpand(dual_node_ptr.clone()) }
DualNodeClass::DefectVertex { defect_index } => {
if let Some(vertex_index) = self.get_vertex_index(defect_index) { let vertex_ptr = &self.vertices[vertex_index];
let vertex = vertex_ptr.read_recursive(active_timestamp);
let mut potential_conflict: Option<(DualNodePtr, DualNodePtr)> = None;
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
let edge = edge_ptr.read_recursive(active_timestamp);
let is_left = vertex_ptr.downgrade() == edge.left;
let remaining_length = edge.weight - edge.left_growth - edge.right_growth;
if remaining_length == 0 {
let peer_dual_node = if is_left { &edge.right_dual_node } else { &edge.left_dual_node };
if let Some(peer_dual_node_ptr) = peer_dual_node {
let peer_grandson_dual_node = if is_left { &edge.right_grandson_dual_node } else { &edge.left_grandson_dual_node };
let peer_dual_node_ptr = peer_dual_node_ptr.upgrade_force().read_recursive().origin.upgrade_force();
let peer_grandson_dual_node_ptr = peer_grandson_dual_node.as_ref().unwrap().upgrade_force().read_recursive().origin.upgrade_force();
if peer_dual_node_ptr.read_recursive().grow_state == DualNodeGrowState::Grow {
if let Some((other_dual_node_ptr, other_grandson_dual_node)) = &potential_conflict {
if &peer_dual_node_ptr != other_dual_node_ptr {
return MaxUpdateLength::Conflicting(
(other_dual_node_ptr.clone(), other_grandson_dual_node.clone()),
(peer_dual_node_ptr, peer_grandson_dual_node_ptr)
)
}
} else {
potential_conflict = Some((peer_dual_node_ptr, peer_grandson_dual_node_ptr));
}
}
}
}
}
return MaxUpdateLength::VertexShrinkStop((dual_node_ptr.clone(), potential_conflict))
} else {
return MaxUpdateLength::VertexShrinkStop((dual_node_ptr.clone(), None))
}
}
}
}
if !dual_node_internal.overgrown_stack.is_empty() {
let last_index = dual_node_internal.overgrown_stack.len() - 1;
let (_, overgrown) = &dual_node_internal.overgrown_stack[last_index];
max_length_abs = std::cmp::min(max_length_abs, *overgrown);
}
max_length_abs = std::cmp::min(max_length_abs, dual_node_internal.dual_variable);
}
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let is_left = *is_left;
let edge = edge_ptr.read_recursive(active_timestamp);
if is_grow {
let peer_dual_node_internal_ptr: Option<DualNodeInternalPtr> = if is_left {
edge.right_dual_node.as_ref().map(|ptr| ptr.upgrade_force())
} else {
edge.left_dual_node.as_ref().map(|ptr| ptr.upgrade_force())
};
match peer_dual_node_internal_ptr {
Some(peer_dual_node_internal_ptr) => {
if peer_dual_node_internal_ptr == dual_node_internal_ptr {
continue
} else {
let peer_dual_node_internal = peer_dual_node_internal_ptr.read_recursive();
let peer_dual_node_ptr = peer_dual_node_internal.origin.upgrade_force();
let peer_dual_node = peer_dual_node_ptr.read_recursive();
let remaining_length = edge.weight - edge.left_growth - edge.right_growth;
let local_max_length_abs = match peer_dual_node.grow_state {
DualNodeGrowState::Grow => {
debug_assert!(remaining_length % 2 == 0, "there is odd gap between two growing nodes, please make sure all weights are even numbers");
remaining_length / 2
},
DualNodeGrowState::Shrink => {
continue
},
DualNodeGrowState::Stay => { remaining_length }
};
if local_max_length_abs == 0 {
let peer_grandson_ptr = if is_left {
edge.right_grandson_dual_node.as_ref().map(|ptr| ptr.upgrade_force()).unwrap().read_recursive().origin.upgrade_force()
} else {
edge.left_grandson_dual_node.as_ref().map(|ptr| ptr.upgrade_force()).unwrap().read_recursive().origin.upgrade_force()
};
let grandson_ptr = if is_left {
edge.left_grandson_dual_node.as_ref().map(|ptr| ptr.upgrade_force()).unwrap().read_recursive().origin.upgrade_force()
} else {
edge.right_grandson_dual_node.as_ref().map(|ptr| ptr.upgrade_force()).unwrap().read_recursive().origin.upgrade_force()
};
return MaxUpdateLength::Conflicting(
(peer_dual_node_ptr.clone(), peer_grandson_ptr),
(dual_node_ptr.clone(), grandson_ptr)
);
}
max_length_abs = std::cmp::min(max_length_abs, local_max_length_abs);
}
},
None => {
let local_max_length_abs = edge.weight - edge.left_growth - edge.right_growth;
if local_max_length_abs == 0 {
let peer_vertex_ptr = if is_left {
edge.right.upgrade_force()
} else {
edge.left.upgrade_force()
};
let peer_vertex = peer_vertex_ptr.read_recursive(active_timestamp);
if peer_vertex.is_virtual || peer_vertex.is_mirror_blocked() {
let grandson_ptr = if is_left {
edge.left_grandson_dual_node.as_ref().map(|ptr| ptr.upgrade_force()).unwrap().read_recursive().origin.upgrade_force()
} else {
edge.right_grandson_dual_node.as_ref().map(|ptr| ptr.upgrade_force()).unwrap().read_recursive().origin.upgrade_force()
};
return MaxUpdateLength::TouchingVirtual((dual_node_ptr.clone(), grandson_ptr)
, (peer_vertex.vertex_index, peer_vertex.is_mirror_blocked()));
} else {
println!("edge: {edge_ptr:?}, peer_vertex_ptr: {peer_vertex_ptr:?}");
unreachable!("this edge should've been removed from boundary because it's already fully grown, and it's peer vertex is not virtual")
}
}
max_length_abs = std::cmp::min(max_length_abs, local_max_length_abs);
},
}
} else {
if is_left {
if edge.left_growth == 0 {
unreachable!()
}
max_length_abs = std::cmp::min(max_length_abs, edge.left_growth);
} else {
if edge.right_growth == 0 {
unreachable!()
}
max_length_abs = std::cmp::min(max_length_abs, edge.right_growth);
}
}
}
MaxUpdateLength::NonZeroGrow((max_length_abs, dual_node_internal.boundary.is_empty()))
}
fn compute_maximum_update_length(&mut self) -> GroupMaxUpdateLength {
self.prepare_all();
debug_assert!(self.sync_requests.is_empty(), "no sync requests should arise here; make sure to deal with all sync requests before growing");
let mut group_max_update_length = GroupMaxUpdateLength::new();
for i in 0..self.active_list.len() {
let dual_node_ptr = {
let internal_dual_node_ptr = self.active_list[i].upgrade_force();
let dual_node_internal = internal_dual_node_ptr.read_recursive();
dual_node_internal.origin.upgrade_force()
};
let dual_node = dual_node_ptr.read_recursive();
let is_grow = match dual_node.grow_state {
DualNodeGrowState::Grow => true,
DualNodeGrowState::Shrink => false,
DualNodeGrowState::Stay => { continue }
};
drop(dual_node); let max_update_length = self.compute_maximum_update_length_dual_node(&dual_node_ptr, is_grow, true);
group_max_update_length.add(max_update_length);
}
group_max_update_length
}
fn grow_dual_node(&mut self, dual_node_ptr: &DualNodePtr, length: Weight) {
let active_timestamp = self.active_timestamp;
if length == 0 {
eprintln!("[warning] calling `grow_dual_node` with zero length, nothing to do");
return
}
self.prepare_dual_node_growth(dual_node_ptr, length > 0);
let dual_node_internal_ptr = self.get_dual_node_internal_ptr(dual_node_ptr);
{
let mut dual_node_internal = dual_node_internal_ptr.write();
dual_node_internal.dual_variable += length;
debug_assert!(dual_node_internal.dual_variable >= 0, "shrinking to negative dual variable is forbidden");
if !dual_node_internal.overgrown_stack.is_empty() {
let last_index = dual_node_internal.overgrown_stack.len() - 1;
let (_, overgrown) = &mut dual_node_internal.overgrown_stack[last_index];
if length < 0 { debug_assert!( *overgrown >= -length, "overgrown vertex cannot shrink so much"); }
*overgrown += length;
}
}
let dual_node_internal = dual_node_internal_ptr.read_recursive();
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let is_left = *is_left;
let (growth, weight) = { let mut edge = edge_ptr.write(active_timestamp);
if is_left {
edge.left_growth += length;
debug_assert!(edge.left_growth >= 0, "negative growth forbidden");
} else {
edge.right_growth += length;
debug_assert!(edge.right_growth >= 0, "negative growth forbidden");
}
(edge.left_growth + edge.right_growth, edge.weight)
};
let edge = edge_ptr.read_recursive(active_timestamp);
if growth > weight {
let dual_node_internal_ptr_2: &Option<DualNodeInternalWeak> = if is_left {
&edge.right_dual_node
} else {
&edge.left_dual_node
};
if dual_node_internal_ptr_2.is_none() || dual_node_internal_ptr_2.as_ref().unwrap() != &dual_node_internal_ptr.downgrade() {
let left_ptr = edge.left.upgrade_force();
let right_ptr = edge.right.upgrade_force();
panic!("over-grown edge ({},{}): {}/{}", left_ptr.read_recursive(active_timestamp).vertex_index
, right_ptr.read_recursive(active_timestamp).vertex_index, growth, weight);
}
} else if growth < 0 {
let left_ptr = edge.left.upgrade_force();
let right_ptr = edge.right.upgrade_force();
panic!("under-grown edge ({},{}): {}/{}", left_ptr.read_recursive(active_timestamp).vertex_index
, right_ptr.read_recursive(active_timestamp).vertex_index, growth, weight);
}
}
}
fn grow(&mut self, length: Weight) {
debug_assert!(length > 0, "only positive growth is supported");
self.renew_active_list();
for i in 0..self.active_list.len() {
let dual_node_ptr = {
let internal_dual_node_ptr = self.active_list[i].upgrade_force();
let dual_node_internal = internal_dual_node_ptr.read_recursive();
dual_node_internal.origin.upgrade_force()
};
let dual_node = dual_node_ptr.read_recursive();
if matches!(dual_node.grow_state, DualNodeGrowState::Shrink) {
self.grow_dual_node(&dual_node_ptr, -length);
}
}
for i in 0..self.active_list.len() {
let dual_node_ptr = {
let internal_dual_node_ptr = self.active_list[i].upgrade_force();
let dual_node_internal = internal_dual_node_ptr.read_recursive();
dual_node_internal.origin.upgrade_force()
};
let dual_node = dual_node_ptr.read_recursive();
if matches!(dual_node.grow_state, DualNodeGrowState::Grow) {
self.grow_dual_node(&dual_node_ptr, length);
}
}
}
fn load_edge_modifier(&mut self, edge_modifier: &[(EdgeIndex, Weight)]) {
debug_assert!(!self.edge_modifier.has_modified_edges(), "the current erasure modifier is not clean, probably forget to clean the state?");
let active_timestamp = self.active_timestamp;
for (edge_index, target_weight) in edge_modifier.iter() {
let edge_ptr = &self.edges[*edge_index as usize];
edge_ptr.dynamic_clear(active_timestamp); let mut edge = edge_ptr.write(active_timestamp);
let original_weight = edge.weight;
edge.weight = *target_weight;
self.edge_modifier.push_modified_edge(*edge_index, original_weight);
}
}
fn prepare_all(&mut self) -> &mut Vec<SyncRequest> {
debug_assert!(self.sync_requests.is_empty(), "make sure to remove all sync requests before prepare to avoid out-dated requests");
self.renew_active_list();
for i in 0..self.active_list.len() {
let dual_node_ptr = {
if let Some(internal_dual_node_ptr) = self.active_list[i].upgrade() {
let dual_node_internal = internal_dual_node_ptr.read_recursive();
dual_node_internal.origin.upgrade_force()
} else {
continue }
};
let dual_node = dual_node_ptr.read_recursive();
match dual_node.grow_state {
DualNodeGrowState::Grow => { },
DualNodeGrowState::Shrink => { self.prepare_dual_node_growth(&dual_node_ptr, false); },
DualNodeGrowState::Stay => { }, };
}
for i in 0..self.active_list.len() {
let dual_node_ptr = {
if let Some(internal_dual_node_ptr) = self.active_list[i].upgrade() {
let dual_node_internal = internal_dual_node_ptr.read_recursive();
dual_node_internal.origin.upgrade_force()
} else {
continue }
};
let dual_node = dual_node_ptr.read_recursive();
match dual_node.grow_state {
DualNodeGrowState::Grow => { self.prepare_dual_node_growth(&dual_node_ptr, true); },
DualNodeGrowState::Shrink => { },
DualNodeGrowState::Stay => { }, };
}
&mut self.sync_requests
}
fn prepare_nodes_shrink(&mut self, nodes_circle: &[DualNodePtr]) -> &mut Vec<SyncRequest> {
debug_assert!(self.sync_requests.is_empty(), "make sure to remove all sync requests before prepare to avoid out-dated requests");
for dual_node_ptr in nodes_circle.iter() {
if self.contains_dual_node(dual_node_ptr) {
self.prepare_dual_node_growth(dual_node_ptr, false); }
}
&mut self.sync_requests
}
fn contains_dual_node(&self, dual_node_ptr: &DualNodePtr) -> bool {
self.get_dual_node_index(dual_node_ptr).is_some()
}
fn new_partitioned(partitioned_initializer: &PartitionedSolverInitializer) -> Self {
let active_timestamp = 0;
let mut vertices: Vec<VertexPtr> = partitioned_initializer.owning_range.iter().map(|vertex_index| VertexPtr::new_value(Vertex {
vertex_index,
is_virtual: false,
is_defect: false,
mirror_unit: partitioned_initializer.owning_interface.clone(),
edges: Vec::new(),
propagated_dual_node: None,
propagated_grandson_dual_node: None,
timestamp: active_timestamp,
})).collect();
for &virtual_vertex in partitioned_initializer.virtual_vertices.iter() {
let mut vertex = vertices[(virtual_vertex - partitioned_initializer.owning_range.start()) as usize].write(active_timestamp);
vertex.is_virtual = true;
}
let mut mirrored_vertices = HashMap::<VertexIndex, VertexIndex>::new(); for (mirror_unit, interface_vertices) in partitioned_initializer.interfaces.iter() {
for (vertex_index, is_virtual) in interface_vertices.iter() {
mirrored_vertices.insert(*vertex_index, vertices.len() as VertexIndex);
vertices.push(VertexPtr::new_value(Vertex {
vertex_index: *vertex_index,
is_virtual: *is_virtual, is_defect: false,
mirror_unit: Some(mirror_unit.clone()),
edges: Vec::new(),
propagated_dual_node: None,
propagated_grandson_dual_node: None,
timestamp: active_timestamp,
}))
}
}
let mut edges = Vec::<EdgePtr>::new();
for &(i, j, weight, edge_index) in partitioned_initializer.weighted_edges.iter() {
assert_ne!(i, j, "invalid edge from and to the same vertex {}", i);
assert!(weight % 2 == 0, "edge ({}, {}) has odd weight value; weight should be even", i, j);
assert!(weight >= 0, "edge ({}, {}) is negative-weighted", i, j);
debug_assert!(partitioned_initializer.owning_range.contains(i) || mirrored_vertices.contains_key(&i)
, "edge ({}, {}) connected to an invalid vertex {}", i, j, i);
debug_assert!(partitioned_initializer.owning_range.contains(j) || mirrored_vertices.contains_key(&j)
, "edge ({}, {}) connected to an invalid vertex {}", i, j, j);
let left = VertexIndex::min(i, j);
let right = VertexIndex::max(i, j);
let left_index = if partitioned_initializer.owning_range.contains(left) {
left - partitioned_initializer.owning_range.start()
} else {
mirrored_vertices[&left]
};
let right_index = if partitioned_initializer.owning_range.contains(right) {
right - partitioned_initializer.owning_range.start()
} else {
mirrored_vertices[&right]
};
let edge_ptr = EdgePtr::new_value(Edge {
edge_index,
weight,
left: vertices[left_index as usize].downgrade(),
right: vertices[right_index as usize].downgrade(),
left_growth: 0,
right_growth: 0,
left_dual_node: None,
left_grandson_dual_node: None,
right_dual_node: None,
right_grandson_dual_node: None,
timestamp: 0,
dedup_timestamp: (0, 0),
});
for (a, b) in [(left_index, right_index), (right_index, left_index)] {
lock_write!(vertex, vertices[a as usize], active_timestamp);
debug_assert!({ let mut no_duplicate = true;
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
let edge = edge_ptr.read_recursive(active_timestamp);
if edge.left == vertices[b as usize].downgrade() || edge.right == vertices[b as usize].downgrade() {
no_duplicate = false;
eprintln!("duplicated edge between {} and {} with weight w1 = {} and w2 = {}, consider merge them into a single edge", i, j, weight, edge.weight);
break
}
}
no_duplicate
});
vertex.edges.push(edge_ptr.downgrade());
}
edges.push(edge_ptr);
}
Self {
vertices,
nodes: vec![],
nodes_length: 0,
edges,
active_timestamp: 0,
vertex_num: partitioned_initializer.vertex_num,
edge_num: partitioned_initializer.edge_num,
owning_range: partitioned_initializer.owning_range,
unit_module_info: Some(UnitModuleInfo {
unit_index: partitioned_initializer.unit_index,
mirrored_vertices,
owning_dual_range: VertexRange::new(0, 0),
dual_node_pointers: PtrWeakKeyHashMap::<DualNodeWeak, usize>::new(),
}),
active_list: vec![],
current_cycle: 0,
edge_modifier: EdgeWeightModifier::new(),
edge_dedup_timestamp: 0,
sync_requests: vec![],
updated_boundary: vec![],
propagating_vertices: vec![],
}
}
fn contains_vertex(&self, vertex_index: VertexIndex) -> bool {
self.get_vertex_index(vertex_index).is_some()
}
fn bias_dual_node_index(&mut self, bias: NodeIndex) {
self.unit_module_info.as_mut().unwrap().owning_dual_range.bias_by(bias);
}
fn execute_sync_event(&mut self, sync_event: &SyncRequest) {
let active_timestamp = self.active_timestamp;
debug_assert!(self.contains_vertex(sync_event.vertex_index));
let propagated_dual_node_internal_ptr = sync_event.propagated_dual_node.as_ref().map(|(dual_node_weak, dual_variable)| {
self.get_otherwise_add_dual_node(&dual_node_weak.upgrade_force(), *dual_variable)
});
let propagated_grandson_dual_node_internal_ptr = sync_event.propagated_grandson_dual_node.as_ref().map(|(dual_node_weak, dual_variable)| {
self.get_otherwise_add_dual_node(&dual_node_weak.upgrade_force(), *dual_variable)
});
let local_vertex_index = self.get_vertex_index(sync_event.vertex_index).expect("cannot synchronize at a non-existing vertex");
let vertex_ptr = &self.vertices[local_vertex_index];
vertex_ptr.dynamic_clear(active_timestamp);
let mut vertex = vertex_ptr.write(active_timestamp);
if vertex.propagated_dual_node == propagated_dual_node_internal_ptr.as_ref().map(|x| x.downgrade()) {
vertex.propagated_grandson_dual_node = propagated_grandson_dual_node_internal_ptr.as_ref().map(|x| x.downgrade());
} else { if let Some(dual_node_internal_weak) = vertex.propagated_dual_node.as_ref() {
debug_assert!(!vertex.is_defect, "cannot vacate a syndrome vertex: it shouldn't happen that a syndrome vertex is updated in any partitioned unit");
let mut updated_boundary = Vec::<(bool, EdgeWeak)>::new();
let dual_node_internal_ptr = dual_node_internal_weak.upgrade_force();
lock_write!(dual_node_internal, dual_node_internal_ptr);
vertex.propagated_dual_node = None;
vertex.propagated_grandson_dual_node = None;
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let is_left = *is_left;
let edge_ptr = edge_weak.upgrade_force();
let mut edge = edge_ptr.write(active_timestamp);
let this_vertex_ptr = if is_left {
edge.left.upgrade_force()
} else {
edge.right.upgrade_force()
};
if &this_vertex_ptr == vertex_ptr {
debug_assert!(if is_left { edge.left_growth == 0 } else { edge.right_growth == 0 }, "vacating a non-boundary vertex is forbidden");
let dual_node = if is_left { &edge.left_dual_node } else { &edge.right_dual_node };
if let Some(dual_node_weak) = dual_node.as_ref() {
debug_assert!(dual_node_weak.upgrade_force() == dual_node_internal_ptr);
if is_left {
edge.left_dual_node = None;
edge.left_grandson_dual_node = None;
} else {
edge.right_dual_node = None;
edge.right_grandson_dual_node = None;
}
}
} else {
updated_boundary.push((is_left, edge_weak.clone()));
}
}
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
edge_ptr.dynamic_clear(active_timestamp);
let mut edge = edge_ptr.write(active_timestamp);
let is_left = vertex_ptr.downgrade() == edge.left;
let dual_node = if is_left { &edge.left_dual_node } else { &edge.right_dual_node };
if let Some(dual_node_weak) = dual_node.as_ref() {
debug_assert!(dual_node_weak.upgrade_force() == dual_node_internal_ptr);
if is_left {
edge.left_dual_node = None;
edge.left_grandson_dual_node = None;
} else {
edge.right_dual_node = None;
edge.right_grandson_dual_node = None;
};
updated_boundary.push((!is_left, edge_weak.clone()));
}
}
std::mem::swap(&mut updated_boundary, &mut dual_node_internal.boundary);
}
if let Some(dual_node_internal_ptr) = propagated_dual_node_internal_ptr.as_ref() {
let grandson_dual_node_internal_ptr = propagated_grandson_dual_node_internal_ptr.unwrap();
vertex.propagated_dual_node = Some(dual_node_internal_ptr.downgrade());
vertex.propagated_grandson_dual_node = Some(grandson_dual_node_internal_ptr.downgrade());
lock_write!(dual_node_internal, dual_node_internal_ptr);
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
edge_ptr.dynamic_clear(active_timestamp);
let mut edge = edge_ptr.write(active_timestamp);
let is_left = vertex_ptr.downgrade() == edge.left;
if is_left {
debug_assert_eq!(edge.left_dual_node, None, "edges incident to the vertex must have been vacated");
edge.left_dual_node = Some(dual_node_internal_ptr.downgrade());
edge.left_grandson_dual_node = Some(grandson_dual_node_internal_ptr.downgrade());
} else {
debug_assert_eq!(edge.right_dual_node, None, "edges incident to the vertex must have been vacated");
edge.right_dual_node = Some(dual_node_internal_ptr.downgrade());
edge.right_grandson_dual_node = Some(grandson_dual_node_internal_ptr.downgrade());
}
dual_node_internal.boundary.push((is_left, edge_weak.clone()));
}
self.active_list.push(dual_node_internal_ptr.downgrade());
}
}
}
}
impl FastClear for Edge {
fn hard_clear(&mut self) {
self.left_growth = 0;
self.right_growth = 0;
self.left_dual_node = None;
self.left_grandson_dual_node = None;
self.right_dual_node = None;
self.right_grandson_dual_node = None;
}
#[inline(always)]
fn get_timestamp(&self) -> FastClearTimestamp { self.timestamp }
#[inline(always)]
fn set_timestamp(&mut self, timestamp: FastClearTimestamp) { self.timestamp = timestamp; }
}
impl FastClear for Vertex {
fn hard_clear(&mut self) {
self.is_defect = false;
self.propagated_dual_node = None;
self.propagated_grandson_dual_node = None;
}
#[inline(always)]
fn get_timestamp(&self) -> FastClearTimestamp { self.timestamp }
#[inline(always)]
fn set_timestamp(&mut self, timestamp: FastClearTimestamp) { self.timestamp = timestamp; }
}
impl Vertex {
pub fn is_mirror_blocked(&self) -> bool {
if let Some(ref mirror_unit_ptr) = self.mirror_unit {
let mirror_unit_ptr = mirror_unit_ptr.upgrade_force();
let mirror_unit = mirror_unit_ptr.read_recursive();
!mirror_unit.enabled
} else {
false
}
}
}
impl DualModuleSerial {
pub fn hard_clear_graph(&mut self) {
for edge in self.edges.iter() {
let mut edge = edge.write_force();
edge.hard_clear();
edge.timestamp = 0;
}
for vertex in self.vertices.iter() {
let mut vertex = vertex.write_force();
vertex.hard_clear();
vertex.timestamp = 0;
}
self.active_timestamp = 0;
}
pub fn clear_graph(&mut self) {
if self.active_timestamp == FastClearTimestamp::MAX { self.hard_clear_graph();
}
self.active_timestamp += 1; }
fn hard_clear_edge_dedup(&mut self) {
for edge in self.edges.iter() {
let mut edge = edge.write_force();
edge.dedup_timestamp = (0 ,0);
}
self.edge_dedup_timestamp = 0;
}
fn clear_edge_dedup(&mut self) {
if self.edge_dedup_timestamp == FastClearTimestamp::MAX { self.hard_clear_edge_dedup();
}
self.edge_dedup_timestamp += 1; }
fn renew_active_list(&mut self) {
if self.current_cycle == usize::MAX {
for i in 0..self.nodes_length {
let internal_dual_node_ptr = {
match self.nodes[i].as_ref() {
Some(internal_dual_node_ptr) => {
internal_dual_node_ptr.clone()
},
_ => { continue }
}
};
let mut internal_dual_node = internal_dual_node_ptr.write();
internal_dual_node.last_visit_cycle = 0;
}
self.current_cycle = 0;
}
self.current_cycle += 1;
let mut updated_active_list = Vec::with_capacity(self.active_list.len());
for i in 0..self.active_list.len() {
let (dual_node_ptr, internal_dual_node_ptr) = {
match self.active_list[i].upgrade() {
Some(internal_dual_node_ptr) => {
let mut dual_node_internal = internal_dual_node_ptr.write();
if self.nodes[dual_node_internal.index as usize].is_none() { continue } if dual_node_internal.last_visit_cycle == self.current_cycle { continue } dual_node_internal.last_visit_cycle = self.current_cycle; (dual_node_internal.origin.upgrade_force(), internal_dual_node_ptr.clone())
},
_ => { continue }
}
};
let dual_node = dual_node_ptr.read_recursive();
match dual_node.grow_state {
DualNodeGrowState::Grow | DualNodeGrowState::Shrink => {
updated_active_list.push(internal_dual_node_ptr.downgrade());
}, DualNodeGrowState::Stay => {
}, };
}
self.active_list = updated_active_list;
}
fn sanity_check_grandson(&self, propagated_dual_node_weak: &DualNodeInternalWeak, propagated_grandson_dual_node_weak: &DualNodeInternalWeak) -> Result<(), String> {
let propagated_dual_node_ptr = propagated_dual_node_weak.upgrade_force();
let propagated_grandson_dual_node_ptr = propagated_grandson_dual_node_weak.upgrade_force();
let propagated_dual_node = propagated_dual_node_ptr.read_recursive();
let propagated_grandson_dual_node = propagated_grandson_dual_node_ptr.read_recursive();
let propagated_node_ptr = propagated_dual_node.origin.upgrade_force();
let propagated_node = propagated_node_ptr.read_recursive();
let propagated_grandson_ptr = propagated_grandson_dual_node.origin.upgrade_force();
let propagated_grandson = propagated_grandson_ptr.read_recursive();
if matches!(propagated_grandson.class, DualNodeClass::DefectVertex{..}) {
if matches!(propagated_node.class, DualNodeClass::DefectVertex{..}) {
if propagated_dual_node_ptr != propagated_grandson_dual_node_ptr {
return Err(format!("syndrome node {:?} must have grandson equal to itself {:?}", propagated_dual_node_ptr, propagated_grandson_dual_node_ptr))
}
} else {
drop(propagated_grandson);
let mut descendant_ptr = propagated_grandson_ptr;
loop {
let descendant = descendant_ptr.read_recursive();
if let Some(descendant_parent_ptr) = descendant.parent_blossom.as_ref() {
let descendant_parent_ptr = descendant_parent_ptr.upgrade_force();
if descendant_parent_ptr == propagated_node_ptr {
return Ok(())
}
drop(descendant);
descendant_ptr = descendant_parent_ptr;
} else {
return Err("grandson check failed".to_string());
}
}
}
} else {
return Err("grandson must be a vertex".to_string())
}
Ok(())
}
pub fn sanity_check(&self) -> Result<(), String> {
let active_timestamp = self.active_timestamp;
for vertex_ptr in self.vertices.iter() {
vertex_ptr.dynamic_clear(active_timestamp);
let vertex = vertex_ptr.read_recursive(active_timestamp);
if let Some(propagated_grandson_dual_node) = vertex.propagated_grandson_dual_node.as_ref() {
if let Some(propagated_dual_node) = vertex.propagated_dual_node.as_ref() {
self.sanity_check_grandson(propagated_dual_node, propagated_grandson_dual_node)?;
} else {
return Err(format!("vertex {} has propagated grandson dual node {:?} but missing propagated dual node"
, vertex.vertex_index, vertex.propagated_grandson_dual_node))
}
}
if vertex.propagated_dual_node.is_some() && vertex.propagated_grandson_dual_node.is_none() {
return Err(format!("vertex {} has propagated dual node {:?} but missing grandson", vertex.vertex_index, vertex.propagated_dual_node))
}
}
let mut duplicate_edges = HashMap::<(bool, EdgeIndex), NodeIndex>::new();
for node_index in 0..self.nodes_length as NodeIndex {
let node_ptr = &self.nodes[node_index as usize];
if let Some(node_ptr) = node_ptr {
let dual_node_internal = node_ptr.read_recursive();
if dual_node_internal.origin.upgrade_force().read_recursive().parent_blossom.is_some() {
continue }
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let edge = edge_ptr.read_recursive(active_timestamp);
if duplicate_edges.contains_key(&(*is_left, edge.edge_index)) {
return Err(format!("boundary edge {:?} appears twice in node {} and {}", (*is_left, edge.edge_index), duplicate_edges.get(&(*is_left, edge.edge_index)).unwrap(), node_index));
}
duplicate_edges.insert((*is_left, edge.edge_index), node_index);
}
}
}
Ok(())
}
}
impl FusionVisualizer for DualModuleSerial {
fn snapshot(&self, abbrev: bool) -> serde_json::Value {
self.sanity_check().unwrap();
let active_timestamp = self.active_timestamp;
let mut vertices: Vec::<serde_json::Value> = (0..self.vertex_num).map(|_| serde_json::Value::Null).collect();
for vertex_ptr in self.vertices.iter() {
vertex_ptr.dynamic_clear(active_timestamp);
let vertex = vertex_ptr.read_recursive(active_timestamp);
vertices[vertex.vertex_index as usize] = json!({
if abbrev { "v" } else { "is_virtual" }: i32::from(vertex.is_virtual),
});
if self.owning_range.contains(vertex.vertex_index) { vertices[vertex.vertex_index as usize].as_object_mut().unwrap().insert((if abbrev { "s" } else { "is_defect" })
.to_string(), json!(i32::from(vertex.is_defect)));
}
if let Some(value) = vertex.propagated_dual_node.as_ref().map(|weak| weak.upgrade_force().read_recursive().origin.upgrade_force().read_recursive().index) {
vertices[vertex.vertex_index as usize].as_object_mut().unwrap().insert((if abbrev { "p" } else { "propagated_dual_node" })
.to_string(), json!(value));
}
if let Some(value) = vertex.propagated_grandson_dual_node.as_ref().map(|weak| weak.upgrade_force().read_recursive().origin.upgrade_force().read_recursive().index) {
vertices[vertex.vertex_index as usize].as_object_mut().unwrap().insert((if abbrev { "pg" } else { "propagated_grandson_dual_node" })
.to_string(), json!(value));
}
if let Some(mirror_unit_ptr) = vertex.mirror_unit.as_ref() {
let mirror_unit_ptr = mirror_unit_ptr.upgrade_force();
let mirror_unit = mirror_unit_ptr.read_recursive();
vertices[vertex.vertex_index as usize].as_object_mut().unwrap().insert((if abbrev { "mi" } else { "mirror_unit_index" }).to_string()
, json!(mirror_unit.unit_index));
vertices[vertex.vertex_index as usize].as_object_mut().unwrap().insert((if abbrev { "me" } else { "mirror_enabled" }).to_string()
, json!(i32::from(mirror_unit.enabled)));
}
}
let mut edges: Vec::<serde_json::Value> = (0..self.edge_num).map(|_| serde_json::Value::Null).collect();
for edge_ptr in self.edges.iter() {
edge_ptr.dynamic_clear(active_timestamp);
let edge = edge_ptr.read_recursive(active_timestamp);
edges[edge.edge_index as usize] = json!({
if abbrev { "w" } else { "weight" }: edge.weight,
if abbrev { "l" } else { "left" }: edge.left.upgrade_force().read_recursive(active_timestamp).vertex_index,
if abbrev { "r" } else { "right" }: edge.right.upgrade_force().read_recursive(active_timestamp).vertex_index,
if abbrev { "lg" } else { "left_growth" }: edge.left_growth,
if abbrev { "rg" } else { "right_growth" }: edge.right_growth,
});
if let Some(value) = edge.left_dual_node.as_ref().map(|weak| weak.upgrade_force().read_recursive().origin.upgrade_force().read_recursive().index) {
edges[edge.edge_index as usize].as_object_mut().unwrap().insert((if abbrev { "ld" } else { "left_dual_node" })
.to_string(), json!(value));
}
if let Some(value) = edge.left_grandson_dual_node.as_ref().map(|weak| weak.upgrade_force().read_recursive().origin.upgrade_force().read_recursive().index) {
edges[edge.edge_index as usize].as_object_mut().unwrap().insert((if abbrev { "lgd" } else { "left_grandson_dual_node" })
.to_string(), json!(value));
}
if let Some(value) = edge.right_dual_node.as_ref().map(|weak| weak.upgrade_force().read_recursive().origin.upgrade_force().read_recursive().index) {
edges[edge.edge_index as usize].as_object_mut().unwrap().insert((if abbrev { "rd" } else { "right_dual_node" })
.to_string(), json!(value));
}
if let Some(value) = edge.right_grandson_dual_node.as_ref().map(|weak| weak.upgrade_force().read_recursive().origin.upgrade_force().read_recursive().index) {
edges[edge.edge_index as usize].as_object_mut().unwrap().insert((if abbrev { "rgd" } else { "right_grandson_dual_node" })
.to_string(), json!(value));
}
}
let mut value = json!({
"vertices": vertices,
"edges": edges,
});
if self.owning_range.start() == 0 && self.owning_range.end() == self.vertex_num {
let mut dual_nodes = Vec::<serde_json::Value>::new();
for node_index in 0..self.nodes_length {
let node_ptr = &self.nodes[node_index];
if let Some(node_ptr) = node_ptr.as_ref() {
let node = node_ptr.read_recursive();
dual_nodes.push(json!({
if abbrev { "b" } else { "boundary" }: node.boundary.iter().map(|(is_left, edge_weak)|
(*is_left, edge_weak.upgrade_force().read_recursive(active_timestamp).edge_index)).collect::<Vec<(bool, EdgeIndex)>>(),
if abbrev { "d" } else { "dual_variable" }: node.dual_variable,
}));
} else {
dual_nodes.push(json!(null));
}
}
value.as_object_mut().unwrap().insert("dual_nodes".to_string(), json!(dual_nodes));
}
value
}
}
impl DualModuleSerial {
fn register_dual_node_ptr(&mut self, dual_node_ptr: &DualNodePtr) {
let node = dual_node_ptr.read_recursive();
if let Some(unit_module_info) = self.unit_module_info.as_mut() {
if unit_module_info.owning_dual_range.is_empty() { unit_module_info.owning_dual_range = VertexRange::new(node.index, node.index);
}
if unit_module_info.owning_dual_range.end() == node.index && self.nodes_length == unit_module_info.owning_dual_range.len() {
unit_module_info.owning_dual_range.append_by(1);
} else {
unit_module_info.dual_node_pointers.insert(dual_node_ptr.clone(), self.nodes_length);
}
} else {
debug_assert!(self.nodes_length as NodeIndex == node.index, "dual node must be created in a sequential manner: no missing or duplicating");
}
}
pub fn get_dual_node_index(&self, dual_node_ptr: &DualNodePtr) -> Option<usize> {
let dual_node = dual_node_ptr.read_recursive();
if let Some(unit_module_info) = self.unit_module_info.as_ref() {
if unit_module_info.owning_dual_range.contains(dual_node.index) {
debug_assert!(dual_node.belonging.upgrade_force().read_recursive().parent.is_none(), "dual node is not updated");
Some((dual_node.index - unit_module_info.owning_dual_range.start()) as usize)
} else {
unit_module_info.dual_node_pointers.get(dual_node_ptr).copied()
}
} else {
Some(dual_node.index as usize)
}
}
pub fn get_vertex_index(&self, vertex_index: VertexIndex) -> Option<usize> {
if self.owning_range.contains(vertex_index) {
return Some((vertex_index - self.owning_range.start()) as usize)
}
if let Some(unit_module_info) = self.unit_module_info.as_ref() {
if let Some(index) = unit_module_info.mirrored_vertices.get(&vertex_index) {
return Some(*index as usize)
}
}
None
}
pub fn get_dual_node_internal_ptr(&self, dual_node_ptr: &DualNodePtr) -> DualNodeInternalPtr {
self.get_dual_node_internal_ptr_optional(dual_node_ptr).unwrap()
}
pub fn get_dual_node_internal_ptr_optional(&self, dual_node_ptr: &DualNodePtr) -> Option<DualNodeInternalPtr> {
self.get_dual_node_index(dual_node_ptr).map(|dual_node_index| {
let dual_node_internal_ptr = self.nodes[dual_node_index].as_ref().expect("internal dual node must exists");
debug_assert!(dual_node_ptr == &dual_node_internal_ptr.read_recursive().origin.upgrade_force(), "dual node and dual internal node must corresponds to each other");
dual_node_internal_ptr.clone()
})
}
pub fn get_otherwise_add_dual_node(&mut self, dual_node_ptr: &DualNodePtr, dual_variable: Weight) -> DualNodeInternalPtr {
let dual_node_index = self.get_dual_node_index(dual_node_ptr).unwrap_or_else(|| {
self.register_dual_node_ptr(dual_node_ptr);
let node_index = self.nodes_length as NodeIndex;
let node_internal_ptr = if node_index < self.nodes.len() as NodeIndex && self.nodes[node_index as usize].is_some() {
let node_ptr = self.nodes[node_index as usize].as_ref().unwrap().clone();
let mut node = node_ptr.write();
node.origin = dual_node_ptr.downgrade();
node.index = node_index;
node.dual_variable = dual_variable;
node.boundary.clear();
node.overgrown_stack.clear();
node.last_visit_cycle = 0;
drop(node);
node_ptr
} else {
DualNodeInternalPtr::new_value(DualNodeInternal {
origin: dual_node_ptr.downgrade(),
index: node_index,
dual_variable,
boundary: Vec::new(),
overgrown_stack: Vec::new(),
last_visit_cycle: 0,
})
};
self.active_list.push(node_internal_ptr.downgrade());
self.nodes_length += 1;
if self.nodes.len() < self.nodes_length {
self.nodes.push(None);
}
self.nodes[node_index as usize] = Some(node_internal_ptr);
node_index as usize
});
let dual_node_internal_ptr = self.nodes[dual_node_index].as_ref().expect("internal dual node must exists");
debug_assert!(dual_node_ptr == &dual_node_internal_ptr.read_recursive().origin.upgrade_force(), "dual node and dual internal node must corresponds to each other");
dual_node_internal_ptr.clone()
}
pub fn prepare_dual_node_growth_single(&mut self, dual_node_ptr: &DualNodePtr, is_grow: bool) -> bool {
let active_timestamp = self.active_timestamp;
self.updated_boundary.clear();
self.propagating_vertices.clear();
let dual_node_internal_ptr = self.get_dual_node_internal_ptr(dual_node_ptr);
let mut newly_propagated_edge_has_zero_weight = false;
if is_grow { let dual_node_internal = dual_node_internal_ptr.read_recursive();
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let is_left = *is_left;
let edge = edge_ptr.read_recursive(active_timestamp);
let peer_dual_node: &Option<DualNodeInternalWeak> = if is_left {
&edge.right_dual_node
} else {
&edge.left_dual_node
};
if edge.left_growth + edge.right_growth == edge.weight && peer_dual_node.is_none() {
let peer_vertex_ptr = if is_left {
edge.right.upgrade_force()
} else {
edge.left.upgrade_force()
};
peer_vertex_ptr.dynamic_clear(active_timestamp);
let peer_vertex = peer_vertex_ptr.read_recursive(active_timestamp);
if peer_vertex.is_virtual || peer_vertex.is_mirror_blocked() { self.updated_boundary.push((is_left, edge_weak.clone()));
} else {
debug_assert!(peer_vertex.propagated_dual_node.is_none(), "growing into another propagated vertex forbidden");
debug_assert!(peer_vertex.propagated_grandson_dual_node.is_none(), "growing into another propagated vertex forbidden");
self.propagating_vertices.push((peer_vertex_ptr.downgrade(), if is_left { edge.left_grandson_dual_node.clone() } else { edge.right_grandson_dual_node.clone() }));
drop(edge); let mut edge = edge_ptr.write(active_timestamp);
if is_left {
edge.right_dual_node = Some(dual_node_internal_ptr.downgrade());
debug_assert!(edge.left_grandson_dual_node.is_some());
edge.right_grandson_dual_node = edge.left_grandson_dual_node.clone();
} else {
edge.left_dual_node = Some(dual_node_internal_ptr.downgrade());
debug_assert!(edge.right_grandson_dual_node.is_some());
edge.left_grandson_dual_node = edge.right_grandson_dual_node.clone();
}
}
} else { self.updated_boundary.push((is_left, edge_weak.clone()));
}
}
drop(dual_node_internal); for (vertex_weak, grandson_dual_node) in self.propagating_vertices.iter() {
let vertex_ptr = vertex_weak.upgrade_force();
let mut vertex = vertex_ptr.write(active_timestamp);
if vertex.propagated_dual_node.is_none() {
vertex.propagated_dual_node = Some(dual_node_internal_ptr.downgrade());
vertex.propagated_grandson_dual_node = grandson_dual_node.clone();
if let Some(mirror_unit_weak) = &vertex.mirror_unit {
self.sync_requests.push(SyncRequest {
mirror_unit_weak: mirror_unit_weak.clone(),
vertex_index: vertex.vertex_index,
propagated_dual_node: vertex.propagated_dual_node.clone().map(|weak| {
let dual_node_ptr = weak.upgrade_force();
let dual_node = dual_node_ptr.read_recursive();
(dual_node.origin.clone(), dual_node.dual_variable)
}),
propagated_grandson_dual_node: vertex.propagated_grandson_dual_node.as_ref().map(|weak| {
let dual_node_ptr = weak.upgrade_force();
let dual_node = dual_node_ptr.read_recursive();
(dual_node.origin.clone(), dual_node.dual_variable)
}),
});
}
let mut count_newly_propagated_edge = 0;
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
let (is_left, newly_propagated_edge) = {
edge_ptr.dynamic_clear(active_timestamp);
let edge = edge_ptr.read_recursive(active_timestamp);
let is_left = vertex_ptr.downgrade() == edge.left;
let newly_propagated_edge = if is_left {
edge.left_dual_node.is_none()
} else {
edge.right_dual_node.is_none()
};
(is_left, newly_propagated_edge)
};
if newly_propagated_edge {
count_newly_propagated_edge += 1;
self.updated_boundary.push((is_left, edge_weak.clone()));
let mut edge = edge_ptr.write(active_timestamp);
if edge.weight == 0 {
newly_propagated_edge_has_zero_weight = true;
}
if is_left {
edge.left_dual_node = Some(dual_node_internal_ptr.downgrade());
edge.left_grandson_dual_node = grandson_dual_node.clone();
} else {
edge.right_dual_node = Some(dual_node_internal_ptr.downgrade());
edge.right_grandson_dual_node = grandson_dual_node.clone();
};
}
}
if count_newly_propagated_edge == 0 {
lock_write!(dual_node_internal, dual_node_internal_ptr);
dual_node_internal.overgrown_stack.push((vertex_ptr.downgrade(), 0));
}
}
}
} else { self.clear_edge_dedup();
{
lock_write!(dual_node_internal, dual_node_internal_ptr);
while !dual_node_internal.overgrown_stack.is_empty() {
let last_index = dual_node_internal.overgrown_stack.len() - 1;
let (_, overgrown) = &dual_node_internal.overgrown_stack[last_index];
if *overgrown == 0 {
let (vertex_weak, _) = dual_node_internal.overgrown_stack.pop().unwrap();
let vertex_ptr = vertex_weak.upgrade_force();
let mut vertex = vertex_ptr.write(active_timestamp);
if vertex.propagated_dual_node == Some(dual_node_internal_ptr.downgrade()) {
vertex.propagated_dual_node = None;
vertex.propagated_grandson_dual_node = None;
if let Some(mirror_unit_weak) = &vertex.mirror_unit {
self.sync_requests.push(SyncRequest {
mirror_unit_weak: mirror_unit_weak.clone(),
vertex_index: vertex.vertex_index,
propagated_dual_node: None,
propagated_grandson_dual_node: None,
});
}
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
let mut edge = edge_ptr.write(active_timestamp);
let is_left = vertex_ptr.downgrade() == edge.left;
if self.unit_module_info.is_none() {
debug_assert!(if is_left {
edge.left_dual_node == Some(dual_node_internal_ptr.downgrade()) && edge.left_grandson_dual_node.is_some()
} else {
edge.right_dual_node == Some(dual_node_internal_ptr.downgrade()) && edge.right_grandson_dual_node.is_some()
}, "overgrown vertices must be surrounded by the same propagated dual node");
}
if is_left {
edge.left_dual_node = None;
edge.left_grandson_dual_node = None;
} else {
edge.right_dual_node = None;
edge.right_grandson_dual_node = None;
}
if (if !is_left { edge.dedup_timestamp.0 } else { edge.dedup_timestamp.1 }) != self.edge_dedup_timestamp {
if !is_left { edge.dedup_timestamp.0 = self.edge_dedup_timestamp; } else { edge.dedup_timestamp.1 = self.edge_dedup_timestamp; }
self.updated_boundary.push((!is_left, edge_weak.clone())); }
}
} else {
debug_assert!(self.unit_module_info.is_some(), "serial module itself cannot happen");
}
} else {
break }
}
}
let dual_node_internal = dual_node_internal_ptr.read_recursive();
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let is_left = *is_left;
let mut edge = edge_ptr.write(active_timestamp);
let this_growth = if is_left {
edge.left_growth
} else {
edge.right_growth
};
if this_growth == 0 {
let this_vertex_ptr = if is_left {
edge.left.upgrade_force()
} else {
edge.right.upgrade_force()
};
let this_vertex = this_vertex_ptr.read_recursive(active_timestamp);
if this_vertex.is_defect { if (if is_left { edge.dedup_timestamp.0 } else { edge.dedup_timestamp.1 }) != self.edge_dedup_timestamp {
if is_left { edge.dedup_timestamp.0 = self.edge_dedup_timestamp; } else { edge.dedup_timestamp.1 = self.edge_dedup_timestamp; }
self.updated_boundary.push((is_left, edge_weak.clone()));
}
} else {
if edge.weight > 0 && self.unit_module_info.is_none() { debug_assert!(this_vertex.propagated_dual_node.is_some(), "unexpected shrink into an empty vertex");
}
self.propagating_vertices.push((this_vertex_ptr.downgrade(), None));
}
} else { if (if is_left { edge.dedup_timestamp.0 } else { edge.dedup_timestamp.1 }) != self.edge_dedup_timestamp {
if is_left { edge.dedup_timestamp.0 = self.edge_dedup_timestamp; } else { edge.dedup_timestamp.1 = self.edge_dedup_timestamp; }
self.updated_boundary.push((is_left, edge_weak.clone()));
}
}
}
for (vertex_weak, _) in self.propagating_vertices.iter() {
let vertex_ptr = vertex_weak.upgrade_force();
let mut vertex = vertex_ptr.write(active_timestamp);
if vertex.propagated_dual_node.is_some() {
vertex.propagated_dual_node = None;
vertex.propagated_grandson_dual_node = None;
if let Some(mirror_unit_weak) = &vertex.mirror_unit {
self.sync_requests.push(SyncRequest {
mirror_unit_weak: mirror_unit_weak.clone(),
vertex_index: vertex.vertex_index,
propagated_dual_node: None,
propagated_grandson_dual_node: None,
});
}
for edge_weak in vertex.edges.iter() {
let edge_ptr = edge_weak.upgrade_force();
let (is_left, newly_propagated_edge) = {
let edge = edge_ptr.read_recursive(active_timestamp);
let is_left = vertex_ptr.downgrade() == edge.left;
debug_assert!(if is_left { edge.right != vertex_ptr.downgrade() } else { edge.right == vertex_ptr.downgrade() });
let newly_propagated_edge = edge.left_dual_node == Some(dual_node_internal_ptr.downgrade())
&& edge.right_dual_node == Some(dual_node_internal_ptr.downgrade())
&& edge.left_growth + edge.right_growth >= edge.weight;
debug_assert!({
newly_propagated_edge || {
if is_left { edge.left_growth == 0 } else { edge.right_growth == 0 }
}
}, "an edge must be either newly propagated or to be removed");
(is_left, newly_propagated_edge)
};
if newly_propagated_edge {
let mut edge = edge_ptr.write(active_timestamp);
if (if !is_left { edge.dedup_timestamp.0 } else { edge.dedup_timestamp.1 }) != self.edge_dedup_timestamp {
if !is_left { edge.dedup_timestamp.0 = self.edge_dedup_timestamp; } else { edge.dedup_timestamp.1 = self.edge_dedup_timestamp; }
self.updated_boundary.push((!is_left, edge_weak.clone()));
} if edge.weight == 0 {
newly_propagated_edge_has_zero_weight = true;
}
if is_left {
debug_assert!(edge.right_dual_node.is_some(), "unexpected shrinking to empty edge");
debug_assert!(edge.right_dual_node.as_ref().unwrap() == &dual_node_internal_ptr.downgrade(), "shrinking edge should be same tree node");
edge.left_dual_node = None;
edge.left_grandson_dual_node = None;
} else {
debug_assert!(edge.left_dual_node.is_some(), "unexpected shrinking to empty edge");
debug_assert!(edge.left_dual_node.as_ref().unwrap() == &dual_node_internal_ptr.downgrade(), "shrinking edge should be same tree node");
edge.right_dual_node = None;
edge.right_grandson_dual_node = None;
};
} else {
let mut edge = edge_ptr.write(active_timestamp);
if is_left {
edge.left_dual_node = None;
edge.left_grandson_dual_node = None;
} else {
edge.right_dual_node = None;
edge.right_grandson_dual_node = None;
}
}
}
}
}
}
lock_write!(dual_node_internal, dual_node_internal_ptr);
std::mem::swap(&mut self.updated_boundary, &mut dual_node_internal.boundary);
if self.unit_module_info.is_none() {
debug_assert!(!dual_node_internal.boundary.is_empty(), "the boundary of a dual cluster is never empty");
}
newly_propagated_edge_has_zero_weight
}
pub fn prepare_dual_node_growth(&mut self, dual_node_ptr: &DualNodePtr, is_grow: bool) {
let mut need_another = self.prepare_dual_node_growth_single(dual_node_ptr, is_grow);
while need_another { need_another = self.prepare_dual_node_growth_single(dual_node_ptr, is_grow);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use super::super::example_codes::*;
use super::super::primal_module_serial::tests::*;
#[allow(dead_code)]
fn debug_print_dual_node(dual_module: &DualModuleSerial, dual_node_ptr: &DualNodePtr) {
println!("boundary:");
let dual_node_internal_ptr = dual_module.get_dual_node_internal_ptr(dual_node_ptr);
let dual_node_internal = dual_node_internal_ptr.read_recursive();
for (is_left, edge_weak) in dual_node_internal.boundary.iter() {
let edge_ptr = edge_weak.upgrade_force();
let edge = edge_ptr.read_recursive_force();
println!(" {} {:?}", if *is_left { " left" } else { "right" }, edge);
}
}
#[test]
fn dual_module_serial_basics() { let visualize_filename = format!("dual_module_serial_basics.json");
let half_weight = 500;
let mut code = CodeCapacityPlanarCode::new(7, 0.1, half_weight);
let mut visualizer = Visualizer::new(Some(visualize_data_folder() + visualize_filename.as_str()), code.get_positions(), true).unwrap();
print_visualize_link(visualize_filename.clone());
let initializer = code.get_initializer();
let mut dual_module = DualModuleSerial::new_empty(&initializer);
code.vertices[19].is_defect = true;
code.vertices[25].is_defect = true;
let interface_ptr = DualModuleInterfacePtr::new_load(&code.get_syndrome(), &mut dual_module);
visualizer.snapshot_combined(format!("syndrome"), vec![&interface_ptr, &dual_module]).unwrap();
let dual_node_19_ptr = interface_ptr.read_recursive().nodes[0].clone().unwrap();
let dual_node_25_ptr = interface_ptr.read_recursive().nodes[1].clone().unwrap();
dual_module.grow_dual_node(&dual_node_19_ptr, half_weight);
dual_module.grow_dual_node(&dual_node_25_ptr, half_weight);
visualizer.snapshot_combined(format!("grow to 0.5"), vec![&interface_ptr, &dual_module]).unwrap();
dual_module.grow_dual_node(&dual_node_19_ptr, half_weight);
dual_module.grow_dual_node(&dual_node_25_ptr, half_weight);
visualizer.snapshot_combined(format!("grow to 1"), vec![&interface_ptr, &dual_module]).unwrap();
dual_module.grow_dual_node(&dual_node_19_ptr, half_weight);
dual_module.grow_dual_node(&dual_node_25_ptr, half_weight);
visualizer.snapshot_combined(format!("grow to 1.5"), vec![&interface_ptr, &dual_module]).unwrap();
dual_module.grow_dual_node(&dual_node_19_ptr, -half_weight);
dual_module.grow_dual_node(&dual_node_25_ptr, -half_weight);
visualizer.snapshot_combined(format!("shrink to 1"), vec![&interface_ptr, &dual_module]).unwrap();
dual_module.grow_dual_node(&dual_node_19_ptr, -half_weight);
dual_module.grow_dual_node(&dual_node_25_ptr, -half_weight);
visualizer.snapshot_combined(format!("shrink to 0.5"), vec![&interface_ptr, &dual_module]).unwrap();
dual_module.grow_dual_node(&dual_node_19_ptr, -half_weight);
dual_module.grow_dual_node(&dual_node_25_ptr, -half_weight);
visualizer.snapshot_combined(format!("shrink to 0"), vec![&interface_ptr, &dual_module]).unwrap();
}
#[test]
fn dual_module_serial_blossom_basics() { let visualize_filename = format!("dual_module_serial_blossom_basics.json");
let half_weight = 500;
let mut code = CodeCapacityPlanarCode::new(7, 0.1, half_weight);
let mut visualizer = Visualizer::new(Some(visualize_data_folder() + visualize_filename.as_str()), code.get_positions(), true).unwrap();
print_visualize_link(visualize_filename.clone());
let initializer = code.get_initializer();
let mut dual_module = DualModuleSerial::new_empty(&initializer);
code.vertices[19].is_defect = true;
code.vertices[26].is_defect = true;
code.vertices[35].is_defect = true;
let interface_ptr = DualModuleInterfacePtr::new_load(&code.get_syndrome(), &mut dual_module);
visualizer.snapshot_combined(format!("syndrome"), vec![&interface_ptr, &dual_module]).unwrap();
let dual_node_19_ptr = interface_ptr.read_recursive().nodes[0].clone().unwrap();
let dual_node_26_ptr = interface_ptr.read_recursive().nodes[1].clone().unwrap();
let dual_node_35_ptr = interface_ptr.read_recursive().nodes[2].clone().unwrap();
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 6 * half_weight);
visualizer.snapshot_combined(format!("before create blossom"), vec![&interface_ptr, &dual_module]).unwrap();
let nodes_circle = vec![dual_node_19_ptr.clone(), dual_node_26_ptr.clone(), dual_node_35_ptr.clone()];
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Shrink, &mut dual_module);
let dual_node_blossom = interface_ptr.create_blossom(nodes_circle, vec![], &mut dual_module);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 7 * half_weight);
visualizer.snapshot_combined(format!("blossom grow half weight"), vec![&interface_ptr, &dual_module]).unwrap();
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 8 * half_weight);
visualizer.snapshot_combined(format!("blossom grow half weight"), vec![&interface_ptr, &dual_module]).unwrap();
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 9 * half_weight);
visualizer.snapshot_combined(format!("blossom grow half weight"), vec![&interface_ptr, &dual_module]).unwrap();
interface_ptr.set_grow_state(&dual_node_blossom, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 8 * half_weight);
visualizer.snapshot_combined(format!("blossom shrink half weight"), vec![&interface_ptr, &dual_module]).unwrap();
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 6 * half_weight);
visualizer.snapshot_combined(format!("blossom shrink weight"), vec![&interface_ptr, &dual_module]).unwrap();
interface_ptr.expand_blossom(dual_node_blossom, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_19_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_35_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 3 * half_weight);
visualizer.snapshot_combined(format!("individual shrink half weight"), vec![&interface_ptr, &dual_module]).unwrap();
}
#[test]
fn dual_module_serial_stop_reason_1() { let visualize_filename = format!("dual_module_serial_stop_reason_1.json");
let half_weight = 500;
let mut code = CodeCapacityPlanarCode::new(7, 0.1, half_weight);
let mut visualizer = Visualizer::new(Some(visualize_data_folder() + visualize_filename.as_str()), code.get_positions(), true).unwrap();
print_visualize_link(visualize_filename.clone());
let initializer = code.get_initializer();
let mut dual_module = DualModuleSerial::new_empty(&initializer);
code.vertices[19].is_defect = true;
code.vertices[25].is_defect = true;
let interface_ptr = DualModuleInterfacePtr::new_load(&code.get_syndrome(), &mut dual_module);
visualizer.snapshot_combined(format!("syndrome"), vec![&interface_ptr, &dual_module]).unwrap();
let dual_node_19_ptr = interface_ptr.read_recursive().nodes[0].clone().unwrap();
let dual_node_25_ptr = interface_ptr.read_recursive().nodes[1].clone().unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 4 * half_weight);
visualizer.snapshot_combined(format!("grow"), vec![&interface_ptr, &dual_module]).unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 6 * half_weight);
visualizer.snapshot_combined(format!("grow"), vec![&interface_ptr, &dual_module]).unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().is_conflicting(&dual_node_19_ptr, &dual_node_25_ptr), "unexpected: {:?}", group_max_update_length);
}
#[test]
fn dual_module_serial_stop_reason_2() { let visualize_filename = format!("dual_module_serial_stop_reason_2.json");
let half_weight = 500;
let mut code = CodeCapacityPlanarCode::new(7, 0.1, half_weight);
let mut visualizer = Visualizer::new(Some(visualize_data_folder() + visualize_filename.as_str()), code.get_positions(), true).unwrap();
print_visualize_link(visualize_filename.clone());
let initializer = code.get_initializer();
let mut dual_module = DualModuleSerial::new_empty(&initializer);
code.vertices[18].is_defect = true;
code.vertices[26].is_defect = true;
code.vertices[34].is_defect = true;
let interface_ptr = DualModuleInterfacePtr::new_load(&code.get_syndrome(), &mut dual_module);
visualizer.snapshot_combined(format!("syndrome"), vec![&interface_ptr, &dual_module]).unwrap();
let dual_node_18_ptr = interface_ptr.read_recursive().nodes[0].clone().unwrap();
let dual_node_26_ptr = interface_ptr.read_recursive().nodes[1].clone().unwrap();
let dual_node_34_ptr = interface_ptr.read_recursive().nodes[2].clone().unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 3 * half_weight);
visualizer.snapshot_combined(format!("grow"), vec![&interface_ptr, &dual_module]).unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().is_conflicting(&dual_node_18_ptr, &dual_node_26_ptr)
|| group_max_update_length.peek().unwrap().is_conflicting(&dual_node_26_ptr, &dual_node_34_ptr), "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_18_ptr, DualNodeGrowState::Stay, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Stay, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().is_conflicting(&dual_node_26_ptr, &dual_node_34_ptr)
, "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_18_ptr, DualNodeGrowState::Grow, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 4 * half_weight);
visualizer.snapshot_combined(format!("grow"), vec![&interface_ptr, &dual_module]).unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().is_conflicting(&dual_node_18_ptr, &dual_node_34_ptr), "unexpected: {:?}", group_max_update_length);
let dual_node_blossom = interface_ptr.create_blossom(vec![dual_node_18_ptr.clone(), dual_node_26_ptr.clone(), dual_node_34_ptr.clone()], vec![], &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 6 * half_weight);
visualizer.snapshot_combined(format!("grow blossom"), vec![&interface_ptr, &dual_module]).unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 8 * half_weight);
visualizer.snapshot_combined(format!("grow blossom"), vec![&interface_ptr, &dual_module]).unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().get_touching_virtual() == Some((dual_node_blossom.clone(), 23))
|| group_max_update_length.peek().unwrap().get_touching_virtual() == Some((dual_node_blossom.clone(), 39))
, "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_blossom, DualNodeGrowState::Stay, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.is_empty(), "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_blossom, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 6 * half_weight);
visualizer.snapshot_combined(format!("shrink blossom"), vec![&interface_ptr, &dual_module]).unwrap();
interface_ptr.set_grow_state(&dual_node_blossom, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 4 * half_weight);
visualizer.snapshot_combined(format!("shrink blossom"), vec![&interface_ptr, &dual_module]).unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap() == &MaxUpdateLength::BlossomNeedExpand(dual_node_blossom.clone())
, "unexpected: {:?}", group_max_update_length);
interface_ptr.expand_blossom(dual_node_blossom, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_18_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Grow, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_34_ptr, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 2 * half_weight);
visualizer.snapshot_combined(format!("shrink"), vec![&interface_ptr, &dual_module]).unwrap();
}
#[test]
fn dual_module_serial_fast_clear_1() { let half_weight = 500;
let mut code = CodeCapacityPlanarCode::new(7, 0.1, half_weight);
let initializer = code.get_initializer();
let mut dual_module = DualModuleSerial::new_empty(&initializer);
code.vertices[18].is_defect = true;
code.vertices[26].is_defect = true;
code.vertices[34].is_defect = true;
let interface_ptr = DualModuleInterfacePtr::new_load(&code.get_syndrome(), &mut dual_module);
let dual_node_18_ptr = interface_ptr.read_recursive().nodes[0].clone().unwrap();
let dual_node_26_ptr = interface_ptr.read_recursive().nodes[1].clone().unwrap();
let dual_node_34_ptr = interface_ptr.read_recursive().nodes[2].clone().unwrap();
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 3 * half_weight);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().is_conflicting(&dual_node_18_ptr, &dual_node_26_ptr)
|| group_max_update_length.peek().unwrap().is_conflicting(&dual_node_26_ptr, &dual_node_34_ptr), "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_18_ptr, DualNodeGrowState::Stay, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Stay, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().is_conflicting(&dual_node_26_ptr, &dual_node_34_ptr)
, "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_18_ptr, DualNodeGrowState::Grow, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 4 * half_weight);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().is_conflicting(&dual_node_18_ptr, &dual_node_34_ptr), "unexpected: {:?}", group_max_update_length);
let dual_node_blossom = interface_ptr.create_blossom(vec![dual_node_18_ptr.clone(), dual_node_26_ptr.clone(), dual_node_34_ptr.clone()], vec![], &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap().get_touching_virtual() == Some((dual_node_blossom.clone(), 23))
|| group_max_update_length.peek().unwrap().get_touching_virtual() == Some((dual_node_blossom.clone(), 39))
, "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_blossom, DualNodeGrowState::Stay, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.is_empty(), "unexpected: {:?}", group_max_update_length);
interface_ptr.set_grow_state(&dual_node_blossom, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_blossom, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert!(group_max_update_length.peek().unwrap() == &MaxUpdateLength::BlossomNeedExpand(dual_node_blossom.clone())
, "unexpected: {:?}", group_max_update_length);
interface_ptr.expand_blossom(dual_node_blossom, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_18_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_26_ptr, DualNodeGrowState::Grow, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_34_ptr, DualNodeGrowState::Shrink, &mut dual_module);
let group_max_update_length = dual_module.compute_maximum_update_length();
assert_eq!(group_max_update_length.get_none_zero_growth(), Some(2 * half_weight), "unexpected: {:?}", group_max_update_length);
interface_ptr.grow(2 * half_weight, &mut dual_module);
assert_eq!(interface_ptr.sum_dual_variables(), 2 * half_weight);
}
#[test]
fn dual_module_grow_iterative_1() { let visualize_filename = format!("dual_module_grow_iterative_1.json");
let half_weight = 500;
let mut code = CodeCapacityPlanarCode::new(11, 0.1, half_weight);
let mut visualizer = Visualizer::new(Some(visualize_data_folder() + visualize_filename.as_str()), code.get_positions(), true).unwrap();
print_visualize_link(visualize_filename.clone());
let initializer = code.get_initializer();
let mut dual_module = DualModuleSerial::new_empty(&initializer);
code.vertices[39].is_defect = true;
code.vertices[65].is_defect = true;
code.vertices[87].is_defect = true;
let interface_ptr = DualModuleInterfacePtr::new_load(&code.get_syndrome(), &mut dual_module);
visualizer.snapshot_combined(format!("syndrome"), vec![&interface_ptr, &dual_module]).unwrap();
interface_ptr.grow_iterative(4 * half_weight, &mut dual_module);
visualizer.snapshot_combined(format!("grow"), vec![&interface_ptr, &dual_module]).unwrap();
assert_eq!(interface_ptr.sum_dual_variables(), 3 * 4 * half_weight);
let dual_node_39_ptr = interface_ptr.read_recursive().nodes[0].clone().unwrap();
let dual_node_65_ptr = interface_ptr.read_recursive().nodes[1].clone().unwrap();
let dual_node_87_ptr = interface_ptr.read_recursive().nodes[2].clone().unwrap();
interface_ptr.set_grow_state(&dual_node_39_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_65_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.set_grow_state(&dual_node_87_ptr, DualNodeGrowState::Shrink, &mut dual_module);
interface_ptr.grow_iterative(4 * half_weight, &mut dual_module);
visualizer.snapshot_combined(format!("shrink"), vec![&interface_ptr, &dual_module]).unwrap();
assert_eq!(interface_ptr.sum_dual_variables(), 0);
}
#[test]
fn dual_module_debug_1() { let visualize_filename = format!("dual_module_debug_1.json");
let defect_vertices = vec![6, 7, 17, 18, 21, 27, 28, 42, 43, 49, 51, 52, 54, 55, 61, 63, 65, 67, 76, 78, 80, 86, 103, 110, 113, 114, 116, 122, 125, 127];
primal_module_serial_basic_standard_syndrome(11, visualize_filename, defect_vertices, 23);
}
#[test]
fn dual_module_debug_2() { let visualize_filename = format!("dual_module_debug_2.json");
let defect_vertices = vec![5, 12, 16, 19, 21, 38, 42, 43, 49, 56, 61, 67, 72, 73, 74, 75, 76, 88, 89, 92, 93, 99, 105, 112, 117, 120, 124, 129];
primal_module_serial_basic_standard_syndrome(11, visualize_filename, defect_vertices, 22);
}
#[test]
fn dual_module_erasure_1() { let visualize_filename = format!("dual_module_erasure_1.json");
let half_weight = 500;
let mut code = CodeCapacityPlanarCode::new(11, 0.1, half_weight);
let mut visualizer = Visualizer::new(Some(visualize_data_folder() + visualize_filename.as_str()), code.get_positions(), true).unwrap();
print_visualize_link(visualize_filename.clone());
let initializer = code.get_initializer();
let mut dual_module = DualModuleSerial::new_empty(&initializer);
code.vertices[64].is_defect = true;
code.set_erasures(&vec![110, 78, 57, 142, 152, 163, 164]);
let interface_ptr = DualModuleInterfacePtr::new_load(&code.get_syndrome(), &mut dual_module);
visualizer.snapshot_combined(format!("syndrome"), vec![&interface_ptr, &dual_module]).unwrap();
for _ in 0..3 {
interface_ptr.grow_iterative(2 * half_weight, &mut dual_module);
visualizer.snapshot_combined(format!("grow"), vec![&interface_ptr, &dual_module]).unwrap();
}
let dual_node_ptr = interface_ptr.read_recursive().nodes[0].clone().unwrap();
interface_ptr.set_grow_state(&dual_node_ptr, DualNodeGrowState::Shrink, &mut dual_module);
for _ in 0..3 {
interface_ptr.grow_iterative(2 * half_weight, &mut dual_module);
visualizer.snapshot_combined(format!("shrink"), vec![&interface_ptr, &dual_module]).unwrap();
}
dual_module.clear();
let interface_ptr = DualModuleInterfacePtr::new_load(&SyndromePattern::new_vertices(code.get_syndrome().defect_vertices), &mut dual_module);
visualizer.snapshot_combined(format!("after clear"), vec![&interface_ptr, &dual_module]).unwrap();
for _ in 0..3 {
interface_ptr.grow_iterative(2 * half_weight, &mut dual_module);
visualizer.snapshot_combined(format!("grow"), vec![&interface_ptr, &dual_module]).unwrap();
}
}
}