graph_base/interfaces/
graph.rs

1use std::{collections::HashMap, fmt::Display, hash::Hash};
2
3use super::vertex::Vertex;
4
5pub trait Graph<'a> {
6    type Node: Vertex;
7    type Edge: Eq + Hash + Clone + IdPair;
8    fn new() -> Self;
9    fn nodes(&'a self) -> impl Iterator<Item = &'a Self::Node>;
10    fn edges(&'a self) -> impl Iterator<Item = &'a Self::Edge>;
11    fn get_edges_pair(&'a self) -> impl Iterator<Item = (&'a Self::Node, &'a Self::Node)> {
12        let id_map: HashMap<_, _> = HashMap::from_iter(self.nodes().map(|node| (node.id(), node)));
13        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()
14    }
15    fn get_edges_pair_with_edge(&'a self) -> impl Iterator<Item = (&'a Self::Node, &'a Self::Edge, &'a Self::Node)> {
16        let id_map: HashMap<_, _> = HashMap::from_iter(self.nodes().map(|node| (node.id(), node)));
17        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()
18    }
19    fn add_node(&mut self, node: Self::Node);
20    fn add_edge(&mut self, edge: Self::Edge);
21}
22
23pub trait SingleId {
24    fn id(&self) -> usize;
25}
26
27pub trait IdPair {
28    fn pair(&self) -> (usize, usize);
29}
30
31pub trait Directed {}
32
33pub trait UnDirected {}
34
35pub struct AdjacencyList<'a, T: Graph<'a>>(HashMap<&'a T::Node, Vec<&'a T::Node>>);
36
37impl<'a, T> Display for AdjacencyList<'a, T> 
38where T: Graph<'a> {    
39    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
40        let mut s = String::new();
41        for (node, adj) in self.0.iter() {
42            
43            let s1 = format!("{}", node);
44            let mut s2 = String::new();
45            for node in adj {
46                s2.push_str(format!("{}, ", node).as_str());
47            }
48
49            s.push_str(format!("Node {} -> {{{}}}\n", s1, s2).as_str());
50        }
51        write!(f, "{}", s)
52    }
53}
54
55pub trait Adjacency<'a>: Graph<'a> + Directed + Sized {
56    fn get_adj(&'a self) -> AdjacencyList<'a, Self> {
57        let mut adj = HashMap::new();
58        for node in self.nodes() {
59            adj.insert(node, Vec::new());
60        }
61        for (src, dst) in self.get_edges_pair() {
62            adj.get_mut(src).unwrap().push(dst);
63        }
64
65        AdjacencyList(adj)
66    }
67    fn get_post(&'a self, adj: &AdjacencyList<'a, Self>, node: &Self::Node) -> impl Iterator<Item = &'a Self::Node> {
68        adj.0.get(node).expect(format!("No node in adjacency table named {} \n adj is: {}", node, adj).as_str()).iter().copied()
69    }
70}
71
72pub trait AdjacencyInv<'a>: Graph<'a> + Directed + Sized {
73    fn get_adj_inv(&'a self) -> AdjacencyList<'a, Self> {
74        let mut adj_inv = HashMap::new();
75        for node in self.nodes() {
76            adj_inv.insert(node, Vec::new());
77        }
78        for (src, dst) in self.get_edges_pair() {
79            adj_inv.get_mut(dst).unwrap().push(src);
80        }
81        AdjacencyList(adj_inv)
82    }
83    fn get_pre(&'a self, adj_inv: &AdjacencyList<'a, Self>, node: &Self::Node) -> impl Iterator<Item = &'a Self::Node> {
84        adj_inv.0.get(node).expect(format!("No node in adjacency table named {} \n adj is: {}", node, adj_inv).as_str()).iter().copied()
85    }
86}
87
88pub struct DegreeList<'a, T: Graph<'a>>(HashMap<&'a T::Node, usize>);
89
90pub trait Degree<'a>: Graph<'a> + Directed + Sized {
91    fn get_in_degree(&'a self) -> DegreeList<'a, Self> {
92        let mut in_degree = HashMap::new();
93        for node in self.nodes() {
94            in_degree.insert(node, 0);
95        }
96        for (_src, dst) in self.get_edges_pair() {
97            *in_degree.get_mut(dst).unwrap() += 1;
98        }
99        DegreeList(in_degree)
100    }
101
102    fn in_degree(&'a self, degree_list: &DegreeList<'a, Self>, node: &Self::Node) -> usize {
103        *degree_list.0.get(node).expect(format!("No node in degree table named {}", node).as_str())
104    }
105
106    fn get_out_degree(&'a self) -> DegreeList<'a, Self> {
107        let mut out_degree = HashMap::new();
108        for node in self.nodes() {
109            out_degree.insert(node, 0);
110        }
111        for (src, _dst) in self.get_edges_pair() {
112            *out_degree.get_mut(src).unwrap() += 1;
113        }
114        DegreeList(out_degree)
115    }
116
117    fn out_degree(&'a self, degree_list: &DegreeList<'a, Self>, node: &Self::Node) -> usize {
118        *degree_list.0.get(node).expect(format!("No node in degree table named {}", node).as_str())
119    }
120}
graph_base/interfaces/graph.rs

graph_base/interfaces/
graph.rs
