chain: a prototype is added.

I have an ostensibly working prototype now.

Further tests are needed to make sure that the algorithm meets the
time complexity requirement, though.

4 files changed, 56 insertions, 15 deletions

diff --git a/graph/src/error.rs b/graph/src/error.rs
index ce45acc..bf2714b 100644
--- a/graph/src/error.rs
+++ b/graph/src/error.rs
@@ -18,8 +18,6 @@ pub enum Error {
     /// The graph does not permit duplicate edges but encounters a
     /// repeated edge.
     DuplicatedEdge(usize, usize),
-    /// The source node has no room to add a new edge.
-    FullNode(usize),
 }
 
 impl Display for Error {
@@ -37,7 +35,6 @@ impl Display for Error {
                     "No duplicate edges permitted, but found one from {source} to {target}"
                 )
             }
-            Error::FullNode(index) => write!(f, "the node {index} has no room for new edges"),
         }
     }
 }
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index bfd8109..e3e1943 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -19,18 +19,22 @@ struct PLChildren {
 }
 
 impl PLChildren {
+    #[inline]
     fn iter(&self) -> Iter<'_, usize> {
         self.children.iter()
     }
 
+    #[inline]
     fn len(&self) -> usize {
         self.children.len()
     }
 
+    #[inline]
     fn is_empty(&self) -> bool {
         self.children.is_empty()
     }
 
+    #[inline]
     fn contains(&self, key: &usize) -> bool {
         self.indices.contains_key(key)
     }
@@ -73,6 +77,15 @@ impl PLChildren {
 
         self.children.remove(key_index);
     }
+
+    /// Retrieve the `n`-th child.
+    #[inline]
+    fn nth(&self, n: usize) -> Result<usize, Error> {
+        self.children
+            .get(n)
+            .copied()
+            .ok_or(Error::IndexOutOfBounds(n, self.children.len()))
+    }
 }
 
 /// A node has some children, some parents, and a label.
@@ -187,7 +200,7 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
     }
 
     fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
-        todo!()
+        unimplemented!("use a `PLGBuilderMut` instead")
     }
 
     fn print_viz(&self, _filename: &str) -> Result<(), std::io::Error> {
@@ -246,6 +259,31 @@ impl<T: GraphLabel> ParentsGraph for PLGraph<T> {
             Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
         }
     }
+
+    #[inline]
+    fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, Error> {
+        if let Some(node) = self.nodes.get(node_id) {
+            node.children.nth(n)
+        } else {
+            Err(Error::IndexOutOfBounds(node_id, self.nodes_len()))
+        }
+    }
+
+    #[inline]
+    fn edge_to_parent(&self, source: usize, target: usize) -> Result<Option<Parent>, Error> {
+        if !self.has_edge(source, target)? {
+            return Ok(None);
+        }
+
+        Ok(self
+            .nodes
+            .get(source)
+            .unwrap()
+            .children
+            .indices
+            .get(&target)
+            .map(|index| Parent::new(source, *index)))
+    }
 }
 
 impl<T: GraphLabel> RedirectGraph for PLGraph<T> {
@@ -378,13 +416,13 @@ impl<'a, T: GraphLabel> std::ops::Deref for PLGBuilderMut<'a, T> {
     type Target = PLGraph<T>;
 
     fn deref(&self) -> &Self::Target {
-        &self.graph
+        self.graph
     }
 }
 
 impl<'a, T: GraphLabel> std::ops::DerefMut for PLGBuilderMut<'a, T> {
     fn deref_mut(&mut self) -> &mut Self::Target {
-        &mut self.graph
+        self.graph
     }
 }
 
diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs
index 4ab8a38..174c8ef 100644
--- a/graph/src/labelled/double.rs
+++ b/graph/src/labelled/double.rs
@@ -150,6 +150,8 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
     }
 
     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\"]
@@ -170,14 +172,14 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
 
         let result = format!("{preamble}{post}");
 
-        if std::fs::metadata(filename).is_ok() {
-            std::fs::remove_file(filename)?;
+        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)?;
+            .open(&filename)?;
 
         use std::io::Write;
 
@@ -206,7 +208,7 @@ impl<'a> Iterator for LabelIndexIter<'a> {
 
     #[inline]
     fn next(&mut self) -> Option<Self::Item> {
-        self.iter.as_mut().and_then(|iterator| iterator.next())
+        self.iter.as_mut().and_then(Iterator::next)
     }
 
     #[inline]
@@ -242,7 +244,7 @@ impl<'a> From<&'a Set<usize>> for LabelIndexIter<'a> {
     }
 }
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 /// A delegation of iterators.
 ///
 /// This is used to avoid a boxed pointer to an iterator.
@@ -278,7 +280,7 @@ impl<'a, T> Iterator for LabelIter<'a, T> {
 }
 
 /// This is used to avoid a boxed pointer to an iterator.
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct EdgeLabelIter<'a, T> {
     iter: Option<Iter<'a, T>>,
 }
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 6af7889..2a0c50d 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -251,10 +251,14 @@ pub trait ParentsGraph: Graph {
 
     /// Return an iterator of parents for a node.
     fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, Error>;
-}
 
-// TODO: Design a trait of graphs which can "replace" a certain child
-// by another child.  To re-direct children, so to speak.
+    /// We need to be able to retrieve the `n`-the child, for the edge
+    /// index to be of any use.
+    fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, Error>;
+
+    /// Convert an edge to a `Parent` construct.
+    fn edge_to_parent(&self, source: usize, target: usize) -> Result<Option<Parent>, Error>;
+}
 
 /// An /exended/ graph in the sense that it offers the ability to
 /// "redirect" children of a node to another node.