From fba9a90cfc6aca2a26cce72f55fb261789139781 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 16 Oct 2026 14:01:01 +0800
Subject: new start

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.
---
 graph/src/dfs.rs | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 88 insertions(+)
 create mode 100644 graph/src/dfs.rs

(limited to 'graph/src/dfs.rs')

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(())
+    }
+}
-- 
cgit v1.2.3-18-g5258