detect_cycle/
lib.rs

1/// 無向グラフの閉路を求めます。
2///
3/// - `n`: 頂点数
4/// - `edges`: 辺
5///
6/// 返り値は、閉路をなす辺の index のベクタです。
7///
8/// # Example
9/// ```
10/// use detect_cycle::detect_cycle_undirected;
11/// //      0       1       3
12/// // (0) --- (1) --- (2) --- (5)
13/// //          |       |
14/// //        5 |       | 2
15/// //          |       |
16/// //         (4) --- (3)
17/// //              4
18///
19/// let cycle = detect_cycle_undirected(6, &[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4), (4, 1)]).unwrap();
20/// let candidates = vec![
21///     vec![1, 2, 4, 5],
22///     vec![2, 4, 5, 1],
23///     vec![4, 5, 1, 2],
24///     vec![5, 1, 2, 4],
25///     vec![1, 5, 4, 2],
26///     vec![5, 4, 2, 1],
27///     vec![4, 2, 1, 5],
28///     vec![2, 1, 5, 4],
29/// ];
30/// assert!(candidates.contains(&cycle));
31/// ```
32pub fn detect_cycle_undirected(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
33    fn dfs(
34        curr: usize,
35        prev: usize,
36        g: &[Vec<(usize, usize)>],
37        seen: &mut Vec<bool>,
38        parent: &mut Vec<(usize, usize)>,
39    ) -> Option<(usize, usize)> {
40        seen[curr] = true;
41        for &(nxt, idx) in &g[curr] {
42            if nxt == prev {
43                continue;
44            }
45            if seen[nxt] {
46                return Some((nxt, curr));
47            }
48            parent[nxt] = (curr, idx);
49            if let Some((start, end)) = dfs(nxt, curr, g, seen, parent) {
50                return Some((start, end));
51            }
52        }
53        None
54    }
55
56    let mut g = vec![vec![]; n];
57    for (idx, &(u, v)) in edges.iter().enumerate() {
58        g[u].push((v, idx));
59        g[v].push((u, idx));
60    }
61    let mut seen = vec![false; n];
62    let mut parent = vec![(!0, !0); n];
63
64    for v in 0..n {
65        if seen[v] {
66            continue;
67        }
68        if let Some((cycle_start, cycle_end)) = dfs(v, !0, &g, &mut seen, &mut parent) {
69            let mut cycle = Vec::new();
70            {
71                let mut curr = cycle_end;
72                while curr != cycle_start {
73                    let (par, idx) = parent[curr];
74                    cycle.push(idx);
75                    curr = par;
76                }
77            }
78            // cycle_end <- parent[cycle_end] <- parent[parent[cycle_end]] <- ... <- cycle_start
79            for (idx, &(u, v)) in edges.iter().enumerate() {
80                if (u, v) == (cycle_start, cycle_end) || (u, v) == (cycle_end, cycle_start) {
81                    cycle.push(idx);
82                    return Some(cycle);
83                }
84            }
85            unreachable!();
86        }
87    }
88    None
89}
90
91/// 有向グラフの閉路を求めます。
92///
93/// - `n`: 頂点数
94/// - `edges`: 辺
95///
96/// 返り値は、閉路をなす辺の index のベクタです。
97///
98/// # Example
99/// ```
100/// use detect_cycle::detect_cycle_directed;
101///
102/// //      0       1       3
103/// // (0) --> (1) --> (2) --> (5)
104/// //          ^       |
105/// //        5 |       | 2
106/// //          |       v
107/// //         (4) <-- (3)
108/// //              4
109///
110/// let cycle = detect_cycle_directed(6, &[(0, 1), (1, 2), (2, 3), (2, 5), (3, 4), (4, 1)]);
111/// assert_eq!(cycle, Some(vec![1, 2, 4, 5]));
112/// ```
113pub fn detect_cycle_directed(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
114    fn dfs(
115        curr: usize,
116        g: &[Vec<(usize, usize)>],
117        seen: &mut Vec<bool>,
118        on_path: &mut Vec<bool>,
119    ) -> Option<(usize, Vec<usize>, bool)> {
120        seen[curr] = true;
121        on_path[curr] = true;
122        for &(nxt, idx) in &g[curr] {
123            if on_path[nxt] {
124                assert!(seen[nxt]);
125                return Some((nxt, vec![idx], true));
126            }
127            if seen[nxt] {
128                continue;
129            }
130            if let Some((start_node, mut cycle, in_cycle)) = dfs(nxt, g, seen, on_path) {
131                return if in_cycle {
132                    cycle.push(idx);
133                    if curr == start_node {
134                        cycle.reverse();
135                        Some((start_node, cycle, false))
136                    } else {
137                        Some((start_node, cycle, true))
138                    }
139                } else {
140                    Some((start_node, cycle, false))
141                };
142            }
143        }
144        on_path[curr] = false;
145        None
146    }
147
148    let mut g = vec![vec![]; n];
149    for (idx, &(u, v)) in edges.iter().enumerate() {
150        g[u].push((v, idx));
151    }
152    let mut seen = vec![false; n];
153    let mut on_path = vec![false; n];
154    for v in 0..n {
155        if seen[v] {
156            continue;
157        }
158        if let Some((_, cycle, in_cycle)) = dfs(v, &g, &mut seen, &mut on_path) {
159            assert!(!in_cycle);
160            return Some(cycle);
161        }
162    }
163    None
164}
165
166#[cfg(test)]
167mod tests {
168    use crate::detect_cycle_directed;
169
170    #[test]
171    fn test_directed_triangle() {
172        let cycle = detect_cycle_directed(3, &[(0, 2), (2, 1), (1, 0)]);
173        assert_eq!(cycle, Some(vec![0, 1, 2]));
174    }
175
176    #[test]
177    fn test_directed_v() {
178        let cycle = detect_cycle_directed(3, &[(0, 2), (0, 1)]);
179        assert_eq!(cycle, None);
180    }
181}
detect_cycle/lib.rs

detect_cycle/
lib.rs
