graph.rs

1use super::census::{corners, edges_of};2use super::models::Cell6d;3use super::{FILL, VOID};4use crate::core::errors::Result;5use crate::num::graph::models::Network;6use std::collections::BTreeMap;78type Point = (i64, i64);9type Edge = (Point, Point);1011fn centroid(c: &[Point; 3]) -> Vec<f64> {12    let xs: f64 = c.iter().map(|p| p.0 as f64).sum::<f64>() / 3.0;13    let ys: f64 = c.iter().map(|p| p.1 as f64).sum::<f64>() / 3.0;14    vec![xs, ys]15}1617fn adjacency_graph(cell: &Cell6d, keep: impl Fn(u8) -> bool) -> Result<Network> {18    let inner = &cell.cell;19    let start = cell.start as i64;20    let (height, width) = (inner.height(), inner.width());21    let mut cells = Vec::new();22    for y in 0..height {23        for x in 0..width {24            if keep(inner.types().get(&[y, x])) {25                cells.push((x as i64, y as i64));26            }27        }28    }29    let mut network = Network::new(2);30    for &(x, y) in &cells {31        network.add_node(centroid(&corners(x, y, start)))?;32    }33    let mut edge_to_cells: BTreeMap<Edge, Vec<usize>> = BTreeMap::new();34    for (i, &(x, y)) in cells.iter().enumerate() {35        for edge in edges_of(&corners(x, y, start)) {36            edge_to_cells.entry(edge).or_default().push(i);37        }38    }39    for shared in edge_to_cells.values() {40        if shared.len() == 2 {41            network.add_branch(shared[0], shared[1], 1.0)?;42        }43    }44    Ok(network)45}4647/// Builds the network of filled triangles joined by shared edges.48pub fn slice_core_graph(cell: &Cell6d) -> Result<Network> {49    adjacency_graph(cell, |v| v == FILL)50}5152/// Builds the network of fill and void triangles joined by shared edges.53pub fn slice_dual_graph(cell: &Cell6d) -> Result<Network> {54    adjacency_graph(cell, |v| v == FILL || v == VOID)55}5657/// Builds the corner-and-edge network of the triangles matching the value, or of every fill and void.58pub fn slice_edge_graph(cell: &Cell6d, value: Option<u8>) -> Result<Network> {59    let inner = &cell.cell;60    let start = cell.start as i64;61    let (height, width) = (inner.height(), inner.width());62    let keep = |v: u8| match value {63        Some(target) => v == target,64        None => v == FILL || v == VOID,65    };66    let mut corner_index: BTreeMap<Point, usize> = BTreeMap::new();67    let mut network = Network::new(2);68    let mut seen: BTreeMap<Edge, bool> = BTreeMap::new();69    for y in 0..height {70        for x in 0..width {71            if !keep(inner.types().get(&[y, x])) {72                continue;73            }74            let c = corners(x as i64, y as i64, start);75            for edge in edges_of(&c) {76                if seen.contains_key(&edge) {77                    continue;78                }79                seen.insert(edge, true);80                let mut node = |p: Point, network: &mut Network| -> Result<usize> {81                    if let Some(&i) = corner_index.get(&p) {82                        return Ok(i);83                    }84                    let i = network.add_node(vec![p.0 as f64, p.1 as f64])?;85                    corner_index.insert(p, i);86                    Ok(i)87                };88                let a = node(edge.0, &mut network)?;89                let b = node(edge.1, &mut network)?;90                network.add_branch(a, b, 1.0)?;91            }92        }93    }94    Ok(network)95}9697#[cfg(test)]98mod tests {99    use super::*;100    use crate::math::formulas::six as formulas;101    use crate::math::six::geometry::blank;102    use crate::math::six::{Orientation, Projection};103    fn solid(radius: usize) -> Cell6d {104        Cell6d::new(105            blank(106                radius,107                Orientation::Horizontal,108                FILL,109                crate::math::six::GRID,110            ),111            Projection::Cut,112            Orientation::Horizontal,113            0,114        )115    }116    #[test]117    fn solid_core_counts_are_pinned() {118        let expected = [(1, 6, 6), (2, 24, 27), (3, 54, 72)];119        for (radius, nodes, branches) in expected {120            let core = slice_core_graph(&solid(radius)).unwrap();121            assert_eq!(core.nodes.len(), nodes, "r={radius}");122            assert_eq!(core.branches.len(), branches, "r={radius}");123        }124        assert_eq!(125            slice_core_graph(&solid(3)).unwrap().branches.len() as u128,126            formulas::solid_slice_core_edges(3).unwrap()127        );128    }129    #[test]130    fn dual_contains_core() {131        let s = solid(2);132        let dual = slice_dual_graph(&s).unwrap();133        let core = slice_core_graph(&s).unwrap();134        assert!(dual.nodes.len() >= core.nodes.len());135        let edge = slice_edge_graph(&s, Some(FILL)).unwrap();136        assert!(!edge.nodes.is_empty());137    }138}