a commit before the forst query

I think the main functionalities are already there, but the lack of
querying capabilities makes this not very useful at the moment.

This commit is right before an attempt to add this missing piece.

17 files changed, 1457 insertions, 8 deletions

diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs
index df61b6f..c6289f1 100644
--- a/chain/src/atom/default.rs
+++ b/chain/src/atom/default.rs
@@ -213,6 +213,11 @@ impl LabelGraph<LabelType<TNT>> for DefaultAtom {
     where
         Self: 'b;
 
+    type TupleIter<'b> = <DefaultNFA<LabelType<TNT>> as LabelGraph<LabelType<TNT>>>::TupleIter<'b>
+    where
+        Self: 'b,
+        DOption<TNT>: 'b;
+
     type LabelIter<'b> = <DefaultNFA<LabelType<TNT>> as LabelGraph<LabelType<TNT>>>::LabelIter<'b>
     where
         Self: 'b,
@@ -247,6 +252,11 @@ impl LabelGraph<LabelType<TNT>> for DefaultAtom {
     }
 
     #[inline]
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GraphError> {
+        self.nfa.tuples_of(node_id)
+    }
+
+    #[inline]
     fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, GraphError> {
         self.nfa.labels_of(node_id)
     }
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 85e3c8f..042f84e 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -324,6 +324,11 @@ impl LabelGraph<Edge> for DefaultChain {
     where
         Self: 'a;
 
+    type TupleIter<'a> = <DLGraph<Edge> as LabelGraph<Edge>>::TupleIter<'a>
+    where
+        Self: 'a,
+        Edge: 'a;
+
     type LabelIter<'a> = <DLGraph<Edge> as LabelGraph<Edge>>::LabelIter<'a>
     where
         Self: 'a,
@@ -349,6 +354,11 @@ impl LabelGraph<Edge> for DefaultChain {
     }
 
     #[inline]
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
+        self.graph.tuples_of(node_id)
+    }
+
+    #[inline]
     fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
         self.graph.labels_of(node_id)
     }
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 01e463e..f532805 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -127,6 +127,11 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> {
     where
         Self: 'a;
 
+    type TupleIter<'a> = std::iter::Empty<(T, usize)>
+    where
+        Self: 'a,
+        T: 'a;
+
     type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)>
     where
         Self: 'a,
@@ -163,6 +168,10 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> {
         unimplemented!("edges have no labels")
     }
 
+    fn tuples_of(&self, _node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
+        unimplemented!("edges have no labels")
+    }
+
     fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
         unimplemented!("edges have no labels")
     }
diff --git a/forest/Cargo.toml b/forest/Cargo.toml
index 5702265..7944bc4 100644
--- a/forest/Cargo.toml
+++ b/forest/Cargo.toml
@@ -13,6 +13,7 @@ test-print-viz = []
 
 [dependencies]
 graph = { path = "../graph" }
+graph_macro = { path = "../graph_macro" }
 grammar = { path = "../grammar" }
 
 # This should be integrated in the package, but it is not yet done.
\ No newline at end of file
diff --git a/forest/src/bytes.rs b/forest/src/bytes.rs
index 951abad..d0d7e1e 100644
--- a/forest/src/bytes.rs
+++ b/forest/src/bytes.rs
@@ -78,6 +78,9 @@
 
 use super::Forest;
 use grammar::{GrammarLabel, GrammarLabelType, TNT};
+use graph::error::Error as GError;
+
+use std::array::TryFromSliceError;
 
 /// Convert any type that implements the `Forest` trait into a
 /// sequence of bytes.
@@ -174,3 +177,280 @@ pub fn forest_to_bytes<F: Forest<GrammarLabel>>(forest: &F) -> Vec<u8> {
 
     bytes
 }
+
+/// The type of a forest that is represented as a sequence of bytes.
+#[derive(Debug, Clone, Default)]
+pub struct BytesForest {
+    /// The sequence of bytes.
+    bytes: Vec<u8>,
+    /// The number of nodes.
+    nodes_len: usize,
+    /// The offset of labels
+    offset: usize,
+}
+
+/// The errors encountered when parsing a sequence of bytes into a
+/// forest.
+#[derive(Debug)]
+pub enum BytesError {
+    /// File size and forest length do not match.
+    LengthNotMatched(usize, usize),
+    /// The underlying sequence has the wrong length.
+    WrongBytesLen(usize, usize),
+    /// The file is too small.
+    TooSmall(usize, usize),
+    /// The special mark at the beginning is corrupted.
+    SpecialCorrupted(u8, u8, u8),
+    /// An error occurs during conversion of slices.
+    WrongSliceConversion(TryFromSliceError),
+    /// The data indicates a wrong offset.
+    InvalidOffset(usize, usize),
+    /// Wrong node index.
+    WrongNodeIndex(usize, usize),
+}
+
+impl std::fmt::Display for BytesError {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Self::WrongBytesLen(wrong, correct) => write!(
+                f,
+                "the sequence has length {wrong} but should have length {correct}"
+            ),
+            Self::LengthNotMatched(file, forest) => write!(
+                f,
+                "the file size is {file}, but the file indicates that the size should be {forest}"
+            ),
+            Self::TooSmall(len, threshold) => {
+                write!(f, "the file size {len} is less than {threshold} bytes")
+            }
+            Self::SpecialCorrupted(a, b, c) => {
+                write!(f, "the special mark is [{a}, {b}, {c}] which is wrong")
+            }
+            Self::WrongSliceConversion(e) => {
+                write!(f, "error during slice conversion: {e}")
+            }
+            Self::InvalidOffset(offset, len) => write!(
+                f,
+                "Data says offset = {offset} but the total length is {len}"
+            ),
+            Self::WrongNodeIndex(index, len) => write!(
+                f,
+                "node index {index} is greater than or equal to the length {len} of nodes"
+            ),
+        }
+    }
+}
+
+impl From<TryFromSliceError> for BytesError {
+    fn from(value: TryFromSliceError) -> Self {
+        Self::WrongSliceConversion(value)
+    }
+}
+
+impl std::error::Error for BytesError {}
+
+impl TryFrom<Vec<u8>> for BytesForest {
+    type Error = BytesError;
+
+    fn try_from(bytes: Vec<u8>) -> Result<Self, Self::Error> {
+        let forest_len = bytes.len();
+
+        if forest_len < 27 {
+            return Err(BytesError::TooSmall(forest_len, 27));
+        }
+
+        let indicated_len = usize::from_be_bytes((&bytes[..8]).try_into()?);
+
+        if forest_len != indicated_len {
+            return Err(BytesError::LengthNotMatched(forest_len, indicated_len));
+        }
+
+        let nodes_len = usize::from_be_bytes((&bytes[11..19]).try_into()?);
+
+        let special_marks = &bytes[8..11];
+
+        if special_marks != [114, 101, 112] {
+            return Err(BytesError::SpecialCorrupted(
+                special_marks[0],
+                special_marks[1],
+                special_marks[2],
+            ));
+        }
+
+        let offset = usize::from_be_bytes((&bytes[19..27]).try_into()?);
+
+        let threshold = std::cmp::max(offset + 34 * nodes_len, 27 + 16 * nodes_len);
+
+        if forest_len < threshold {
+            return Err(BytesError::TooSmall(forest_len, threshold));
+        }
+
+        let mut total_degree = 0usize;
+
+        for node in 0..nodes_len {
+            let degree =
+                usize::from_be_bytes((&bytes[(27 + 16 * node)..(35 + 16 * node)]).try_into()?);
+
+            total_degree += degree;
+        }
+
+        let total_degree = total_degree;
+
+        let correct_len: usize = 27 + 50 * nodes_len + 8 * total_degree;
+
+        if forest_len != correct_len {
+            return Err(BytesError::WrongBytesLen(forest_len, correct_len));
+        }
+
+        for node in 0..nodes_len {
+            let degree =
+                usize::from_be_bytes((&bytes[(27 + 16 * node)..(35 + 16 * node)]).try_into()?);
+
+            let node_offset =
+                usize::from_be_bytes((&bytes[(35 + 16 * node)..(43 + 16 * node)]).try_into()?);
+
+            if forest_len <= node_offset + 8 * degree {
+                return Err(BytesError::InvalidOffset(node_offset, forest_len));
+            }
+
+            for n in 0..degree {
+                let target = usize::from_be_bytes(
+                    (&bytes[(node_offset + 8 * n)..(node_offset + 8 * n + 8)]).try_into()?,
+                );
+
+                if nodes_len <= target {
+                    return Err(BytesError::WrongNodeIndex(target, nodes_len));
+                }
+            }
+        }
+
+        Ok(Self {
+            bytes,
+            nodes_len,
+            offset,
+        })
+    }
+}
+
+/// The delegation of iterators for children of nodes.
+#[derive(Debug, Clone)]
+pub struct BytesChildrenIter<'a> {
+    vec: &'a [u8],
+    offset: usize,
+    degree: usize,
+    current: usize,
+}
+
+impl<'a> Iterator for BytesChildrenIter<'a> {
+    type Item = usize;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.current + 1 >= self.degree {
+            return None;
+        }
+
+        let len = self.vec.len();
+
+        if self.offset + 8 * self.degree > len {
+            dbg!();
+            return None;
+        }
+
+        Some(usize::from_be_bytes(
+            (&self.vec[(self.offset + 8 * self.current)..(self.offset + 8 * self.current + 8)])
+                .try_into()
+                .ok()?,
+        ))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.degree, Some(self.degree))
+    }
+}
+
+impl<'a> ExactSizeIterator for BytesChildrenIter<'a> {
+    fn len(&self) -> usize {
+        self.degree
+    }
+}
+
+impl graph::Graph for BytesForest {
+    type Iter<'a> = BytesChildrenIter<'a>
+    where
+        Self: 'a;
+
+    fn is_empty(&self) -> bool {
+        self.bytes.is_empty()
+    }
+
+    fn nodes_len(&self) -> usize {
+        self.nodes_len
+    }
+
+    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> {
+        if node_id >= self.nodes_len {
+            return Err(GError::IndexOutOfBounds(node_id, self.nodes_len));
+        }
+
+        let degree = usize::from_be_bytes(
+            (&self.bytes[(27 + 16 * node_id)..(35 + 16 * node_id)])
+                .try_into()
+                .unwrap(),
+        );
+
+        let offset = usize::from_be_bytes(
+            (&self.bytes[(35 + 16 * node_id)..(43 + 16 * node_id)])
+                .try_into()
+                .unwrap(),
+        );
+
+        let current = 0;
+
+        let vec = &self.bytes;
+
+        Ok(BytesChildrenIter {
+            vec,
+            offset,
+            degree,
+            current,
+        })
+    }
+
+    fn degree(&self, node_id: usize) -> Result<usize, GError> {
+        if node_id >= self.nodes_len {
+            return Err(GError::IndexOutOfBounds(node_id, self.nodes_len));
+        }
+
+        let degree = usize::from_be_bytes(
+            (&self.bytes[(27 + 16 * node_id)..(35 + 16 * node_id)])
+                .try_into()
+                .unwrap(),
+        );
+
+        Ok(degree)
+    }
+
+    fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> {
+        Ok(self.degree(node_id)? == 0)
+    }
+
+    fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> {
+        for child in self.children_of(source)? {
+            if child == target {
+                return Ok(true);
+            }
+        }
+
+        Ok(false)
+    }
+
+    fn replace_by_builder(&mut self, builder: impl graph::Builder<Result = Self>) {
+        let result = builder.build();
+
+        self.nodes_len = result.nodes_len;
+        self.offset = result.offset;
+        self.bytes = result.bytes;
+    }
+}
+
+// TODO: Implement labelgraph
diff --git a/forest/src/iter/mod.rs b/forest/src/iter/mod.rs
new file mode 100644
index 0000000..49aa4f1
--- /dev/null
+++ b/forest/src/iter/mod.rs
@@ -0,0 +1,91 @@
+//! This module defines the expected behaviours of "iterators of
+//! forests", or "walkers of forests".  Moreover, an implementation
+//! that provides querying capabilities is provided.
+
+use super::*;
+
+/// The state of the iterator.
+#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+pub enum State {
+    /// The iterator goes to the next state.
+    Continue,
+    /// The iterator cannot proceed anymore.
+    Finish,
+    /// The iterator finishes for this tree, but there are trees not
+    /// visited yet.
+    ChangeBranch,
+}
+
+impl std::fmt::Display for State {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
+        use State::*;
+        match self {
+            Continue => write!(f, "next"),
+            Finish => write!(f, "finished"),
+            ChangeBranch => write!(
+                f,
+                "this branch is finished, but there are unvisited branches"
+            ),
+        }
+    }
+}
+
+/// An iterator is able to walk any forest, so no forest type is
+/// associated with iterators.  Essentially speaking, an iterator just
+/// provides the abilities to iterate through nodes of forests which
+/// meet certain conditions, in certain orders.
+pub trait ForestIter: Default {
+    /// Return the currenty visited node.
+    ///
+    /// If the iterator is not visiting any node, return `None`.
+    ///
+    /// The default implementation always returns `None`.
+    fn current(&self) -> Option<usize> {
+        None
+    }
+
+    /// The type of labels that can be iterated by this iterator.
+    type ForestLabel: GraphLabel;
+
+    /// The type of objects of iteration.
+    type Item<'a>: Default
+    where
+        Self: 'a;
+
+    /// The type of iteration errors.
+    type Error: std::error::Error + From<graph::error::Error>;
+
+    /// Walk to the next node according to this iterator.
+    ///
+    /// `forest` is any type that implements the `Forest` trait.
+    /// Theoretically, the forest can be different in two calls of
+    /// this method.  This makes it somehow more flexible.
+    ///
+    /// `root` specifies the root of the sub-forest to iterate.
+    ///
+    /// Of course this flexibility is not the main reason for the
+    /// design.  My purpose is to decouple the iterator from the
+    /// forest, so that the iterator can be as simple as a wrapper of
+    /// a vector of unsigned integers.
+    ///
+    /// The default implementation is lazy and always returns
+    /// "finished".
+    fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error>
+    where
+        F: LabelGraph<ForestLabel<Self::ForestLabel>>,
+    {
+        // just to silence the compiler
+        let _f = forest;
+        let _r = root;
+
+        Ok(State::Finish)
+    }
+
+    /// Reset the progress of this iterator so that it can be used to
+    /// iterate any forest again.
+    ///
+    /// The default implementation does nothing.
+    fn clear(&mut self) {}
+}
+
+pub mod query;
diff --git a/forest/src/iter/query.rs b/forest/src/iter/query.rs
new file mode 100644
index 0000000..aff8eef
--- /dev/null
+++ b/forest/src/iter/query.rs
@@ -0,0 +1,372 @@
+//! This module implements an iterator of forests, which provides
+//! querying capabilities.
+
+use super::*;
+
+use graph::{error::Error as GError, labelled::SLGraph, Graph};
+
+use graph_macro::Graph;
+
+/// The label of a query graph.
+///
+/// Such a label is responsible for matching forest labels.
+pub trait QueryLabel: GraphLabel {
+    /// The type of labels this matches against.
+    type Obj: GraphLabel;
+
+    /// Determine whether or not a label matches this query label.
+    fn matches(&self, label: Self::Obj, status: ForestLabelType) -> bool {
+        let _ = label;
+        let _ = status;
+
+        false
+    }
+
+    /// Perform the query for one single query label.
+    fn run<F>(
+        &self,
+        forest: &F,
+        node: usize,
+        packs: &mut Vec<(usize, usize)>,
+    ) -> Result<Option<usize>, QRError>
+    where
+        F: LabelGraph<ForestLabel<<Self as QueryLabel>::Obj>>,
+    {
+        let mut dfs_stack: Vec<usize> = vec![node];
+
+        let nodes_len = forest.nodes_len();
+
+        while let Some(node) = dfs_stack.pop() {
+            let label = match forest.vertex_label(node) {
+                Ok(None) => return Err(QRError::NodeNoLabel(node)),
+                Err(_) => return Err(QRError::IndexOutOfBounds(node, nodes_len)),
+                Ok(Some(label)) => label,
+            };
+
+            let status = label.status();
+            let label = label.label();
+
+            if status == ForestLabelType::Packed {
+                packs.push((node, 0));
+
+                dfs_stack.extend(forest.children_of(node).unwrap().take(1));
+
+                continue;
+            }
+
+            if self.matches(label, status) {
+                return Ok(Some(node));
+            }
+
+            dfs_stack.extend(
+                forest
+                    .children_of(node)
+                    .unwrap()
+                    .collect::<Vec<_>>()
+                    .into_iter()
+                    .rev(),
+            );
+        }
+
+        Ok(None)
+    }
+}
+
+/// How should the current query skip nodes
+#[derive(Debug, Clone, Copy, Default, Ord, PartialOrd, Hash, Eq, PartialEq)]
+pub enum SkipState {
+    /// Skip anything in the depth-first search
+    Any,
+    /// Skip siblings
+    Sibling,
+    /// Do not skip
+    #[default]
+    None,
+}
+
+impl std::fmt::Display for SkipState {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Self::Any => write!(f, "skip anything"),
+            Self::Sibling => write!(f, "skip siblings"),
+            Self::None => write!(f, "no skipping"),
+        }
+    }
+}
+
+impl From<bool> for SkipState {
+    fn from(value: bool) -> Self {
+        if value {
+            Self::Sibling
+        } else {
+            Self::None
+        }
+    }
+}
+
+/// The type that represents queries as dependency graphs of query
+/// labels.
+///
+/// The labels of vertices are query labels that match against forest
+/// labels, whereas the labels of graphs indicate whether or not the
+/// edge should allow skipping siblings before matching.
+#[derive(Debug, Clone, Graph)]
+pub struct Query<T: QueryLabel> {
+    graph: SLGraph<SkipState>,
+    vertex_labels: Vec<T>,
+    root: Option<usize>,
+}
+
+impl<T: QueryLabel> Query<T> {
+    /// Construct a new query from raw fields.
+    pub fn new(graph: SLGraph<SkipState>, vertex_labels: Vec<T>, root: Option<usize>) -> Self {
+        Self {
+            graph,
+            vertex_labels,
+            root,
+        }
+    }
+
+    /// Return the root of this query.
+    ///
+    /// This returns `None` if and only if the graph is empty.
+    pub fn root(&self) -> Option<usize> {
+        self.root
+    }
+
+    /// Return the label of the given node.
+    ///
+    /// This cannot be implemented as a method of the `LabelGraph`
+    /// trait as the type differs from that of the labels.
+    #[inline]
+    pub fn label_of_vertex(&self, node: usize) -> Result<T, GError> {
+        self.vertex_labels
+            .get(node)
+            .copied()
+            .ok_or(GError::IndexOutOfBounds(node, self.vertex_labels.len()))
+    }
+}
+
+impl<T: QueryLabel> Default for Query<T> {
+    fn default() -> Self {
+        let graph = Default::default();
+        let vertex_labels = Vec::new();
+        let root = None;
+
+        Self {
+            graph,
+            vertex_labels,
+            root,
+        }
+    }
+}
+
+// delegation of labelgraph
+
+impl<T: QueryLabel> LabelGraph<SkipState> for Query<T> {
+    type Iter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::Iter<'a>
+    where
+        Self: 'a;
+
+    type TupleIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::TupleIter<'a>
+    where
+        Self: 'a;
+
+    type LabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::LabelIter<'a>
+    where
+        Self: 'a;
+
+    type EdgeLabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::EdgeLabelIter<'a>
+    where
+        Self: 'a;
+
+    #[inline]
+    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> {
+        self.graph.edge_label(source, target)
+    }
+
+    fn find_children_with_label(
+        &self,
+        _node_id: usize,
+        _label: &SkipState,
+    ) -> Result<<Self as LabelGraph<SkipState>>::Iter<'_>, GError> {
+        unimplemented!("Unsupported operation")
+    }
+
+    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
+        unimplemented!("Unsupported operation")
+    }
+
+    #[inline]
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
+        self.graph.tuples_of(node_id)
+    }
+
+    #[inline]
+    fn has_edge_label(
+        &self,
+        node_id: usize,
+        label: &SkipState,
+        target: usize,
+    ) -> Result<bool, GError> {
+        self.graph.has_edge_label(node_id, label, target)
+    }
+}
+
+#[derive(Debug, Clone)]
+/// The type of errors that can occur when querying forests.
+pub enum QRError {
+    /// AN index is out of bounds.
+    IndexOutOfBounds(usize, usize),
+    /// A node has no labels while it is required to have one.
+    NodeNoLabel(usize),
+    /// Encounter an invalid error in converting from an error of
+    /// graphs.
+    InvalidGraphError(GError),
+}
+
+impl std::fmt::Display for QRError {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            QRError::IndexOutOfBounds(n, b) => {
+                write!(f, "index {n} out of bound {b}")
+            }
+            QRError::NodeNoLabel(n) => write!(f, "the node {n} has no label but should have one"),
+            QRError::InvalidGraphError(g) => {
+                write!(f, "an invalid error for forest iterators: {g}")
+            }
+        }
+    }
+}
+
+impl std::error::Error for QRError {}
+
+impl From<GError> for QRError {
+    fn from(value: GError) -> Self {
+        match value {
+            GError::IndexOutOfBounds(n, b) => Self::IndexOutOfBounds(n, b),
+            _ => Self::InvalidGraphError(value),
+        }
+    }
+}
+
+/// An implementation of the forest iterator for querying purposes.
+#[derive(Debug, Clone)]
+pub struct QRun<T: QueryLabel> {
+    /// The currently visited node.
+    current: Option<usize>,
+    /// The queries dependency graph.
+    query: Query<T>,
+    /// The packed nodes that can be used to change to another branch
+    /// if needed.
+    packs: Vec<usize>,
+}
+
+impl<T: QueryLabel> Default for QRun<T> {
+    fn default() -> Self {
+        let current = Default::default();
+        let query = Default::default();
+        let packs = Default::default();
+
+        Self {
+            current,
+            query,
+            packs,
+        }
+    }
+}
+
+impl<T: QueryLabel> ForestIter for QRun<T> {
+    #[inline]
+    fn current(&self) -> Option<usize> {
+        self.current
+    }
+
+    type ForestLabel = <T as QueryLabel>::Obj;
+
+    type Item<'a> = Option<&'a [usize]>
+    where
+        Self: 'a;
+
+    type Error = QRError;
+
+    #[allow(unused)]
+    #[allow(clippy::collapsible_if)]
+    fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error>
+    where
+        F: LabelGraph<ForestLabel<Self::ForestLabel>>,
+    {
+        let query_root = if let Some(r) = self.query.root() {
+            r
+        } else {
+            return Ok(State::Finish);
+        };
+
+        #[derive(Debug, Clone, Copy)]
+        enum Item<T: Copy + Clone + std::fmt::Debug> {
+            Seen(T),
+            Unseen(T),
+        }
+
+        use Item::*;
+
+        impl<T: Copy + Clone + std::fmt::Debug> Item<T> {
+            fn is_seen(self) -> bool {
+                matches!(self, Self::Seen(_))
+            }
+
+            fn value(&self) -> T {
+                match self {
+                    Seen(v) => *v,
+                    Unseen(v) => *v,
+                }
+            }
+        }
+
+        let query_len = self.query.nodes_len();
+
+        let mut stack: Vec<Item<(SkipState, usize, usize)>> = Vec::with_capacity(query_len);
+
+        stack.push(Unseen((SkipState::Any, root, query_root)));
+
+        let mut parents_stack: Vec<usize> = Vec::with_capacity(query_len);
+
+        let mut match_result = false;
+
+        while let Some(item) = stack.pop() {
+            if item.is_seen() {
+                if match_result {
+                    continue;
+                }
+
+                // fallback
+            }
+
+            let (state, top, qtop) = item.value();
+
+            let top_label = forest.vertex_label(top)?.ok_or(QRError::NodeNoLabel(top))?;
+
+            let query_label = self.query.label_of_vertex(qtop)?;
+
+            if query_label.matches(top_label.label(), top_label.status()) {
+                // Success branch
+
+                match_result = true;
+
+                // TODO: Deal with captures later
+            } else {
+                // Failure branch
+
+                match_result = false;
+            }
+        }
+
+        todo!()
+    }
+
+    #[inline]
+    fn clear(&mut self) {
+        self.current.take();
+        self.packs.clear();
+    }
+}
diff --git a/forest/src/lib.rs b/forest/src/lib.rs
index a888fae..c3ee706 100644
--- a/forest/src/lib.rs
+++ b/forest/src/lib.rs
@@ -220,3 +220,5 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
 pub mod bytes;
 
 pub use bytes::forest_to_bytes;
+
+pub mod iter;
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index 5120522..862f25b 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -420,6 +420,11 @@ impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> {
         Self: 'a,
         T: 'a;
 
+    type TupleIter<'a> = std::iter::Empty<(T, usize)>
+    where
+        Self: 'a,
+        T: 'a;
+
     #[inline]
     fn query_label(&self, label: T) -> Option<usize> {
         self.label_index_map.get(&label).copied()
@@ -446,6 +451,10 @@ impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> {
         unimplemented!("Edges have no labels")
     }
 
+    fn tuples_of(&self, _node_id: usize) -> Result<Self::TupleIter<'_>, Error> {
+        unimplemented!("Edges have no labels")
+    }
+
     fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> {
         unimplemented!("Edges have no labels")
     }
diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs
index a641c74..b01a13b 100644
--- a/graph/src/labelled/double.rs
+++ b/graph/src/labelled/double.rs
@@ -319,6 +319,8 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
         Self: 'a,
         T: 'a;
 
+    type TupleIter<'a> = std::iter::Copied<std::slice::Iter<'a, (T, usize)>> where Self: 'a, T:'a;
+
     fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
         if self.has_edge(source, target)? {
             Ok(EdgeLabelIter::new(
@@ -353,6 +355,14 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
     }
 
     #[inline]
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(node.flat.iter().copied()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())),
+        }
+    }
+
+    #[inline]
     fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error> {
         match self.nodes.get(node_id) {
             Some(node) => Ok(Self::LabelIter::new(node.by_label.iter())),
diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs
index fb7b405..13fd8c1 100644
--- a/graph/src/labelled/mod.rs
+++ b/graph/src/labelled/mod.rs
@@ -17,3 +17,6 @@ pub use double::{DLGBuilder, DLGraph};
 
 pub mod binary;
 pub use binary::{PLGBuilderMut, PLGraph};
+
+pub mod simple;
+pub use simple::{SLGBuilder, SLGraph};
diff --git a/graph/src/labelled/simple.rs b/graph/src/labelled/simple.rs
new file mode 100644
index 0000000..b5388a9
--- /dev/null
+++ b/graph/src/labelled/simple.rs
@@ -0,0 +1,579 @@
+//! This file implements a simple labelled graph without extra
+//! functionalities.
+//!
+//! Neither the method
+//! [`find_children_with_label`][crate::LabelGraph::find_children_with_label]
+//! nor the method [`labels_of`][crate::LabelGraph::labels_of] are
+//! implemented efficiently.
+
+use super::*;
+
+#[derive(Debug, Clone)]
+struct SLNode<T: GraphLabel> {
+    children: Vec<(T, usize)>,
+}
+
+impl<T: GraphLabel> Default for SLNode<T> {
+    fn default() -> Self {
+        Self {
+            children: Vec::new(),
+        }
+    }
+}
+
+impl<T: GraphLabel> SLNode<T> {
+    fn new(children: Vec<(T, usize)>) -> Self {
+        Self { children }
+    }
+}
+
+/// Simple Labelled Graph.
+#[derive(Debug, Clone)]
+pub struct SLGraph<T: GraphLabel> {
+    nodes: Vec<SLNode<T>>,
+}
+
+impl<T: GraphLabel> SLGraph<T> {
+    /// Return a builder.
+    #[inline]
+    pub fn builder(self) -> SLGBuilder<T> {
+        SLGBuilder(self)
+    }
+
+    /// Return a builder from a reference.
+    #[inline]
+    pub fn builder_ref(&self) -> SLGBuilder<T> {
+        SLGBuilder(self.clone())
+    }
+}
+
+impl<T: GraphLabel> Default for SLGraph<T> {
+    #[inline]
+    fn default() -> Self {
+        let nodes = Vec::new();
+
+        Self { nodes }
+    }
+}
+
+/// An iterator delegation for children of nodes of `SLGraph`.
+#[derive(Debug, Clone)]
+pub struct ChildrenIter<'a, T: GraphLabel> {
+    iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>,
+}
+
+impl<'a, T: GraphLabel> ChildrenIter<'a, T> {
+    fn new(iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>) -> Self {
+        Self { iter }
+    }
+}
+
+impl<'a, T: GraphLabel> Iterator for ChildrenIter<'a, T> {
+    type Item = usize;
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(|(_, to)| to)
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a, T: GraphLabel> ExactSizeIterator for ChildrenIter<'a, T> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<T: GraphLabel> Graph for SLGraph<T> {
+    // Not using a boxed pointer is supposed to save some allocations.
+    type Iter<'a> = ChildrenIter<'a, T> where T: '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 (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)
+            .open(&filename)?;
+
+        use std::io::Write;
+
+        file.write_all(result.as_bytes())
+    }
+
+    #[inline]
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) {
+        let new_graph = builder.build();
+
+        self.nodes = new_graph.nodes;
+    }
+}
+
+impl<T: GraphLabel> LabelGraph<T> for SLGraph<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> = std::iter::Copied<std::slice::Iter<'a, (T, usize)>>
+    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| 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 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<T: GraphLabel> LabelExtGraph<T> for SLGraph<T> {
+    #[inline]
+    fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error> {
+        let mut children = Vec::new();
+
+        for (label, to) in edges {
+            if !self.has_node(to) {
+                return Err(Error::IndexOutOfBounds(to, self.nodes.len()));
+            }
+
+            children.push((label, to));
+        }
+
+        let new_node = SLNode::new(children);
+        let new_index = self.nodes_len();
+
+        self.nodes.push(new_node);
+
+        Ok(new_index)
+    }
+}
+
+// Builder for this implementation of graph
+
+/// A builder for simple labelled graphs.
+#[derive(Debug, Clone)]
+pub struct SLGBuilder<T: GraphLabel>(SLGraph<T>);
+
+impl<T: GraphLabel> Default for SLGBuilder<T> {
+    fn default() -> Self {
+        Self(Default::default())
+    }
+}
+
+impl<T: GraphLabel> Deref for SLGBuilder<T> {
+    type Target = SLGraph<T>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl<T: GraphLabel> DerefMut for SLGBuilder<T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+impl<T: GraphLabel> Builder for SLGBuilder<T> {
+    type Label = T;
+
+    type Result = SLGraph<T>;
+
+    #[inline]
+    fn with_capacity(size: usize) -> Self {
+        Self(SLGraph {
+            nodes: Vec::with_capacity(size),
+        })
+    }
+
+    #[inline]
+    fn add_vertex(&mut self) -> usize {
+        self.nodes.push(SLNode::default());
+        self.nodes.len() - 1
+    }
+
+    #[inline]
+    fn add_vertices(&mut self, n: usize) {
+        self.nodes
+            .extend(std::iter::repeat_with(Default::default).take(n));
+    }
+
+    fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> {
+        let nodes_len = self.nodes.len();
+
+        let source_node = self
+            .nodes
+            .get_mut(source)
+            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;
+
+        if !(0..nodes_len).contains(&target) {
+            return Err(Error::IndexOutOfBounds(target, nodes_len));
+        }
+
+        source_node.children.push((label, target));
+
+        Ok(())
+    }
+
+    fn remove_edge<F>(
+        &mut self,
+        source: usize,
+        target: usize,
+        mut predicate: F,
+    ) -> Result<(), Error>
+    where
+        F: FnMut(Self::Label) -> bool,
+    {
+        let nodes_len = self.nodes.len();
+
+        let source_node = self
+            .nodes
+            .get_mut(source)
+            .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;
+
+        if !(0..nodes_len).contains(&target) {
+            return Err(Error::IndexOutOfBounds(target, nodes_len));
+        }
+
+        source_node
+            .children
+            .retain(|(label, end)| !(*end == target && predicate(*label)));
+
+        Ok(())
+    }
+
+    fn build_ref(&self) -> Self::Result {
+        self.0.clone()
+    }
+
+    fn build(self) -> Self::Result {
+        self.0
+    }
+}
+
+#[cfg(test)]
+mod simple_test {
+    use super::*;
+
+    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
+            }
+        };
+    }
+
+    // macro_rules! map {
+    //     () => { Map::<usize, Set<usize>>::default() };
+    //     ($(($key:literal, $value:expr)),*) => {
+    //         {
+    //             let mut map: Map<usize, Set<usize>> = Map::default();
+    //             $(map.insert($key, $value);)*
+    //             map
+    //         }
+    //     };
+    // }
+
+    #[test]
+    fn test_graph_apis() -> Result<(), Error> {
+        let mut graph: SLGraph<usize> = Default::default();
+
+        // testing empty graph
+        assert!(graph.is_empty());
+
+        // testing adding an empty node
+        assert_eq!(graph.extend(std::iter::empty())?, 0);
+
+        // testing nodes_len
+        assert_eq!(graph.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);
+
+        // 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);
+
+        let graph = graph;
+
+        // ensuring the correct length
+        assert_eq!(graph.nodes_len(), 8);
+
+        // testing children_of
+        assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2));
+
+        // testing find_children_with_label
+        assert!(std::panic::catch_unwind(|| { graph.find_children_with_label(5, &2) }).is_err());
+
+        // testing edge_label
+        assert_eq!(graph.edge_label(5, 2)?.collect::<Set<_>>(), set!(3));
+        assert!(matches!(
+            graph.edge_label(8, 2),
+            Err(Error::IndexOutOfBounds(8, 8))
+        ));
+
+        // testing degree
+        assert_eq!(graph.degree(4)?, 2);
+
+        // testing is_empty_node
+        assert!(graph.is_empty_node(0)?);
+        assert!(!graph.is_empty_node(1)?);
+
+        // testing has_edge
+        assert!(graph.has_edge(3, 2)?);
+        assert!(!graph.has_edge(3, 1)?);
+        assert!(matches!(
+            graph.has_edge(3, 8),
+            Err(Error::IndexOutOfBounds(8, 8))
+        ));
+
+        // testing labels_of
+        assert!(std::panic::catch_unwind(|| { graph.labels_of(5) }).is_err());
+
+        Ok(())
+    }
+}
+
+#[cfg(test)]
+mod test_slgraph_builder {
+    use super::*;
+
+    #[test]
+    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = SLGBuilder::<usize>::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        // Link each node to its successor and link the last node with
+        // the first one to form a cycle.
+        for i in 0..5 {
+            builder.add_edge(i, if i < 4 { i + 1 } else { 0 }, i)?;
+        }
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        // build a graph
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_errors() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = SLGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        // Errors in add_edge
+
+        assert!(matches!(
+            builder.add_edge(0, 5, 0),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        assert!(matches!(
+            builder.add_edge(10, 5, 0),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        assert!(matches!(
+            builder.add_edge(10, 50, 0),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        // Errors in remove_edge
+
+        assert!(matches!(
+            builder.remove_edge(0, 5, |_| true),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        assert!(matches!(
+            builder.remove_edge(10, 5, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        assert!(matches!(
+            builder.remove_edge(10, 50, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),));
+
+        Ok(())
+    }
+}
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index e27ace0..058d62c 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -276,6 +276,58 @@ pub trait RedirectGraph: Graph {
     ) -> Result<(), Error>;
 }
 
+// TODO: Design traits for vertex-labelled, edge-labelled, and
+// both-labelled graphs separately.
+//
+// This is needed because we need better iterators to return labels
+// simultaneously with children nodes.  This can then reduce the
+// number of checking bounds when iterating.  I think this is the
+// right way of doing things, and can help with the performance as
+// well.
+
+/// A graph whose vertices are associated with labels.
+///
+/// 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.
+    type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a
+    where
+        Self: 'a,
+        T: 'a;
+
+    /// Query the graph for a label, and return the node index if
+    /// this operation is supported.
+    ///
+    /// The default implementation always returns `None`.
+    #[inline]
+    fn query_label(&self, _label: T) -> Option<usize> {
+        None
+    }
+
+    #[inline]
+    /// Return the label of a vertex or an error if the node is
+    /// invalid.
+    ///
+    /// The default implementation always returns `None` after
+    /// checking the validity of `node_id`.
+    fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> {
+        if self.has_node(node_id) {
+            Ok(None)
+        } else {
+            Err(Error::IndexOutOfBounds(node_id, self.nodes_len()))
+        }
+    }
+
+    /// Return an iterator of tuples of vertex labels and indices of
+    /// targets 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 labelled graph is just a graph with labels associated to
 /// vertices and / or edges.
 ///
@@ -289,9 +341,12 @@ pub trait LabelGraph<T: GraphLabel>: Graph {
     where
         Self: 'a;
 
-    // TODO: Add a type that iterates through children and labels of
-    // children simultaneously.  This can reduce the number of bounds
-    // checking.
+    /// A type that iterates through tuples of labels and targets of
+    /// edges.
+    type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a
+    where
+        Self: 'a,
+        T: 'a;
 
     /// A type that iterates through labels.
     type LabelIter<'a>: Iterator<Item = (&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + 'a
@@ -347,6 +402,10 @@ pub trait LabelGraph<T: GraphLabel>: Graph {
     /// The efficiency of this method matters in implementations.
     fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error>;
 
+    /// Return an iterator of tuples of edge labels and targets of
+    /// edges out of a node.
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error>;
+
     /// Return true if and only if the node has an edge with the given
     /// label and target.
     fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error>;
diff --git a/graph_macro/src/lib.rs b/graph_macro/src/lib.rs
index 3b7742a..409e6db 100644
--- a/graph_macro/src/lib.rs
+++ b/graph_macro/src/lib.rs
@@ -137,6 +137,8 @@ macro_rules! myerror {
     };
 }
 
+/// Derive macro generating an implementation of the trait `Graph`
+/// inheriting a field.
 #[proc_macro_derive(Graph, attributes(graph))]
 pub fn graph_derive(input: TokenStream) -> TokenStream {
     let mut input = input.into_iter().peekable();
diff --git a/nfa/src/default/nfa.rs b/nfa/src/default/nfa.rs
index e38a1a9..42f7fd8 100644
--- a/nfa/src/default/nfa.rs
+++ b/nfa/src/default/nfa.rs
@@ -43,6 +43,11 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultNFA<T> {
         Self: 'a,
         T: 'a;
 
+    type TupleIter<'a> = <DLGraph<T> as LabelGraph<T>>::TupleIter<'a>
+    where
+        Self: 'a,
+        T: 'a;
+
     #[inline]
     fn vertex_label(&self, node_id: usize) -> Result<Option<T>, GError> {
         if self.has_node(node_id) {
@@ -67,6 +72,11 @@ impl<T: GraphLabel> LabelGraph<T> for DefaultNFA<T> {
     }
 
     #[inline]
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
+        self.graph.tuples_of(node_id)
+    }
+
+    #[inline]
     fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
         self.graph.labels_of(node_id)
     }
diff --git a/nfa/src/default/regex.rs b/nfa/src/default/regex.rs
index 8185ca5..261b10c 100644
--- a/nfa/src/default/regex.rs
+++ b/nfa/src/default/regex.rs
@@ -211,6 +211,12 @@ where
             .take(self.len())
             .collect();
 
+        // FIXME: This seems wrong: we shall perform a depth-first
+        // search to find nodes without children and collect their
+        // results first.  However this function is not actually used
+        // elsewhere, so it is left unfixed until it is needed in the
+        // future.
+
         for index in 0..=self.len() {
             let algebra_result = {
                 let results_of_children: Vec<T> = self
diff --git a/semiring/Cargo.toml b/semiring/Cargo.toml
index d62eea6..8c03308 100644
--- a/semiring/Cargo.toml
+++ b/semiring/Cargo.toml
@@ -7,8 +7,4 @@ edition = "2021"
 
 [dependencies]
 grammar = { path = "../grammar" }
-
-[dev-dependencies]
-grammar = { path = "../grammar", features = ["test-helper"] }
-
-# TODO
+forest = { path = "../forest" }