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.

4 files changed, 601 insertions, 0 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(())
+    }
+}