haar_lib/graph/cycle/
directed_shortest.rs1use crate::graph::{bfs::*, *};
7
8pub fn directed_shortest_cycle<E: EdgeTrait>(
12 g: &Graph<Directed, E>,
13 src: usize,
14) -> Option<Vec<&E>> {
15 let res = bfs(g, Some(src));
16 let p = res
17 .iter()
18 .flatten()
19 .flat_map(|(d, e)| {
20 e.map(|e| {
21 g.nodes[e.to()]
22 .edges
23 .iter()
24 .find(|e| e.to() == src)
25 .map(|e_src| (d, e, e_src))
26 })
27 .flatten()
28 })
29 .min_by_key(|(d, _, _)| *d);
30
31 p.map(|(_, e, e_src)| {
32 let mut ret = vec![];
33 let mut cur = e.to();
34
35 ret.push(e_src);
36
37 while cur != src {
38 let e = res[cur].unwrap().1.unwrap();
39 ret.push(e);
40 cur = e.from();
41 }
42
43 ret.reverse();
44 ret
45 })
46}