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.
 ///