algae_graph/
undirected.rs

1/*
2    Appellation: undirected <module>
3    Contrib: FL03 <jo3mccain@icloud.com>
4    Description: ... Summary ...
5*/
6use crate::{cmp::Edge, store::AdjacencyTable};
7use crate::{Contain, Graph, GraphExt, Node, Subgraph, Weight};
8
9use serde::{Deserialize, Serialize};
10
11#[derive(Clone, Debug, Default, Deserialize, Eq, PartialEq, Serialize)]
12pub struct UndirectedGraph<N = String, V = i64>
13where
14    N: Node,
15    V: Weight,
16{
17    store: AdjacencyTable<N, V>,
18}
19
20impl<N, V> UndirectedGraph<N, V>
21where
22    N: Node,
23    V: Weight,
24{
25    pub fn new() -> Self {
26        Self {
27            store: AdjacencyTable::new(),
28        }
29    }
30    pub fn with_capacity(capacity: usize) -> Self {
31        Self {
32            store: AdjacencyTable::with_capacity(capacity),
33        }
34    }
35}
36
37impl<N, V> AsMut<AdjacencyTable<N, V>> for UndirectedGraph<N, V>
38where
39    N: Node,
40    V: Weight,
41{
42    fn as_mut(&mut self) -> &mut AdjacencyTable<N, V> {
43        &mut self.store
44    }
45}
46
47impl<N, V> AsRef<AdjacencyTable<N, V>> for UndirectedGraph<N, V>
48where
49    N: Node,
50    V: Weight,
51{
52    fn as_ref(&self) -> &AdjacencyTable<N, V> {
53        &self.store
54    }
55}
56
57impl<N, V> Contain<N> for UndirectedGraph<N, V>
58where
59    N: Node,
60    V: Weight,
61{
62    fn contains(&self, elem: &N) -> bool {
63        self.store.contains_key(elem)
64    }
65}
66
67impl<N, V> Contain<Edge<N, V>> for UndirectedGraph<N, V>
68where
69    N: Node,
70    V: Weight,
71{
72    fn contains(&self, elem: &Edge<N, V>) -> bool {
73        self.edges().contains(elem)
74    }
75}
76
77impl<N, V> Graph<N, V> for UndirectedGraph<N, V>
78where
79    N: Node,
80    V: Weight,
81{
82    fn add_edge(&mut self, edge: Edge<N, V>) {
83        let pair = edge.pair();
84        self.add_node(pair.0.clone());
85        self.add_node(pair.1.clone());
86
87        self.store.entry(pair.0.clone()).and_modify(|e| {
88            e.push((pair.1.clone(), edge.value().clone()));
89        });
90        self.store.entry(pair.1).and_modify(|e| {
91            e.push((pair.0, edge.value().clone()));
92        });
93    }
94    fn store_mut(&mut self) -> &mut AdjacencyTable<N, V> {
95        &mut self.store
96    }
97    fn store(&self) -> &AdjacencyTable<N, V> {
98        &self.store
99    }
100}
101
102impl<N, V> GraphExt<N, V> for UndirectedGraph<N, V>
103where
104    N: Node,
105    V: Weight,
106{
107}
108
109impl<N, V> Subgraph<N, V> for UndirectedGraph<N, V>
110where
111    N: Node,
112    V: Weight,
113{
114}
115
116impl<N, V> From<AdjacencyTable<N, V>> for UndirectedGraph<N, V>
117where
118    N: Node,
119    V: Weight,
120{
121    fn from(store: AdjacencyTable<N, V>) -> Self {
122        Self { store }
123    }
124}
125
126impl<N, V> std::ops::Index<N> for UndirectedGraph<N, V>
127where
128    N: Node,
129    V: Weight,
130{
131    type Output = Vec<(N, V)>;
132
133    fn index(&self, index: N) -> &Self::Output {
134        &self.store[index]
135    }
136}
137
138impl<N, V> std::ops::IndexMut<N> for UndirectedGraph<N, V>
139where
140    N: Node,
141    V: Weight,
142{
143    fn index_mut(&mut self, index: N) -> &mut Self::Output {
144        self.store.index_mut(index)
145    }
146}
147
148#[cfg(test)]
149mod tests {
150    use super::*;
151
152    const TEST_EDGES: [(&str, &str, usize); 3] = [("a", "b", 5), ("c", "a", 7), ("b", "c", 10)];
153
154    const EXPECTED: [(&str, &str, usize); 6] = [
155        ("a", "b", 5),
156        ("b", "a", 5),
157        ("c", "a", 7),
158        ("a", "c", 7),
159        ("b", "c", 10),
160        ("c", "b", 10),
161    ];
162
163    #[test]
164    fn test_add_edge() {
165        let mut graph = UndirectedGraph::new();
166
167        for i in TEST_EDGES {
168            graph.add_edge(i.into());
169        }
170        // assert that the graph contains all the edges
171        assert!(graph.contains_all(EXPECTED.into_iter().map(Edge::from).collect::<Vec<_>>()));
172        // assert that the graph can be indexed
173        assert_eq!(graph["a"], vec![("b", 5), ("c", 7)]);
174    }
175
176    #[test]
177    fn test_neighbours() {
178        let mut graph = UndirectedGraph::new();
179
180        for i in TEST_EDGES {
181            graph.add_edge(i.into());
182        }
183
184        assert_eq!(graph["a"], vec![("b", 5), ("c", 7)]);
185    }
186}
algae_graph/undirected.rs

algae_graph/
undirected.rs
