rustworkx_core/connectivity/
find_cycle.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13use hashbrown::{HashMap, HashSet};
14use petgraph::algo;
15use petgraph::visit::{
16    EdgeCount, GraphBase, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCount, Visitable,
17};
18use petgraph::Direction::Outgoing;
19use std::hash::Hash;
20
21/// Return the first cycle encountered during DFS of a given directed graph.
22/// Empty list is returned if no cycle is found.
23///
24/// Arguments:
25///
26/// * `graph` - The directed graph in which to find the first cycle.
27/// * `source` - Optional node index for starting the search. If not specified,
28///     an arbitrary node is chosen to start the search.
29///
30/// # Example
31/// ```rust
32/// use petgraph::prelude::*;
33/// use rustworkx_core::connectivity::find_cycle;
34///
35/// let edge_list = vec![
36///     (0, 1),
37///     (3, 0),
38///     (0, 5),
39///     (8, 0),
40///     (1, 2),
41///     (1, 6),
42///     (2, 3),
43///     (3, 4),
44///     (4, 5),
45///     (6, 7),
46///     (7, 8),
47///     (8, 9),
48/// ];
49/// let graph = DiGraph::<i32, i32>::from_edges(&edge_list);
50/// let mut res: Vec<(usize, usize)> = find_cycle(&graph, Some(NodeIndex::new(0)))
51///     .iter()
52///     .map(|(s, t)| (s.index(), t.index()))
53///     .collect();
54/// assert_eq!(res, [(0, 1), (1, 2), (2, 3), (3, 0)]);
55/// ```
56pub fn find_cycle<G>(graph: G, source: Option<G::NodeId>) -> Vec<(G::NodeId, G::NodeId)>
57where
58    G: GraphBase,
59    G: NodeCount,
60    G: EdgeCount,
61    for<'b> &'b G:
62        GraphBase<NodeId = G::NodeId> + IntoNodeIdentifiers + IntoNeighborsDirected + Visitable,
63    G::NodeId: Eq + Hash,
64{
65    // Find a cycle in the given graph and return it as a list of edges
66    let mut cycle: Vec<(G::NodeId, G::NodeId)> = Vec::with_capacity(graph.edge_count());
67    // If source is not set get a node in an arbitrary cycle if it exists,
68    // otherwise return that there is no cycle
69    let source_index = match source {
70        Some(source_value) => source_value,
71        None => match find_node_in_arbitrary_cycle(&graph) {
72            Some(node_in_cycle) => node_in_cycle,
73            None => {
74                return Vec::new();
75            }
76        },
77    };
78    // Stack (ie "pushdown list") of vertices already in the spanning tree
79    let mut stack: Vec<G::NodeId> = vec![source_index];
80    // map to store parent of a node
81    let mut pred: HashMap<G::NodeId, G::NodeId> = HashMap::new();
82    // a node is in the visiting set if at least one of its child is unexamined
83    let mut visiting = HashSet::new();
84    // a node is in visited set if all of its children have been examined
85    let mut visited = HashSet::new();
86    while !stack.is_empty() {
87        let mut z = *stack.last().unwrap();
88        visiting.insert(z);
89
90        let children = graph.neighbors_directed(z, Outgoing);
91        for child in children {
92            //cycle is found
93            if visiting.contains(&child) {
94                cycle.push((z, child));
95                //backtrack
96                loop {
97                    if z == child {
98                        cycle.reverse();
99                        break;
100                    }
101                    cycle.push((pred[&z], z));
102                    z = pred[&z];
103                }
104                return cycle;
105            }
106            //if an unexplored node is encountered
107            if !visited.contains(&child) {
108                stack.push(child);
109                pred.insert(child, z);
110            }
111        }
112        let top = *stack.last().unwrap();
113        //if no further children and explored, move to visited
114        if top == z {
115            stack.pop();
116            visiting.remove(&z);
117            visited.insert(z);
118        }
119    }
120    cycle
121}
122
123fn find_node_in_arbitrary_cycle<G>(graph: &G) -> Option<G::NodeId>
124where
125    G: GraphBase,
126    G: NodeCount,
127    G: EdgeCount,
128    for<'b> &'b G:
129        GraphBase<NodeId = G::NodeId> + IntoNodeIdentifiers + IntoNeighborsDirected + Visitable,
130    G::NodeId: Eq + Hash,
131{
132    for scc in algo::kosaraju_scc(&graph) {
133        if scc.len() > 1 {
134            return Some(scc[0]);
135        }
136    }
137    for node in graph.node_identifiers() {
138        for neighbor in graph.neighbors_directed(node, Outgoing) {
139            if neighbor == node {
140                return Some(node);
141            }
142        }
143    }
144    None
145}
146
147#[cfg(test)]
148mod tests {
149    use crate::connectivity::find_cycle;
150    use petgraph::prelude::*;
151
152    // Utility to assert cycles in the response
153    macro_rules! assert_cycle {
154        ($g: expr, $cycle: expr) => {{
155            for i in 0..$cycle.len() {
156                let (s, t) = $cycle[i];
157                assert!($g.contains_edge(s, t));
158                let (next_s, _) = $cycle[(i + 1) % $cycle.len()];
159                assert_eq!(t, next_s);
160            }
161        }};
162    }
163
164    #[test]
165    fn test_find_cycle_source() {
166        let edge_list = vec![
167            (0, 1),
168            (3, 0),
169            (0, 5),
170            (8, 0),
171            (1, 2),
172            (1, 6),
173            (2, 3),
174            (3, 4),
175            (4, 5),
176            (6, 7),
177            (7, 8),
178            (8, 9),
179        ];
180        let graph = DiGraph::<i32, i32>::from_edges(edge_list);
181        for i in [0, 1, 2, 3].iter() {
182            let idx = NodeIndex::new(*i);
183            let res = find_cycle(&graph, Some(idx));
184            assert_cycle!(graph, res);
185            assert_eq!(res[0].0, idx);
186        }
187        let res = find_cycle(&graph, Some(NodeIndex::new(5)));
188        assert_eq!(res, []);
189    }
190
191    #[test]
192    fn test_self_loop() {
193        let edge_list = vec![
194            (0, 1),
195            (3, 0),
196            (0, 5),
197            (8, 0),
198            (1, 2),
199            (1, 6),
200            (2, 3),
201            (3, 4),
202            (4, 5),
203            (6, 7),
204            (7, 8),
205            (8, 9),
206        ];
207        let mut graph = DiGraph::<i32, i32>::from_edges(edge_list);
208        graph.add_edge(NodeIndex::new(1), NodeIndex::new(1), 0);
209        let res = find_cycle(&graph, Some(NodeIndex::new(0)));
210        assert_eq!(res[0].0, NodeIndex::new(1));
211        assert_cycle!(graph, res);
212    }
213
214    #[test]
215    fn test_self_loop_no_source() {
216        let edge_list = vec![(0, 1), (1, 2), (2, 3), (2, 2)];
217        let graph = DiGraph::<i32, i32>::from_edges(edge_list);
218        let res = find_cycle(&graph, None);
219        assert_cycle!(graph, res);
220    }
221
222    #[test]
223    fn test_cycle_no_source() {
224        let edge_list = vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 2)];
225        let graph = DiGraph::<i32, i32>::from_edges(edge_list);
226        let res = find_cycle(&graph, None);
227        assert_cycle!(graph, res);
228    }
229
230    #[test]
231    fn test_no_cycle_no_source() {
232        let edge_list = vec![(0, 1), (1, 2), (2, 3)];
233        let graph = DiGraph::<i32, i32>::from_edges(edge_list);
234        let res = find_cycle(&graph, None);
235        assert_eq!(res, []);
236    }
237}
rustworkx_core/connectivity/find_cycle.rs

rustworkx_core/connectivity/
find_cycle.rs
