1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//! Submodule providing the `CycleDetection` trait and its blanket
//! implementation.
use alloc::vec::Vec;
use num_traits::AsPrimitive;
use crate::{impls::BitSet, traits::MonoplexMonopartiteGraph};
/// Trait providing the `has_cycle` method, which returns true if the graph
/// contains a cycle, and false otherwise. The cycle detection algorithm is
/// based on a depth-first search (DFS) approach.
pub trait CycleDetection: MonoplexMonopartiteGraph {
/// Returns true if the graph contains a cycle, false otherwise.
///
/// # Complexity
///
/// O(V + E) time and O(V) space. Node membership in the current DFS path
/// is tracked with a `Vec<bool>` for O(1) per lookup instead of the
/// O(n) `Vec::contains` that the naive stack approach would require.
///
/// # Examples
///
/// ```
/// use geometric_traits::{
/// impls::{SortedVec, SquareCSR2D},
/// prelude::*,
/// traits::{EdgesBuilder, VocabularyBuilder},
/// };
///
/// let nodes: Vec<usize> = vec![0, 1, 2, 3, 4, 5];
/// let edges: Vec<(usize, usize)> = vec![(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)];
/// let nodes: SortedVec<usize> = GenericVocabularyBuilder::default()
/// .expected_number_of_symbols(nodes.len())
/// .symbols(nodes.into_iter().enumerate())
/// .build()
/// .unwrap();
/// let edges: SquareCSR2D<_> = DiEdgesBuilder::default()
/// .expected_number_of_edges(edges.len())
/// .expected_shape(nodes.len())
/// .edges(edges.into_iter())
/// .build()
/// .unwrap();
/// let graph: DiGraph<usize> = DiGraph::from((nodes, edges));
///
/// assert!(!graph.has_cycle());
/// ```
#[inline]
fn has_cycle(&self) -> bool {
let n = self.number_of_nodes().as_();
let mut visited = BitSet::zeros(n);
let mut on_stack = BitSet::zeros(n);
// DFS stack entries: (node, collected successors, next-successor index)
let mut dfs_stack: Vec<(Self::NodeId, Vec<Self::NodeId>, usize)> = Vec::new();
for start in self.node_ids() {
if visited.contains(start.as_()) {
continue;
}
visited.insert(start.as_());
on_stack.insert(start.as_());
dfs_stack.push((start, self.successors(start).collect(), 0));
loop {
if dfs_stack.is_empty() {
break;
}
let top_idx = dfs_stack.last().unwrap().2;
let top_len = dfs_stack.last().unwrap().1.len();
if top_idx < top_len {
let successor = dfs_stack.last().unwrap().1[top_idx];
dfs_stack.last_mut().unwrap().2 += 1;
if on_stack.contains(successor.as_()) {
return true;
}
if !visited.contains(successor.as_()) {
visited.insert(successor.as_());
on_stack.insert(successor.as_());
dfs_stack.push((successor, self.successors(successor).collect(), 0));
}
} else {
let (node, _, _) = dfs_stack.pop().unwrap();
on_stack.remove(node.as_());
}
}
}
false
}
}
impl<G: MonoplexMonopartiteGraph> CycleDetection for G {}