graphs.rs

1use mrlycore::{Rng, Tensor};2use mrlymath::bang::factory::{corners_to_code, residue_corners};3use mrlynum::graph::core_graph;4use std::collections::HashMap;56pub struct Graph {7    pub adjacency: Vec<Vec<u32>>,8}910impl Graph {11    pub fn nodes(&self) -> usize {12        self.adjacency.len()13    }1415    pub fn edges(&self) -> usize {16        self.adjacency.iter().map(|row| row.len()).sum::<usize>() / 217    }1819    pub fn from_pairs(nodes: usize, pairs: &[(usize, usize)]) -> Graph {20        let mut adjacency = vec![Vec::new(); nodes];21        for (a, b) in pairs {22            adjacency[*a].push(*b as u32);23            adjacency[*b].push(*a as u32);24        }25        Graph { adjacency }26    }2728    pub fn of(grid: &Tensor) -> Graph {29        let network = core_graph(grid).expect("a grid has a core graph");30        let pairs: Vec<(usize, usize)> = network31            .branches32            .iter()33            .map(|b| (b.parent, b.child))34            .collect();35        Graph::from_pairs(network.nodes.len(), &pairs)36    }3738    pub fn components(&self) -> usize {39        let mut parent: Vec<usize> = (0..self.nodes()).collect();40        for (node, row) in self.adjacency.iter().enumerate() {41            for other in row {42                let (a, b) = (root(&mut parent, node), root(&mut parent, *other as usize));43                if a != b {44                    parent[a] = b;45                }46            }47        }48        (0..self.nodes())49            .filter(|node| root(&mut parent, *node) == *node)50            .count()51    }52}5354fn root(parent: &mut [usize], mut node: usize) -> usize {55    while parent[node] != node {56        parent[node] = parent[parent[node]];57        node = parent[node];58    }59    node60}6162pub fn carpet(level: usize) -> Graph {63    Graph::of(64        mrlymath::two::create(495, 3, level, 0, 3)65            .expect("the carpet renders")66            .types(),67    )68}6970pub fn sierpinski(level: usize) -> Graph {71    Graph::of(72        mrlymath::two::create(7, 2, level, 0, 2)73            .expect("the gasket renders")74            .types(),75    )76}7778fn sponge_code() -> u128 {79    let filled: Vec<Vec<u8>> = residue_corners(3, 3)80        .into_iter()81        .filter(|corner| corner.iter().filter(|digit| **digit == 1).count() <= 1)82        .collect();83    corners_to_code(&filled, 3, 3)84}8586pub fn sponge(level: usize) -> Graph {87    Graph::of(88        mrlymath::three::create(sponge_code(), 3, level, 3)89            .expect("the sponge renders")90            .types(),91    )92}9394pub fn square(side: usize) -> Graph {95    Graph::of(&Tensor::of(vec![1; side * side], vec![side, side]))96}9798pub fn random(nodes: usize, p: f64, seed: u64) -> Graph {99    let mut rng = Rng::new(seed);100    let mut pairs = Vec::new();101    for a in 0..nodes {102        for b in a + 1..nodes {103            if rng.chance(p) {104                pairs.push((a, b));105            }106        }107    }108    Graph::from_pairs(nodes, &pairs)109}110111type Point = [i32; 3];112type Triangle = [Point; 3];113114fn sponge_cell(mut cell: [usize; 3], level: usize) -> bool {115    for _ in 0..level {116        let ones = cell.iter().filter(|c| **c % 3 == 1).count();117        if ones > 1 {118            return false;119        }120        cell = [cell[0] / 3, cell[1] / 3, cell[2] / 3];121    }122    true123}124125fn cut_points(cell: [usize; 3], d: i32) -> Vec<Point> {126    let base = [2 * cell[0] as i32, 2 * cell[1] as i32, 2 * cell[2] as i32];127    let mut out = Vec::new();128    for axis in 0..3 {129        let others: Vec<usize> = (0..3).filter(|b| *b != axis).collect();130        for b1 in [0, 2] {131            for b2 in [0, 2] {132                if d - b1 - b2 == 1 {133                    let mut p = base;134                    p[axis] += 1;135                    p[others[0]] += b1;136                    p[others[1]] += b2;137                    out.push(p);138                }139            }140        }141    }142    out143}144145fn sorted(mut t: Triangle) -> Triangle {146    t.sort();147    t148}149150fn dist2(u: &Point, v: &Point) -> i32 {151    (0..3).map(|k| (u[k] - v[k]) * (u[k] - v[k])).sum()152}153154fn cell_pieces(cell: [usize; 3], d: i32) -> Vec<Triangle> {155    let pts = cut_points(cell, d);156    if pts.len() == 3 {157        return vec![sorted([pts[0], pts[1], pts[2]])];158    }159    let mid = [160        2 * cell[0] as i32 + 1,161        2 * cell[1] as i32 + 1,162        2 * cell[2] as i32 + 1,163    ];164    let mut out = Vec::new();165    for i in 0..pts.len() {166        for j in i + 1..pts.len() {167            if dist2(&pts[i], &pts[j]) == 2 {168                out.push(sorted([mid, pts[i], pts[j]]));169            }170        }171    }172    out173}174175pub fn slice(level: usize) -> Graph {176    let n = 3usize.pow(level as u32);177    let sigma = (3 * n - 1) / 2;178    let mut triangles: Vec<Triangle> = Vec::new();179    for i in 0..n {180        for j in 0..n {181            for s in [sigma - 2, sigma - 1, sigma] {182                if s < i + j || s - i - j >= n {183                    continue;184                }185                let cell = [i, j, s - i - j];186                if !sponge_cell(cell, level) {187                    continue;188                }189                triangles.extend(cell_pieces(cell, 3 * n as i32 - 2 * s as i32));190            }191        }192    }193    let mut owners: HashMap<(Point, Point), Vec<usize>> = HashMap::new();194    for (index, t) in triangles.iter().enumerate() {195        for (a, b) in [(0, 1), (0, 2), (1, 2)] {196            owners.entry((t[a], t[b])).or_default().push(index);197        }198    }199    let pairs: Vec<(usize, usize)> = owners200        .values()201        .filter(|o| o.len() == 2)202        .map(|o| (o[0], o[1]))203        .collect();204    Graph::from_pairs(triangles.len(), &pairs)205}