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
|
//! This module implements a function to produce the depth-first order
//! for a graph.
use super::*;
use error::Error;
/// Return a list of indices that are ordered according to a depth-first search.
///
/// A node is only recorded at most once. And the search starts from
/// the `root`, so this in fact only includes the connected component
/// of the `root`.
pub fn dfs(g: &impl Graph, root: usize) -> Result<Vec<usize>, Error> {
// let g = g.borrow();
let nodes_len = g.nodes_len();
let mut result: Vec<usize> = Vec::with_capacity(nodes_len);
let mut stack: Vec<usize> = Vec::with_capacity(nodes_len);
stack.push(root);
let mut seen_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();
while let Some(top) = stack.pop() {
match seen_nodes.get_mut(top) {
Some(reference) if !*reference => {
*reference = true;
result.push(top);
// REVIEW: Maybe I shall add a method
// `children_of_rev`.
stack.extend(g.children_of(top)?.collect::<Vec<_>>().into_iter().rev());
}
None => {
return Err(Error::IndexOutOfBounds(top, nodes_len));
}
_ => {}
}
}
Ok(result)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::labelled::simple::SLGBuilder;
#[test]
fn test_dfs() -> Result<(), Box<dyn std::error::Error>> {
let mut builder = SLGBuilder::<usize, usize>::default();
// Add five nodes
builder.add_vertex(0);
builder.add_vertex(1);
builder.add_vertex(2);
builder.add_vertex(3);
builder.add_vertex(4);
let dummy_label = 0usize;
builder.add_edge(0, 1, dummy_label)?;
builder.add_edge(0, 4, dummy_label)?;
builder.add_edge(1, 4, dummy_label)?;
builder.add_edge(1, 2, dummy_label)?;
builder.add_edge(2, 3, dummy_label)?;
builder.add_edge(3, 4, dummy_label)?;
// build a graph
let graph = builder.build();
let dfs = dfs(&graph, 0)?;
println!("dfs = {dfs:?}");
let answer = vec![0, 1, 4, 2, 3];
assert_eq!(answer, dfs);
Ok(())
}
}
|
