lssg_lib/sitetree/
relational_graph.rs

1use std::{
2    ops::{Index, IndexMut},
3};
4
5#[derive(Debug, Clone)]
6pub enum Relation {
7    /// from parent to child
8    Family,
9    External,
10    Discovered {
11        raw_path: String,
12    },
13}
14
15#[derive(Debug, Clone)]
16pub struct Link {
17    pub from: usize,
18    pub to: usize,
19    pub relation: Relation,
20}
21
22/// A directional graph that stores relationships between nodes
23#[derive(Debug)]
24pub struct RelationalGraph {
25    links: Vec<Vec<Link>>,
26}
27impl RelationalGraph {
28    pub fn new() -> Self {
29        RelationalGraph {
30            links: vec![vec![]],
31        }
32    }
33
34    pub fn add(&mut self, from: usize, to: usize, relation: Relation) {
35        // increase size if too short
36        let max = from.max(to);
37        if self.links.len() < max + 1 {
38            for _ in self.links.len()..max + 1 {
39                self.links.push(vec![]);
40            }
41        }
42
43        let link = Link { from, to, relation };
44        self[from].push(link.clone());
45        self[to].push(link.clone());
46    }
47
48    pub fn links_from(&self, node_id: usize) -> Vec<&Link> {
49        self.links[node_id]
50            .iter()
51            .filter(|l| l.from == node_id)
52            .collect()
53    }
54
55    pub fn get(&self, node_id: usize) -> &Vec<Link> {
56        self.links
57            .get(node_id)
58            .expect(&format!("{node_id} not found in rel graph"))
59    }
60
61    pub fn get_mut(&mut self, node_id: usize) -> &mut Vec<Link> {
62        self.links
63            .get_mut(node_id)
64            .expect(&format!("{node_id} not found in rel graph"))
65    }
66
67    pub fn remove(&mut self, from: usize, to: usize) {
68        let links = self.get_mut(from);
69        links.retain(|l| l.from == from && l.to == to);
70        let links = self.get_mut(to);
71        links.retain(|l| l.from == from && l.to == to);
72    }
73
74    /// remove all links to and from `node_id`
75    pub fn remove_all(&mut self, node_id: usize) {
76        // remove links pointing to node_id
77        for Link { from, to, .. } in self[node_id].clone() {
78            if from != node_id {
79                self[from].retain(|l| l.from == from && l.to == to);
80            }
81        }
82        self[node_id] = vec![];
83    }
84}
85
86impl Index<usize> for RelationalGraph {
87    type Output = Vec<Link>;
88
89    fn index(&self, index: usize) -> &Self::Output {
90        &self.links[index]
91    }
92}
93impl IndexMut<usize> for RelationalGraph {
94    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
95        &mut self.links[index]
96    }
97}
lssg_lib/sitetree/relational_graph.rs

lssg_lib/sitetree/
relational_graph.rs
