1use std::collections::HashMap;
6
7use delegate::delegate;
8use itertools::Itertools;
9use yui_core::algo::KeyedUnionFind;
10use crate::{Node, Edge, Link, Path, Slot, State, PDCodeX};
11
12#[derive(Debug, Clone)]
14pub struct InvLink {
15 inner: Link,
16 e_map: HashMap<Edge, Edge>,
17 x_map: HashMap<Node, Node>
18}
19
20impl InvLink {
21 pub fn new<I>(inner: Link, e_map: I) -> InvLink
22 where I: IntoIterator<Item = (Edge, Edge)> {
23 assert!(inner.loops().is_empty(), "free loops are not supported");
24 let e_map: HashMap<Edge, Edge> = e_map.into_iter().collect();
25
26 let link_edges = inner.edges();
28 let missing = link_edges.iter().filter(|e| !e_map.contains_key(e)).collect_vec();
29 assert!(missing.is_empty(), "e_map does not cover edges {missing:?}");
30
31 let extra = e_map.keys().filter(|e| !link_edges.contains(e)).sorted().collect_vec();
32 assert!(extra.is_empty(), "e_map maps edges {extra:?}, which are not in the link");
33
34 for &e in &link_edges {
35 let f = e_map[&e];
36 assert!(link_edges.contains(&f), "e_map sends edge {e} to {f}, not an edge of the link");
37 assert_eq!(e_map[&f], e, "e_map is not involutive: {e} ↦ {f} ↦ {}", e_map[&f]);
38 }
39
40 let x_map: HashMap<Node, Node> = inner.nodes().map(|x| {
42 let y = Self::find_tau_x(x, &inner, &e_map);
43 (x.clone(), y.clone())
44 }).collect();
45
46 assert_eq!(x_map.len(), inner.n_nodes(), "the diagram has duplicate nodes");
47
48 for (x, y) in &x_map {
49 let z = &x_map[y];
50 assert_eq!(z, x, "e_map induces a non-involutive node map: {x} ↦ {y} ↦ {z}");
51 }
52
53 Self { inner, e_map, x_map }
54 }
55
56 fn find_tau_x<'a>(x: &'a Node, inner: &'a Link, e_map: &HashMap<Edge, Edge>) -> &'a Node {
59 let matches = |y: &Node| Slot::ALL.into_iter().any(|k|
60 Slot::ALL.into_iter().all(|s| y.edge(k.shift(4 - s.index())) == e_map[&x.edge(s)])
61 );
62 let cands = inner.nodes().filter(|y| matches(y)).collect_vec();
63
64 match cands.as_slice() {
65 [y] => {
66 assert_eq!(x.node_type(), y.node_type(), "e_map changes the type of node {x}");
67 y
68 },
69 [] => panic!("e_map sends node {x} to no node of the link"),
70 _ => panic!("e_map does not determine the image of node {x}: {} nodes match", cands.len())
71 }
72 }
73
74 pub fn from_symmetric_pd_code<I1>(pd_code: I1) -> Self
75 where I1: IntoIterator<Item = PDCodeX> {
76 Self::si_knot_from(Link::from_pd_code(pd_code))
78 }
79
80 pub fn si_knot_from(inner: Link) -> InvLink {
83 assert!(inner.is_knot(), "expected a knot, found {} components", inner.n_comps());
84 let base = inner.base_pt().expect("the diagram needs a base point on the axis");
85 let comps = inner.comps();
86 let seq = comps[0].edges();
87 let n = seq.len();
88 let k = seq.iter().position(|&e| e == base).expect("the base point is not on a strand");
89
90 let e_map = (0..n).map(|i| (seq[(k + i) % n], seq[(k + n - i) % n])).collect_vec();
91 let l = Self::new(inner.clone(), e_map);
92 assert!(l.is_oriented(), "the diagram is not oriented");
93 if let Some(x) = l.inner.nodes().find(|x| l.preserves_dir_at(x) != Some(false)) {
94 panic!("τ does not reverse the orientation at node {x} — the diagram is not symmetric there");
95 }
96 l
97 }
98
99 pub fn inner(&self) -> &Link {
100 &self.inner
101 }
102
103 pub fn pd_code(&self) -> Vec<PDCodeX> {
108 let n = self.inner.n_edges() as Edge;
109 assert!(
110 self.inner.edges().into_iter().all(|e| self.inv_edge(e) == (n + 1 - e) % n + 1),
111 "pd_code requires the standard involution `e ↦ (n+1-e)%n+1`; reindex the InvLink first"
112 );
113 self.inner.pd_code()
114 }
115
116 delegate! {
119 to self.inner {
120 pub fn is_empty(&self) -> bool;
121 pub fn is_knot(&self) -> bool;
122 pub fn is_oriented(&self) -> bool;
123 pub fn writhe(&self) -> i32;
124 pub fn n_nodes(&self) -> usize;
125 pub fn nodes(&self) -> impl Iterator<Item = &Node>;
126 pub fn node(&self, i: usize) -> &Node;
127 pub fn crossings(&self) -> impl Iterator<Item = &Node>;
128 pub fn n_crossings(&self) -> usize;
129 pub fn n_signed_crossings(&self) -> (usize, usize);
130 pub fn n_edges(&self) -> usize;
131 pub fn edges(&self) -> Vec<Edge>;
132 pub fn n_comps(&self) -> usize;
133 pub fn comps(&self) -> Vec<Path>;
134 pub fn seifert_state(&self) -> State;
135 pub fn seifert_circles(&self) -> Vec<Path>;
136 pub fn base_pt(&self) -> Option<Edge>;
137 }
138 }
139
140 pub fn with_base_pt(mut self, e: Edge) -> Self {
141 assert!(self.is_on_axis(e), "base_pt {e} must be on-axis (fixed by involution)");
142 self.inner = self.inner.with_base_pt(e);
143 self
144 }
145
146 pub fn inv_edge(&self, e: Edge) -> Edge {
147 self.e_map.get(&e).cloned().unwrap()
148 }
149
150 pub fn inv_node(&self, x: &Node) -> &Node {
151 self.x_map.get(x).unwrap()
152 }
153
154 pub fn is_on_axis(&self, e: Edge) -> bool {
156 self.inv_edge(e) == e
157 }
158
159 pub fn on_axis_edges(&self) -> Vec<Edge> {
160 self.edges().into_iter().filter(|&e| self.is_on_axis(e)).collect()
161 }
162
163 pub fn is_transvergent(&self) -> bool {
166 let off_axis = self.inner.nodes().filter(|&x| self.inv_node(x) != x).collect_vec();
167
168 let shares_edge = |x: &Node, y: &Node|
170 x.edges().iter()
171 .filter(|&&e| !self.is_on_axis(e))
172 .any(|e| y.edges().contains(e));
173
174 let mut uf = KeyedUnionFind::from_iter(off_axis.iter().copied());
175 for (i, &x) in off_axis.iter().enumerate() {
176 for &y in &off_axis[..i] {
177 if shares_edge(x, y) {
178 uf.union(&x, &y);
179 }
180 }
181 }
182
183 uf.into_disjoint().into_iter().all(|group|
184 group.first().is_none_or(|&rep| !group.contains(&self.inv_node(rep)))
185 )
186 }
187
188 pub fn is_strongly_invertible(&self) -> bool {
190 self.is_oriented()
191 && self.inner.nodes().all(|x| self.preserves_dir_at(x) == Some(false))
192 }
193
194 pub fn is_2periodic(&self) -> bool {
196 self.is_oriented()
197 && self.inner.nodes().all(|x| self.preserves_dir_at(x) == Some(true))
198 }
199
200 fn preserves_dir_at(&self, x: &Node) -> Option<bool> {
203 let y = self.inv_node(x);
204 let (p, q) = x.incoming()?;
205 let k = Slot::ALL.into_iter().find(|k|
206 Slot::ALL.into_iter().all(|s| y.edge(k.shift(4 - s.index())) == self.inv_edge(x.edge(s)))
207 )?;
208
209 let is_in = |s: Slot| {
210 let img = k.shift(4 - s.index());
211 y.incoming().is_some_and(|(a, b)| img == a || img == b)
212 };
213 match (is_in(p), is_in(q)) {
214 (true, true) => Some(true),
215 (false, false) => Some(false),
216 _ => None,
217 }
218 }
219
220 pub fn mirror(&self) -> Self {
221 Self {
222 inner: self.inner.mirror(),
223 e_map: self.e_map.clone(),
224 x_map: self.x_map.iter().map(|(x, y)|
225 (x.mirror(), y.mirror())
226 ).collect(),
227 }
228 }
229
230 pub fn reversed(&self) -> Self {
233 Self {
234 inner: self.inner.reversed(),
235 e_map: self.e_map.clone(),
236 x_map: self.x_map.iter().map(|(x, y)|
237 (x.reversed(), y.reversed())
238 ).collect(),
239 }
240 }
241
242 pub fn conn_sum(&self, other: &InvLink) -> InvLink {
245 let base = self.base_pt().expect("self needs a base point");
246 let self_e = self.on_axis_edges().into_iter()
247 .find(|&e| e != base)
248 .expect("self needs a second on-axis edge");
249 let other_e = other.base_pt().expect("other needs a base point");
250 self.conn_sum_at(other, self_e, other_e)
251 }
252
253 pub fn conn_sum_at(&self, other: &InvLink, self_e: Edge, other_e: Edge) -> InvLink {
256 assert!(self.is_knot() && other.is_knot(), "connected sum requires knots");
257 assert!(self.is_strongly_invertible() && other.is_strongly_invertible(),
258 "connected sum requires strongly invertible knots");
259 assert_ne!(Some(self_e), self.base_pt(), "the splice must not consume self's base point");
260 assert_eq!(self.inv_edge(self_e), self_e, "self_e {self_e} must be on-axis");
261 assert_eq!(other.inv_edge(other_e), other_e, "other_e {other_e} must be on-axis");
262
263 let inner = self.inner.conn_sum_at(other.inner(), self_e, other_e);
265 Self::si_knot_from(inner)
266 }
267}
268
269impl InvLink {
270 pub fn load(name: &str) -> Result<InvLink, Box<dyn std::error::Error>> {
271 let json = yui_core::util::data_dir::load_json("inv_link", name)?;
272 let data: Vec<PDCodeX> = serde_json::from_str(&json)?;
273 Ok(InvLink::from_symmetric_pd_code(data))
274 }
275}
276
277#[cfg(test)]
278mod tests {
279 use super::*;
280 use crate::Slot;
281 use crate::misc::det;
282
283 #[test]
284 fn pd_code_roundtrip() {
285 let l = InvLink::from_symmetric_pd_code([[1,7,2,6],[3,9,4,8],[5,1,6,10],[7,3,8,2],[9,5,10,4]]);
288 let l2 = InvLink::from_symmetric_pd_code(l.pd_code());
289 assert_eq!(l.pd_code(), l2.pd_code());
290 for e in l.inner().edges() {
291 assert_eq!(l.inv_edge(e), l2.inv_edge(e), "involution differs at edge {e}");
292 }
293 }
294
295 #[test]
296 fn test_data_diagrams() {
297 for (name, n) in [("3_1", 3), ("4_1", 4), ("4_1a", 4), ("4_1b", 4), ("6_3", 7), ("6_3a", 8), ("7_7b", 7)] {
299 assert_eq!(InvLink::test_data(name).n_crossings(), n, "{name}");
300 }
301 }
302
303 #[test]
304 fn inv_edge() {
305 let l = InvLink::test_data("3_1");
306
307 assert_eq!(l.inv_edge(1), 1);
308 assert_eq!(l.inv_edge(2), 6);
309 assert_eq!(l.inv_edge(3), 5);
310 assert_eq!(l.inv_edge(4), 4);
311 assert_eq!(l.inv_edge(5), 3);
312 assert_eq!(l.inv_edge(6), 2);
313 }
314
315 #[test]
316 fn inv_node() {
317 let l = InvLink::test_data("3_1");
318 let nodes = l.inner.nodes().collect_vec();
319
320 assert_eq!(l.inv_node(nodes[0]), nodes[1]);
321 assert_eq!(l.inv_node(nodes[1]), nodes[0]);
322 assert_eq!(l.inv_node(nodes[2]), nodes[2]);
323 }
324
325 #[test]
326 fn mirror_keeps_the_involution() {
327 let k = InvLink::test_data("3_1");
328 let m = k.mirror();
329 assert_eq!(m.n_crossings(), k.n_crossings());
330 for e in k.edges() {
331 assert_eq!(m.inv_edge(e), k.inv_edge(e), "involution differs at edge {e}");
332 }
333 for (x, y) in k.inner().nodes().zip(m.inner().nodes()) {
334 assert_eq!(m.inv_node(y), &k.inv_node(x).mirror(), "τ differs at node {x:?}");
335 }
336 }
337
338 #[test]
339 #[should_panic(expected = "e_map does not cover edges [3, 4, 5, 6]")]
340 fn new_names_the_uncovered_edges() {
341 let _ = InvLink::new(Link::test_data("3_1"), [(1, 1), (2, 2)]);
342 }
343
344 #[test]
345 #[should_panic(expected = "e_map sends node")]
346 fn new_rejects_an_edge_map_no_rotation_realizes() {
347 let l = Link::test_data("3_1");
350 let e_map: Vec<_> = l.edges().into_iter().map(|e| (e, e)).collect();
351 let _ = InvLink::new(l, e_map);
352 }
353
354 #[test]
355 fn nodes_sharing_an_edge_set() {
356 let l = Link::from_pd_code([[4, 1, 3, 2], [2, 3, 1, 4]]);
359 let il = InvLink::new(l, [(1, 1), (2, 2), (3, 3), (4, 4)]);
360
361 let (x0, x1) = (il.node(0), il.node(1));
362 assert_eq!(il.inv_node(x0), x1);
363 assert_eq!(il.inv_node(x1), x0);
364 }
365
366 #[test]
367 fn transvergent() {
368 let l = InvLink::from_symmetric_pd_code([[1,7,2,6],[3,9,4,8],[5,1,6,10],[7,3,8,2],[9,5,10,4]]);
371 assert!(l.is_transvergent());
372
373 let m = InvLink::new(Link::from_pd_code([[4,1,3,2],[2,3,1,4]]), [(1,2),(2,1),(3,4),(4,3)]);
376 assert!(m.on_axis_edges().is_empty());
377 assert!(!m.is_transvergent());
378 }
379
380 #[test]
381 fn twist_unknot() {
382 let l = Link::from_pd_code([[0, 1, 1, 0]]);
385
386 let si = InvLink::new(l.clone(), [(0, 0), (1, 1)]);
387 assert_eq!(si.on_axis_edges(), vec![0, 1]);
388 assert!(si.is_strongly_invertible());
389 assert!(!si.is_2periodic());
390
391 let per = InvLink::new(l, [(0, 1), (1, 0)]);
392 assert!(per.on_axis_edges().is_empty());
393 assert!(!per.is_strongly_invertible());
394 assert!(per.is_2periodic());
395 }
396
397 #[test]
398 fn involution_is_a_strong_inversion() {
399 fn check(name: &str, l: &InvLink) {
402 let inner = l.inner();
403 assert_eq!(l.on_axis_edges().len(), 2, "{name}: the axis must meet the knot twice");
404 assert!(l.is_strongly_invertible(), "{name}: τ must reverse the orientation");
405
406 for x in inner.nodes() {
407 let y = l.inv_node(x);
408 assert_eq!(y.node_type(), x.node_type(), "{name}: τ changed a crossing type");
409 assert_eq!(l.inv_node(y), x, "{name}: τ is not an involution on nodes");
410
411 let k = (0..4).find(|&k|
413 Slot::ALL.iter().all(|&s|
414 y.edge(Slot::from((k + 4 - s.index()) % 4)) == l.inv_edge(x.edge(s))
415 )
416 );
417 assert!(matches!(k, Some(1) | Some(3)), "{name}: τ does not reverse the slot order at {x}");
418 }
419 }
420
421 for name in ["3_1", "4_1", "6_3"] {
422 check(name, &InvLink::test_data(name));
423 }
424 check("sym_pretzel(-3,3,-3)", &InvLink::sym_pretzel(-3, 3, -3));
425 check("sym_wh+(3_1)", &InvLink::whitehead_double(&InvLink::test_data("3_1"), true, 0));
426 }
427
428 #[test]
429 #[should_panic(expected = "must be on-axis")]
430 fn with_base_pt_rejects_an_off_axis_edge() {
431 let _ = InvLink::test_data("3_1").with_base_pt(2);
433 }
434
435 #[test]
436 fn strong_inversions_are_not_2periodic() {
437 for name in ["3_1", "4_1", "6_3", "5_2a", "7_7b"] {
439 let k = InvLink::test_data(name);
440 assert!(k.is_strongly_invertible(), "{name}");
441 assert!(!k.is_2periodic(), "{name}");
442 }
443 }
444
445 #[test]
446 fn reindexed_keeps_strong_inversion() {
447 let il = InvLink::test_data("3_1");
450 let n = il.n_edges() as Edge;
451
452 for start in il.on_axis_edges() {
453 let r = il.inner().reindexed(start, 1);
454 assert_eq!(r.edges(), (1..=n).collect::<Vec<Edge>>());
455
456 let e_map: Vec<_> = r.edges().into_iter().map(|e| (e, (n + 1 - e) % n + 1)).collect();
457 let re = InvLink::new(r, e_map);
458 assert!(re.is_strongly_invertible(), "renumbered from edge {start}");
459 }
460 }
461
462 #[test]
463 fn conn_sum_at_depends_on_which_side_of_the_axis() {
464 let k1 = InvLink::test_data("3_1");
470 let k2 = InvLink::test_data("6_3");
471
472 let axis = k2.on_axis_edges();
473 assert_eq!(axis, vec![1, 8]);
474 assert_eq!(k2.base_pt(), Some(axis[0]));
475
476 assert_eq!(k1.on_axis_edges(), vec![1, 4]);
478 assert_eq!(k1.base_pt(), Some(1));
479 let self_e = 4;
480
481 let sums = axis.iter().map(|&e| k1.conn_sum_at(&k2, self_e, e)).collect_vec();
482
483 for (s, e) in Iterator::zip(sums.iter(), axis.iter()) {
484 assert!(s.is_knot(), "other_e = {e}");
485 assert!(s.is_strongly_invertible(), "other_e = {e}");
486 let base = s.base_pt().expect("the sum keeps a base point");
487 assert_eq!(s.inv_edge(base), base, "other_e = {e}: base point is off-axis");
488 assert_eq!(s.n_crossings(), k1.n_crossings() + k2.n_crossings(), "other_e = {e}");
489 assert_eq!(det(s.inner()), det(k1.inner()) * det(k2.inner()), "other_e = {e}");
490 }
491
492 let canon = |k: &InvLink| k.inner().reindexed_canon();
493 assert_ne!(canon(&sums[0]), canon(&sums[1]), "the two sides must give different diagrams");
494 assert_eq!(canon(&k1.conn_sum(&k2)), canon(&sums[0]), "conn_sum splices at other's base point");
495 }
496
497 #[test]
498 fn inv_link_reversed() {
499 let k = InvLink::test_data("3_1");
500 let r = k.reversed();
501
502 assert!(r.inner().is_oriented());
503 assert!(r.is_strongly_invertible(), "reversing does not disturb the axis");
504 assert_eq!(r.writhe(), k.writhe());
505 assert_eq!(r.on_axis_edges(), k.on_axis_edges(), "τ is a map of edges, unchanged");
506 for e in k.inner().edges() {
507 assert_eq!(r.inv_edge(e), k.inv_edge(e));
508 }
509 assert_eq!(r.reversed().inner(), k.inner(), "reversing twice is the identity");
510 }
511
512 #[test]
513 fn dms_construction() {
514 let k = InvLink::from_symmetric_pd_code([[1,4,2,5],[5,2,6,3],[3,6,4,1]]);
518 assert_eq!(k.on_axis_edges(), vec![1, 4]);
519
520 let k2 = InvLink::si_knot_from(k.inner().conn_sum(k.inner()));
523 assert_eq!(k2.inner().pd_code(), Link::from_pd_code([
524 [1,4,2,5],[5,2,6,3],[3,6,4,7],[7,10,8,11],[11,8,12,9],[9,12,10,1],
525 ]).pd_code());
526 assert_eq!(k2.on_axis_edges(), vec![1, 7]);
527
528 let mk = k.mirror();
530 let with_mk = k2.conn_sum(&mk);
531 assert_eq!(with_mk.inner().pd_code(), Link::from_pd_code([
532 [1,4,2,5],[5,2,6,3],[3,6,4,13],[7,10,8,11],[11,8,12,9],[9,12,10,1],
533 [16,14,17,13],[14,18,15,17],[18,16,7,15],
534 ]).pd_code());
535 assert_eq!(with_mk.on_axis_edges(), vec![1, 16]);
536
537 let dms = with_mk.conn_sum(&mk.reversed());
539 assert_eq!(dms.inner().pd_code(), Link::from_pd_code([
540 [1,4,2,5],[5,2,6,3],[3,6,4,13],[7,10,8,11],[11,8,12,9],[9,12,10,1],
541 [16,14,17,13],[14,18,15,17],[18,19,7,15],
542 [19,21,24,22],[21,23,20,24],[23,16,22,20],
543 ]).pd_code());
544 assert!(dms.is_strongly_invertible());
545 assert_eq!(dms.base_pt(), Some(1));
546 }
547
548 #[test]
549 fn conn_sum_is_equivariant() {
550 let k1 = InvLink::test_data("3_1");
552 let k2 = InvLink::test_data("4_1");
553 let cs = k1.conn_sum(&k2);
554 assert!(cs.is_knot());
555 assert!(cs.is_strongly_invertible());
556 let base = cs.base_pt().expect("the sum keeps a base point");
557 assert_eq!(cs.inv_edge(base), base, "the sum's base point is on-axis");
558 assert_eq!(det(cs.inner()), 3 * 5, "det is multiplicative under conn sum");
559 }
560}