ciclo/
all_cycles.rs

1use std::{fmt::Debug, hash::Hash};
2
3use crate::Graph;
4
5pub fn all_cycles<T: Eq + Hash + Clone + Debug>(
6    mut graph: Graph<T>,
7) -> Vec<Vec<T>> {
8    let mut result = Vec::new();
9
10    for key in graph.keys() {
11        for paths in graph.remove(&key) {
12            for path in paths {
13                if &path.target != &key {
14                    continue;
15                }
16
17                result.push(Vec::from(path))
18            }
19        }
20    }
21
22    result
23}
24
25#[cfg(test)]
26mod tests {
27    use std::collections::HashSet;
28
29    use crate::Cycle;
30
31    use super::*;
32    use pretty_assertions::assert_eq;
33
34    fn to_set(cycles: Vec<Vec<u32>>) -> HashSet<Cycle<u32>> {
35        cycles
36            .into_iter()
37            .map(|c| Cycle::new(c))
38            .collect::<HashSet<_>>()
39    }
40
41    #[test]
42    fn p3() {
43        let graph = Graph::from_edges(vec![(0, 1)]).unwrap();
44
45        assert_eq!(all_cycles(graph), Vec::<Vec<u32>>::new())
46    }
47
48    #[test]
49    fn c3() {
50        let graph = Graph::from_edges(vec![(0, 1), (1, 2), (2, 0)]).unwrap();
51
52        assert_eq!(
53            to_set(all_cycles(graph)),
54            HashSet::from([Cycle::new(vec![0, 1, 2])])
55        )
56    }
57
58    #[test]
59    fn butterfly() {
60        let graph = Graph::from_edges(vec![
61            (0, 1),
62            (1, 2),
63            (2, 3),
64            (3, 4),
65            (4, 2),
66            (2, 0),
67        ])
68        .unwrap();
69
70        assert_eq!(
71            to_set(all_cycles(graph)),
72            HashSet::from([
73                Cycle::new(vec![0, 1, 2]),
74                Cycle::new(vec![2, 3, 4])
75            ])
76        )
77    }
78
79    #[test]
80    fn diamond() {
81        let graph =
82            Graph::from_edges(vec![(0, 1), (1, 2), (2, 0), (2, 3), (3, 1)])
83                .unwrap();
84
85        assert_eq!(
86            to_set(all_cycles(graph)),
87            HashSet::from([
88                Cycle::new(vec![0, 1, 2]),
89                Cycle::new(vec![1, 2, 3]),
90                Cycle::new(vec![0, 1, 3, 2])
91            ])
92        )
93    }
94
95    #[test]
96    fn k4() {
97        let graph = Graph::from_edges(vec![
98            (0, 1),
99            (1, 2),
100            (2, 3),
101            (3, 0),
102            (0, 2),
103            (1, 3)
104        ])
105        .unwrap();
106
107        assert_eq!(
108            to_set(all_cycles(graph)),
109            HashSet::from([
110                Cycle::new(vec![0, 1, 2]),
111                Cycle::new(vec![0, 1, 3]),
112                Cycle::new(vec![0, 2, 3]),
113                Cycle::new(vec![1, 2, 3]),
114                Cycle::new(vec![1, 2, 0, 3]),
115                Cycle::new(vec![1, 0, 2, 3]),
116                Cycle::new(vec![0, 1, 2, 3])
117            ])
118        )
119    }
120
121    // see: http://efficientbits.blogspot.com/2013/06/allringsfinder-sport-edition.html
122    #[test]
123    fn k5() {
124        let graph = Graph::from_edges(vec![
125            (0, 1),
126            (1, 2),
127            (2, 3),
128            (3, 4),
129            (4, 0),
130            (0, 3),
131            (0, 2),
132            (1, 3),
133            (1, 4),
134            (2, 4),
135        ]).unwrap();
136
137        assert_eq!(all_cycles(graph).len(), 37 * 2)
138    }
139}
ciclo/all_cycles.rs

ciclo/
all_cycles.rs
