From 8f8d3d1a3c276be4be2e5d2e767ada564c47279a Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 13 Jan 2023 14:26:28 +0800 Subject: forest seems to be completed I seem to have finished the implementation of forests. Now it remains the implementation of the chain-rule machine, of which I have a rough plan now. --- Cargo.toml | 2 +- chain/src/plan.org | 19 +- forest/Cargo.toml | 6 + forest/src/default.rs | 484 ++++++++++++++++++++++++- forest/src/lib.rs | 81 ++--- grammar/Cargo.toml | 3 + grammar/src/lib.rs | 15 +- grammar/src/tests/test_grammar_left_closure.rs | 38 +- graph/src/labelled/binary.rs | 171 ++++++++- graph/src/labelled/mod.rs | 1 + graph/src/lib.rs | 18 + 11 files changed, 727 insertions(+), 111 deletions(-) diff --git a/Cargo.toml b/Cargo.toml index e34a8cf..1ddd0a0 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -13,7 +13,7 @@ rust-version = "1.65" [workspace] members = [ "graph", "receme", "nfa", "chain", "viz", "grammar", - "forest", "semiring"] + "forest", "semiring", "graph_macro" ] # testing the new resolver, even though this has no dependencies ;p resolver = "2" diff --git a/chain/src/plan.org b/chain/src/plan.org index b708413..84192f0 100644 --- a/chain/src/plan.org +++ b/chain/src/plan.org @@ -2,7 +2,7 @@ #+AUTHOR: Durand #+DATE: <2022-11-18 Ven 19:57> -* Things to do [6/10] +* Things to do [7/10] - [X] Implement builders for graphs - [X] Find sets of the first terminals for each non-terminal, in the @@ -79,6 +79,15 @@ lack of this step might be the root cause of the failure of the previous version of this project. + [X] Test atoms +- [X] Implement forests [4/4] + + [X] Design a format of forests. This should be the most crucial + thing to do, in order to have a better understanding of the whole + picture. I need to have a clear understanding of the details of + the binarised shared packed parsed forests, that reflects the + regular expressions in the grammar equations. + + [X] Define a trait with the expected behaviours. + + [X] Implement them as parents-knowing graphs. + + [X] Test - [-] Implement languages. [1/4] + [X] First define a trait with the expected behaviours. + [ ] Then implement them as doubly labelled graphs. @@ -86,14 +95,6 @@ + [ ] Each edge in the chain-rule machine needs to be labelled also with a position in the forest. This perfectly solves the problem of those "plugs"! -- [-] Implement forests [2/3] - + [X] Design a format of forests. This should be the most crucial - thing to do, in order to have a better understanding of the whole - picture. I need to have a clear understanding of the details of - the binarised shared packed parsed forests, that reflects the - regular expressions in the grammar equations. - + [X] Define a trait with the expected behaviours. - + [-] Implement them as parents-knowing graphs. - [ ] Implement semiring. [0/5] + [ ] Define the trait. + [ ] Implement the boolean semiring. 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 { -// graph: ALGraph, -// vertex_labels: HashMap, -// edge_labels: HashMap<(usize, usize), EdgeLabel>, -// plugins: HashSet, -// plugouts: HashSet, -// } +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 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 { + graph: PLGraph, + root: Option, +} + +impl Default for DefaultForest { + fn default() -> Self { + let graph = Default::default(); + let root = None; + + Self { graph, root } + } +} + +impl AsRef> for DefaultForest { + fn as_ref(&self) -> &DefaultForest { + &self + } +} + +impl Graph for DefaultForest { + type Iter<'a> = 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 { + self.graph.edges_len() + } + + #[inline] + fn children_of(&self, node_id: usize) -> Result, GError> { + self.graph.children_of(node_id) + } + + #[inline] + fn degree(&self, node_id: usize) -> Result { + self.graph.degree(node_id) + } + + #[inline] + fn is_empty_node(&self, node_id: usize) -> Result { + self.graph.is_empty_node(node_id) + } + + #[inline] + fn has_edge(&self, source: usize, target: usize) -> Result { + self.graph.has_edge(source, target) + } + + fn replace_by_builder(&mut self, _builder: impl graph::Builder) { + unimplemented!() + } +} + +impl ParentsGraph for DefaultForest { + type Iter<'a>= as ParentsGraph>::Iter<'a> + where + Self:'a; + + fn parents_of(&self, node_id: usize) -> Result<::Iter<'_>, GError> { + self.graph.parents_of(node_id) + } +} + +impl LabelGraph for DefaultForest { + type Iter<'a> = std::iter::Empty + where + Self: 'a; + + type LabelIter<'a> = std::iter::Empty<(&'a T, >::Iter<'a>)> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::iter::Empty + where + Self: 'a, + T: 'a; + + #[inline] + fn query_label(&self, label: T) -> Option { + self.graph.query_label(label) + } + + #[inline] + fn vertex_label(&self, node_id: usize) -> Result, GError> { + self.graph.vertex_label(node_id) + } + + fn edge_label( + &self, + _source: usize, + _target: usize, + ) -> Result, GError> { + unimplemented!("edges have no labels") + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &T, + ) -> Result<>::Iter<'_>, GError> { + unimplemented!("edges have no labels") + } + + fn labels_of(&self, _node_id: usize) -> Result, GError> { + unimplemented!("edges have no labels") + } + + fn has_edge_label(&self, _node_id: usize, _label: &T, _target: usize) -> Result { + unimplemented!("edges have no labels") + } +} + +impl Forest for DefaultForest { + type Error = Error; + + fn root(&self) -> Option { + 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(&self, node_id: usize, fragment: F) -> Result + where + F: AsRef, + { + 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(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error> + where + F: AsRef, + { + // 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(&mut self, node_id: usize, clone_transform: F) -> Result + 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::::new_leaf($label) + } + ); + + #[test] + fn test_forest_api() -> Result<(), Box> { + let forest: DefaultForest = 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 { -// /// The type of the resulting forest. -// type Output: Forest; - -// /// 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: ParentsGraph + LabelGraph { /// The type of errors for operations on the forest. - type Error: std::error::Error + From; + type Error: std::error::Error + From; + + /// Return the root of the forest. + /// + /// A forest without a root is regarded as empty. + fn root(&self) -> Option; + + /// 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>(&self, node_id: usize, fragment: F) -> Result; + fn is_prefix(&self, node_id: usize, fragment: F) -> Result + where + F: AsRef; /// Extend the forest by adjoining another forest at a given node. - fn plant>(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error>; + fn plant(&mut self, node_id: usize, fragment: F) -> Result<(), Self::Error> + where + F: AsRef; /// 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(&mut self, node_id: usize, clone_transform: F) -> Result + where + F: Fn(T) -> T; } pub mod default; diff --git a/grammar/Cargo.toml b/grammar/Cargo.toml index 20c4b48..793ab5a 100644 --- a/grammar/Cargo.toml +++ b/grammar/Cargo.toml @@ -12,6 +12,9 @@ default = [] # some grammars for testing. test-helper = [] +# This flag controls whether to print GraphViz files during testing. +test-print-viz = [] + [dependencies] nfa = { path = "../nfa" } graph = { path = "../graph" } diff --git a/grammar/src/lib.rs b/grammar/src/lib.rs index 627ae6f..297cb66 100644 --- a/grammar/src/lib.rs +++ b/grammar/src/lib.rs @@ -462,6 +462,19 @@ impl Grammar { // REVIEW: Do we have a better way to record expansion information // than to compute the transitive closure? + // REVIEW: We need a way to eliminate those left-linearly expanded + // edges whose labels had already been considered, and we need to + // preserve the transition of the `left_p` property at the same + // time. + // + // Maybe we could decide to delete those edges in the + // `remove_predicate`? But we cannot access the states of NFA in + // that predicate, in the current design, thus we need to refactor + // some codes, it seems: we need a way to "compactify" an NFA, by + // a key function, in such a way that if two entries have the same + // key (determined by the key function), then only one, determined + // by another function, remains in the NFA. + /// A transformer of labels to be fed into /// [`closure`][nfa::default::nfa::DefaultNFA::closure], with the /// predicate that returns true if and only if the label of the @@ -483,7 +496,7 @@ impl Grammar { } // Compute if this is from left-linear expansion: it is so if - // and only if one if either the edges comes from left-linear + // and only if either one of the edges comes from left-linear // expansion or we are moving across a non-terminal expansion, // that is to say, the source of the second edge is the // starting edge of a non-terminal. diff --git a/grammar/src/tests/test_grammar_left_closure.rs b/grammar/src/tests/test_grammar_left_closure.rs index 003c211..ffc7c0f 100644 --- a/grammar/src/tests/test_grammar_left_closure.rs +++ b/grammar/src/tests/test_grammar_left_closure.rs @@ -33,9 +33,6 @@ fn test_regex() -> Result<(), Box> { Ok(()) } -// We ignore this test by default as it is possibly involved with -// printing to a graphviz file. -#[ignore] #[test] fn test_nfa() -> Result<(), Box> { let mut grammar = new_notes_grammar()?; @@ -69,19 +66,22 @@ fn test_nfa() -> Result<(), Box> { grammar .left_closure_to_nfa(&closure) .map(|_| ()) - .map_err(Into::into) + .map_err(Into::>::into)?; // let _nfa = grammar.left_closure_to_nfa(&closure)?; - // writeln!(lock, "Not printing nfa to nfa.gv")?; + #[cfg(features = "test-print-viz")] + { + writeln!(lock, "Not printing nfa to nfa.gv")?; - // nfa.print_viz("nfa.gv").map_err(Into::into) + nfa.print_viz("nfa.gv") + .map_err(Into::>::into)?; + } - // Ok(()) + Ok(()) } #[test] -#[ignore] fn test_remove_epsilon() -> Result<(), Box> { let mut lock = stdout().lock(); @@ -123,17 +123,18 @@ fn test_remove_epsilon() -> Result<(), Box> { let mut nfa = grammar.left_closure_to_nfa(&closure)?; + #[cfg(features = "test-print-viz")] nfa.print_viz("nfa_orig.gv")?; nfa.remove_epsilon(|label| label.get_value().is_none())?; + #[cfg(features = "test-print-viz")] nfa.print_viz("nfa_no_epsilon.gv")?; Ok(()) } #[test] -#[ignore] fn test_remove_dead() -> Result<(), Box> { let mut grammar = new_paren_grammar()?; let closure = new_closure_regex(&mut grammar)?; @@ -173,9 +174,10 @@ fn test_remove_dead() -> Result<(), Box> { let mut nfa = grammar.left_closure_to_nfa(&closure)?; + #[cfg(features = "test-print-viz")] nfa.print_viz("nfa_orig.gv")?; - nfa.remove_epsilon(|label| label.get_value().is_none())?; + // nfa.remove_epsilon(|label| label.get_value().is_none())?; let accumulators: HashSet = accumulators.into_iter().collect(); @@ -183,15 +185,22 @@ fn test_remove_dead() -> Result<(), Box> { let grammar_reserve_node = |node| accumulators.contains(&node); + nfa.closure( + |label| label.get_value().is_none(), + true, + |two_edges| two_edges.second_edge().2, + |label| label.get_value().is_none(), + )?; + nfa.remove_dead(grammar_reserve_node)?; + #[cfg(features = "test-print-viz")] nfa.print_viz("nfa_no_dead.gv")?; Ok(()) } #[test] -#[ignore] fn test_nulling() -> Result<(), Box> { // TODO: Test more grammars. let mut grammar = new_right_recursive_grammar()?; @@ -273,9 +282,12 @@ fn test_nulling() -> Result<(), Box> { nfa.remove_dead(grammar_reserve_nodes)?; - writeln!(lock, "Printing nfa to nfa.gv")?; + #[cfg(features = "test-print-viz")] + { + writeln!(lock, "Printing nfa to nfa.gv")?; - nfa.print_viz("nfa.gv")?; + nfa.print_viz("nfa.gv")?; + } Ok(()) } diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs index 67d86f9..bfd8109 100644 --- a/graph/src/labelled/binary.rs +++ b/graph/src/labelled/binary.rs @@ -2,7 +2,7 @@ //! labels and each node knows about its parents. use super::*; -use crate::{Parent, ParentsGraph}; +use crate::{Parent, ParentsGraph, RedirectGraph}; use std::{ collections::{hash_map::Iter as MapIter, HashMap as Map}, @@ -141,6 +141,11 @@ impl Graph for PLGraph { self.nodes.len() } + #[inline] + fn edges_len(&self) -> Option { + Some(self.nodes.iter().map(|node| node.children.len()).sum()) + } + #[inline] fn children_of(&self, node_id: usize) -> Result, Error> { if let Some(node) = self.nodes.get(node_id) { @@ -243,6 +248,76 @@ impl ParentsGraph for PLGraph { } } +impl RedirectGraph for PLGraph { + fn redirect( + &mut self, + node_id: usize, + child_index: usize, + new_child: usize, + ) -> Result<(), Error> { + let nodes_len = self.nodes.len(); + + if !self.has_node(new_child) { + return Err(Error::IndexOutOfBounds(new_child, nodes_len)); + } + + if let Some(node) = self.nodes.get_mut(node_id) { + if node.children.len() <= child_index { + return Err(Error::IndexOutOfBounds(child_index, node.children.len())); + } + + // Check if `new_child` is already pointed to by the node. + if let Some(index) = node.children.indices.get(&new_child) { + // This should not happen in our use case, but we + // should still do somthing: as the edges cannot + // duplicate, we simply remove the original edge, + // unless index = child_index, in which case the old + // child is equal to the new child, and we have + // nothing to do. + if *index != child_index { + node.children.remove(new_child); + } + } else { + // The index has been checked above, so it is safe to + // call `unwrap` here. + let old_child = std::mem::replace( + node.children.children.get_mut(child_index).unwrap(), + new_child, + ); + + node.children.indices.remove(&old_child); + + node.children.indices.insert(new_child, child_index); + + // Don't forget to remove `node` from the parents of + // the old child. + + if let Some(old_child_node) = self.nodes.get_mut(old_child) { + old_child_node.parents.remove(&node_id); + } else { + // The node contained an invalid child. + return Err(Error::IndexOutOfBounds(old_child, nodes_len)); + } + + // Don't forget to add node as a parent to the new + // child. + + // new_child has been checked at the beginning of the + // function, so it is safe to call `unwrap`. + self.nodes + .get_mut(new_child) + .unwrap() + .parents + .insert(node_id, child_index); + } + + Ok(()) + } else { + Err(Error::IndexOutOfBounds(node_id, nodes_len)) + } + } +} + impl LabelGraph for PLGraph { type Iter<'a> = std::iter::Empty where @@ -299,6 +374,20 @@ pub struct PLGBuilderMut<'a, T: GraphLabel> { graph: &'a mut PLGraph, } +impl<'a, T: GraphLabel> std::ops::Deref for PLGBuilderMut<'a, T> { + type Target = PLGraph; + + fn deref(&self) -> &Self::Target { + &self.graph + } +} + +impl<'a, T: GraphLabel> std::ops::DerefMut for PLGBuilderMut<'a, T> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.graph + } +} + impl<'a, T: GraphLabel> BuilderMut for PLGBuilderMut<'a, T> { type Label = T; @@ -467,6 +556,8 @@ mod binary_test { builder.add_vertex(4); builder.add_vertex(5); + // These labels are not used on edges: they are just place + // holders. builder.add_edge(1, 0, 0)?; builder.add_edge(2, 0, 0)?; builder.add_edge(2, 1, 0)?; @@ -481,43 +572,73 @@ mod binary_test { // testing adding a duplicatedly labelled node assert_eq!(builder.add_vertex(0), 0); - let graph = graph; - // ensuring the correct length - assert_eq!(graph.nodes_len(), 6); + assert_eq!(builder.nodes_len(), 6); // testing children_of - assert_eq!(graph.children_of(5)?.collect::>(), set!(1, 3, 2)); + assert_eq!(builder.children_of(5)?.collect::>(), set!(1, 3, 2)); // testing parents_of assert_eq!( - graph.parents_of(0)?.collect::>(), + builder.parents_of(0)?.collect::>(), set!(Parent::new(1, 0), Parent::new(2, 0), Parent::new(3, 0)) ); assert_eq!( - graph.parents_of(1)?.collect::>(), + builder.parents_of(1)?.collect::>(), set!(Parent::new(2, 1), Parent::new(4, 0), Parent::new(5, 2)) ); - assert_eq!(graph.parents_of(5)?.len(), 0); + assert_eq!(builder.parents_of(5)?.len(), 0); // testing degree - assert_eq!(graph.degree(4)?, 2); + assert_eq!(builder.degree(4)?, 2); // testing is_empty_node - assert!(graph.is_empty_node(0)?); - assert!(!graph.is_empty_node(1)?); + assert!(builder.is_empty_node(0)?); + assert!(!builder.is_empty_node(1)?); // testing has_edge - assert!(graph.has_edge(3, 2)?); - assert!(!graph.has_edge(3, 1)?); + assert!(builder.has_edge(3, 2)?); + assert!(!builder.has_edge(3, 1)?); assert!(matches!( - graph.has_edge(3, 6), + builder.has_edge(3, 6), Err(Error::IndexOutOfBounds(6, 6)) )); + // testing redirect + builder.redirect(5, 2, 0)?; + assert_eq!(builder.children_of(5)?.collect::>(), set!(0, 3, 2)); + + assert_eq!( + builder.parents_of(0)?.collect::>(), + set!( + Parent::new(1, 0), + Parent::new(2, 0), + Parent::new(3, 0), + Parent::new(5, 2) + ) + ); + + builder.redirect(5, 0, 1)?; + + assert_eq!(builder.children_of(5)?.collect::>(), set!(1, 0, 3)); + + assert_eq!( + builder.parents_of(1)?.collect::>(), + set!(Parent::new(2, 1), Parent::new(4, 0), Parent::new(5, 0)) + ); + + builder.redirect(5, 0, 1)?; // should be no-op + + assert_eq!(builder.children_of(5)?.collect::>(), set!(1, 0, 3)); + + assert_eq!( + builder.parents_of(1)?.collect::>(), + set!(Parent::new(2, 1), Parent::new(4, 0), Parent::new(5, 0)) + ); + Ok(()) } } @@ -636,6 +757,28 @@ mod test_plgraph_builder { // println!(); + // source out of bounds + assert!(matches!( + builder.redirect(5, 0, 0), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + // child_index out of bounds + assert!(matches!( + builder.redirect(4, 0, 0), + Err(Error::IndexOutOfBounds(0, 0)) + )); + + // new_child out of bounds + assert!(matches!( + builder.redirect(4, 0, 10), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + // println!("Correct errors when redirecting"); + + // println!(); + let graph = graph; println!("final graph: {graph:?}"); diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs index fa26bc4..2bbc7ec 100644 --- a/graph/src/labelled/mod.rs +++ b/graph/src/labelled/mod.rs @@ -16,5 +16,6 @@ pub mod double; pub use double::{DLGBuilder, DLGraph}; pub mod binary; +pub use binary::{PLGBuilderMut, PLGraph}; // pub use binary::BLGraph; diff --git a/graph/src/lib.rs b/graph/src/lib.rs index 6813df3..6af7889 100644 --- a/graph/src/lib.rs +++ b/graph/src/lib.rs @@ -23,6 +23,7 @@ pub use adlist::ALGraph; pub mod labelled; pub use labelled::DLGraph; +pub use labelled::PLGraph; pub mod builder; @@ -252,6 +253,23 @@ pub trait ParentsGraph: Graph { 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. + +/// An /exended/ graph in the sense that it offers the ability to +/// "redirect" children of a node to another node. +pub trait RedirectGraph: Graph { + /// Replace the edge that points from `node_id` to the + /// `child_index`-th child by a new edge that points to + /// `new_child`. + fn redirect( + &mut self, + node_id: usize, + child_index: usize, + new_child: usize, + ) -> Result<(), Error>; +} + /// A labelled graph is just a graph with labels associated to /// vertices and / or edges. /// -- cgit v1.2.3-18-g5258