renaming core to chain and some other changes

Some changes:

- The core crate is renamed to "chain".

- The crate "viz" is added, which will provide layered graph drawing
  algorithms.

- A function is added to convert from a grammar to the regular
  language of its left-linear closures.

- A function is added to convert from a nondeterministic finite
  automaton to its "null" closure.  A null closure is the same
  automaton with edges added, as if some edges are "null".  Whether an
  edge is null is determined by a function.
  Combined with the previous change, we can convert a grammar to the
  regular language of the null closure of its left-linear closures.

---

Now it remains to test more grammars and add an Atom trait, before
finishing the part about compilations.

6 files changed, 1027 insertions, 16 deletions

diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs
index 18ad770..6c1dcd0 100644
--- a/graph/src/adlist.rs
+++ b/graph/src/adlist.rs
@@ -3,8 +3,9 @@
 //! [`Graph`][super::Graph].  This data type represents graphs using
 //! adjacency lists internally.
 
-use super::{ExtGraph, Graph};
-use crate::error::Error;
+use std::ops::{Deref, DerefMut};
+
+use crate::{builder::Builder, error::Error, ExtGraph, Graph};
 
 // #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
 // struct ALEdge {
@@ -80,6 +81,13 @@ impl Graph for ALGraph {
             Ok(self.nodes.get(source).unwrap().children.contains(&target))
         }
     }
+
+    #[inline]
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) {
+        let graph = builder.build();
+
+        self.nodes = graph.nodes;
+    }
 }
 
 impl ExtGraph for ALGraph {
@@ -102,11 +110,115 @@ impl ExtGraph for ALGraph {
     }
 }
 
-// TODO: Add a way to build a graph by its raw adjacency list representation.
 impl From<Vec<Vec<usize>>> for ALGraph {
     fn from(adlist: Vec<Vec<usize>>) -> Self {
-        let nodes: Vec<ALNode> = adlist.iter().cloned().map(ALNode::new).collect();
-        Self { nodes }
+        Self {
+            nodes: adlist.into_iter().map(ALNode::new).collect(),
+        }
+    }
+}
+
+// Builder for this implementation of graph
+
+/// A builder for adjacency list graphs.
+#[derive(Debug, Default, Clone)]
+pub struct ALGBuilder(ALGraph);
+
+impl Deref for ALGBuilder {
+    type Target = ALGraph;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl DerefMut for ALGBuilder {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+impl Builder for ALGBuilder {
+    type Label = ();
+
+    type Result = ALGraph;
+
+    fn with_capacity(size: usize) -> Self {
+        Self(ALGraph {
+            nodes: Vec::with_capacity(size),
+        })
+    }
+
+    #[inline]
+    fn add_vertex(&mut self) -> usize {
+        self.nodes.push(ALNode::default());
+        self.nodes.len() - 1
+    }
+
+    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
+        let nodes_len = self.nodes.len();
+
+        let source_children = 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_children.children.push(target);
+
+        Ok(())
+    }
+
+    /// Remove an edge from the source to the target.
+    ///
+    /// Since some graphs are labelled, the users are allowed to pass
+    /// a predicate to determine if an edge from the source to the
+    /// target should be removed.
+    ///
+    /// # Performance note
+    ///
+    /// It is possible that the target appears more than once in the
+    /// vector of children, so we have to remove every instance of
+    /// target.
+    ///
+    /// Since I do not think builders should be used for performance
+    /// critical tasks, this is fine.
+    ///
+    /// If one desires more performance, maybe
+    /// [`ASGraph`][crate::ASGraph] is a good choice.
+    ///
+    /// Of course, if one just wants to use adjacency list
+    /// representation and wants a performant builder, one can
+    /// implement a customized builder.
+    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
+    where
+        F: Fn(Self::Label) -> bool,
+    {
+        let nodes_len = self.nodes.len();
+
+        let source_children = 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_children.children.retain(|child| *child != target);
+
+        Ok(())
+    }
+
+    fn build(self) -> Self::Result {
+        self.0
+    }
+
+    fn build_ref(&self) -> Self::Result {
+        self.0.clone()
     }
 }
 
@@ -187,3 +299,123 @@ mod algraph_test {
         Ok(())
     }
 }
+
+#[cfg(test)]
+mod test_algraph_builder {
+    use super::*;
+
+    #[test]
+    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = ALGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // 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 { 0 } else { i + 1 }, ())?;
+        }
+
+        println!("a cycle of five nodes: {builder:?}");
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        println!("a line of five nodes: {builder:?}");
+
+        // 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 = ALGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // Errors in add_edge
+
+        println!();
+        println!("Testing errors in add_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.add_edge(0, 5, ()),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.add_edge(10, 5, ()),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.add_edge(10, 50, ()),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        // Errors in remove_edge
+
+        println!();
+        println!("Testing errors in remove_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.remove_edge(0, 5, |_| true),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.remove_edge(10, 5, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.remove_edge(10, 50, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),));
+
+        println!("No errors for removing a non-existing edge");
+
+        println!();
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+}
diff --git a/graph/src/adset.rs b/graph/src/adset.rs
index 58fed4c..c225986 100644
--- a/graph/src/adset.rs
+++ b/graph/src/adset.rs
@@ -7,8 +7,9 @@
 //! 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;
+use std::ops::{Deref, DerefMut};
+
+use crate::{builder::Builder, error::Error, ExtGraph, Graph};
 
 // If one wants to use another implementation for a set, import that
 // as Set, and nothing else needs to be changed, ideally.
@@ -122,6 +123,13 @@ impl Graph for ASGraph {
                 .contains(&ASEdge::new(target)))
         }
     }
+
+    #[inline]
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) {
+        let graph = builder.build();
+
+        self.nodes = graph.nodes;
+    }
 }
 
 impl ExtGraph for ASGraph {
@@ -144,6 +152,90 @@ impl ExtGraph for ASGraph {
     }
 }
 
+// Builder for this implementation of graph
+
+/// A builder for adjacency set graphs.
+#[derive(Debug, Default, Clone)]
+pub struct ASGBuilder(ASGraph);
+
+impl Deref for ASGBuilder {
+    type Target = ASGraph;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl DerefMut for ASGBuilder {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+impl Builder for ASGBuilder {
+    type Label = ();
+
+    type Result = ASGraph;
+
+    #[inline]
+    fn with_capacity(size: usize) -> Self {
+        Self(ASGraph {
+            nodes: Vec::with_capacity(size),
+        })
+    }
+
+    #[inline]
+    fn add_vertex(&mut self) -> usize {
+        self.nodes.push(ASNode::default());
+        self.nodes.len() - 1
+    }
+
+    fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
+        let nodes_len = self.nodes.len();
+
+        let source_children = 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_children.children.insert(ASEdge::new(target));
+
+        Ok(())
+    }
+
+    fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
+    where
+        F: Fn(Self::Label) -> bool,
+    {
+        let nodes_len = self.nodes.len();
+
+        let source_children = 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_children.children.remove(&ASEdge::new(target));
+
+        Ok(())
+    }
+
+    fn build(self) -> Self::Result {
+        self.0
+    }
+
+    fn build_ref(&self) -> Self::Result {
+        self.0.clone()
+    }
+}
+
 #[cfg(test)]
 mod asgraph_test {
     use super::*;
@@ -227,3 +319,123 @@ mod asgraph_test {
         Ok(())
     }
 }
+
+#[cfg(test)]
+mod test_asgraph_builder {
+    use super::*;
+
+    #[test]
+    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = ASGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // 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 { 0 } else { i + 1 }, ())?;
+        }
+
+        println!("a cycle of five nodes: {builder:?}");
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        println!("a line of five nodes: {builder:?}");
+
+        // 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 = ASGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // Errors in add_edge
+
+        println!();
+        println!("Testing errors in add_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.add_edge(0, 5, ()),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.add_edge(10, 5, ()),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.add_edge(10, 50, ()),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        // Errors in remove_edge
+
+        println!();
+        println!("Testing errors in remove_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.remove_edge(0, 5, |_| true),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.remove_edge(10, 5, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.remove_edge(10, 50, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),));
+
+        println!("No errors for removing a non-existing edge");
+
+        println!();
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+}
diff --git a/graph/src/builder.rs b/graph/src/builder.rs
new file mode 100644
index 0000000..ce85cce
--- /dev/null
+++ b/graph/src/builder.rs
@@ -0,0 +1,53 @@
+//! This file defines the expected behaviours of a builder of graphs.
+
+use crate::{error::Error, Graph};
+
+/// A builder is actually just a graph that can be altered in more
+/// ways than an extension graph can.  It should not have any methods
+/// from the Graph trait, though, as we shall convert a builder to a
+/// normal final graph before using it.
+pub trait Builder: Default {
+    /// Some graphs are labelled.  This type should be the type of the
+    /// labels.
+    type Label;
+
+    /// The type of the result graph.
+    type Result: Graph;
+
+    /// Construct an empty builder with the capacity to hold a given
+    /// number of nodes.
+    ///
+    /// Implementations may ignore this method, where the default
+    /// implementation just calls `Default::default`.
+    #[inline]
+    fn with_capacity(_size: usize) -> Self {
+        Self::default()
+    }
+
+    /// Add a vertex without children.
+    fn add_vertex(&mut self) -> usize;
+
+    /// Add an edge from the source to the target.
+    fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>;
+
+    /// Remove an edge from the source to the target.
+    ///
+    /// Since some graphs are labelled, the users are allowed to pass
+    /// a predicate to determine if an edge from the source to the
+    /// target should be removed.
+    fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error>
+    where
+        F: Fn(Self::Label) -> bool;
+
+    /// Convert the builder into a graph.
+    ///
+    /// This is the purpose of having a builder.
+    fn build(self) -> Self::Result;
+
+    /// Convert the builder into a graph using a reference.
+    ///
+    /// This is similar to [`build`][Builder::build], but takes an
+    /// immutable reference of the builder, so that the builder can
+    /// still be used later on.
+    fn build_ref(&self) -> Self::Result;
+}
diff --git a/graph/src/error.rs b/graph/src/error.rs
index 2162685..3600005 100644
--- a/graph/src/error.rs
+++ b/graph/src/error.rs
@@ -1,16 +1,20 @@
 #![warn(missing_docs)]
 //! This file implements the error data type of the graph library.
 
-use std::fmt::{self, Display};
+use core::fmt::{self, Display};
 
 /// The error type for methods of the trait [`Graph`][`super::Graph`].
-#[derive(Debug, Clone, PartialEq, Eq, Ord, PartialOrd)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd)]
+#[non_exhaustive]
 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),
+    /// The graph does not permit duplicate nodes but encounters a
+    /// repeated node
+    DuplicatedNode,
 }
 
 impl Display for Error {
@@ -19,6 +23,7 @@ impl Display for Error {
             Error::IndexOutOfBounds(index, len) => {
                 write!(f, "index {index} out of bounds {len} ")
             }
+            Error::DuplicatedNode => write!(f, "No duplicate nodes permitted, but found one"),
         }
     }
 }
diff --git a/graph/src/labelled.rs b/graph/src/labelled.rs
index d02e301..d0a02d0 100644
--- a/graph/src/labelled.rs
+++ b/graph/src/labelled.rs
@@ -7,10 +7,9 @@
 //! 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;
+use std::ops::{Deref, DerefMut};
+
+use crate::{builder::Builder, error::Error, Graph, GraphLabel, LabelExtGraph, LabelGraph};
 
 // We use BTreeMap and BTreeSet here as we need to exclude duplicate
 // edge sets, while an ordinary hashmap and hashset do not allow
@@ -21,13 +20,23 @@ use std::collections::{
     BTreeMap as Map, BTreeSet as Set, HashMap as HMap,
 };
 
-#[derive(Debug, Clone, Default)]
+#[derive(Debug, Clone)]
 struct DLNode<T: GraphLabel> {
     by_target: Map<usize, Set<T>>,
     by_label: Map<T, Set<usize>>,
     flat: Vec<(T, usize)>,
 }
 
+impl<T: GraphLabel> Default for DLNode<T> {
+    fn default() -> Self {
+        Self {
+            by_target: Default::default(),
+            by_label: Default::default(),
+            flat: Default::default(),
+        }
+    }
+}
+
 impl<T: GraphLabel> DLNode<T> {
     fn new(
         by_target: Map<usize, Set<T>>,
@@ -66,6 +75,18 @@ impl<T: GraphLabel> DLGraph<T> {
             edges_table: HMap::default(),
         }
     }
+
+    /// Return a builder.
+    #[inline]
+    pub fn builder(self) -> DLGBuilder<T> {
+        DLGBuilder(self)
+    }
+
+    /// Return a builder from a reference.
+    #[inline]
+    pub fn builder_ref(&self) -> DLGBuilder<T> {
+        DLGBuilder(self.clone())
+    }
 }
 
 impl<T: GraphLabel> Default for DLGraph<T> {
@@ -129,6 +150,49 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
             None => Err(Error::IndexOutOfBounds(source, self.nodes.len())),
         }
     }
+
+    fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
+        let preamble = "digraph nfa {
+    fontname=\"Helvetica,Arial,sans-serif\"
+    node [fontname=\"Helvetica,Arial,sans-serif\"]
+    edge [fontname=\"Helvetica,Arial,sans-serif\"]
+    rankdir=LR;\n";
+
+        let mut post = String::new();
+
+        use std::fmt::Write as FWrite;
+
+        for (source, target) in self.edges() {
+            for label in self.edge_label(source, target).unwrap() {
+                let _ = writeln!(post, "    {source} -> {target} [label = \"{label}\"]");
+            }
+        }
+
+        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;
+        self.edges_table = new_graph.edges_table;
+    }
 }
 
 /// A delegation of iterators.
@@ -261,6 +325,25 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
             None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())),
         }
     }
+
+    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));
+                }
+
+                if let Some(labels) = node.by_target.get(&target) {
+                    Ok(labels.contains(label))
+                } else {
+                    Ok(false)
+                }
+            }
+            None => Err(Error::IndexOutOfBounds(node_id, nodes_len)),
+        }
+    }
 }
 
 impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
@@ -315,6 +398,181 @@ impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
     }
 }
 
+// Builder for this implementation of graph
+
+/// A builder for labelled adjacency doubly linked graphs.
+#[derive(Debug, Clone)]
+pub struct DLGBuilder<T: GraphLabel>(DLGraph<T>);
+
+impl<T: GraphLabel> Default for DLGBuilder<T> {
+    fn default() -> Self {
+        Self(Default::default())
+    }
+}
+
+impl<T: GraphLabel> Deref for DLGBuilder<T> {
+    type Target = DLGraph<T>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl<T: GraphLabel> DerefMut for DLGBuilder<T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+impl<T: GraphLabel> Builder for DLGBuilder<T> {
+    type Label = T;
+
+    type Result = DLGraph<T>;
+
+    #[inline]
+    fn with_capacity(size: usize) -> Self {
+        Self(DLGraph {
+            nodes: Vec::with_capacity(size),
+            edges_table: Default::default(),
+        })
+    }
+
+    #[inline]
+    fn add_vertex(&mut self) -> usize {
+        self.nodes.push(DLNode::default());
+        self.nodes.len() - 1
+    }
+
+    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));
+        }
+
+        let new_edge_p = !matches!(
+            source_node
+                .by_target
+                .get(&target)
+                .map(|set| set.contains(&label)),
+            Some(true)
+        );
+
+        if new_edge_p {
+            let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+            source_node
+                .by_target
+                .entry(target)
+                .or_insert_with(Set::default)
+                .insert(label);
+
+            source_node
+                .by_label
+                .entry(label)
+                .or_insert_with(Set::default)
+                .insert(target);
+
+            source_node.flat.push((label, target));
+
+            let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+            // When source_node is in use, we cannot borrow self
+            // mutably again, so we move the following two statements
+            // to after all uses of source_node.
+
+            self.edges_table.remove(&old_children_set);
+
+            self.edges_table.insert(new_children_set, source);
+        }
+
+        Ok(())
+    }
+
+    fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error>
+    where
+        F: Fn(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));
+        }
+
+        if let Some(target_labels_set) = source_node.by_target.get(&target) {
+            let mut to_remove = Vec::new();
+
+            for label in target_labels_set.iter() {
+                if predicate(*label) {
+                    to_remove.push(*label);
+                }
+            }
+
+            if !to_remove.is_empty() {
+                let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+                for label in to_remove.iter().copied() {
+                    // This must be "Some", as the outer "if" checks
+                    source_node
+                        .by_target
+                        .get_mut(&target)
+                        .map(|set| set.remove(&label));
+
+                    source_node
+                        .by_label
+                        .get_mut(&label)
+                        .map(|set| set.remove(&target));
+
+                    source_node.flat.retain(|(child_label, child_target)| {
+                        (*child_label, *child_target) != (label, target)
+                    });
+                }
+
+                // If after removal no labels remain for the target,
+                // we remove the edge entirely, to avoid false empty
+                // edges.
+                if source_node.flat.is_empty() {
+                    source_node.by_target.remove(&target);
+
+                    for label in to_remove.iter() {
+                        source_node.by_label.remove(label);
+                    }
+                }
+
+                let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
+
+                // When source_node is in use, we cannot borrow self
+                // mutably again, so we move the following two
+                // statements to after all uses of source_node.
+
+                self.edges_table.remove(&old_children_set);
+
+                self.edges_table.insert(new_children_set, source);
+            }
+        }
+
+        Ok(())
+    }
+
+    fn build_ref(&self) -> Self::Result {
+        self.0.clone()
+    }
+
+    fn build(self) -> Self::Result {
+        self.0
+    }
+}
+
 #[cfg(test)]
 mod label_test {
     use super::*;
@@ -424,3 +682,125 @@ mod label_test {
         Ok(())
     }
 }
+
+// TODO: Test print_viz
+
+#[cfg(test)]
+mod test_dlgraph_builder {
+    use super::*;
+
+    #[test]
+    fn test_builder() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder = DLGBuilder::<usize>::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // 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)?;
+        }
+
+        println!("a cycle of five nodes: {builder:?}");
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        println!("a line of five nodes: {builder:?}");
+
+        // 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 = DLGBuilder::default();
+
+        // Add five nodes
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+        builder.add_vertex();
+
+        println!("five empty nodes: {builder:?}");
+
+        // Errors in add_edge
+
+        println!();
+        println!("Testing errors in add_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.add_edge(0, 5, 0),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.add_edge(10, 5, 0),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.add_edge(10, 50, 0),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        // Errors in remove_edge
+
+        println!();
+        println!("Testing errors in remove_edge:");
+        println!();
+
+        assert!(matches!(
+            builder.remove_edge(0, 5, |_| true),
+            Err(Error::IndexOutOfBounds(5, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the target");
+
+        assert!(matches!(
+            builder.remove_edge(10, 5, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for an index out of bounds as the source");
+
+        assert!(matches!(
+            builder.remove_edge(10, 50, |_| true),
+            Err(Error::IndexOutOfBounds(10, 5))
+        ));
+
+        println!("Right error for both indices out of bounds");
+
+        assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),));
+
+        println!("No errors for removing a non-existing edge");
+
+        println!();
+
+        let graph = builder.build();
+
+        println!("final graph: {graph:?}");
+
+        Ok(())
+    }
+}
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 7b74ee1..2d23af3 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -8,6 +8,8 @@
 
 use std::hash::Hash;
 
+use core::fmt::{Debug, Display};
+
 pub mod error;
 
 pub mod adset;
@@ -22,6 +24,10 @@ pub mod labelled;
 
 pub use labelled::DLGraph;
 
+pub mod builder;
+
+pub use builder::Builder;
+
 use error::Error;
 
 /// The expected behaviour of an immutable graph.
@@ -101,6 +107,83 @@ pub trait Graph: Default {
     /// 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>;
+
+    /// Output the edges into a graphviz file.
+    fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
+        let preamble = "digraph nfa {
+    fontname=\"Helvetica,Arial,sans-serif\"
+    node [fontname=\"Helvetica,Arial,sans-serif\"]
+    edge [fontname=\"Helvetica,Arial,sans-serif\"]
+    rankdir=LR;\n";
+
+        let mut post = String::new();
+
+        use std::fmt::Write as FWrite;
+
+        for (source, target) in self.edges() {
+            let _ = writeln!(post, "{source} -> {target}");
+        }
+
+        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())
+    }
+
+    /// Returns whether or not the graph contains cycles.
+    ///
+    /// If, and only if, the graph contains invalid nodes, an error
+    /// will be signalled.
+    fn contains_cycles(&self) -> Result<bool, Error> {
+        use std::collections::HashSet;
+
+        let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len());
+
+        for node in self.nodes() {
+            if seen_nodes.contains(&node) {
+                continue;
+            }
+
+            let mut edges_seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len());
+
+            let mut stack = Vec::with_capacity(self.nodes_len());
+            stack.push(node);
+
+            while let Some(top) = stack.pop() {
+                if edges_seen_nodes.contains(&top) {
+                    // a cycle is found
+                    return Ok(true);
+                }
+
+                edges_seen_nodes.insert(top);
+
+                let mut local_stack: Vec<usize> = self.children_of(top)?.collect();
+
+                local_stack.reverse();
+
+                stack.extend(local_stack);
+            }
+
+            seen_nodes.extend(edges_seen_nodes);
+        }
+
+        Ok(false)
+    }
+
+    /// Replace the contents of the graph by a builder.
+    fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>);
 }
 
 /// A graph that can be extended, but not mutated, in the sense that
@@ -121,9 +204,15 @@ pub trait ExtGraph: Graph {
 }
 
 /// The type of labels should be comparable and hashable.
-pub trait GraphLabel: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd {}
+pub trait GraphLabel:
+    Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug
+{
+}
 
-impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd> GraphLabel for T {}
+impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug> GraphLabel
+    for T
+{
+}
 
 /// A labelled graph is just a graph with labels associated to
 /// vertices and / or edges.
@@ -182,6 +271,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 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>;
 }
 
 /// A labelled graph that can be extended, but not mutated, in the
@@ -201,3 +294,39 @@ pub trait LabelExtGraph<T: GraphLabel>: LabelGraph<T> {
     /// an error.
     fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error>;
 }
+
+#[cfg(test)]
+mod test_cycle_detection {
+    use super::{builder::Builder, labelled::DLGBuilder, Graph};
+
+    #[test]
+    fn test() -> Result<(), Box<dyn std::error::Error>> {
+        let mut builder: DLGBuilder<usize> = DLGBuilder::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)?;
+        }
+
+        let graph = builder.build_ref();
+
+        assert_eq!(graph.contains_cycles()?, true);
+
+        // Remove the link from the last node to the first node.
+        builder.remove_edge(4, 0, |_| true)?;
+
+        let graph = builder.build();
+
+        assert_eq!(graph.contains_cycles()?, false);
+
+        Ok(())
+    }
+}