grafos_tools/
simple_graph.rs

1use crate::{
2    adjacency_list::{AdjacencyList, ToAdjacencyList},
3    Graph, SymmetricEdge, Vertice,
4};
5use std::{collections::HashSet, fmt::Debug, hash::Hash};
6
7// GRAPH
8pub struct SimpleGraph<T: PartialOrd + Debug> {
9    vertices: HashSet<Vertice<T>>,
10    edges: HashSet<SymmetricEdge<T>>, // this graph uses symmetric edges
11}
12
13impl SimpleGraph<usize> {
14    // GENERATORS
15    pub fn new() -> Self {
16        Self {
17            vertices: HashSet::new(),
18            edges: HashSet::new(),
19        }
20    }
21
22    pub fn new_two() -> Self {
23        Self {
24            vertices: HashSet::from([Vertice(0), Vertice(1)]),
25            edges: HashSet::from([SymmetricEdge::new(Vertice(0), Vertice(1))]),
26        }
27    }
28
29    pub fn new_star() -> Self {
30        let mut vertices = HashSet::new();
31        let mut edges = HashSet::new();
32
33        for i in 0..5 {
34            vertices.insert(Vertice(i));
35            for vertice in &vertices {
36                if vertice.0 != i {
37                    edges.insert(SymmetricEdge::new(vertice.clone(), Vertice(i)));
38                }
39            }
40        }
41
42        Self { vertices, edges }
43    }
44}
45
46impl<T> Graph<T, SymmetricEdge<T>> for SimpleGraph<T>
47where
48    T: Eq + PartialOrd + Hash + Debug,
49{
50    fn edges(&self) -> &HashSet<SymmetricEdge<T>> {
51        &self.edges
52    }
53
54    fn vertices(&self) -> &HashSet<Vertice<T>> {
55        &self.vertices
56    }
57
58    fn add_vertice(&mut self, vertice: Vertice<T>) {
59        self.vertices.insert(vertice);
60    }
61}
62
63impl<T: PartialOrd + Debug> ToAdjacencyList<T> for SimpleGraph<T>
64where
65    T: Eq + PartialOrd + Hash + Clone,
66{
67    fn to_adjacency_list(&self) -> AdjacencyList<T> {
68        let mut list = AdjacencyList::new();
69        self.edges()
70            .iter()
71            .for_each(|edge| list.insert_with_edge(edge));
72        list
73    }
74}
75
76// TESTS
77#[cfg(test)]
78mod tests {
79    use crate::{adjacency_list::AdjacencyList, Edge};
80
81    use super::*;
82
83    // TEST GRAPHS
84    #[test]
85    fn create_simple_graph() {
86        let graph = SimpleGraph::new();
87
88        assert_eq!(graph.vertices.len(), 0);
89        assert_eq!(graph.vertices.len(), 0);
90    }
91
92    #[test]
93    fn create_simple_graph_star() {
94        let graph = SimpleGraph::new_star();
95
96        assert_eq!(graph.vertices.len(), 5);
97        assert_eq!(graph.edges.len(), 10);
98    }
99
100    #[test]
101    fn edges_have_existing_vertices() {
102        let graph = SimpleGraph::new_star();
103
104        for edge in &graph.edges {
105            assert!(graph.vertices.contains(edge.ver_a()));
106            assert!(graph.vertices.contains(edge.ver_b()));
107        }
108    }
109
110    // TEST ADJACENTS
111    #[test]
112    fn adjacency_list_check_no_selfedges_two_vertices() {
113        let graph = SimpleGraph::new_two();
114        let adjacency_list = AdjacencyList::from(&graph);
115        for (vertice, adjacents) in adjacency_list {
116            assert!(!adjacents.contains(&vertice))
117        }
118    }
119
120    #[test]
121    fn adjacency_list_check_no_selfedges_star() {
122        let graph = SimpleGraph::new_star();
123        let adjacency_list = AdjacencyList::from(&graph);
124        for (vertice, adjacents) in adjacency_list {
125            assert!(!adjacents.contains(&vertice))
126        }
127    }
128}
grafos_tools/simple_graph.rs

grafos_tools/
simple_graph.rs
