1use std::{collections::HashMap, fmt::Debug, hash::Hash};
2
3use crate::{Error, Path};
4
5#[derive(Debug, PartialEq)]
6pub struct Graph<T: Eq + Hash + Clone + Debug> {
7 paths: HashMap<T, Vec<Path<T>>>,
8}
9
10impl<T: Eq + Hash + Clone + Debug> Graph<T> {
11 pub fn from_edges(edges: Vec<(T, T)>) -> Result<Self, Error> {
12 let mut paths: HashMap<T, Vec<Path<T>>> = HashMap::new();
13
14 for (source, target) in edges {
15 if source == target {
16 return Err(Error::Dummy);
17 }
18
19 match paths.entry(source.clone()) {
20 std::collections::hash_map::Entry::Occupied(mut occupied) => {
21 for path in occupied.get().iter() {
22 if &path.target == &target {
23 return Err(Error::Dummy);
24 }
25 }
26
27 occupied.get_mut().push(Path::to(target.clone()));
28 }
29 std::collections::hash_map::Entry::Vacant(vacant) => {
30 vacant.insert(vec![Path::to(target.clone())]);
31 }
32 }
33 match paths.entry(target) {
34 std::collections::hash_map::Entry::Occupied(mut occupied) => {
35 occupied.get_mut().push(Path::to(source.clone()))
36 }
37 std::collections::hash_map::Entry::Vacant(vacant) => {
38 vacant.insert(vec![Path::to(source.clone())]);
39 }
40 }
41 }
42
43 Ok(Self { paths })
44 }
45
46 pub fn keys(&self) -> Vec<T> {
47 self.paths.keys().cloned().collect()
48 }
49
50 pub fn remove(&mut self, out_source: &T) -> Option<Vec<Path<T>>> {
51 let out_paths = self.paths.remove(out_source)?;
52 let mut paths = HashMap::new();
53
54 std::mem::swap(&mut self.paths, &mut paths);
55
56 for (in_source, in_paths) in paths {
57 let mut new_in_paths = Vec::new();
58
59 for in_path in in_paths.into_iter() {
60 if &in_path.target == out_source {
61 for out_path in out_paths.iter() {
62 if let Some(new_path) =
63 in_path.concat(&in_source, &out_path)
64 {
65 new_in_paths.push(new_path)
66 }
67 }
68 } else {
69 new_in_paths.push(in_path)
70 }
71 }
72
73 if !new_in_paths.is_empty() {
74 self.paths.insert(in_source, new_in_paths);
75 }
76 }
77
78 Some(out_paths)
79 }
80}
81
82#[cfg(test)]
83mod from_edges {
84 use super::*;
85 use pretty_assertions::assert_eq;
86
87 #[test]
88 fn loop_edge() {
89 let edges = vec![(1, 1)];
90
91 assert_eq!(Graph::from_edges(edges), Err(Error::Dummy))
92 }
93
94 #[test]
95 fn duplicate_edge_forward() {
96 let edges = vec![(0, 1), (0, 1)];
97
98 assert_eq!(Graph::from_edges(edges), Err(Error::Dummy))
99 }
100
101 #[test]
102 fn duplicate_edge_reverse() {
103 let edges = vec![(0, 1), (1, 0)];
104
105 assert_eq!(Graph::from_edges(edges), Err(Error::Dummy))
106 }
107
108 #[test]
109 fn p3_duplicate_second_reverse() {
110 let edges = vec![(0, 1), (1, 2), (2, 1)];
111
112 assert_eq!(Graph::from_edges(edges), Err(Error::Dummy))
113 }
114
115 #[test]
116 fn p2() {
117 let edges = vec![(0, 1)];
118
119 assert_eq!(
120 Graph::from_edges(edges),
121 Ok(Graph {
122 paths: vec![(0, vec![Path::to(1)]), (1, vec![Path::to(0)]),]
123 .into_iter()
124 .collect()
125 })
126 )
127 }
128
129 #[test]
130 fn p3() {
131 let edges = vec![(0, 1), (1, 2)];
132
133 assert_eq!(
134 Graph::from_edges(edges),
135 Ok(Graph {
136 paths: vec![
137 (0, vec![Path::to(1)]),
138 (1, vec![Path::to(0), Path::to(2)]),
139 (2, vec![Path::to(1)])
140 ]
141 .into_iter()
142 .collect()
143 })
144 )
145 }
146
147 #[test]
148 fn p3_inverted_first() {
149 let edges = vec![(1, 0), (1, 2)];
150
151 assert_eq!(
152 Graph::from_edges(edges),
153 Ok(Graph {
154 paths: vec![
155 (0, vec![Path::to(1)]),
156 (1, vec![Path::to(0), Path::to(2)]),
157 (2, vec![Path::to(1)])
158 ]
159 .into_iter()
160 .collect()
161 })
162 )
163 }
164
165 #[test]
166 fn p3_inverted_second() {
167 let edges = vec![(0, 1), (2, 1)];
168
169 assert_eq!(
170 Graph::from_edges(edges),
171 Ok(Graph {
172 paths: vec![
173 (0, vec![Path::to(1)]),
174 (1, vec![Path::to(0), Path::to(2)]),
175 (2, vec![Path::to(1)])
176 ]
177 .into_iter()
178 .collect()
179 })
180 )
181 }
182
183 #[test]
184 fn s3() {
185 let edges = vec![(0, 1), (1, 2), (1, 3)];
186
187 assert_eq!(
188 Graph::from_edges(edges),
189 Ok(Graph {
190 paths: vec![
191 (0, vec![Path::to(1)]),
192 (1, vec![Path::to(0), Path::to(2), Path::to(3)]),
193 (2, vec![Path::to(1)]),
194 (3, vec![Path::to(1)])
195 ]
196 .into_iter()
197 .collect()
198 })
199 )
200 }
201}
202
203#[cfg(test)]
204mod remove {
205 use super::*;
206 use pretty_assertions::assert_eq;
207
208 #[test]
209 fn missing_node() {
210 let mut graph = Graph {
211 paths: vec![(0, vec![Path::to(1)]), (1, vec![Path::to(0)])]
212 .into_iter()
213 .collect(),
214 };
215
216 assert_eq!(graph.remove(&2), None)
217 }
218
219 #[test]
220 fn p3_terminal() {
221 let mut graph = Graph {
222 paths: HashMap::from([
223 (0, vec![Path::to(1)]),
224 (1, vec![Path::to(0), Path::to(2)]),
225 (2, vec![Path::to(1)]),
226 ]),
227 };
228
229 assert_eq!(graph.remove(&0), Some(vec![Path::to(1)]));
230 assert_eq!(
231 graph,
232 Graph {
233 paths: HashMap::from([
234 (1, vec![Path::to(2)]),
235 (2, vec![Path::to(1)])
236 ])
237 }
238 )
239 }
240
241 #[test]
242 fn p3_internal() {
243 let mut graph = Graph {
244 paths: HashMap::from([
245 (0, vec![Path::to(1)]),
246 (1, vec![Path::to(0), Path::to(2)]),
247 (2, vec![Path::to(1)]),
248 ]),
249 };
250
251 assert_eq!(graph.remove(&1), Some(vec![Path::to(0), Path::to(2)]));
252 assert_eq!(
253 graph,
254 Graph {
255 paths: HashMap::from([
256 (0, vec![Path::new(vec![1], 2)]),
257 (2, vec![Path::new(vec![1], 0)])
258 ])
259 }
260 )
261 }
262
263 #[test]
264 fn s3_internal() {
265 let mut graph = Graph {
266 paths: HashMap::from([
267 (0, vec![Path::to(1)]),
268 (1, vec![Path::to(0), Path::to(2), Path::to(3)]),
269 (2, vec![Path::to(1)]),
270 (3, vec![Path::to(1)]),
271 ]),
272 };
273
274 assert_eq!(
275 graph.remove(&1),
276 Some(vec![Path::to(0), Path::to(2), Path::to(3)])
277 );
278 assert_eq!(
279 graph,
280 Graph {
281 paths: HashMap::from([
282 (0, vec![Path::new(vec![1], 2), Path::new(vec![1], 3)]),
283 (2, vec![Path::new(vec![1], 0), Path::new(vec![1], 3),]),
284 (3, vec![Path::new(vec![1], 0), Path::new(vec![1], 2)])
285 ])
286 }
287 )
288 }
289
290 #[test]
291 fn pre_cycle() {
292 let mut graph = Graph {
293 paths: HashMap::from([
294 (0, vec![Path::new(vec![1], 2), Path::to(2)]),
295 (2, vec![Path::new(vec![1], 0), Path::to(0)]),
296 ]),
297 };
298
299 assert_eq!(
300 graph.remove(&2),
301 Some(vec![Path::new(vec![1], 0), Path::to(0)])
302 );
303 assert_eq!(
304 graph,
305 Graph {
306 paths: HashMap::from([(
307 0,
308 vec![Path::new(vec![1, 2], 0), Path::new(vec![2, 1], 0)]
309 )])
310 }
311 )
312 }
313}