bloq_graph/zx/
layer.rs

1//! Read-only views of one ZX time layer.
2
3use super::ZXGraph;
4
5/// A precomputed snapshot of one time (`z`) layer of a [`ZXGraph`]: its nodes,
6/// in-layer edges, and the nodes with edges into the past or future layers.
7#[derive(Debug, Clone)]
8pub struct ZXLayerView {
9    z: i32,
10    node_ids: Vec<usize>,
11    spacelike_edges: Vec<(usize, usize)>,
12    past_timelike_nodes: Vec<usize>,
13    future_timelike_nodes: Vec<usize>,
14}
15
16impl ZXLayerView {
17    pub(crate) fn new(zx: &ZXGraph, z: i32) -> Self {
18        let mut node_ids = zx
19            .nodes
20            .iter()
21            .filter(|node| node.pos.z == z)
22            .map(|node| node.id)
23            .collect::<Vec<_>>();
24        node_ids.sort_unstable();
25
26        let mut spacelike_edges = zx
27            .edges
28            .iter()
29            .filter(|edge| {
30                edge.n1 < edge.n2 && zx.nodes[edge.n1].pos.z == z && zx.nodes[edge.n2].pos.z == z
31            })
32            .map(|edge| (edge.n1, edge.n2))
33            .collect::<Vec<_>>();
34        spacelike_edges.sort_unstable();
35
36        let mut past_timelike_nodes = Vec::new();
37        let mut future_timelike_nodes = Vec::new();
38        for &node_id in &node_ids {
39            let neighbors = zx.neighbor_ids(node_id);
40            if neighbors
41                .iter()
42                .any(|&neighbor| zx.nodes[neighbor].pos.z < z)
43            {
44                past_timelike_nodes.push(node_id);
45            }
46            if neighbors
47                .iter()
48                .any(|&neighbor| zx.nodes[neighbor].pos.z > z)
49            {
50                future_timelike_nodes.push(node_id);
51            }
52        }
53
54        Self {
55            z,
56            node_ids,
57            spacelike_edges,
58            past_timelike_nodes,
59            future_timelike_nodes,
60        }
61    }
62
63    /// Returns the time layer this view covers.
64    pub fn z(&self) -> i32 {
65        self.z
66    }
67
68    /// Returns the ids of nodes in this layer.
69    pub fn node_ids(&self) -> &[usize] {
70        &self.node_ids
71    }
72
73    /// Returns the in-layer edges as sorted `(n1, n2)` pairs.
74    pub fn spacelike_edges(&self) -> &[(usize, usize)] {
75        &self.spacelike_edges
76    }
77
78    /// Returns the layer nodes that connect to an earlier layer.
79    pub fn past_timelike_nodes(&self) -> &[usize] {
80        &self.past_timelike_nodes
81    }
82
83    /// Returns the layer nodes that connect to a later layer.
84    pub fn future_timelike_nodes(&self) -> &[usize] {
85        &self.future_timelike_nodes
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use glam::ivec3;
92    use rustc_hash::FxHashMap;
93
94    use crate::zx::graph::{CsrAdjacency, ZXEdge, ZXNode};
95    use crate::zx::{NodeKind, ZXGraph};
96
97    #[test]
98    fn zx_layer_view_exposes_exact_membership_and_edges() {
99        let zx = hand_built_zx_graph();
100        let layer = zx.layer(0);
101
102        let past = node_id(&zx, ivec3(0, 0, 0));
103        let left = node_id(&zx, ivec3(1, 0, 0));
104        let right = node_id(&zx, ivec3(2, 0, 0));
105        let isolated = node_id(&zx, ivec3(5, 5, 0));
106        let below = node_id(&zx, ivec3(0, 0, -1));
107
108        assert_eq!(zx.z_layers(), vec![-1, 0, 1]);
109        assert_eq!(layer.z(), 0);
110        assert_eq!(layer.node_ids(), &[past, left, right, isolated]);
111        assert_eq!(layer.spacelike_edges(), &[(left, right)]);
112        assert_eq!(layer.past_timelike_nodes(), &[past]);
113        assert_eq!(layer.future_timelike_nodes(), &[right]);
114
115        assert_eq!(
116            zx.edge_between(left, right)
117                .map(|edge| (edge.n1, edge.n2, edge.hadamard)),
118            Some((left, right, false))
119        );
120        assert_eq!(
121            zx.edge_between(right, left)
122                .map(|edge| (edge.n1, edge.n2, edge.hadamard)),
123            Some((right, left, false))
124        );
125        assert_eq!(
126            zx.edge_between(past, below)
127                .map(|edge| (edge.n1, edge.n2, edge.hadamard)),
128            Some((past, below, false))
129        );
130        assert_eq!(
131            zx.edge_between(below, past)
132                .map(|edge| (edge.n1, edge.n2, edge.hadamard)),
133            Some((below, past, false))
134        );
135    }
136
137    #[test]
138    fn zx_output_ports_ignore_isolated_ports() {
139        let zx = hand_built_zx_graph();
140
141        assert_eq!(zx.output_ports(), vec![glam::ivec3(0, 0, 0)]);
142    }
143
144    fn hand_built_zx_graph() -> crate::ZXGraph {
145        ZXGraph {
146            nodes: vec![
147                ZXNode::new(0, ivec3(0, 0, -1), NodeKind::X),
148                ZXNode::new(1, ivec3(0, 0, 0), NodeKind::Port),
149                ZXNode::new(2, ivec3(1, 0, 0), NodeKind::X),
150                ZXNode::new(3, ivec3(2, 0, 0), NodeKind::Z),
151                ZXNode::new(4, ivec3(2, 0, 1), NodeKind::X),
152                ZXNode::new(5, ivec3(5, 5, 0), NodeKind::Port),
153            ],
154            edges: vec![
155                ZXEdge {
156                    n1: 0,
157                    n2: 1,
158                    id: 6,
159                    hadamard: false,
160                },
161                ZXEdge {
162                    n1: 1,
163                    n2: 0,
164                    id: 7,
165                    hadamard: false,
166                },
167                ZXEdge {
168                    n1: 2,
169                    n2: 3,
170                    id: 8,
171                    hadamard: false,
172                },
173                ZXEdge {
174                    n1: 3,
175                    n2: 2,
176                    id: 9,
177                    hadamard: false,
178                },
179                ZXEdge {
180                    n1: 3,
181                    n2: 4,
182                    id: 10,
183                    hadamard: false,
184                },
185                ZXEdge {
186                    n1: 4,
187                    n2: 3,
188                    id: 11,
189                    hadamard: false,
190                },
191            ],
192            adjacency: CsrAdjacency::from_edges(
193                6,
194                &[
195                    (0, 1, 6),
196                    (1, 0, 7),
197                    (2, 3, 8),
198                    (3, 2, 9),
199                    (3, 4, 10),
200                    (4, 3, 11),
201                ],
202            ),
203            pos_to_node: FxHashMap::from_iter([
204                (ivec3(0, 0, -1), 0),
205                (ivec3(0, 0, 0), 1),
206                (ivec3(1, 0, 0), 2),
207                (ivec3(2, 0, 0), 3),
208                (ivec3(2, 0, 1), 4),
209                (ivec3(5, 5, 0), 5),
210            ]),
211            action_graph: crate::ActionDag::default(),
212            total_ids: 12,
213            cross_incident: Default::default(),
214            stabilizer_phase_basis: Default::default(),
215        }
216    }
217
218    fn node_id(zx: &ZXGraph, pos: glam::IVec3) -> usize {
219        zx.nodes
220            .iter()
221            .find(|node| node.pos == pos)
222            .map(|node| node.id)
223            .expect("node exists at position")
224    }
225}
bloq_graph/zx/layer.rs

bloq_graph/zx/
layer.rs
