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. --- graph/src/labelled/binary.rs | 171 +++++++++++++++++++++++++++++++++++++++---- graph/src/labelled/mod.rs | 1 + graph/src/lib.rs | 18 +++++ 3 files changed, 176 insertions(+), 14 deletions(-) (limited to 'graph') 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