mod lerp;
pub use crate::lerp::Lerp;
use petgraph::visit::EdgeRef;
use petgraph::Undirected;
pub use petgraph::{Direction, Incoming, Outgoing};
use std::collections::hash_map::DefaultHasher;
use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher};
pub trait Position {
fn position(&self) -> [f32; 2];
}
pub trait IsBlank {
fn is_blank(&self) -> bool;
}
pub trait Weight {
fn weight(&self) -> u32;
}
pub trait Blanked {
fn blanked(&self) -> Self;
}
pub type PointIndex = u32;
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Segment {
pub start: PointIndex,
pub end: PointIndex,
pub kind: SegmentKind,
}
#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
pub enum SegmentKind {
Blank,
Lit,
}
pub type PointGraph = petgraph::Graph<PointIndex, (), Undirected, u32>;
pub type EulerGraph = petgraph::Graph<PointIndex, SegmentKind, Undirected, u32>;
pub type EulerCircuit = Vec<(EdgeIndex, Direction)>;
type EdgeIndex = petgraph::graph::EdgeIndex<u32>;
type NodeIndex = petgraph::graph::NodeIndex<u32>;
type Edge<E> = petgraph::graph::Edge<E, u32>;
type EgEdge = Edge<SegmentKind>;
#[derive(Clone)]
pub struct Segments<I>
where
I: Iterator,
{
points: I,
last: Option<I::Item>,
}
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct EdgeProfile {
start_weight: u32,
kind: EdgeProfileKind,
}
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum EdgeProfileKind {
Blank,
Lit { distance: f32, end_corner: f32 },
}
#[repr(C)]
#[derive(Clone, Debug, PartialEq)]
pub struct InterpolationConfig {
pub distance_per_point: f32,
pub blank_delay_points: u32,
pub radians_per_point: f32,
}
pub const BLANK_MIN_POINTS: u32 = 3;
impl InterpolationConfig {
pub const DEFAULT_DISTANCE_PER_POINT: f32 = 0.1;
pub const DEFAULT_BLANK_DELAY_POINTS: u32 = 10;
pub const DEFAULT_RADIANS_PER_POINT: f32 = 0.6;
}
impl EdgeProfile {
pub fn from_abc<P>(
points: &[P],
ab_kind: SegmentKind,
a_ix: PointIndex,
b_ix: PointIndex,
c: Option<PointIndex>,
) -> Self
where
P: Position + Weight,
{
let a = &points[a_ix as usize];
let start_weight = a.weight();
let kind = match ab_kind {
SegmentKind::Blank => EdgeProfileKind::Blank,
SegmentKind::Lit => {
let b = &points[b_ix as usize];
let a_pos = a.position();
let b_pos = b.position();
let distance = distance_squared(a_pos, b_pos).sqrt();
let end_corner = match c {
None => 0.0,
Some(c_ix) => {
let c = &points[c_ix as usize];
let c_pos = c.position();
straight_angle_variance(a_pos, b_pos, c_pos)
}
};
EdgeProfileKind::Lit {
distance,
end_corner,
}
}
};
EdgeProfile { start_weight, kind }
}
pub fn start_weight(&self) -> u32 {
self.start_weight
}
pub fn kind(&self) -> &EdgeProfileKind {
&self.kind
}
pub fn is_blank(&self) -> bool {
match self.kind {
EdgeProfileKind::Lit { .. } => false,
EdgeProfileKind::Blank => true,
}
}
pub fn is_lit(&self) -> bool {
match self.kind {
EdgeProfileKind::Lit { .. } => true,
EdgeProfileKind::Blank => false,
}
}
pub fn lit_distance(&self) -> f32 {
match self.kind {
EdgeProfileKind::Lit { distance, .. } => distance,
_ => 0.0,
}
}
pub fn min_points(&self, conf: &InterpolationConfig) -> u32 {
match self.kind {
EdgeProfileKind::Blank => {
blank_segment_point_count(self.start_weight, conf.blank_delay_points)
}
EdgeProfileKind::Lit {
distance,
end_corner,
} => lit_segment_min_point_count(
distance,
end_corner,
conf.distance_per_point,
conf.radians_per_point,
self.start_weight,
),
}
}
pub fn points<P, R>(
&self,
points: &[P],
a_ix: PointIndex,
b_ix: PointIndex,
conf: &InterpolationConfig,
excess_points: u32,
) -> Vec<R>
where
P: Clone + Into<R> + Position + Weight,
R: Blanked + Clone + Lerp<Scalar = f32>,
{
let a = points[a_ix as usize].clone();
let b = points[b_ix as usize].clone();
let br: R = b.into();
match self.kind {
EdgeProfileKind::Blank => {
blank_segment_points(a, br, conf.blank_delay_points).collect()
}
EdgeProfileKind::Lit {
end_corner,
distance,
} => {
let dist_point_count = distance_min_point_count(distance, conf.distance_per_point);
let corner_point_count = corner_point_count(end_corner, conf.radians_per_point);
lit_segment_points(a, br, corner_point_count, dist_point_count, excess_points)
.collect()
}
}
}
}
impl<'a, T> Position for &'a T
where
T: Position,
{
fn position(&self) -> [f32; 2] {
(**self).position()
}
}
impl<'a, T> IsBlank for &'a T
where
T: IsBlank,
{
fn is_blank(&self) -> bool {
(**self).is_blank()
}
}
impl<'a, T> Weight for &'a T
where
T: Weight,
{
fn weight(&self) -> u32 {
(**self).weight()
}
}
impl Position for [f32; 2] {
fn position(&self) -> [f32; 2] {
self.clone()
}
}
impl Default for InterpolationConfig {
fn default() -> Self {
Self {
distance_per_point: Self::DEFAULT_DISTANCE_PER_POINT,
blank_delay_points: Self::DEFAULT_BLANK_DELAY_POINTS,
radians_per_point: Self::DEFAULT_RADIANS_PER_POINT,
}
}
}
impl<I, P> Iterator for Segments<I>
where
I: Iterator<Item = (PointIndex, P)>,
P: Clone + IsBlank + Position,
{
type Item = Segment;
fn next(&mut self) -> Option<Self::Item> {
while let Some((end_ix, end)) = self.points.next() {
let (start_ix, start) = match self.last.replace((end_ix, end.clone())) {
None => continue,
Some(last) => last,
};
let kind = if start.position() == end.position() {
if !start.is_blank() && !end.is_blank() {
SegmentKind::Lit
} else {
continue;
}
} else if start.is_blank() && end.is_blank() {
SegmentKind::Blank
} else {
SegmentKind::Lit
};
let start = start_ix;
let end = end_ix;
return Some(Segment { start, end, kind });
}
None
}
}
pub fn points_to_segments<I>(points: I) -> impl Iterator<Item = Segment>
where
I: IntoIterator,
I::Item: Clone + IsBlank + Position,
{
let points = points
.into_iter()
.enumerate()
.map(|(i, p)| (i as PointIndex, p));
let last = None;
Segments { points, last }
}
pub fn segments_to_point_graph<P, I>(points: &[P], segments: I) -> PointGraph
where
P: Hash + Weight,
I: IntoIterator<Item = Segment>,
{
struct Node {
ix: NodeIndex,
weight: u32,
}
fn point_hash<P: Hash>(p: &P) -> u64 {
let mut hasher = DefaultHasher::new();
p.hash(&mut hasher);
hasher.finish()
}
let mut g = PointGraph::default();
let mut pt_to_id = HashMap::new();
let mut segments = segments.into_iter().peekable();
let mut prev_seg_kind = None;
while let Some(seg) = segments.next() {
let prev_kind = prev_seg_kind;
prev_seg_kind = Some(seg.kind);
if let SegmentKind::Blank = seg.kind {
continue;
}
let pa = &points[seg.start as usize];
let pb = &points[seg.end as usize];
let ha = point_hash(&pa);
let hb = point_hash(&pb);
let na = {
let n = pt_to_id.entry(ha).or_insert_with(|| {
let ix = g.add_node(seg.start);
let weight = pa.weight();
Node { ix, weight }
});
n.weight = std::cmp::max(n.weight, pa.weight());
n.ix
};
let nb = {
let n = pt_to_id.entry(hb).or_insert_with(|| {
let ix = g.add_node(seg.end);
let weight = pb.weight();
Node { ix, weight }
});
n.weight = std::cmp::max(n.weight, pb.weight());
n.ix
};
if na == nb {
let prev_edge_lit = match prev_kind {
Some(SegmentKind::Lit) => true,
_ => false,
};
let mut next_edge_lit = || match segments.peek() {
Some(s) if s.kind == SegmentKind::Lit => true,
_ => false,
};
if prev_edge_lit || next_edge_lit() {
continue;
}
}
if g.find_edge(na, nb).is_none() {
g.add_edge(na, nb, ());
}
}
g
}
pub fn point_graph_to_euler_graph(pg: &PointGraph) -> EulerGraph {
let ccs = petgraph::algo::kosaraju_scc(pg);
fn edge_is_loop<E>(e: &E) -> bool
where
E: EdgeRef,
E::NodeId: PartialEq,
{
e.source() == e.target()
}
fn node_has_even_degree(pg: &PointGraph, n: NodeIndex) -> bool {
let non_loop_edges = pg.edges(n).filter(|e| !edge_is_loop(e)).count();
non_loop_edges % 2 == 0
}
let euler_components: HashSet<_> = ccs
.iter()
.enumerate()
.filter(|(_, cc)| cc.iter().all(|&n| node_has_even_degree(pg, n)))
.map(|(i, _)| i)
.collect();
struct ToConnect {
prev: NodeIndex,
inner: Vec<NodeIndex>,
next: NodeIndex,
}
let mut to_connect = vec![];
for (i, cc) in ccs.iter().enumerate() {
if euler_components.contains(&i) {
let n = cc[0];
to_connect.push(ToConnect {
prev: n,
inner: vec![],
next: n,
});
} else {
let v: Vec<_> = cc
.iter()
.filter(|&&n| !node_has_even_degree(pg, n))
.collect();
if v.len() == 1 {
let p = *v[0];
let prev = p;
let inner = vec![];
let next = p;
to_connect.push(ToConnect { prev, inner, next });
continue;
} else {
assert_eq!(
v.len() % 2,
0,
"expected even number of odd-degree nodes for non-Euler component, found {}",
v.len(),
);
let prev = *v[0];
let inner = v[1..v.len() - 1].iter().map(|&&n| n).collect();
let next = *v[v.len() - 1];
to_connect.push(ToConnect { prev, inner, next });
}
}
}
let mut pairs = vec![];
let mut iter = to_connect.iter().enumerate().peekable();
while let Some((i, this)) = iter.next() {
for ch in this.inner.chunks(2) {
pairs.push((ch[0], ch[1]));
}
match iter.peek() {
Some((_, next)) => pairs.push((this.next, next.prev)),
None if i > 0 => pairs.push((this.next, to_connect[0].prev)),
None => match euler_components.contains(&0) {
true => (),
false => pairs.push((this.next, this.prev)),
},
}
}
let mut eg = pg.map(|_n_ix, n| n.clone(), |_e_ix, _| SegmentKind::Lit);
for (na, nb) in pairs {
eg.add_edge(na, nb, SegmentKind::Blank);
}
eg
}
pub fn ec_edge_start(eg: &EulerGraph, e: EdgeIndex, d: Direction) -> NodeIndex {
fn edge_start(edge: &EgEdge, d: Direction) -> NodeIndex {
match d {
Outgoing => edge.source(),
Incoming => edge.target(),
}
}
edge_start(&eg.raw_edges()[e.index()], d)
}
pub fn ec_edge_end(eg: &EulerGraph, e: EdgeIndex, d: Direction) -> NodeIndex {
fn edge_end(edge: &EgEdge, d: Direction) -> NodeIndex {
match d {
Outgoing => edge.target(),
Incoming => edge.source(),
}
}
edge_end(&eg.raw_edges()[e.index()], d)
}
pub fn euler_graph_to_euler_circuit<P>(points: &[P], eg: &EulerGraph) -> EulerCircuit
where
P: Position,
{
if eg.node_count() == 0 || eg.node_count() == 1 {
return vec![];
}
let start_n = eg
.node_indices()
.next()
.expect("expected at least two nodes, found none");
let mut visited: HashSet<EdgeIndex> = HashSet::new();
let mut visit_order: Vec<(EdgeIndex, Direction)> = vec![];
loop {
let (merge_ix, n) = match visit_order.is_empty() {
true => (0, start_n),
false => {
match visit_order
.iter()
.map(|&(e, dir)| ec_edge_start(eg, e, dir))
.enumerate()
.find(|&(_i, n)| eg.edges(n).any(|e| !visited.contains(&e.id())))
{
Some(n) => n,
None => break,
}
}
};
let traversal = traverse_unvisited(points, n, eg, &mut visited);
let new_visit_order = visit_order
.iter()
.take(merge_ix)
.cloned()
.chain(traversal)
.chain(visit_order.iter().skip(merge_ix).cloned())
.collect();
visit_order = new_visit_order;
}
visit_order
}
fn traverse_unvisited<P>(
points: &[P],
start: NodeIndex,
eg: &EulerGraph,
visited: &mut HashSet<EdgeIndex>,
) -> Vec<(EdgeIndex, Direction)>
where
P: Position,
{
let mut n = start;
let mut traversal: Vec<(EdgeIndex, Direction)> = vec![];
loop {
let e_ref = {
let mut untraversed_edges = eg
.edges_directed(n, Outgoing)
.filter(|e_ref| !visited.contains(&e_ref.id()));
let init_e_ref = untraversed_edges
.next()
.expect("expected a strongly connected euler graph");
match traversal
.last()
.map(|&(e, dir)| ec_edge_start(eg, e, dir))
.map(|n| points[eg[n] as usize].position())
{
None => init_e_ref,
Some(prev_source_p) => {
let source_p = points[eg[init_e_ref.source()] as usize].position();
let target_p = points[eg[init_e_ref.target()] as usize].position();
let init_dist = straight_angle_variance(prev_source_p, source_p, target_p);
let init = (init_e_ref, init_dist);
let (e_ref, _) = untraversed_edges.fold(init, |best, e_ref| {
let (_, best_dist) = best;
let target_p = points[eg[e_ref.target()] as usize].position();
let dist = straight_angle_variance(prev_source_p, source_p, target_p);
if dist < best_dist {
(e_ref, dist)
} else {
best
}
});
e_ref
}
}
};
let e = e_ref.id();
let dir = if n == eg.raw_edges()[e.index()].source() {
Direction::Outgoing
} else {
Direction::Incoming
};
n = e_ref.target();
visited.insert(e);
traversal.push((e, dir));
if e_ref.target() == start {
break;
}
}
traversal
}
fn straight_angle_variance([ax, ay]: [f32; 2], [bx, by]: [f32; 2], [cx, cy]: [f32; 2]) -> f32 {
let [ux, uy] = [bx - ax, by - ay];
let [vx, vy] = [cx - bx, cy - by];
let ur = uy.atan2(ux);
let vr = vy.atan2(vx);
let diff_rad = vr - ur;
fn angular_dist(rad: f32) -> f32 {
let rad = rad.abs();
if rad > std::f32::consts::PI {
-rad + std::f32::consts::PI * 2.0
} else {
rad
}
}
angular_dist(diff_rad)
}
fn distance_squared(a: [f32; 2], b: [f32; 2]) -> f32 {
let [ax, ay] = a;
let [bx, by] = b;
let [abx, aby] = [bx - ax, by - ay];
abx * abx + aby * aby
}
pub fn blank_segment_point_count(a_weight: u32, blank_delay_points: u32) -> u32 {
a_weight + BLANK_MIN_POINTS + blank_delay_points
}
pub fn blank_segment_points<A, B>(a: A, br: B, blank_delay_points: u32) -> impl Iterator<Item = B>
where
A: Into<B> + Weight,
B: Blanked + Clone,
{
let a_weight = a.weight();
let ar: B = a.into();
let ar_blanked = ar.blanked();
let br_blanked = br.blanked();
Some(ar.clone())
.into_iter()
.chain((0..a_weight).map(move |_| ar.clone()))
.chain(Some(ar_blanked))
.chain(Some(br_blanked.clone()))
.chain((0..blank_delay_points).map(move |_| br_blanked.clone()))
}
pub fn corner_point_count(rad: f32, corner_delay_radians_per_point: f32) -> u32 {
(rad / corner_delay_radians_per_point) as _
}
pub fn distance_min_point_count(dist: f32, min_distance_per_point: f32) -> u32 {
const MIN_COUNT: u32 = 1;
MIN_COUNT + (dist * min_distance_per_point) as u32
}
pub fn lit_segment_min_point_count(
distance: f32,
end_corner_radians: f32,
distance_per_point: f32,
radians_per_point: f32,
start_weight: u32,
) -> u32 {
start_weight
+ corner_point_count(end_corner_radians, radians_per_point)
+ distance_min_point_count(distance, distance_per_point)
}
pub fn lit_segment_points<A, B>(
a: A,
br: B,
corner_point_count: u32,
distance_min_point_count: u32,
excess_points: u32,
) -> impl Iterator<Item = B>
where
A: Into<B> + Weight,
B: Clone + Lerp<Scalar = f32>,
{
let dist_point_count = distance_min_point_count + excess_points;
let a_weight = a.weight();
let ar: B = a.into();
let ar2 = ar.clone();
let br2 = br.clone();
let weight_points = (0..a_weight).map(move |_| ar.clone());
let dist_points = (0..dist_point_count).map(move |i| {
let lerp_amt = i as f32 / dist_point_count as f32;
ar2.clone().lerp(&br2.clone(), lerp_amt)
});
let corner_points = (0..corner_point_count).map(move |_| br.clone());
weight_points.chain(dist_points).chain(corner_points)
}
pub fn profile_path<'a, P, E>(
points: &'a [P],
edges: E,
) -> impl 'a + Iterator<Item = (EdgeProfile, PointIndex, PointIndex)>
where
P: Position + Weight,
E: 'a + IntoIterator<Item = Segment>,
{
let mut iter = edges.into_iter();
let mut ab = iter.next();
let first = ab;
std::iter::from_fn(move || {
let bc = iter.next();
let profile = ab.take().map(|ab| {
let (a, b) = (ab.start, ab.end);
let c = bc
.map(|bc| bc.end)
.or_else(|| first.and_then(|f| if f.start == b { Some(f.end) } else { None }));
let ab_prof = EdgeProfile::from_abc(points, ab.kind, a, b, c);
(ab_prof, a, b)
});
ab = bc;
profile
})
}
pub fn interpolate_profiled_path<'a, P, R>(
points: &'a [P],
edges: &[(EdgeProfile, PointIndex, PointIndex)],
target_points: u32,
conf: &'a InterpolationConfig,
output_points: &mut Vec<R>,
) where
P: Clone + Into<R> + Position + Weight,
R: Blanked + Clone + Lerp<Scalar = f32>,
{
if points.is_empty() || edges.is_empty() || edges.iter().all(|&(e, _, _)| e.is_blank()) {
return;
}
let min_points = edges
.iter()
.fold(0, |acc, &(e, _, _)| acc + e.min_points(conf));
let target_points_minus_last = target_points - 1;
let edge_excess_point_counts = if min_points < target_points_minus_last {
let excess_points = target_points_minus_last - min_points;
let edge_lit_dists = edges
.iter()
.map(|&(e, _, _)| (e.is_lit(), e.lit_distance()))
.collect::<Vec<_>>();
let total_lit_dist = edge_lit_dists.iter().fold(0.0, |acc, &(_, d)| acc + d);
let edge_weights: Vec<(bool, f32)> = match total_lit_dist <= std::f32::EPSILON {
true => {
let n_lit_edges = edge_lit_dists.iter().filter(|&&(b, _)| b).count();
edge_lit_dists
.iter()
.map(|&(is_lit, _)| (is_lit, 1.0 / n_lit_edges as f32))
.collect()
}
false => {
edge_lit_dists
.iter()
.map(|&(is_lit, dist)| (is_lit, dist / total_lit_dist))
.collect()
}
};
let mut v = Vec::with_capacity(edges.len());
let mut err = 0.0;
let mut count = 0;
for (is_lit, w) in edge_weights {
if !is_lit {
v.push(0);
continue;
}
let nf = w * excess_points as f32 + err;
err = nf.fract();
let n = nf as u32;
count += n;
v.push(n);
}
if count == (excess_points - 1) {
let (i, _) = edges
.iter()
.enumerate()
.find(|&(_, &(e, _, _))| e.is_lit())
.expect("expected at least one lit edge");
v[i] += 1;
count += 1;
}
debug_assert_eq!(count, excess_points);
v
} else {
vec![0; edges.len()]
};
for (&(prof, a_ix, b_ix), &excess) in edges.iter().zip(&edge_excess_point_counts) {
output_points.extend(prof.points(points, a_ix, b_ix, conf, excess));
}
let last_point = points[edges.last().unwrap().2 as usize].clone().into();
output_points.push(last_point);
let total_points = std::cmp::max(min_points, target_points);
debug_assert!(output_points.len() >= target_points as usize);
debug_assert!(total_points >= target_points);
}
pub fn interpolate_path<'a, P, E, R>(
points: &'a [P],
edges: E,
target_points: u32,
conf: &'a InterpolationConfig,
output_points: &mut Vec<R>,
) where
P: Clone + Into<R> + Position + Weight,
E: IntoIterator<Item = Segment>,
R: Blanked + Clone + Lerp<Scalar = f32>,
{
let profiled_edges: Vec<_> = profile_path(points, edges).collect();
interpolate_profiled_path(points, &profiled_edges, target_points, conf, output_points);
}
pub fn euler_circuit_to_segments<'a>(
ec: &'a EulerCircuit,
eg: &'a EulerGraph,
) -> impl 'a + Iterator<Item = Segment> {
ec.iter().map(move |&(e_ix, e_dir)| {
let kind = eg[e_ix];
let start = eg[ec_edge_start(eg, e_ix, e_dir)];
let end = eg[ec_edge_end(eg, e_ix, e_dir)];
Segment { kind, start, end }
})
}
pub fn interpolate_euler_circuit<P, R>(
points: &[P],
ec: &EulerCircuit,
eg: &EulerGraph,
target_points: u32,
conf: &InterpolationConfig,
) -> Vec<R>
where
P: Clone + Into<R> + Position + Weight,
R: Blanked + Clone + Lerp<Scalar = f32>,
{
let edges = euler_circuit_to_segments(ec, eg);
let mut output_points = vec![];
interpolate_path(points, edges, target_points, conf, &mut output_points);
output_points
}
#[cfg(test)]
mod test {
use super::{
euler_graph_to_euler_circuit, point_graph_to_euler_graph, points_to_segments,
segments_to_point_graph,
};
use super::{EulerGraph, Outgoing, PointGraph, SegmentKind};
use crate::{Blanked, IsBlank, Position, Weight};
use std::collections::HashSet;
use std::hash::{Hash, Hasher};
#[derive(Copy, Clone, Debug, PartialEq)]
struct Point {
position: [f32; 2],
rgb: [f32; 3],
weight: u32,
}
#[derive(Eq, Hash, PartialEq)]
struct HashPoint {
pos: [i32; 2],
rgb: [u32; 3],
}
#[derive(Copy, Clone, Debug, PartialEq)]
struct RawPoint {
position: [f32; 2],
rgb: [f32; 3],
}
impl From<Point> for HashPoint {
fn from(p: Point) -> Self {
let [px, py] = p.position;
let [pr, pg, pb] = p.rgb;
let x = (px * std::i16::MAX as f32) as i32;
let y = (py * std::i16::MAX as f32) as i32;
let r = (pr * std::u16::MAX as f32) as u32;
let g = (pg * std::u16::MAX as f32) as u32;
let b = (pb * std::u16::MAX as f32) as u32;
let pos = [x, y];
let rgb = [r, g, b];
HashPoint { pos, rgb }
}
}
impl Blanked for RawPoint {
fn blanked(&self) -> Self {
RawPoint {
position: self.position,
rgb: [0.0; 3],
}
}
}
impl Hash for Point {
fn hash<H: Hasher>(&self, hasher: &mut H) {
HashPoint::from(self.clone()).hash(hasher)
}
}
impl IsBlank for Point {
fn is_blank(&self) -> bool {
self.rgb == [0.0; 3]
}
}
impl Position for Point {
fn position(&self) -> [f32; 2] {
self.position
}
}
impl Position for RawPoint {
fn position(&self) -> [f32; 2] {
self.position
}
}
impl Weight for Point {
fn weight(&self) -> u32 {
self.weight
}
}
fn graph_eq<N, E, Ty, Ix>(
a: &petgraph::Graph<N, E, Ty, Ix>,
b: &petgraph::Graph<N, E, Ty, Ix>,
) -> bool
where
N: PartialEq,
E: PartialEq,
Ty: petgraph::EdgeType,
Ix: petgraph::graph::IndexType + PartialEq,
{
let a_ns = a.raw_nodes().iter().map(|n| &n.weight);
let b_ns = b.raw_nodes().iter().map(|n| &n.weight);
let a_es = a
.raw_edges()
.iter()
.map(|e| (e.source(), e.target(), &e.weight));
let b_es = b
.raw_edges()
.iter()
.map(|e| (e.source(), e.target(), &e.weight));
a_ns.eq(b_ns) && a_es.eq(b_es)
}
fn is_euler_graph<N, E, Ty, Ix>(g: &petgraph::Graph<N, E, Ty, Ix>) -> bool
where
Ty: petgraph::EdgeType,
Ix: petgraph::graph::IndexType,
{
let even_degree = g.node_indices().all(|n| g.edges(n).count() % 2 == 0);
let strongly_connected = petgraph::algo::kosaraju_scc(g).len() == 1;
even_degree && strongly_connected
}
fn white_pt(position: [f32; 2]) -> Point {
Point {
position,
rgb: [1.0; 3],
weight: 0,
}
}
fn blank_pt(position: [f32; 2]) -> Point {
Point {
position,
rgb: [0.0; 3],
weight: 0,
}
}
fn square_pts() -> [Point; 5] {
let a = white_pt([-1.0, -1.0]);
let b = white_pt([-1.0, 1.0]);
let c = white_pt([1.0, 1.0]);
let d = white_pt([1.0, -1.0]);
[a, b, c, d, a]
}
fn two_vertical_lines_pts() -> [Point; 8] {
let a = [-1.0, -1.0];
let b = [-1.0, 1.0];
let c = [1.0, -1.0];
let d = [1.0, 1.0];
[
white_pt(a),
white_pt(b),
blank_pt(b),
blank_pt(c),
white_pt(c),
white_pt(d),
blank_pt(d),
blank_pt(a),
]
}
#[test]
fn test_points_to_point_graph_no_blanks() {
let pts = square_pts();
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let mut expected = PointGraph::default();
let na = expected.add_node(0);
let nb = expected.add_node(1);
let nc = expected.add_node(2);
let nd = expected.add_node(3);
expected.add_edge(na, nb, ());
expected.add_edge(nb, nc, ());
expected.add_edge(nc, nd, ());
expected.add_edge(nd, na, ());
assert!(graph_eq(&pg, &expected));
}
#[test]
fn test_points_to_point_graph_with_blanks() {
let pts = two_vertical_lines_pts();
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let mut expected = PointGraph::default();
let na = expected.add_node(0);
let nb = expected.add_node(1);
let nc = expected.add_node(4);
let nd = expected.add_node(5);
expected.add_edge(na, nb, ());
expected.add_edge(nc, nd, ());
assert!(graph_eq(&pg, &expected));
}
#[test]
fn test_point_graph_to_euler_graph_no_blanks() {
let pts = square_pts();
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let eg = point_graph_to_euler_graph(&pg);
let mut expected = EulerGraph::default();
let na = expected.add_node(0);
let nb = expected.add_node(1);
let nc = expected.add_node(2);
let nd = expected.add_node(3);
expected.add_edge(na, nb, SegmentKind::Lit);
expected.add_edge(nb, nc, SegmentKind::Lit);
expected.add_edge(nc, nd, SegmentKind::Lit);
expected.add_edge(nd, na, SegmentKind::Lit);
assert!(graph_eq(&eg, &expected));
}
#[test]
fn test_point_graph_to_euler_graph_with_blanks() {
let pts = two_vertical_lines_pts();
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let eg = point_graph_to_euler_graph(&pg);
assert!(is_euler_graph(&eg));
let pg_ns: Vec<_> = pg.raw_nodes().iter().map(|n| n.weight).collect();
let eg_ns: Vec<_> = eg.raw_nodes().iter().map(|n| n.weight).collect();
assert_eq!(pg_ns, eg_ns);
assert_eq!(
eg.raw_edges()
.iter()
.filter(|e| e.weight == SegmentKind::Blank)
.count(),
2
);
assert_eq!(
eg.raw_edges()
.iter()
.filter(|e| e.weight == SegmentKind::Lit)
.count(),
2
);
}
#[test]
fn test_euler_graph_to_euler_circuit_no_blanks() {
let pts = square_pts();
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let eg = point_graph_to_euler_graph(&pg);
let ec = euler_graph_to_euler_circuit(&pts, &eg);
let mut ns = eg.node_indices();
let na = ns.next().unwrap();
let nb = ns.next().unwrap();
let nc = ns.next().unwrap();
let nd = ns.next().unwrap();
let expected = vec![
(eg.find_edge(na, nb).unwrap(), Outgoing),
(eg.find_edge(nb, nc).unwrap(), Outgoing),
(eg.find_edge(nc, nd).unwrap(), Outgoing),
(eg.find_edge(nd, na).unwrap(), Outgoing),
];
assert_eq!(ec, expected);
}
#[test]
fn test_euler_graph_to_euler_circuit_with_blanks() {
let pts = two_vertical_lines_pts();
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let eg = point_graph_to_euler_graph(&pg);
let ec = euler_graph_to_euler_circuit(&pts, &eg);
assert_eq!(ec.len(), eg.edge_count());
let mut visited = HashSet::new();
let mut walk = ec
.iter()
.cycle()
.map(|&(e, _)| (e, &eg.raw_edges()[e.index()]));
while visited.len() < 4 {
let (e_id, _) = walk.next().unwrap();
assert!(visited.insert(e_id));
}
}
#[test]
fn test_euler_circuit_duplicate_points() {
let pts = [white_pt([0., 0.]), white_pt([0., 1.]), white_pt([0., 1.])];
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let eg = point_graph_to_euler_graph(&dbg!(pg));
let _ = euler_graph_to_euler_circuit(&pts, &dbg!(eg));
}
#[test]
fn test_single_point() {
let pts = [white_pt([0., 0.]), white_pt([0., 0.])];
let segs = points_to_segments(pts.iter().cloned());
let pg = segments_to_point_graph(&pts, segs);
let eg = point_graph_to_euler_graph(&dbg!(pg));
let ec = euler_graph_to_euler_circuit(&pts, &dbg!(eg));
assert_eq!(ec.len(), 0);
}
}