use rustc_hash::FxHashMap;
use crate::quiver::Quiver;
use super::types::{DynkinType, EuclideanType};
pub(crate) fn reachable_count(neighbours: &[Vec<usize>], start: usize) -> usize {
if start >= neighbours.len() {
return 0;
}
let mut seen = vec![false; neighbours.len()];
let mut stack = vec![start];
seen[start] = true;
let mut count = 1;
while let Some(vertex) = stack.pop() {
for &next in &neighbours[vertex] {
if !seen[next] {
seen[next] = true;
count += 1;
stack.push(next);
}
}
}
count
}
pub fn dynkin_type(quiver: &Quiver) -> Option<DynkinType> {
dynkin_shape(tree(quiver)?.shape()?)
}
fn dynkin_shape(shape: Shape) -> Option<DynkinType> {
match shape {
Shape::Path(n) => Some(DynkinType::A(n)),
Shape::Star(arms) => dynkin_star(&arms),
Shape::DoubleFork { .. } => None,
}
}
fn dynkin_star(arms: &[usize]) -> Option<DynkinType> {
if let [1, 1, length] = arms {
return Some(DynkinType::D(length + 3));
}
[
([1, 2, 2], DynkinType::E6),
([1, 2, 3], DynkinType::E7),
([1, 2, 4], DynkinType::E8),
]
.iter()
.find_map(|(expected, kind)| (arms == expected).then_some(*kind))
}
enum EuclideanCase {
Reject,
MultipleEdge,
Cycle,
Tree,
}
fn euclidean_case(graph: &Underlying) -> EuclideanCase {
if !euclidean_candidate(graph) {
EuclideanCase::Reject
} else if graph.max_multiplicity() > 1 {
EuclideanCase::MultipleEdge
} else if graph.num_edges() == graph.num_vertices {
EuclideanCase::Cycle
} else {
EuclideanCase::Tree
}
}
fn euclidean_candidate(graph: &Underlying) -> bool {
graph.loops == 0 && graph.num_vertices > 0 && graph.is_connected()
}
fn multiple_edge_euclidean(graph: &Underlying) -> Option<EuclideanType> {
(graph.num_vertices == 2 && graph.multiplicity.len() == 1 && graph.num_edges() == 2)
.then_some(EuclideanType::A(1))
}
fn cycle_euclidean(graph: &Underlying) -> Option<EuclideanType> {
let n = graph.num_vertices;
let simple = graph.simple();
(n >= 3 && (0..n).all(|vertex| simple.degree(vertex) == 2)).then_some(EuclideanType::A(n - 1))
}
fn euclidean_tree_type(quiver: &Quiver) -> Option<EuclideanType> {
euclidean_tree_shape(tree(quiver)?.shape()?)
}
fn euclidean_tree_shape(shape: Shape) -> Option<EuclideanType> {
match shape {
Shape::Path(_) => None,
Shape::Star(arms) => euclidean_star(&arms),
Shape::DoubleFork { separation } => Some(EuclideanType::D(separation + 4)),
}
}
fn euclidean_star(arms: &[usize]) -> Option<EuclideanType> {
if arms == [1, 1, 1, 1] {
return Some(EuclideanType::D(4));
}
[
([2, 2, 2], EuclideanType::E6),
([1, 3, 3], EuclideanType::E7),
([1, 2, 5], EuclideanType::E8),
]
.iter()
.find_map(|(expected, kind)| (arms == expected).then_some(*kind))
}
pub fn euclidean_type(quiver: &Quiver) -> Option<EuclideanType> {
let graph = Underlying::of(quiver);
match euclidean_case(&graph) {
EuclideanCase::Reject => None,
EuclideanCase::MultipleEdge => multiple_edge_euclidean(&graph),
EuclideanCase::Cycle => cycle_euclidean(&graph),
EuclideanCase::Tree => euclidean_tree_type(quiver),
}
}
pub(crate) struct Underlying {
pub(crate) num_vertices: usize,
pub(crate) loops: usize,
pub(crate) multiplicity: FxHashMap<(usize, usize), usize>,
}
pub(crate) struct Simple {
pub(crate) neighbours: Vec<Vec<usize>>,
}
pub(crate) enum Shape {
Path(usize),
Star(Vec<usize>),
DoubleFork { separation: usize },
}
impl Underlying {
pub(crate) fn of(quiver: &Quiver) -> Underlying {
let mut loops = 0usize;
let mut multiplicity: FxHashMap<(usize, usize), usize> = FxHashMap::default();
for &(s, t) in quiver.arrows() {
let (u, v) = (s as usize, t as usize);
if u == v {
loops += 1;
} else {
*multiplicity.entry((u.min(v), u.max(v))).or_insert(0) += 1;
}
}
Underlying {
num_vertices: quiver.num_vertices() as usize,
loops,
multiplicity,
}
}
accessor_methods! {
num_edges() -> usize = |this| this.loops + this.multiplicity.values().sum::<usize>();
max_multiplicity() -> usize = |this| this.multiplicity.values().copied().max().unwrap_or(0);
simple() -> Simple = |this| {
let mut neighbours = vec![Vec::new(); this.num_vertices];
for &(u, v) in this.multiplicity.keys() {
neighbours[u].push(v);
neighbours[v].push(u);
}
for list in &mut neighbours {
list.sort_unstable();
}
Simple { neighbours }
};
}
fn is_connected(&self) -> bool {
self.num_vertices > 0 && reachable_count(&self.simple().neighbours, 0) == self.num_vertices
}
}
pub(crate) fn tree(quiver: &Quiver) -> Option<Simple> {
let graph = Underlying::of(quiver);
if graph.loops > 0 || graph.max_multiplicity() > 1 || graph.num_vertices == 0 {
return None;
}
if graph.num_edges() != graph.num_vertices - 1 || !graph.is_connected() {
return None;
}
Some(graph.simple())
}
impl Simple {
fn degree(&self, v: usize) -> usize {
self.neighbours[v].len()
}
fn arm(&self, center: usize, first: usize) -> (usize, usize) {
let mut previous = center;
let mut current = first;
let mut length = 1usize;
while self.degree(current) == 2 {
let next = if self.neighbours[current][0] == previous {
self.neighbours[current][1]
} else {
self.neighbours[current][0]
};
previous = current;
current = next;
length += 1;
}
(length, current)
}
fn shape(&self) -> Option<Shape> {
let n = self.neighbours.len();
let branch: Vec<usize> = (0..n).filter(|&v| self.degree(v) >= 3).collect();
match branch[..] {
[] => Some(Shape::Path(n)),
[center] => self.star_shape(center),
[first, second] => self.double_fork_shape(first, second),
_ => None,
}
}
fn star_shape(&self, center: usize) -> Option<Shape> {
if self.degree(center) > 4 {
return None;
}
let mut arms: Vec<usize> = self.neighbours[center]
.iter()
.map(|&neighbour| self.arm(center, neighbour).0)
.collect();
arms.sort_unstable();
Some(Shape::Star(arms))
}
fn fork_center(&self, center: usize, other: usize) -> Option<usize> {
if self.degree(center) != 3 {
return None;
}
let mut separation = None;
let mut leaves = 0;
for &neighbour in &self.neighbours[center] {
let (length, end) = self.arm(center, neighbour);
if end == other {
separation = Some(length);
} else if length == 1 {
leaves += 1;
} else {
return None;
}
}
(leaves == 2).then_some(separation).flatten()
}
fn double_fork_shape(&self, first: usize, second: usize) -> Option<Shape> {
let separation = self.fork_center(first, second)?;
let reverse = self.fork_center(second, first)?;
(separation == reverse).then_some(Shape::DoubleFork { separation })
}
}