new startHEADmaster

Now I tested and discussed with claude, and had a working version of
this project.  The rest is to port the claude version to my own
writings.  So this serves as the starting point before that attempt.

In the new attempt the design is better, and a number of bugs were
found and supposedly fixed, so let us see how this goes at the end.

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(())
+    }
+}