yui_link/link/
pd_code.rs

1//! PD (planar diagram) codes — the KnotAtlas `X[i,j,k,l]` presentation of a link, and loading a
2//! link from the data directory by name.
3//!
4//! A PD code is a sequence of crossings of the form:
5//!
6//! ```text
7//!     d   c
8//!      \ /
9//!       \     = [a, b, c, d]
10//!      / \
11//!     a   b
12//! ```
13//!
14//! The lower edge is always oriented a -> c.
15//! see: <http://katlas.math.toronto.edu/wiki/Planar_Diagrams>
16
17use itertools::Itertools;
18
19use super::{Edge, Link, Node, NodeType};
20
21/// One crossing of a PD code: `X[i,j,k,l]`, listed counter-clockwise from the incoming under-strand.
22pub type PDCodeX = [Edge; 4];
23
24impl Link {
25    pub fn from_pd_code<I>(pd_code: I) -> Self
26    where I: IntoIterator<Item = PDCodeX> {
27        let nodes = pd_code.into_iter().map(Node::from_pd_code).collect_vec();
28        let mut l = Self::from_nodes(nodes); // unoriented
29        l.reorient(|_, s| s.index() == 0); // PD convention: the under-strand enters at slot 0.
30        l
31    }
32
33    /// The KnotAtlas PD code — one `X[i,j,k,l]` per crossing, CCW from the incoming under-strand `i`.
34    /// Built by traversing the components and emitting each crossing at its under-pass, so `i` is the
35    /// under-strand's incoming edge; round-trips through `from_pd_code`. Resolved (V/H) nodes are
36    /// skipped. Panics on free loops, which a PD code has no way to express.
37    pub fn pd_code(&self) -> Vec<PDCodeX> {
38        assert!(self.loops().is_empty(), "a PD code cannot represent free loops");
39
40        let mut pd = Vec::with_capacity(self.n_nodes());
41        self.traverse_comps(|_, i, j| {
42            let x = self.node(i);
43            // under-pass: `XL`'s under-strand enters at an even port (0/2), `XR`'s at an odd port (1/3);
44            // the other pass is the over-strand and is skipped, so each crossing is emitted exactly once.
45            let under = match x.node_type() {
46                NodeType::XL => j.index() % 2 == 0,
47                NodeType::XR => j.index() % 2 == 1,
48                _ => return,
49            };
50            if under {
51                pd.push([x.edge(j), x.edge(j.shift(1)), x.edge(j.shift(2)), x.edge(j.shift(3))]);
52            }
53        });
54        pd
55    }
56
57    pub fn load(name: &str) -> Result<Link, Box<dyn std::error::Error>> {
58        let json = yui_core::util::data_dir::load_json("links", name)?;
59        let data: Vec<PDCodeX> = serde_json::from_str(&json)?;
60        Ok(Link::from_pd_code(data))
61    }
62}
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67    use crate::NodeType::XL;
68
69    #[test]
70    fn pd_code_roundtrip() {
71        use crate::misc::jones_polynomial;
72
73        let l = Link::test_data("3_1"); // chiral trefoil (oriented)
74
75        // XL round-trip: pd_code -> from_pd_code recovers the same link.
76        let l2 = Link::from_pd_code(l.pd_code());
77        assert_eq!(jones_polynomial(&l), jones_polynomial(&l2), "XL round-trip");
78
79        // XR round-trip: `mirror` flips XL<->XR, exercising the rotated PD emission.
80        let m = l.mirror();
81        let m2 = Link::from_pd_code(m.pd_code());
82        assert_eq!(jones_polynomial(&m), jones_polynomial(&m2), "XR round-trip");
83
84        // chirality guard: 3_1 differs from its mirror, so the XR case isn't vacuous.
85        assert_ne!(jones_polynomial(&l), jones_polynomial(&m));
86    }
87
88    #[test]
89    fn pd_code_depends_only_on_the_diagram() {
90        // Rebuilding changes the node order, so this holds only if traversal follows the orientation.
91        for name in ["3_1", "4_1", "5_2", "6_1", "L2a1", "L4a1"] {
92            let l = Link::test_data(name);
93            assert_eq!(Link::from_pd_code(l.pd_code()).pd_code(), l.pd_code(), "{name}");
94        }
95        let l = Link::pretzel(1, 3, 5);
96        assert_eq!(Link::from_pd_code(l.pd_code()).pd_code(), l.pd_code(), "pretzel(1,3,5)");
97    }
98
99    #[test]
100    #[should_panic(expected = "cannot represent free loops")]
101    fn pd_code_rejects_free_loops() {
102        let _ = Link::unknot().pd_code();
103    }
104
105    #[test]
106    fn link_from_pd_code() {
107        let l = Link::test_data("unknot_l_twist");
108        assert_eq!(l.n_nodes(), 1);
109        assert_eq!(l.node(0).node_type(), XL);
110    }
111}
yui_link/link/pd_code.rs

yui_link/link/
pd_code.rs
