| 78 | } |
| 79 | |
| 80 | fn dfs(&mut self, graph: &dyn IGraph, v: usize) { |
| 81 | self.on_stack[v] = true; |
| 82 | self.marked[v] = true; |
| 83 | for &w in graph.adj(v) { |
| 84 | // short circuit if directed cycle found |
| 85 | if self.cycle.is_some() { |
| 86 | return; |
| 87 | } |
| 88 | |
| 89 | // found new vertex, so recur |
| 90 | if !self.marked[w] { |
| 91 | self.edge_to[w] = v; |
| 92 | self.dfs(graph, w); |
| 93 | } |
| 94 | // trace back directed cycle |
| 95 | else if self.on_stack[w] { |
| 96 | let mut cycle = Stack::default(); |
| 97 | let mut x = v; |
| 98 | while x != w { |
| 99 | cycle.push(x); |
| 100 | x = self.edge_to[x]; |
| 101 | } |
| 102 | cycle.push(w); |
| 103 | cycle.push(v); |
| 104 | self.cycle = Some(cycle); |
| 105 | } |
| 106 | } |
| 107 | self.on_stack[v] = false; |
| 108 | } |
| 109 | |
| 110 | pub fn check(&self) -> Result<(), String> { |
| 111 | if let Some(cycle) = self.cycle() { |