diff options
Diffstat (limited to 'forest')
| -rw-r--r-- | forest/Cargo.toml | 6 | ||||
| -rw-r--r-- | forest/src/default.rs | 484 | ||||
| -rw-r--r-- | forest/src/lib.rs | 81 |
3 files changed, 498 insertions, 73 deletions
diff --git a/forest/Cargo.toml b/forest/Cargo.toml index b88451d..c51bf36 100644 --- a/forest/Cargo.toml +++ b/forest/Cargo.toml @@ -5,5 +5,11 @@ edition = "2021" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html +[features] +default = [] + +# This flag controls whether to print GraphViz files during testing. +test-print-viz = [] + [dependencies] graph = { path = "../graph" } diff --git a/forest/src/default.rs b/forest/src/default.rs index d3970e9..d79c1c7 100644 --- a/forest/src/default.rs +++ b/forest/src/default.rs @@ -1,21 +1,471 @@ //! This file provides a default implementation for the //! [`Forest`][crate::Forest] trait. -#[allow(unused_imports)] use super::*; -#[allow(unused_imports)] -use graph::{error::Error as GraphError, ALGraph, Graph}; - -#[allow(unused_imports)] -use std::collections::{hash_set::Iter, HashMap, HashSet}; - -// TODO: Use PLGraph instead. - -// #[derive(Debug, Clone)] -// pub struct DefaultForest<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> { -// graph: ALGraph, -// vertex_labels: HashMap<usize, NodeLabel>, -// edge_labels: HashMap<(usize, usize), EdgeLabel>, -// plugins: HashSet<usize>, -// plugouts: HashSet<usize>, -// } +use graph::{ + builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, LabelGraph, PLGraph, RedirectGraph, +}; + +use core::fmt::Display; + +/// The type of errors for forest operations. +#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd)] +pub enum Error { + /// An 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 forest does not permit duplicate nodes but encounters a + /// repeated node. + DuplicatedNode(usize), + /// A node has no labels while it is required to have one. + NodeNoLabel(usize), + /// Encounter an invalid error in converting from an error of + /// graphs. + InvalidGraphError(GError), +} + +impl Display for Error { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Error::IndexOutOfBounds(index, bound) => { + write!(f, "index {index} is out of bound {bound}") + } + Error::DuplicatedNode(n) => write!(f, "node {n} is duplicated"), + Error::InvalidGraphError(ge) => write!(f, "invalid error: {ge}"), + Error::NodeNoLabel(n) => write!(f, "node {n} has no labels, but it should have one"), + } + } +} + +impl std::error::Error for Error {} + +impl From<GError> for Error { + fn from(ge: GError) -> Self { + match ge { + GError::IndexOutOfBounds(index, bound) => Self::IndexOutOfBounds(index, bound), + GError::DuplicatedNode(n) => Self::DuplicatedNode(n), + _ => Self::InvalidGraphError(ge), + } + } +} + +/// A default implementation of forest. +#[derive(Debug, Clone)] +pub struct DefaultForest<T: GraphLabel> { + graph: PLGraph<T>, + root: Option<usize>, +} + +impl<T: GraphLabel> Default for DefaultForest<T> { + fn default() -> Self { + let graph = Default::default(); + let root = None; + + Self { graph, root } + } +} + +impl<T: GraphLabel> AsRef<DefaultForest<T>> for DefaultForest<T> { + fn as_ref(&self) -> &DefaultForest<T> { + &self + } +} + +impl<T: GraphLabel> Graph for DefaultForest<T> { + type Iter<'a> = <PLGraph<T> as Graph>::Iter<'a> + where + Self: 'a; + + #[inline] + fn is_empty(&self) -> bool { + self.graph.is_empty() + } + + #[inline] + fn nodes_len(&self) -> usize { + self.graph.nodes_len() + } + + #[inline] + fn edges_len(&self) -> Option<usize> { + self.graph.edges_len() + } + + #[inline] + fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, GError> { + self.graph.children_of(node_id) + } + + #[inline] + fn degree(&self, node_id: usize) -> Result<usize, GError> { + self.graph.degree(node_id) + } + + #[inline] + fn is_empty_node(&self, node_id: usize) -> Result<bool, GError> { + self.graph.is_empty_node(node_id) + } + + #[inline] + fn has_edge(&self, source: usize, target: usize) -> Result<bool, GError> { + self.graph.has_edge(source, target) + } + + fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) { + unimplemented!() + } +} + +impl<T: GraphLabel> ParentsGraph for DefaultForest<T> { + type Iter<'a>= <PLGraph<T> as ParentsGraph>::Iter<'a> + where + Self:'a; + + fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, GError> { + self.graph.parents_of(node_id) + } +} + +impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> { + type Iter<'a> = std::iter::Empty<usize> + where + Self: 'a; + + type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::iter::Empty<T> + where + Self: 'a, + T: 'a; + + #[inline] + fn query_label(&self, label: T) -> Option<usize> { + self.graph.query_label(label) + } + + #[inline] + fn vertex_label(&self, node_id: usize) -> Result<Option<T>, GError> { + self.graph.vertex_label(node_id) + } + + fn edge_label( + &self, + _source: usize, + _target: usize, + ) -> Result<Self::EdgeLabelIter<'_>, GError> { + unimplemented!("edges have no labels") + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &T, + ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, GError> { + unimplemented!("edges have no labels") + } + + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> { + unimplemented!("edges have no labels") + } + + fn has_edge_label(&self, _node_id: usize, _label: &T, _target: usize) -> Result<bool, GError> { + unimplemented!("edges have no labels") + } +} + +impl<T: GraphLabel> Forest<T> for DefaultForest<T> { + type Error = Error; + + fn root(&self) -> Option<usize> { + self.root + } + + fn new_leaf(label: T) -> Self { + let mut graph = PLGraph::default(); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut graph); + + let root = Some(builder.add_vertex(label)); + + Self { graph, root } + } + + fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error> + where + F: AsRef<Self>, + { + if !self.has_node(node_id) { + return Err(Error::IndexOutOfBounds(node_id, self.nodes_len())); + } + + // We do a depth-first traversal to determine if every node + // encountered has the same set of children (labels taken into + // the consideration). + + let fragment = fragment.as_ref(); + + let mut frag_stack = Vec::with_capacity(fragment.nodes_len()); + + let mut self_stack = Vec::with_capacity(fragment.nodes_len()); + + let frag_root = if let Some(root) = fragment.root() { + root + } else { + // an empty forest is a prefix of any forest. + return Ok(true); + }; + + frag_stack.push(frag_root); + self_stack.push(node_id); + + // defer popping + while let (Some(frag_top), Some(self_top)) = + (frag_stack.last().copied(), self_stack.last().copied()) + { + frag_stack.pop(); + self_stack.pop(); + + if fragment.vertex_label(frag_top)? != self.vertex_label(self_top)? { + // not a prefix + return Ok(false); + } + + let mut self_children = self.children_of(self_top)?; + + for child in fragment.children_of(frag_top)? { + if let Some(self_child) = self_children.next() { + frag_stack.push(child); + self_stack.push(self_child); + } else { + // too few children + return Ok(false); + } + } + } + + // Check both stacks are empty at the end. + Ok(frag_stack.is_empty() && self_stack.is_empty()) + } + + fn plant<F>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error> + where + F: AsRef<Self>, + { + // Convert self to a builder_mut, and traverse fragment in a + // depth-first manner and adjoin corresponding nodes along the + // way. + + if !self.has_node(node_id) { + return Err(Error::IndexOutOfBounds(node_id, self.nodes_len())); + } + + let fragment = fragment.as_ref(); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + let root = if let Some(root) = fragment.root() { + root + } else { + // Nothing to do to plant an empty forest. + return Ok(()); + }; + + // Just a dummy label for use in adding edges. + // + // REVIEW: I probably should refactor the API for builder_mut. + let root_label = fragment + .vertex_label(root)? + .ok_or(Error::NodeNoLabel(root))?; + + let nodes_len = fragment.nodes_len(); + + // First adjoin those nodes and join the edges later. + + for node in 0..nodes_len { + let label = fragment + .vertex_label(node)? + .ok_or(Error::NodeNoLabel(node))?; + + builder.add_vertex(label); + } + + // If the fragment root has a duplicate label, the forest will + // not grow, so we use the label to find the adjoined node + // index. + + // the nodes hava already been added to the forest, so it is + // safe to call unwrap. + macro_rules! conversion ( + ($node:expr) => { + { + builder + .query_label( + fragment + .vertex_label($node)? + .ok_or(Error::NodeNoLabel($node))? + ).unwrap() + } + } + ); + + // Don't forget to join the new sub-forest to the original + // forest, at the specified position. + + builder.add_edge(node_id, conversion!(root), root_label)?; + + // We can try to calculate the depth of fragments, if we need + // to lower the memory usage. But in our use cases, we + // usually deal with fragments where each node has at most one + // child, so the depth is supposed to be equal to the length + // in this case. + let mut stack = Vec::with_capacity(fragment.nodes_len()); + + stack.push(root); + + while let Some(top) = stack.pop() { + for child in fragment.children_of(top)? { + builder.add_edge(conversion!(top), conversion!(child), root_label)?; + } + } + + Ok(()) + } + + fn clone_node<F>(&mut self, node_id: usize, clone_transform: F) -> Result<usize, Self::Error> + where + F: Fn(T) -> T, + { + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + let old_label = builder + .vertex_label(node_id)? + .ok_or(Error::NodeNoLabel(node_id))?; + + let new_label = clone_transform(old_label); + + // Make a new node + let new_index = builder.add_vertex(new_label); + + // Re-direct parents to the new node. + // + // This must be done before pointing the new node to the old + // node, otherwise that edge will be redirected as well. + + // Unfortunately I cannot loop through parents and mutate them + // at the same time, so I first collect them into a vector. + let parents: Vec<_> = builder.parents_of(node_id)?.collect(); + + for parent in parents.into_iter() { + builder.redirect(parent.node(), parent.edge(), new_index)?; + } + + // Point the new node to the old node. OLD_LABEL is just a + // place holder. + + builder.add_edge(new_index, node_id, old_label)?; + + Ok(new_index) + } +} + +#[cfg(test)] +mod forest_test { + use super::*; + + macro_rules! leaf ( + ($label:expr, $type:tt) =>{ + DefaultForest::<$type>::new_leaf($label) + }; + ($label:expr) => { + DefaultForest::<usize>::new_leaf($label) + } + ); + + #[test] + fn test_forest_api() -> Result<(), Box<dyn std::error::Error>> { + let forest: DefaultForest<usize> = Default::default(); + + // empty forest + + assert!(forest.is_empty()); + + // leaf forest + + let mut forest = leaf!(0, usize); + + assert_eq!(forest.nodes_len(), 1); + assert_eq!(forest.root(), Some(0)); + + // add some child + + forest.plant(0, leaf!(1))?; + + assert_eq!(forest.nodes_len(), 2); + let mut children = forest.children_of(0)?; + assert_eq!(children.next(), Some(1)); + assert_eq!(children.next(), None); + + // add more children + + forest.plant(0, leaf!(2))?; + forest.plant(0, leaf!(3))?; + forest.plant(0, leaf!(4))?; + forest.plant(2, leaf!(5))?; + + assert_eq!(forest.nodes_len(), 6); + let mut children = forest.children_of(0)?; + assert_eq!(children.next(), Some(1)); + assert_eq!(children.next(), Some(2)); + assert_eq!(children.next(), Some(3)); + assert_eq!(children.next(), Some(4)); + let mut children = forest.children_of(2)?; + assert_eq!(children.next(), Some(5)); + assert_eq!(children.next(), None); + + let mut test_forest = leaf!(0); + test_forest.plant(0, leaf!(1))?; + test_forest.plant(0, leaf!(2))?; + test_forest.plant(0, leaf!(3))?; + test_forest.plant(2, leaf!(5))?; + + assert!(forest.is_prefix(0, &test_forest)?); + + let mut test_forest = leaf!(0); + test_forest.plant(0, leaf!(1))?; + test_forest.plant(0, leaf!(2))?; + // this child of the root should have label 3 in order to be a + // prefix. + test_forest.plant(0, leaf!(4))?; + test_forest.plant(2, leaf!(5))?; + + assert!(!forest.is_prefix(0, &test_forest)?); + + let mut test_forest = leaf!(2); + test_forest.plant(0, leaf!(5))?; + + assert!(forest.is_prefix(2, &test_forest)?); + + // now test cloning + + // add a duplicate label + forest.plant(3, leaf!(5))?; + + let len = forest.nodes_len(); + + let clone_transform = |label| label + len; + + forest.clone_node(5, clone_transform)?; + + assert_eq!(forest.nodes_len(), 7); + + #[cfg(feature = "test-print-viz")] + forest.print_viz("forest.gv")?; + + Ok(()) + } +} diff --git a/forest/src/lib.rs b/forest/src/lib.rs index c2f4988..f843bc1 100644 --- a/forest/src/lib.rs +++ b/forest/src/lib.rs @@ -11,57 +11,7 @@ //! out-coming and in-coming plugs. These plugs are used to join //! different fragments of forests together. -use graph::{GraphLabel, LabelGraph, ParentsGraph}; - -use core::fmt::Display; - -// TODO: move this to default - -/// The type of errors for forest operations. -#[derive(Debug)] -pub enum Error { - /// An index is out of bounds. - IndexOutOfBounds(usize, usize), -} - -impl Display for Error { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - match self { - Error::IndexOutOfBounds(index, bound) => { - write!(f, "index {index} is out of bound {bound}") - } - } - } -} - -impl std::error::Error for Error {} - -// /// A builder of a forest. -// pub trait ForestBuilder<NodeLabel: GraphLabel, EdgeLabel: GraphLabel> { -// /// The type of the resulting forest. -// type Output: Forest<NodeLabel, EdgeLabel>; - -// /// Construct a new builder with only one node with the given -// /// label. -// fn new_leaf(label: NodeLabel) -> Self; - -// /// Add a child to the builder the given labels for the new node -// /// and the added edge. -// /// -// /// All plug-out nodes within the builder should have a new child -// /// with the specified labels, and hence multiple children might -// /// be added, and the plug-out nodes should be modified -// /// accordingly. -// fn add_children(&mut self, vertex_label: NodeLabel, edge_labe: EdgeLabel); - -// /// Build the forest. -// fn build(self) -> Self::Output; - -// /// Build the forest from a reference. -// fn build_ref(&self) -> Self::Output; -// } - -// FIXME: The trait should be re-designed. +use graph::{error::Error as GError, GraphLabel, LabelGraph, ParentsGraph}; /// The expected behaviours of a forest. /// @@ -69,19 +19,38 @@ impl std::error::Error for Error {} /// labelled graphs. pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<T> { /// The type of errors for operations on the forest. - type Error: std::error::Error + From<graph::error::Error>; + type Error: std::error::Error + From<GError>; + + /// Return the root of the forest. + /// + /// A forest without a root is regarded as empty. + fn root(&self) -> Option<usize>; + + /// Construct a forest consisting of one leaf node with the given + /// label. + fn new_leaf(label: T) -> Self; /// Detect if the fragment is a prefix of the sub-forest rooted at /// `node_id`. - fn is_prefix<F: AsRef<Self>>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>; + fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error> + where + F: AsRef<Self>; /// Extend the forest by adjoining another forest at a given node. - fn plant<F: AsRef<Self>>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error>; + fn plant<F>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error> + where + F: AsRef<Self>; /// Clone a node by making a new node and making all the nodes /// that previously pointed to the old node now point to the new - /// node, and the new node points to the old node. - fn clone(&mut self, node_id: usize) -> Result<(), Self::Error>; + /// node, and the new node points to the old node. Return the + /// index of the new node. + /// + /// The label of the new node will be given by the label + /// transformer. + fn clone_node<F>(&mut self, node_id: usize, clone_transform: F) -> Result<usize, Self::Error> + where + F: Fn(T) -> T; } pub mod default; |