1 files changed, 88 insertions, 0 deletions
diff --git a/graph/src/dfs.rs b/graph/src/dfs.rs
new file mode 100644
index 0000000..e9af3de
--- /dev/null
+++ b/graph/src/dfs.rs
@@ -0,0 +1,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(())
+    }
+}