use super::shape::{Shape, Sign};
use super::threads::GentleThread;
type End = (u32, Sign);
type Step = (u32, Sign);
pub(super) struct RibbonGraph {
ends: Vec<(usize, usize)>,
incident: Vec<Vec<End>>,
}
pub(super) struct Cycle(Vec<Step>);
impl RibbonGraph {
pub(super) fn new(shape: &Shape, permitted: &[GentleThread]) -> RibbonGraph {
let vertices = shape.vertices() as usize;
let mut ends = vec![None; 2 * vertices];
let mut incident = Vec::with_capacity(permitted.len());
for (thread, path) in permitted.iter().enumerate() {
let positions = thread_ends(shape, path);
for (position, &end) in positions.iter().enumerate() {
let entry = &mut ends[slot(end)];
assert!(
entry.is_none(),
"two thread positions share an end; library bug"
);
*entry = Some((thread, position));
}
incident.push(positions);
}
let ends = ends
.into_iter()
.map(|entry| entry.expect("every end lies on a permitted thread; library bug"))
.collect();
RibbonGraph { ends, incident }
}
fn position(&self, end: End) -> usize {
self.ends[slot(end)].1
}
fn node(&self, end: End) -> usize {
self.ends[slot(end)].0
}
pub(super) fn fundamental_cycles(&self) -> Vec<Cycle> {
let parent = self.spanning_tree();
let vertices = (self.ends.len() / 2) as u32;
(0..vertices)
.filter(|&vertex| {
parent[self.node((vertex, Sign::Minus))] != Some((vertex, Sign::Plus))
&& parent[self.node((vertex, Sign::Plus))] != Some((vertex, Sign::Minus))
})
.map(|vertex| self.close(&parent, vertex))
.collect()
}
fn spanning_tree(&self) -> Vec<Option<Step>> {
let mut parent = vec![None; self.incident.len()];
let mut seen = vec![false; self.incident.len()];
seen[0] = true;
let mut queue = vec![0];
let mut next = 0;
while let Some(&node) = queue.get(next) {
next += 1;
for &(vertex, sign) in &self.incident[node] {
let child = self.node((vertex, sign.negated()));
if !seen[child] {
seen[child] = true;
parent[child] = Some((vertex, sign));
queue.push(child);
}
}
}
assert!(
seen.iter().all(|&s| s),
"the ribbon graph is disconnected; library bug"
);
parent
}
fn close(&self, parent: &[Option<Step>], vertex: u32) -> Cycle {
let mut back = self.to_root(parent, self.node((vertex, Sign::Minus)));
let mut out = self.to_root(parent, self.node((vertex, Sign::Plus)));
while !back.is_empty() && back.last() == out.last() {
back.pop();
out.pop();
}
let mut steps = vec![(vertex, Sign::Plus)];
steps.extend(back);
steps.extend(out.iter().rev().map(|&(v, s)| (v, s.negated())));
Cycle(steps)
}
fn to_root(&self, parent: &[Option<Step>], mut node: usize) -> Vec<Step> {
let mut steps = Vec::new();
while let Some((vertex, sign)) = parent[node] {
steps.push((vertex, sign.negated()));
node = self.node((vertex, sign));
}
steps
}
fn turns(&self, cycle: &Cycle) -> Vec<(usize, End, End)> {
let steps = &cycle.0;
(0..steps.len())
.map(|index| {
let (vertex, sign) = steps[index];
let arrive = (vertex, sign.negated());
let leave = steps[(index + 1) % steps.len()];
assert_eq!(
self.node(arrive),
self.node(leave),
"a cycle step does not continue at its node; library bug"
);
(self.node(arrive), arrive, leave)
})
.collect()
}
pub(super) fn winding(&self, cycle: &Cycle) -> i64 {
self.turns(cycle)
.iter()
.map(|&(_, arrive, leave)| {
let (from, to) = (self.position(arrive), self.position(leave));
assert_ne!(from, to, "a cycle turns back on one end; library bug");
if to > from { 1 } else { -1 }
})
.sum()
}
pub(super) fn pairing(&self, cycles: &[Cycle]) -> Vec<Vec<i64>> {
let turns: Vec<_> = cycles.iter().map(|cycle| self.turns(cycle)).collect();
let size = cycles.len();
let mut matrix = vec![vec![0; size]; size];
for (row, left) in turns.iter().enumerate() {
for (column, right) in turns.iter().enumerate() {
if row != column {
matrix[row][column] = self.intersection(left, right);
}
}
}
let antisymmetric =
(0..size).all(|row| (0..row).all(|column| matrix[row][column] == -matrix[column][row]));
assert!(
antisymmetric,
"the intersection pairing is not antisymmetric; library bug"
);
matrix
}
fn intersection(&self, left: &[(usize, End, End)], right: &[(usize, End, End)]) -> i64 {
let mut total = 0;
for &(node, arrive, leave) in left {
let (a, b) = (self.centered(arrive), self.centered(leave));
for &(_, into, out) in right.iter().filter(|turn| turn.0 == node) {
total += crossing(a, b, self.shifted(into), self.shifted(out));
}
}
total
}
fn centered(&self, end: End) -> i64 {
2 * self.position(end) as i64
}
fn shifted(&self, end: End) -> i64 {
self.centered(end) + if end.1 == Sign::Plus { 1 } else { -1 }
}
}
fn crossing(a: i64, b: i64, c: i64, d: i64) -> i64 {
let inside = |x: i64| a.min(b) < x && x < a.max(b);
let direction = (b - a).signum();
match (inside(c), inside(d)) {
(true, false) => direction,
(false, true) => -direction,
_ => 0,
}
}
fn thread_ends(shape: &Shape, thread: &GentleThread) -> Vec<End> {
let mut ends: Vec<End> = thread
.arrows()
.iter()
.map(|&arrow| (shape.source(arrow), shape.sigma(arrow)))
.collect();
let last = match thread.arrows().last() {
Some(_) => thread.epsilon().negated(),
None => thread.sigma(),
};
ends.push((thread.end(), last));
ends
}
fn slot((vertex, sign): End) -> usize {
2 * vertex as usize + usize::from(sign == Sign::Minus)
}