Initial commit

Basic GNU standard files are added, and we now stop worrying about
monadic anamorphisms.

The current focus is on testing the correctness of the algorithm, so I
need convenient support for manipulating, interpreting, examining, and
per chance animating nondeterministic automata.

5 files changed, 1065 insertions, 0 deletions

diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs
new file mode 100644
index 0000000..c16ceb2
--- /dev/null
+++ b/graph/src/adlist.rs
@@ -0,0 +1,181 @@
+#![warn(missing_docs)]
+//! This file implements a data type that implements the trait
+//! [`Graph`][super::Graph].  This data type represents graphs using
+//! adjacency lists internally.
+
+use super::{ExtGraph, Graph};
+use crate::error::Error;
+
+// #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
+// struct ALEdge {
+//     to: usize,
+// }
+
+// impl ALEdge {
+//     fn new(to: usize) -> Self {
+//         Self { to }
+//     }
+// }
+
+#[derive(Debug, Clone, Default)]
+struct ALNode {
+    children: Vec<usize>,
+}
+
+impl ALNode {
+    fn new(children: Vec<usize>) -> Self {
+        Self { children }
+    }
+}
+
+/// The graph implemented using adjacency lists.
+#[derive(Debug, Clone, Default)]
+pub struct ALGraph {
+    nodes: Vec<ALNode>,
+}
+
+impl Graph for ALGraph {
+    type Iter<'a> = std::iter::Copied<std::slice::Iter<'a, usize>>;
+
+    #[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(node.children.iter().copied()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn degree(&self, node_id: usize) -> Result<usize, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(node.children.len()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(node.children.is_empty()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
+        if !self.has_node(source) {
+            Err(Error::IndexOutOfBounds(source, self.nodes_len()))
+        } else if !self.has_node(target) {
+            Err(Error::IndexOutOfBounds(target, self.nodes_len()))
+        } else {
+            Ok(self.nodes.get(source).unwrap().children.contains(&target))
+        }
+    }
+}
+
+impl ExtGraph for ALGraph {
+    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, Error> {
+        let mut new_node_children = Vec::new();
+
+        for edge_to in edges.into_iter() {
+            if !self.has_node(edge_to) {
+                return Err(Error::IndexOutOfBounds(edge_to, self.nodes_len()));
+            }
+
+            new_node_children.push(edge_to);
+        }
+
+        let new_node = ALNode::new(new_node_children);
+
+        self.nodes.push(new_node);
+
+        Ok(self.nodes.len() - 1)
+    }
+}
+
+#[cfg(test)]
+mod algraph_test {
+    use super::*;
+
+    #[test]
+    fn test_graph_apis() -> Result<(), Error> {
+        let mut graph = ALGraph::default();
+
+        assert!(graph.is_empty());
+
+        graph.extend(std::iter::empty())?;
+
+        graph.extend([0].iter().copied())?;
+        graph.extend([0, 1].iter().copied())?;
+        graph.extend([0, 2].iter().copied())?;
+        graph.extend([1, 2].iter().copied())?;
+        graph.extend([1, 2, 3].iter().copied())?;
+
+        let graph = graph;
+
+        assert_eq!(graph.nodes_len(), 6);
+
+        assert_eq!(graph.children_of(5)?.collect::<Vec<_>>(), vec![1, 2, 3]);
+
+        assert_eq!(graph.degree(4)?, 2);
+
+        assert!(graph.is_empty_node(0)?);
+        assert!(!graph.is_empty_node(1)?);
+
+        assert!(graph.has_edge(3, 2)?);
+        assert!(!graph.has_edge(3, 1)?);
+        assert_eq!(graph.has_edge(3, 6), Err(Error::IndexOutOfBounds(6, 6)));
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_extending_algraph_normal() -> Result<(), Error> {
+        let mut graph = ALGraph::default();
+
+        let new = graph.extend(std::iter::empty())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        let new = graph.extend([0].iter().copied())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        let new = graph.extend([0, 1].iter().copied())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_extending_algraph_error() -> Result<(), Error> {
+        let mut graph = ALGraph::default();
+
+        graph.extend(std::iter::empty())?;
+
+        graph.extend([0].iter().copied())?;
+
+        assert_eq!(
+            graph.extend([2].iter().copied()),
+            Err(Error::IndexOutOfBounds(2, 2))
+        );
+
+        Ok(())
+    }
+}
diff --git a/graph/src/adset.rs b/graph/src/adset.rs
new file mode 100644
index 0000000..58fed4c
--- /dev/null
+++ b/graph/src/adset.rs
@@ -0,0 +1,229 @@
+#![warn(missing_docs)]
+//! This file implements a data type that implements the trait
+//! [`Graph`][super::Graph].  This data type represents graphs using
+//! adjacency sets internally.
+//!
+//! I need this because the derivatives languages should not allow
+//! duplications of languages, so it is more convenient if the
+//! underlying graph type **cannot** represent duplicate edges.
+
+use super::{ExtGraph, Graph};
+use crate::error::Error;
+
+// If one wants to use another implementation for a set, import that
+// as Set, and nothing else needs to be changed, ideally.
+use std::collections::{hash_set::Iter, HashSet as Set};
+
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+struct ASEdge {
+    to: usize,
+}
+
+impl ASEdge {
+    fn new(to: usize) -> Self {
+        Self { to }
+    }
+}
+
+#[derive(Debug, Clone, Default)]
+struct ASNode {
+    children: Set<ASEdge>,
+}
+
+impl ASNode {
+    fn new(children: Set<ASEdge>) -> Self {
+        Self { children }
+    }
+}
+
+/// The graph implemented using adjacency sets.
+#[derive(Debug, Clone, Default)]
+pub struct ASGraph {
+    nodes: Vec<ASNode>,
+}
+
+/// A delegation of iterators.
+///
+/// This is here to avoid using a boxed pointer, in order to save some
+/// allocations.
+pub struct ASIter<'a> {
+    iter: Iter<'a, ASEdge>,
+}
+
+impl<'a> Iterator for ASIter<'a> {
+    type Item = usize;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(|edge| edge.to)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<'a> ExactSizeIterator for ASIter<'a> {
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl Graph for ASGraph {
+    type Iter<'a> = ASIter<'a>;
+
+    #[inline]
+    fn is_empty(&self) -> bool {
+        self.nodes.is_empty()
+    }
+
+    #[inline]
+    fn nodes_len(&self) -> usize {
+        self.nodes.len()
+    }
+
+    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => {
+                let iter = node.children.iter();
+                Ok(Self::Iter { iter })
+            }
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn degree(&self, node_id: usize) -> Result<usize, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(node.children.len()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
+        match self.nodes.get(node_id) {
+            Some(node) => Ok(node.children.is_empty()),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())),
+        }
+    }
+
+    #[inline]
+    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
+        if !self.has_node(source) {
+            Err(Error::IndexOutOfBounds(source, self.nodes_len()))
+        } else if !self.has_node(target) {
+            Err(Error::IndexOutOfBounds(target, self.nodes_len()))
+        } else {
+            Ok(self
+                .nodes
+                .get(source)
+                .unwrap()
+                .children
+                .contains(&ASEdge::new(target)))
+        }
+    }
+}
+
+impl ExtGraph for ASGraph {
+    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, Error> {
+        let mut new_node_children = Set::default();
+
+        for edge_to in edges.into_iter() {
+            if !self.has_node(edge_to) {
+                return Err(Error::IndexOutOfBounds(edge_to, self.nodes_len()));
+            }
+
+            new_node_children.insert(ASEdge::new(edge_to));
+        }
+
+        let new_node = ASNode::new(new_node_children);
+
+        self.nodes.push(new_node);
+
+        Ok(self.nodes.len() - 1)
+    }
+}
+
+#[cfg(test)]
+mod asgraph_test {
+    use super::*;
+
+    #[test]
+    fn test_graph_apis() -> Result<(), Error> {
+        let mut graph = ASGraph::default();
+
+        assert!(graph.is_empty());
+
+        graph.extend(std::iter::empty())?;
+
+        graph.extend([0].iter().copied())?;
+        graph.extend([0, 1].iter().copied())?;
+        graph.extend([0, 2].iter().copied())?;
+        graph.extend([1, 2].iter().copied())?;
+        graph.extend([1, 2, 3].iter().copied())?;
+
+        let graph = graph;
+
+        assert_eq!(graph.nodes_len(), 6);
+
+        assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), {
+            let mut set = Set::default();
+            set.insert(1);
+            set.insert(3);
+            set.insert(2);
+            set
+        });
+
+        assert_eq!(graph.degree(4)?, 2);
+
+        assert!(graph.is_empty_node(0)?);
+        assert!(!graph.is_empty_node(1)?);
+
+        assert!(graph.has_edge(3, 2)?);
+        assert!(!graph.has_edge(3, 1)?);
+        assert_eq!(graph.has_edge(3, 6), Err(Error::IndexOutOfBounds(6, 6)));
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_extending_algraph_normal() -> Result<(), Error> {
+        let mut graph = ASGraph::default();
+
+        let new = graph.extend(std::iter::empty())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        let new = graph.extend([0].iter().copied())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        let new = graph.extend([0, 1].iter().copied())?;
+
+        println!("new index = {new}");
+
+        println!("new graph = {graph:?}");
+
+        Ok(())
+    }
+
+    #[test]
+    fn test_extending_algraph_error() -> Result<(), Error> {
+        let mut graph = ASGraph::default();
+
+        graph.extend(std::iter::empty())?;
+
+        graph.extend([0].iter().copied())?;
+
+        assert_eq!(
+            graph.extend([2].iter().copied()),
+            Err(Error::IndexOutOfBounds(2, 2))
+        );
+
+        Ok(())
+    }
+}
diff --git a/graph/src/error.rs b/graph/src/error.rs
new file mode 100644
index 0000000..2162685
--- /dev/null
+++ b/graph/src/error.rs
@@ -0,0 +1,26 @@
+#![warn(missing_docs)]
+//! This file implements the error data type of the graph library.
+
+use std::fmt::{self, Display};
+
+/// The error type for methods of the trait [`Graph`][`super::Graph`].
+#[derive(Debug, Clone, PartialEq, Eq, Ord, PartialOrd)]
+pub enum Error {
+    /// The index is out of bounds.
+    ///
+    /// The first component is the index that is out of bounds, and
+    /// the second component is the current length of nodes.
+    IndexOutOfBounds(usize, usize),
+}
+
+impl Display for Error {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Error::IndexOutOfBounds(index, len) => {
+                write!(f, "index {index} out of bounds {len} ")
+            }
+        }
+    }
+}
+
+impl std::error::Error for Error {}
diff --git a/graph/src/labelled.rs b/graph/src/labelled.rs
new file mode 100644
index 0000000..1cb2461
--- /dev/null
+++ b/graph/src/labelled.rs
@@ -0,0 +1,426 @@
+#![warn(missing_docs)]
+//! This file implements a labelled graph.  See the
+//! [trait][super::LabelGraph] for details.
+//!
+//! Since the method
+//! [`find_children_with_label`][super::LabelGraph::find_children_with_label]
+//! needs to be implemented efficiently, we store the mappings between
+//! labels and edges in both directions.
+
+#[allow(unused_imports)]
+use super::{Graph, GraphLabel, LabelExtGraph, LabelGraph};
+#[allow(unused_imports)]
+use crate::error::Error;
+
+// We use BTreeMap and BTreeSet here as we need to exclude duplicate
+// edge sets, while an ordinary hashmap and hashset do not allow
+// hashing.
+use std::collections::{
+    btree_map::{Iter as MapIter, Keys},
+    btree_set::Iter,
+    BTreeMap as Map, BTreeSet as Set, HashMap as HMap,
+};
+
+#[derive(Debug, Clone, Default)]
+struct DLNode<T: GraphLabel> {
+    by_target: Map<usize, Set<T>>,
+    by_label: Map<T, Set<usize>>,
+    flat: Vec<(T, usize)>,
+}
+
+impl<T: GraphLabel> DLNode<T> {
+    fn new(
+        by_target: Map<usize, Set<T>>,
+        by_label: Map<T, Set<usize>>,
+        flat: Vec<(T, usize)>,
+    ) -> Self {
+        Self {
+            by_target,
+            by_label,
+            flat,
+        }
+    }
+}
+
+/// Mapping a set of edges to an index of node.
+type EdgeMap<T> = HMap<Set<(T, usize)>, usize>;
+
+/// Double direction Labelled Graph.
+///
+/// Each node is supposed to have a unique edge set.  Constructing
+/// methods such as from the trait
+/// [`LabelExtGraph`][super::LabelExtGraph] already handles the
+/// elimination of duplication.
+#[derive(Debug, Clone)]
+pub struct DLGraph<T: GraphLabel> {
+    nodes: Vec<DLNode<T>>,
+    edges_table: EdgeMap<T>,
+}
+
+impl<T: GraphLabel> DLGraph<T> {
+    #[inline]
+    /// Return an empty graph.
+    pub fn new() -> Self {
+        Self {
+            nodes: Vec::new(),
+            edges_table: HMap::default(),
+        }
+    }
+}
+
+impl<T: GraphLabel> Default for DLGraph<T> {
+    #[inline]
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<T: GraphLabel> Graph for DLGraph<T> {
+    // Not using a boxed pointer is supposed to save some allocations.
+    type Iter<'a> = std::iter::Copied<Keys<'a, usize, Set<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(node.by_target.keys().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.flat.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.flat.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() {
+                    return Err(Error::IndexOutOfBounds(target, self.nodes.len()));
+                }
+
+                Ok(source_node.by_target.contains_key(&target))
+            }
+            None => Err(Error::IndexOutOfBounds(source, self.nodes.len())),
+        }
+    }
+}
+
+/// A delegation of iterators.
+///
+/// This is used to avoid a boxed pointer to an iterator.
+#[derive(Default, Debug)]
+pub struct LabelIndexIter<'a> {
+    iter: Option<std::iter::Copied<Iter<'a, usize>>>,
+}
+
+impl<'a> Iterator for LabelIndexIter<'a> {
+    type Item = usize;
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.as_mut().map(|iterator| iterator.next()).flatten()
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        match &self.iter {
+            Some(iter) => iter.size_hint(),
+            None => (0, Some(0)),
+        }
+    }
+}
+
+impl<'a> ExactSizeIterator for LabelIndexIter<'a> {
+    #[inline]
+    fn len(&self) -> usize {
+        match &self.iter {
+            Some(iter) => iter.len(),
+            None => 0,
+        }
+    }
+}
+
+impl<'a> LabelIndexIter<'a> {
+    fn new(iter: std::iter::Copied<Iter<'a, usize>>) -> Self {
+        let iter = Some(iter);
+        Self { iter }
+    }
+}
+
+// A convenience method
+impl<'a> From<&'a Set<usize>> for LabelIndexIter<'a> {
+    fn from(set: &'a Set<usize>) -> Self {
+        Self::new(set.iter().copied())
+    }
+}
+
+#[derive(Debug)]
+/// A delegation of iterators.
+///
+/// This is used to avoid a boxed pointer to an iterator.
+pub struct LabelIter<'a, T> {
+    iter: MapIter<'a, T, Set<usize>>,
+}
+
+impl<'a, T> ExactSizeIterator for LabelIter<'a, T> {
+    #[inline]
+    fn len(&self) -> usize {
+        self.iter.len()
+    }
+}
+
+impl<'a, T> LabelIter<'a, T> {
+    fn new(iter: MapIter<'a, T, Set<usize>>) -> Self {
+        Self { iter }
+    }
+}
+
+impl<'a, T> Iterator for LabelIter<'a, T> {
+    type Item = (&'a T, LabelIndexIter<'a>);
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        self.iter.next().map(|(label, set)| (label, set.into()))
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
+    type Iter<'a> = LabelIndexIter<'a> where T: 'a;
+
+    type LabelIter<'a> = LabelIter<'a,T> where T: 'a;
+
+    fn edge_label(&self, source: usize, target: usize) -> Result<Vec<T>, Error> {
+        if self.has_edge(source, target)? {
+            Ok(self
+                .nodes
+                .get(source)
+                .unwrap()
+                .by_target
+                .get(&target)
+                .unwrap()
+                .iter()
+                .copied()
+                .collect())
+        } else {
+            Ok(Vec::new())
+        }
+    }
+
+    fn find_children_with_label(
+        &self,
+        node_id: usize,
+        label: &T,
+    ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error> {
+        match self
+            .nodes
+            .get(node_id)
+            .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))?
+            .by_label
+            .get(label)
+        {
+            Some(set) => Ok(set.into()),
+            None => Ok(Default::default()),
+        }
+    }
+
+    #[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())),
+            None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())),
+        }
+    }
+}
+
+impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
+    fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error> {
+        let mut by_target: Map<usize, Set<T>> = Map::default();
+        let mut by_label: Map<T, Set<usize>> = Map::default();
+        let mut flat = Vec::new();
+        let mut edges_set = Set::new();
+
+        for (label, to) in edges {
+            if !self.has_node(to) {
+                return Err(Error::IndexOutOfBounds(to, self.nodes.len()));
+            }
+
+            edges_set.insert((label, to));
+
+            if let Some(set) = by_target.get(&to) {
+                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);
+                }
+            } 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);
+            }
+        }
+
+        match self.edges_table.get(&edges_set) {
+            Some(old_index) => Ok(*old_index),
+            None => {
+                let new_node = DLNode::new(by_target, by_label, flat);
+                let new_index = self.nodes_len();
+
+                self.edges_table.insert(edges_set, new_index);
+
+                self.nodes.push(new_node);
+
+                Ok(new_index)
+            }
+        }
+    }
+}
+
+#[cfg(test)]
+mod label_test {
+    use super::*;
+
+    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: DLGraph<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())?, 5);
+        assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 3);
+
+        let graph = graph;
+
+        // ensuring the correct length
+        assert_eq!(graph.nodes_len(), 6);
+
+        // testing children_of
+        assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2));
+
+        // testing find_children_with_label
+        assert_eq!(
+            graph.find_children_with_label(5, &2)?.collect::<Set<_>>(),
+            set!(1, 3)
+        );
+
+        // testing edge_label
+        assert_eq!(
+            graph.edge_label(5, 2)?.into_iter().collect::<Set<_>>(),
+            set!(3)
+        );
+        assert!(matches!(
+            graph.edge_label(6, 2),
+            Err(Error::IndexOutOfBounds(6, 6))
+        ));
+
+        // 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, 6),
+            Err(Error::IndexOutOfBounds(6, 6))
+        ));
+
+        // testing labels_of
+        let mut label_map: Map<usize, Set<usize>> = Map::default();
+
+        for (label, children) in graph.labels_of(5)? {
+            label_map.insert(*label, children.collect());
+        }
+
+        let compare_map = map!((2, set!(1, 3)), (3, set!(2)));
+
+        assert_eq!(label_map, compare_map);
+
+        assert!(matches!(
+            graph.labels_of(6),
+            Err(Error::IndexOutOfBounds(6, 6))
+        ));
+
+        Ok(())
+    }
+}
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
new file mode 100644
index 0000000..7b74ee1
--- /dev/null
+++ b/graph/src/lib.rs
@@ -0,0 +1,203 @@
+#![warn(missing_docs)]
+//! This crate implements a trait API for graphs that the crate "rep"
+//! needs.
+//!
+//! Also a default implementation for the trait is provided, so that
+//! by default no external crates are needed, whereas it is easy to
+//! use external crates, if so derired.
+
+use std::hash::Hash;
+
+pub mod error;
+
+pub mod adset;
+
+pub use adset::ASGraph;
+
+pub mod adlist;
+
+pub use adlist::ALGraph;
+
+pub mod labelled;
+
+pub use labelled::DLGraph;
+
+use error::Error;
+
+/// The expected behaviour of an immutable graph.
+pub trait Graph: Default {
+    /// A type that iterates through the node indices.
+    type Iter<'a>: Iterator<Item = usize> + 'a
+    where
+        Self: 'a;
+
+    /// Return true if and only if the graph has no nodes.
+    fn is_empty(&self) -> bool;
+
+    /// Return the length of nodes in the graph.
+    fn nodes_len(&self) -> usize;
+
+    #[inline]
+    /// Return the length of edges in the graph.
+    ///
+    /// This is optional.  Implementations need not support this.
+    fn edges_len(&self) -> Option<usize> {
+        None
+    }
+
+    #[inline]
+    /// Return an iterator of nodes represented as unsigned integers.
+    ///
+    /// If a custom application needs to have labels on nodes, just
+    /// associate the label to the node internally, and define an
+    /// extension trait that allows querying those additional labels.
+    ///
+    /// This design choice is based on the idea that this library
+    /// should be minimal and only provide the core of a graph.  As a
+    /// label is not really core, it is not included here.
+    fn nodes(&self) -> Box<dyn Iterator<Item = usize> + '_> {
+        Box::new(0..self.nodes_len())
+    }
+
+    /// Return an iterator of edges going out of a node.
+    ///
+    /// Return an error if the node is not known to the graph.
+    fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error>;
+
+    #[inline]
+    /// Return an iterator of edges represented as pairs (FROM, TO).
+    ///
+    /// The default implementation iterates through the nodes and then
+    /// iterates through their children.  If the implementation has a
+    /// more efficient method, overwrite this method.
+    fn edges(&self) -> Box<dyn Iterator<Item = (usize, usize)> + '_> {
+        Box::new(self.nodes().flat_map(|node| {
+            self.children_of(node)
+                // If this node is invalid, this means the
+                // implementation of `nodes` is wrong, so it is
+                // appropriate to panic here.
+                .unwrap()
+                .map(move |child| (node, child))
+        }))
+    }
+
+    #[inline]
+    /// Return true if and only if the node is in the graph.
+    fn has_node(&self, node_id: usize) -> bool {
+        (0..self.nodes_len()).contains(&node_id)
+    }
+
+    /// Return the number of "children" of a node, or an error if the
+    /// node is not a member of the graph.
+    fn degree(&self, node_id: usize) -> Result<usize, Error>;
+
+    /// Return a boolean indicating if the node has no children, or an
+    /// error if the node is not a member of the graph.
+    fn is_empty_node(&self, node_id: usize) -> Result<bool, Error>;
+
+    /// Return true if and only if there is an edge from the source to
+    /// the target.
+    ///
+    /// Return an error if either the source or the target is an
+    /// invalid node.
+    fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error>;
+}
+
+/// A graph that can be extended, but not mutated, in the sense that
+/// existing nodes and edges will not be modified nor removed, but new
+/// nodes can be added.  The index of the new node will be returned.
+///
+/// Implementations can choose to keep a set of sets of edges, so that
+/// new nodes will not have duplicate edge sets.  In this case, the
+/// returned new node index is not necessarily equal to
+/// self.nodes_len() - 1, and hence the return type is designed in
+/// this way.
+pub trait ExtGraph: Graph {
+    /// Add a new node with `edges`.
+    ///
+    /// If an edge from `edges` points to a non-existent node, return
+    /// an error.
+    fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, Error>;
+}
+
+/// The type of labels should be comparable and hashable.
+pub trait GraphLabel: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd {}
+
+impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd> GraphLabel for T {}
+
+/// A labelled graph is just a graph with labels associated to
+/// vertices and / or edges.
+///
+/// This trait defines what the package needs out of a labelled graph.
+///
+/// Any implementation should be able to handle a set of types for
+/// labels, so this trait is generic over the label type.
+pub trait LabelGraph<T: GraphLabel>: Graph {
+    /// A type that iterates through the node indices.
+    type Iter<'a>: Iterator<Item = usize> + 'a
+    where
+        Self: 'a;
+
+    /// A type that iterates through labels.
+    type LabelIter<'a>: Iterator<Item = (&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + 'a
+    where
+        Self: 'a,
+        T: 'a;
+
+    #[inline]
+    /// Return the label of a vertex or an error if the node is
+    /// invalid.
+    ///
+    /// The default implementation always returns None for a valid
+    /// node.
+    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()))
+        }
+    }
+
+    #[inline]
+    /// Return the label of an edge or an error if some node is
+    /// invalid.
+    ///
+    /// The default implementation always returns an empty vector for
+    /// valid nodes.
+    fn edge_label(&self, source: usize, target: usize) -> Result<Vec<T>, Error> {
+        self.has_edge(source, target).map(|_| Vec::new())
+    }
+
+    /// Return an iterator of edges out of a node, whose associated
+    /// label is as given.
+    ///
+    /// The efficiency of this method matters in implementations.
+    fn find_children_with_label(
+        &self,
+        node_id: usize,
+        label: &T,
+    ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error>;
+
+    /// Return an iterator of labels of edges out of a node.
+    ///
+    /// The efficiency of this method matters in implementations.
+    fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error>;
+}
+
+/// A labelled graph that can be extended, but not mutated, in the
+/// sense that existing nodes and edges will not be modified nor
+/// removed, but new nodes can be added.  The index of the new node
+/// will be returned.
+///
+/// Implementations can choose to keep a set of sets of edges, so that
+/// new nodes will not have duplicate edge sets.  In this case, the
+/// returned new node index is not necessarily equal to
+/// self.nodes_len() - 1, and hence the return type is designed in
+/// this way.
+pub trait LabelExtGraph<T: GraphLabel>: LabelGraph<T> {
+    /// Add a new node with `edges`.
+    ///
+    /// If an edge from `edges` points to a non-existent node, return
+    /// an error.
+    fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error>;
+}