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.

5 files changed, 663 insertions, 3 deletions

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>;