From 18d7955b7d84c00467ede38baae53f4ce1fb6908 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 20 Jan 2023 13:48:26 +0800 Subject: 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. --- graph/src/error.rs | 3 --- graph/src/labelled/binary.rs | 44 +++++++++++++++++++++++++++++++++++++++++--- graph/src/labelled/double.rs | 14 ++++++++------ graph/src/lib.rs | 10 +++++++--- 4 files changed, 56 insertions(+), 15 deletions(-) (limited to 'graph') 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 { + 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 Graph for PLGraph { } fn replace_by_builder(&mut self, _builder: impl Builder) { - todo!() + unimplemented!("use a `PLGBuilderMut` instead") } fn print_viz(&self, _filename: &str) -> Result<(), std::io::Error> { @@ -246,6 +259,31 @@ impl ParentsGraph for PLGraph { Err(Error::IndexOutOfBounds(node_id, self.nodes.len())) } } + + #[inline] + fn nth_child(&self, node_id: usize, n: usize) -> Result { + 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, 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 RedirectGraph for PLGraph { @@ -378,13 +416,13 @@ impl<'a, T: GraphLabel> std::ops::Deref for PLGBuilderMut<'a, T> { type Target = PLGraph; 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 Graph for DLGraph { } 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 Graph for DLGraph { 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.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> 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>, } 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<::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; + + /// Convert an edge to a `Parent` construct. + fn edge_to_parent(&self, source: usize, target: usize) -> Result, Error>; +} /// An /exended/ graph in the sense that it offers the ability to /// "redirect" children of a node to another node. -- cgit v1.2.3-18-g5258