graph_simulation/graph/
base.rs

1use std::{collections::HashMap, fmt::Display, hash::Hash};
2
3pub trait Graph<'a> {
4    type Node: Eq + Hash + Clone + Sized + Display + SingleId;
5    type Edge: Eq + Hash + Clone + IdPair;
6    fn nodes(&'a self) -> impl Iterator<Item = &'a Self::Node>;
7    fn edges(&'a self) -> impl Iterator<Item = &'a Self::Edge>;
8    fn get_edges_pair(&'a self) -> impl Iterator<Item = (&'a Self::Node, &'a Self::Node)> {
9        let id_map: HashMap<_, _> = HashMap::from_iter(self.nodes().map(|node| (node.id(), node)));
10        self.edges().map(move |edge| (id_map.get(&edge.pair().0).unwrap().clone(), id_map.get(&edge.pair().1).unwrap().clone()) ).collect::<Vec<_>>().into_iter()
11    }
12    fn get_edges_pair_with_edge(&'a self) -> impl Iterator<Item = (&'a Self::Node, &'a Self::Edge, &'a Self::Node)> {
13        let id_map: HashMap<_, _> = HashMap::from_iter(self.nodes().map(|node| (node.id(), node)));
14        self.edges().map(move |edge| (id_map.get(&edge.pair().0).unwrap().clone(), edge, id_map.get(&edge.pair().1).unwrap().clone()) ).collect::<Vec<_>>().into_iter()
15    }
16    fn add_node(&mut self, node: Self::Node);
17    fn add_edge(&mut self, edge: Self::Edge);
18}
19
20pub trait SingleId {
21    fn id(&self) -> usize;
22}
23pub trait Label {
24    fn label(&self) -> &str;
25}
26
27pub trait IdPair {
28    fn pair(&self) -> (usize, usize);
29}
30
31pub trait Directed {}
32
33pub struct AdjacencyList<'a, T: Graph<'a>>(HashMap<&'a T::Node, Vec<&'a T::Node>>);
34
35impl<'a, T> Display for AdjacencyList<'a, T> 
36where T: Graph<'a> {    
37    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
38        let mut s = String::new();
39        for (node, adj) in self.0.iter() {
40            
41            let s1 = format!("{}", node);
42            let mut s2 = String::new();
43            for node in adj {
44                s2.push_str(format!("{}, ", node).as_str());
45            }
46
47            s.push_str(format!("Node {} -> {{{}}}\n", s1, s2).as_str());
48        }
49        write!(f, "{}", s)
50    }
51}
52
53pub trait Adjacency<'a>: Graph<'a> + Directed + Sized {
54    fn get_adj(&'a self) -> AdjacencyList<'a, Self> {
55        let mut adj = HashMap::new();
56        for node in self.nodes() {
57            adj.insert(node, Vec::new());
58        }
59        for (src, dst) in self.get_edges_pair() {
60            adj.get_mut(src).unwrap().push(dst);
61        }
62
63        AdjacencyList(adj)
64    }
65    fn get_post(&'a self, adj: &AdjacencyList<'a, Self>, node: &Self::Node) -> impl Iterator<Item = &'a Self::Node> {
66        adj.0.get(node).expect(format!("No node in adjacency table named {} \n adj is: {}", node, adj).as_str()).iter().copied()
67    }
68}
69
70pub trait AdjacencyInv<'a>: Graph<'a> + Directed + Sized {
71    fn get_adj_inv(&'a self) -> AdjacencyList<'a, Self> {
72        let mut adj_inv = HashMap::new();
73        for node in self.nodes() {
74            adj_inv.insert(node, Vec::new());
75        }
76        for (src, dst) in self.get_edges_pair() {
77            adj_inv.get_mut(dst).unwrap().push(src);
78        }
79        AdjacencyList(adj_inv)
80    }
81    fn get_pre(&'a self, adj_inv: &AdjacencyList<'a, Self>, node: &Self::Node) -> impl Iterator<Item = &'a Self::Node> {
82        adj_inv.0.get(node).expect(format!("No node in adjacency table named {} \n adj is: {}", node, adj_inv).as_str()).iter().copied()
83    }
84}
graph_simulation/graph/base.rs

graph_simulation/graph/
base.rs
