haar_lib/graph/
detect_cycle.rs

1//! 有向グラフの閉路検出
2
3use crate::graph::*;
4
5#[derive(Clone, Copy, PartialEq, Eq)]
6enum Status {
7    Unchecked,
8    Searched,
9    Searching,
10}
11
12/// 有向グラフの閉路検出
13pub fn detect_cycle<D: Direction, E: EdgeTrait>(g: &Graph<D, E>) -> Option<Vec<&E>> {
14    let size = g.len();
15    let mut check = vec![Status::Unchecked; size];
16
17    for i in 0..size {
18        if check[i] == Status::Unchecked {
19            let mut ret = vec![];
20            rec(g, i, &mut ret, &mut check);
21
22            if !ret.is_empty() {
23                ret.reverse();
24                return Some(ret);
25            }
26        }
27    }
28
29    None
30}
31
32fn rec<'a, D: Direction, E: EdgeTrait>(
33    g: &'a Graph<D, E>,
34    cur: usize,
35    ret: &mut Vec<&'a E>,
36    check: &mut [Status],
37) -> Option<isize> {
38    match check[cur] {
39        Status::Searched => None,
40        Status::Searching => Some(cur as isize),
41        Status::Unchecked => {
42            check[cur] = Status::Searching;
43
44            for e in g.nodes[cur].edges.iter() {
45                if let Some(res) = rec(g, e.to(), ret, check) {
46                    if res != -1 {
47                        ret.push(e);
48                        if res == cur as isize {
49                            return Some(-1);
50                        }
51                    }
52
53                    return Some(res);
54                }
55            }
56
57            check[cur] = Status::Searched;
58
59            None
60        }
61    }
62}
haar_lib/graph/detect_cycle.rs

haar_lib/graph/
detect_cycle.rs
