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.

6 files changed, 748 insertions, 103 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(())
+    }
+}
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index 862f25b..fecc295 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -2,7 +2,7 @@
 //! labels and each node knows about its parents.
 
 use super::*;
-use crate::{Parent, ParentsGraph, RedirectGraph};
+use crate::{Parent, ParentsGraph, RedirectGraph, VLabelGraph};
 
 use std::{
     collections::{hash_map::Iter as MapIter, HashMap as Map},
@@ -223,7 +223,7 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
         for node in self.nodes() {
             post.push_str(&format!(
                 "    {node} [label = \"{node}:{}\"]\n",
-                match self.vertex_label(node) {
+                match VLabelGraph::vertex_label(self, node) {
                     Ok(Some(label)) => {
                         format!("{label}")
                     }
@@ -249,6 +249,7 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
         let mut file = std::fs::File::options()
             .write(true)
             .create(true)
+            .truncate(true)
             .open(&filename)?;
 
         use std::io::Write;
@@ -405,6 +406,79 @@ impl<T: GraphLabel> RedirectGraph for PLGraph<T> {
     }
 }
 
+/// A delegation of iterators.
+///
+/// This is used to avoid a boxed pointer to an iterator.
+#[derive(Debug, Clone)]
+pub struct PLVIter<'a, T: GraphLabel> {
+    iter: Iter<'a, usize>,
+    graph: &'a PLGraph<T>,
+}
+
+impl<'a, T: GraphLabel> PLVIter<'a, T> {
+    /// Return an iterator from a graph and a node.
+    pub fn try_new(graph: &'a PLGraph<T>, node: usize) -> Result<Self, Error> {
+        let iter = graph
+            .nodes
+            .get(node)
+            .ok_or(Error::IndexOutOfBounds(node, graph.nodes.len()))?
+            .children
+            .iter();
+
+        Ok(Self { iter, graph })
+    }
+}
+
+impl<'a, T: GraphLabel> Iterator for PLVIter<'a, T> {
+    type Item = (T, usize);
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().and_then(|child| {
+            VLabelGraph::vertex_label(self.graph, *child)
+                .ok()
+                .flatten()
+                .map(|label| (label, *child))
+        })
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let len = self.iter.len();
+
+        (len, Some(len))
+    }
+}
+
+impl<'a, T: GraphLabel> ExactSizeIterator for PLVIter<'a, T> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<T: GraphLabel> VLabelGraph<T> for PLGraph<T> {
+    type TupleIter<'a> = PLVIter<'a,T>
+    where
+        Self: 'a,
+        T: 'a;
+
+    fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> {
+        self.nodes
+            .get(node_id)
+            .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+            .map(|node| Some(node.label))
+    }
+
+    fn query_label(&self, label: T) -> Option<usize> {
+        self.label_index_map.get(&label).copied()
+    }
+
+    fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> {
+        PLVIter::try_new(self, node_id)
+    }
+}
+
 impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> {
     type Iter<'a> = std::iter::Empty<usize>
     where
diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs
index b01a13b..12d0e54 100644
--- a/graph/src/labelled/double.rs
+++ b/graph/src/labelled/double.rs
@@ -158,6 +158,7 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
         let mut file = std::fs::File::options()
             .write(true)
             .create(true)
+            .truncate(true)
             .open(&filename)?;
 
         use std::io::Write;
@@ -408,21 +409,12 @@ impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
                 if !set.contains(&label) {
                     flat.push((label, to));
                     by_target.get_mut(&to).unwrap().insert(label);
-                    by_label
-                        .entry(label)
-                        .or_insert_with(Default::default)
-                        .insert(to);
+                    by_label.entry(label).or_default().insert(to);
                 }
             } else {
                 flat.push((label, to));
-                by_target
-                    .entry(to)
-                    .or_insert_with(Default::default)
-                    .insert(label);
-                by_label
-                    .entry(label)
-                    .or_insert_with(Default::default)
-                    .insert(to);
+                by_target.entry(to).or_default().insert(label);
+                by_label.entry(label).or_default().insert(to);
             }
         }
 
diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs
index 13fd8c1..f0704e0 100644
--- a/graph/src/labelled/mod.rs
+++ b/graph/src/labelled/mod.rs
@@ -19,4 +19,7 @@ pub mod binary;
 pub use binary::{PLGBuilderMut, PLGraph};
 
 pub mod simple;
-pub use simple::{SLGBuilder, SLGraph};
+pub use simple::{
+    // SLGBuilder ,
+    SLGraph,
+};
diff --git a/graph/src/labelled/simple.rs b/graph/src/labelled/simple.rs
index b5388a9..5fb7641 100644
--- a/graph/src/labelled/simple.rs
+++ b/graph/src/labelled/simple.rs
@@ -8,49 +8,74 @@
 
 use super::*;
 
+use crate::VLabelGraph;
+
 #[derive(Debug, Clone)]
-struct SLNode<T: GraphLabel> {
-    children: Vec<(T, usize)>,
+struct SLNode<S: GraphLabel, T: GraphLabel> {
+    children: Box<[(T, usize)]>,
+    label: S,
 }
 
-impl<T: GraphLabel> Default for SLNode<T> {
+impl<S: GraphLabel + Default, T: GraphLabel> Default for SLNode<S, T> {
     fn default() -> Self {
         Self {
-            children: Vec::new(),
+            children: Box::new([]),
+            label: Default::default(),
         }
     }
 }
 
-impl<T: GraphLabel> SLNode<T> {
-    fn new(children: Vec<(T, usize)>) -> Self {
-        Self { children }
+impl<S: GraphLabel, T: GraphLabel> SLNode<S, T> {
+    #[allow(dead_code)]
+    fn new(children: Box<[(T, usize)]>, label: S) -> Self {
+        Self { children, label }
+    }
+
+    fn into_builder(self) -> SLBNode<S, T> {
+        let label = self.label;
+        let children = self.children.into_vec();
+
+        SLBNode { children, label }
+    }
+
+    fn to_builder(&self) -> SLBNode<S, T> {
+        let label = self.label;
+        let children = self.children.to_vec();
+
+        SLBNode { children, label }
     }
 }
 
 /// Simple Labelled Graph.
 #[derive(Debug, Clone)]
-pub struct SLGraph<T: GraphLabel> {
-    nodes: Vec<SLNode<T>>,
+pub struct SLGraph<S: GraphLabel, T: GraphLabel> {
+    nodes: Box<[SLNode<S, T>]>,
 }
 
-impl<T: GraphLabel> SLGraph<T> {
+impl<S: GraphLabel, T: GraphLabel> SLGraph<S, T> {
     /// Return a builder.
     #[inline]
-    pub fn builder(self) -> SLGBuilder<T> {
-        SLGBuilder(self)
+    pub fn builder(self) -> SLGBuilder<S, T> {
+        SLGBuilder {
+            nodes: <Box<[_]> as IntoIterator>::into_iter(self.nodes)
+                .map(SLNode::into_builder)
+                .collect(),
+        }
     }
 
     /// Return a builder from a reference.
     #[inline]
-    pub fn builder_ref(&self) -> SLGBuilder<T> {
-        SLGBuilder(self.clone())
+    pub fn builder_ref(&self) -> SLGBuilder<S, T> {
+        SLGBuilder {
+            nodes: self.nodes.iter().map(SLNode::to_builder).collect(),
+        }
     }
 }
 
-impl<T: GraphLabel> Default for SLGraph<T> {
+impl<S: GraphLabel, T: GraphLabel> Default for SLGraph<S, T> {
     #[inline]
     fn default() -> Self {
-        let nodes = Vec::new();
+        let nodes = Box::new([]);
 
         Self { nodes }
     }
@@ -89,9 +114,12 @@ impl<'a, T: GraphLabel> ExactSizeIterator for ChildrenIter<'a, T> {
     }
 }
 
-impl<T: GraphLabel> Graph for SLGraph<T> {
+impl<S: GraphLabel, T: GraphLabel> Graph for SLGraph<S, T> {
     // Not using a boxed pointer is supposed to save some allocations.
-    type Iter<'a> = ChildrenIter<'a, T> where T: 'a;
+    type Iter<'a> = ChildrenIter<'a, T>
+    where
+        T: 'a,
+        S:'a;
 
     #[inline]
     fn is_empty(&self) -> bool {
@@ -161,6 +189,10 @@ impl<T: GraphLabel> Graph for SLGraph<T> {
 
         let mut post = String::new();
 
+        for (node_id, node_label) in self.nodes.iter().map(|node| &node.label).enumerate() {
+            post.push_str(&format!("    {node_id} [label = \"{node_label}\"]\n"));
+        }
+
         for (source, target) in self.edges() {
             for label in self.edge_label(source, target).unwrap() {
                 post.push_str(&format!("    {source} -> {target} [label = \"{label}\"]\n"));
@@ -178,6 +210,7 @@ impl<T: GraphLabel> Graph for SLGraph<T> {
         let mut file = std::fs::File::options()
             .write(true)
             .create(true)
+            .truncate(true)
             .open(&filename)?;
 
         use std::io::Write;
@@ -193,7 +226,112 @@ impl<T: GraphLabel> Graph for SLGraph<T> {
     }
 }
 
-impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> {
+/// An iterator delegation for children, and labels of children, of
+/// nodes of `SLGraph`.
+#[derive(Debug, Clone)]
+pub struct VLChildrenIter<'a, S: GraphLabel, T: GraphLabel> {
+    iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>,
+    graph: &'a SLGraph<S, T>,
+}
+
+impl<'a, S: GraphLabel, T: GraphLabel> VLChildrenIter<'a, S, T> {
+    fn new(
+        iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>,
+        graph: &'a SLGraph<S, T>,
+    ) -> Self {
+        Self { iter, graph }
+    }
+}
+
+impl<'a, S: GraphLabel, T: GraphLabel> Iterator for VLChildrenIter<'a, S, T> {
+    type Item = (S, usize);
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().and_then(|(_, to)| {
+            let label = self.graph.nodes.get(to)?.label;
+            Some((label, to))
+        })
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a, S: GraphLabel, T: GraphLabel> ExactSizeIterator for VLChildrenIter<'a, S, T> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<S: GraphLabel, T: GraphLabel> VLabelGraph<S> for SLGraph<S, T> {
+    type TupleIter<'a> = VLChildrenIter<'a, S, T>
+    where
+        Self: 'a,
+        T:'a,
+        S: 'a;
+
+    fn vertex_label(&self, node_id: usize) -> Result<Option<S>, Error> {
+        Ok(Some(
+            self.nodes
+                .get(node_id)
+                .ok_or(Error::IndexOutOfBounds(node_id, self.nodes_len()))?
+                .label,
+        ))
+    }
+
+    fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> {
+        let iter = self
+            .nodes
+            .get(node_id)
+            .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))?
+            .children
+            .iter()
+            .copied();
+
+        Ok(Self::TupleIter::new(iter, self))
+    }
+}
+
+/// An iterator delegation for children of nodes of `SLGraph`.
+///
+/// This iterates through labels and targets of edges simultaneously.
+#[derive(Debug, Clone)]
+pub struct ELChildrenIter<'a, T: GraphLabel> {
+    iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>,
+}
+
+impl<'a, T: GraphLabel> ELChildrenIter<'a, T> {
+    fn new(iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>) -> Self {
+        Self { iter }
+    }
+}
+
+impl<'a, T: GraphLabel> Iterator for ELChildrenIter<'a, T> {
+    type Item = (T, usize);
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next()
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a, T: GraphLabel> ExactSizeIterator for ELChildrenIter<'a, T> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<S: GraphLabel, T: GraphLabel> LabelGraph<T> for SLGraph<S, T> {
     type Iter<'a> = std::iter::Empty<usize>
     where
         Self:'a,
@@ -204,7 +342,7 @@ impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> {
         Self: 'a,
         T: 'a;
 
-    type TupleIter<'a> = std::iter::Copied<std::slice::Iter<'a, (T, usize)>>
+    type TupleIter<'a> = ELChildrenIter<'a, T>
     where
         Self: 'a,
         T: 'a;
@@ -218,7 +356,7 @@ impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> {
         self.nodes
             .get(node_id)
             .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))
-            .map(|node| node.children.iter().copied())
+            .map(|node| ELChildrenIter::new(node.children.iter().copied()))
     }
 
     fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
@@ -276,9 +414,16 @@ impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> {
     }
 }
 
-impl<T: GraphLabel> LabelExtGraph<T> for SLGraph<T> {
-    #[inline]
-    fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error> {
+impl<S: GraphLabel, T: GraphLabel> SLGBuilder<S, T> {
+    /// Add a new node with `edges` and `label`.
+    ///
+    /// If an edge from `edges` points to a non-existent node, return
+    /// an error.
+    pub fn extend(
+        &mut self,
+        label: S,
+        edges: impl IntoIterator<Item = (T, usize)>,
+    ) -> Result<usize, Error> {
         let mut children = Vec::new();
 
         for (label, to) in edges {
@@ -289,7 +434,7 @@ impl<T: GraphLabel> LabelExtGraph<T> for SLGraph<T> {
             children.push((label, to));
         }
 
-        let new_node = SLNode::new(children);
+        let new_node = SLBNode::new(children, label);
         let new_index = self.nodes_len();
 
         self.nodes.push(new_node);
@@ -300,55 +445,326 @@ impl<T: GraphLabel> LabelExtGraph<T> for SLGraph<T> {
 
 // Builder for this implementation of graph
 
+/// The type of nodes for builders.
+#[derive(Debug, Clone)]
+struct SLBNode<S: GraphLabel, T: GraphLabel> {
+    children: Vec<(T, usize)>,
+    label: S,
+}
+
+impl<S: GraphLabel, T: GraphLabel> SLBNode<S, T> {
+    fn new(children: Vec<(T, usize)>, label: S) -> Self {
+        Self { children, label }
+    }
+
+    fn into_boxed(self) -> SLNode<S, T> {
+        let label = self.label;
+
+        let children = self.children.into_boxed_slice();
+        SLNode { children, label }
+    }
+}
+
 /// A builder for simple labelled graphs.
 #[derive(Debug, Clone)]
-pub struct SLGBuilder<T: GraphLabel>(SLGraph<T>);
+pub struct SLGBuilder<S: GraphLabel, T: GraphLabel> {
+    nodes: Vec<SLBNode<S, T>>,
+}
 
-impl<T: GraphLabel> Default for SLGBuilder<T> {
+impl<S: GraphLabel, T: GraphLabel> Default for SLGBuilder<S, T> {
     fn default() -> Self {
-        Self(Default::default())
+        Self { nodes: Vec::new() }
+    }
+}
+
+impl<S: GraphLabel, T: GraphLabel> Graph for SLGBuilder<S, T> {
+    // Not using a boxed pointer is supposed to save some allocations.
+    type Iter<'a> = ChildrenIter<'a, T>
+    where
+        T: 'a,
+        S:'a;
+
+    #[inline]
+    fn is_empty(&self) -> bool {
+        self.nodes.is_empty()
+    }
+
+    #[inline]
+    fn nodes_len(&self) -> usize {
+        self.nodes.len()
+    }
+
+    #[inline]
+    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(ChildrenIter::new(node.children.iter().copied())),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())),
+        }
+    }
+
+    #[inline]
+    /// Return the number of "children" of a node, or an error if the
+    /// node is not a member of the graph.
+    ///
+    /// This counts edges with different labels as different edges.
+    fn degree(&self, node_id: usize) -> Result<usize, Error> {
+        self.nodes
+            .get(node_id)
+            .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+            .map(|node| node.children.len())
+    }
+
+    #[inline]
+    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
+        self.nodes
+            .get(node_id)
+            .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+            .map(|node| node.children.is_empty())
+    }
+
+    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
+        match self.nodes.get(source) {
+            Some(source_node) => {
+                if self.nodes.get(target).is_none() {
+                    Err(Error::IndexOutOfBounds(target, self.nodes.len()))
+                } else {
+                    for (_, to) in source_node.children.iter() {
+                        if *to == target {
+                            return Ok(true);
+                        }
+                    }
+
+                    Ok(false)
+                }
+            }
+            None => Err(Error::IndexOutOfBounds(source, self.nodes.len())),
+        }
+    }
+
+    fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
+        let filename = format!("output/{filename}");
+
+        let preamble = "digraph nfa {
+    fontname=\"Helvetica,Arial,sans-serif\"
+    node [fontname=\"Helvetica,Arial,sans-serif\", ordering=out]
+    edge [fontname=\"Helvetica,Arial,sans-serif\"]
+    rankdir=LR;\n";
+
+        let mut post = String::new();
+
+        for (node_id, node_label) in self.nodes.iter().map(|node| &node.label).enumerate() {
+            post.push_str(&format!("    {node_id} [label = \"{node_label}\"]\n"));
+        }
+
+        for (source, target) in self.edges() {
+            for label in self.edge_label(source, target).unwrap() {
+                post.push_str(&format!("    {source} -> {target} [label = \"{label}\"]\n"));
+            }
+        }
+
+        post.push_str("}\n");
+
+        let result = format!("{preamble}{post}");
+
+        if std::fs::metadata(&filename).is_ok() {
+            std::fs::remove_file(&filename)?;
+        }
+
+        let mut file = std::fs::File::options()
+            .write(true)
+            .create(true)
+            .truncate(true)
+            .open(&filename)?;
+
+        use std::io::Write;
+
+        file.write_all(result.as_bytes())
+    }
+
+    #[inline]
+    fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
+        unimplemented!()
     }
 }
 
-impl<T: GraphLabel> Deref for SLGBuilder<T> {
-    type Target = SLGraph<T>;
+/// An iterator delegation for children, and labels of children, of
+/// nodes of `SLGBuilder`.
+#[derive(Debug, Clone)]
+pub struct VLBChildrenIter<'a, S: GraphLabel, T: GraphLabel> {
+    iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>,
+    builder: &'a SLGBuilder<S, T>,
+}
 
-    fn deref(&self) -> &Self::Target {
-        &self.0
+impl<'a, S: GraphLabel, T: GraphLabel> VLBChildrenIter<'a, S, T> {
+    fn new(
+        iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>,
+        builder: &'a SLGBuilder<S, T>,
+    ) -> Self {
+        Self { iter, builder }
     }
 }
 
-impl<T: GraphLabel> DerefMut for SLGBuilder<T> {
-    fn deref_mut(&mut self) -> &mut Self::Target {
-        &mut self.0
+impl<'a, S: GraphLabel, T: GraphLabel> Iterator for VLBChildrenIter<'a, S, T> {
+    type Item = (S, usize);
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().and_then(|(_, to)| {
+            let label = self.builder.nodes.get(to)?.label;
+            Some((label, to))
+        })
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a, S: GraphLabel, T: GraphLabel> ExactSizeIterator for VLBChildrenIter<'a, S, T> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.iter.len()
     }
 }
 
-impl<T: GraphLabel> Builder for SLGBuilder<T> {
-    type Label = T;
+impl<S: GraphLabel, T: GraphLabel> VLabelGraph<S> for SLGBuilder<S, T> {
+    type TupleIter<'a> = VLBChildrenIter<'a, S,T>
+    where
+        Self: 'a,
+        T:'a,
+        S: 'a;
+
+    fn vertex_label(&self, node_id: usize) -> Result<Option<S>, Error> {
+        Ok(Some(
+            self.nodes
+                .get(node_id)
+                .ok_or(Error::IndexOutOfBounds(node_id, self.nodes_len()))?
+                .label,
+        ))
+    }
 
-    type Result = SLGraph<T>;
+    fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> {
+        let iter = self
+            .nodes
+            .get(node_id)
+            .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))?
+            .children
+            .iter()
+            .copied();
+
+        Ok(Self::TupleIter::new(iter, self))
+    }
+}
+
+impl<S: GraphLabel, T: GraphLabel> LabelGraph<T> for SLGBuilder<S, T> {
+    type Iter<'a> = std::iter::Empty<usize>
+    where
+        Self:'a,
+        T:'a;
+
+    type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)>
+    where
+        Self: 'a,
+        T: 'a;
+
+    type TupleIter<'a> = ELChildrenIter<'a,T>
+    where
+        Self: 'a,
+        T: 'a;
+
+    type EdgeLabelIter<'a> = std::option::IntoIter<T>
+    where
+        Self: 'a,
+        T: 'a;
+
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> {
+        self.nodes
+            .get(node_id)
+            .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+            .map(|node| ELChildrenIter::new(node.children.iter().copied()))
+    }
+
+    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
+        let nodes_len = self.nodes.len();
+
+        if let Some(source_node) = self.nodes.get(source) {
+            if !(0..nodes_len).contains(&target) {
+                return Err(Error::IndexOutOfBounds(target, nodes_len));
+            }
+
+            for (label, end) in source_node.children.iter() {
+                if *end == target {
+                    return Ok(Some(*label).into_iter());
+                }
+            }
+
+            Ok(None.into_iter())
+        } else {
+            Err(Error::IndexOutOfBounds(source, nodes_len))
+        }
+    }
+
+    fn find_children_with_label(
+        &self,
+        _node_id: usize,
+        _label: &T,
+    ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error> {
+        unimplemented!("Unsupported operation")
+    }
+
+    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> {
+        unimplemented!("Unsupported operation")
+    }
 
     #[inline]
-    fn with_capacity(size: usize) -> Self {
-        Self(SLGraph {
+    fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error> {
+        let nodes_len = self.nodes.len();
+
+        match self.nodes.get(node_id) {
+            Some(node) => {
+                if target >= nodes_len {
+                    return Err(Error::IndexOutOfBounds(target, nodes_len));
+                }
+
+                for (edge_label, end) in node.children.iter() {
+                    if *edge_label == *label && *end == target {
+                        return Ok(true);
+                    }
+                }
+
+                Ok(false)
+            }
+            None => Err(Error::IndexOutOfBounds(node_id, nodes_len)),
+        }
+    }
+}
+
+impl<S: GraphLabel, T: GraphLabel> SLGBuilder<S, T> {
+    /// Return a builder with a fixed capacity.
+    #[inline]
+    pub fn with_capacity(size: usize) -> Self {
+        SLGBuilder {
             nodes: Vec::with_capacity(size),
-        })
+        }
     }
 
+    /// Add a vertex with a given label.
     #[inline]
-    fn add_vertex(&mut self) -> usize {
-        self.nodes.push(SLNode::default());
+    pub fn add_vertex(&mut self, label: S) -> usize {
+        self.nodes.push(SLBNode::new(Vec::new(), label));
         self.nodes.len() - 1
     }
 
+    /// Add vertices with an iterator of labels.
     #[inline]
-    fn add_vertices(&mut self, n: usize) {
+    pub fn add_vertices(&mut self, labels: impl Iterator<Item = S>) {
         self.nodes
-            .extend(std::iter::repeat_with(Default::default).take(n));
+            .extend(labels.map(|label| SLBNode::new(Vec::new(), label)));
     }
 
-    fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> {
+    /// Add an edge from the source to the target.
+    pub fn add_edge(&mut self, source: usize, target: usize, label: T) -> Result<(), Error> {
         let nodes_len = self.nodes.len();
 
         let source_node = self
@@ -365,14 +781,19 @@ impl<T: GraphLabel> Builder for SLGBuilder<T> {
         Ok(())
     }
 
-    fn remove_edge<F>(
+    /// Remove an edge from the source to the target.
+    ///
+    /// Since some graphs are labelled, the users are allowed to pass
+    /// a predicate to determine if an edge from the source to the
+    /// target should be removed.
+    pub fn remove_edge<F>(
         &mut self,
         source: usize,
         target: usize,
         mut predicate: F,
     ) -> Result<(), Error>
     where
-        F: FnMut(Self::Label) -> bool,
+        F: FnMut(T) -> bool,
     {
         let nodes_len = self.nodes.len();
 
@@ -392,12 +813,35 @@ impl<T: GraphLabel> Builder for SLGBuilder<T> {
         Ok(())
     }
 
-    fn build_ref(&self) -> Self::Result {
-        self.0.clone()
+    /// Convert the builder into a graph using a reference.
+    ///
+    /// This is similar to [`build`][Builder::build], but takes an
+    /// immutable reference of the builder, so that the builder can
+    /// still be used later on.
+    pub fn build_ref(&self) -> SLGraph<S, T> {
+        let nodes = self
+            .nodes
+            .clone()
+            .into_iter()
+            .map(SLBNode::into_boxed)
+            .collect::<Vec<_>>()
+            .into_boxed_slice();
+
+        SLGraph { nodes }
     }
 
-    fn build(self) -> Self::Result {
-        self.0
+    /// Convert the builder into a graph.
+    ///
+    /// This is the purpose of having a builder.
+    pub fn build(self) -> SLGraph<S, T> {
+        let nodes = self
+            .nodes
+            .into_iter()
+            .map(SLBNode::into_boxed)
+            .collect::<Vec<_>>()
+            .into_boxed_slice();
+
+        SLGraph { nodes }
     }
 }
 
@@ -408,15 +852,15 @@ mod simple_test {
     use std::collections::BTreeSet as Set;
 
     macro_rules! set {
-        () => { Set::<usize>::default() };
-        ($($num:literal),*) => {
-            {
-                let mut set: Set<usize> = Set::default();
-                $(set.insert($num);)*
-                set
-            }
-        };
-    }
+    () => { Set::<usize>::default() };
+    ($($num:literal),*) => {
+        {
+            let mut set: Set<usize> = Set::default();
+            $(set.insert($num);)*
+            set
+        }
+    };
+}
 
     // macro_rules! map {
     //     () => { Map::<usize, Set<usize>>::default() };
@@ -431,30 +875,36 @@ mod simple_test {
 
     #[test]
     fn test_graph_apis() -> Result<(), Error> {
-        let mut graph: SLGraph<usize> = Default::default();
+        let mut builder: SLGBuilder<usize, usize> = Default::default();
 
         // testing empty graph
-        assert!(graph.is_empty());
+        assert!(builder.is_empty());
 
         // testing adding an empty node
-        assert_eq!(graph.extend(std::iter::empty())?, 0);
+        assert_eq!(builder.extend(0, std::iter::empty())?, 0);
 
         // testing nodes_len
-        assert_eq!(graph.nodes_len(), 1);
+        assert_eq!(builder.nodes_len(), 1);
 
         // testing extension
 
-        assert_eq!(graph.extend([(0, 0)].iter().copied())?, 1);
-        assert_eq!(graph.extend([(1, 0), (1, 1)].iter().copied())?, 2);
-        assert_eq!(graph.extend([(3, 0), (3, 2)].iter().copied())?, 3);
-        assert_eq!(graph.extend([(1, 1), (1, 2)].iter().copied())?, 4);
-        assert_eq!(graph.extend([(2, 1), (3, 2), (2, 3)].iter().copied())?, 5);
+        assert_eq!(builder.extend(1, [(0, 0)].iter().copied())?, 1);
+        assert_eq!(builder.extend(2, [(1, 0), (1, 1)].iter().copied())?, 2);
+        assert_eq!(builder.extend(3, [(3, 0), (3, 2)].iter().copied())?, 3);
+        assert_eq!(builder.extend(4, [(1, 1), (1, 2)].iter().copied())?, 4);
+        assert_eq!(
+            builder.extend(5, [(2, 1), (3, 2), (2, 3)].iter().copied())?,
+            5
+        );
 
         // testing adding a duplicated edge set
-        assert_eq!(graph.extend([(2, 1), (2, 3), (3, 2)].iter().copied())?, 6);
-        assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 7);
+        assert_eq!(
+            builder.extend(6, [(2, 1), (2, 3), (3, 2)].iter().copied())?,
+            6
+        );
+        assert_eq!(builder.extend(7, [(3, 2), (3, 0)].iter().copied())?, 7);
 
-        let graph = graph;
+        let graph = builder.build();
 
         // ensuring the correct length
         assert_eq!(graph.nodes_len(), 8);
@@ -500,14 +950,10 @@ mod test_slgraph_builder {
 
     #[test]
     fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
-        let mut builder = SLGBuilder::<usize>::default();
+        let mut builder = SLGBuilder::<usize, usize>::default();
 
         // Add five nodes
-        builder.add_vertex();
-        builder.add_vertex();
-        builder.add_vertex();
-        builder.add_vertex();
-        builder.add_vertex();
+        builder.add_vertices(0..5);
 
         // Link each node to its successor and link the last node with
         // the first one to form a cycle.
@@ -529,14 +975,10 @@ mod test_slgraph_builder {
 
     #[test]
     fn test_errors() -> Result<(), Box<dyn std::error::Error>> {
-        let mut builder = SLGBuilder::default();
+        let mut builder = SLGBuilder::<usize, usize>::default();
 
         // Add five nodes
-        builder.add_vertex();
-        builder.add_vertex();
-        builder.add_vertex();
-        builder.add_vertex();
-        builder.add_vertex();
+        builder.add_vertices(0..5);
 
         // Errors in add_edge
 
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 058d62c..36fc545 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -22,6 +22,7 @@ pub use adlist::ALGraph;
 
 pub mod labelled;
 
+pub use labelled::simple::{SLGBuilder, SLGraph};
 pub use labelled::DLGraph;
 pub use labelled::PLGraph;
 
@@ -29,6 +30,8 @@ pub mod builder;
 
 pub use builder::Builder;
 
+pub mod dfs;
+
 use error::Error;
 
 /// The expected behaviour of an immutable graph.
@@ -138,6 +141,7 @@ pub trait Graph: Default {
         let mut file = std::fs::File::options()
             .write(true)
             .create(true)
+            .truncate(true)
             .open(filename)?;
 
         use std::io::Write;
@@ -290,8 +294,8 @@ pub trait RedirectGraph: Graph {
 /// This trait defines some convenient methods for accessing the
 /// labels of vertices.
 pub trait VLabelGraph<T: GraphLabel>: Graph {
-    /// A type that iterates through tuples of labels and targets of
-    /// edges.
+    /// A type that iterates through tuples of target labels and
+    /// target indices of edges.
     type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a
     where
         Self: 'a,
@@ -321,13 +325,55 @@ pub trait VLabelGraph<T: GraphLabel>: Graph {
     }
 
     /// Return an iterator of tuples of vertex labels and indices of
-    /// targets edges out of a node.
+    /// targets for edges out of a node.
     ///
     /// The name is a weird new word created to stand as a
     /// simplification of the phrase "vertex label and children of".
     fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error>;
 }
 
+/// A graph whose edges are associated with labels.
+///
+/// This trait defines some convenient methods for accessing the
+/// labels of edges.
+pub trait ELabelGraph<T: GraphLabel>: Graph {
+    /// A type that iterates through tuples of edge labels and target
+    /// indices of edges.
+    type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a
+    where
+        Self: 'a,
+        T: 'a;
+
+    #[inline]
+    /// Return the label of an edge or an error if the node is
+    /// invalid.
+    ///
+    /// The default implementation always returns `None` after
+    /// checking the validity of the edge.
+    fn edge_label(&self, from: usize, to: usize) -> Result<Option<T>, Error> {
+        self.has_edge(from, to).map(|_| None)
+    }
+
+    /// Return an iterator of tuples of edge labels and indices of
+    /// targets for edges out of a node.
+    ///
+    /// The name is a weird new word created to stand as a
+    /// simplification of the phrase "edge label and children of".
+    fn edlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error>;
+}
+
+impl<T: GraphLabel, G: LabelGraph<T>> ELabelGraph<T> for G {
+    type TupleIter<'a> = <G as LabelGraph<T>>::TupleIter<'a>
+    where
+        Self: 'a,
+        T: 'a;
+
+    #[inline]
+    fn edlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> {
+        LabelGraph::tuples_of(self, node_id)
+    }
+}
+
 /// A labelled graph is just a graph with labels associated to
 /// vertices and / or edges.
 ///