From 8463dd24f815fe2b8f25fe9763e0a43023bfbb20 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 23 Dec 2022 00:36:31 +0800 Subject: renaming core to chain and some other changes Some changes: - The core crate is renamed to "chain". - The crate "viz" is added, which will provide layered graph drawing algorithms. - A function is added to convert from a grammar to the regular language of its left-linear closures. - A function is added to convert from a nondeterministic finite automaton to its "null" closure. A null closure is the same automaton with edges added, as if some edges are "null". Whether an edge is null is determined by a function. Combined with the previous change, we can convert a grammar to the regular language of the null closure of its left-linear closures. --- Now it remains to test more grammars and add an Atom trait, before finishing the part about compilations. --- graph/src/adset.rs | 216 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 214 insertions(+), 2 deletions(-) (limited to 'graph/src/adset.rs') diff --git a/graph/src/adset.rs b/graph/src/adset.rs index 58fed4c..c225986 100644 --- a/graph/src/adset.rs +++ b/graph/src/adset.rs @@ -7,8 +7,9 @@ //! duplications of languages, so it is more convenient if the //! underlying graph type **cannot** represent duplicate edges. -use super::{ExtGraph, Graph}; -use crate::error::Error; +use std::ops::{Deref, DerefMut}; + +use crate::{builder::Builder, error::Error, ExtGraph, Graph}; // If one wants to use another implementation for a set, import that // as Set, and nothing else needs to be changed, ideally. @@ -122,6 +123,13 @@ impl Graph for ASGraph { .contains(&ASEdge::new(target))) } } + + #[inline] + fn replace_by_builder(&mut self, builder: impl Builder) { + let graph = builder.build(); + + self.nodes = graph.nodes; + } } impl ExtGraph for ASGraph { @@ -144,6 +152,90 @@ impl ExtGraph for ASGraph { } } +// Builder for this implementation of graph + +/// A builder for adjacency set graphs. +#[derive(Debug, Default, Clone)] +pub struct ASGBuilder(ASGraph); + +impl Deref for ASGBuilder { + type Target = ASGraph; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl DerefMut for ASGBuilder { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl Builder for ASGBuilder { + type Label = (); + + type Result = ASGraph; + + #[inline] + fn with_capacity(size: usize) -> Self { + Self(ASGraph { + nodes: Vec::with_capacity(size), + }) + } + + #[inline] + fn add_vertex(&mut self) -> usize { + self.nodes.push(ASNode::default()); + self.nodes.len() - 1 + } + + fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> { + let nodes_len = self.nodes.len(); + + let source_children = self + .nodes + .get_mut(source) + .ok_or(Error::IndexOutOfBounds(source, nodes_len))?; + + if !(0..nodes_len).contains(&target) { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + source_children.children.insert(ASEdge::new(target)); + + Ok(()) + } + + fn remove_edge(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error> + where + F: Fn(Self::Label) -> bool, + { + let nodes_len = self.nodes.len(); + + let source_children = self + .nodes + .get_mut(source) + .ok_or(Error::IndexOutOfBounds(source, nodes_len))?; + + if !(0..nodes_len).contains(&target) { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + source_children.children.remove(&ASEdge::new(target)); + + Ok(()) + } + + fn build(self) -> Self::Result { + self.0 + } + + fn build_ref(&self) -> Self::Result { + self.0.clone() + } +} + #[cfg(test)] mod asgraph_test { use super::*; @@ -227,3 +319,123 @@ mod asgraph_test { Ok(()) } } + +#[cfg(test)] +mod test_asgraph_builder { + use super::*; + + #[test] + fn test_builder() -> Result<(), Box> { + let mut builder = ASGBuilder::default(); + + // Add five nodes + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + + println!("five empty nodes: {builder:?}"); + + // Link each node to its successor and link the last node with + // the first one to form a cycle. + for i in 0..5 { + builder.add_edge(i, if i == 4 { 0 } else { i + 1 }, ())?; + } + + println!("a cycle of five nodes: {builder:?}"); + + // Remove the link from the last node to the first node. + builder.remove_edge(4, 0, |_| true)?; + + println!("a line of five nodes: {builder:?}"); + + // build a graph + + let graph = builder.build(); + + println!("final graph: {graph:?}"); + + Ok(()) + } + + #[test] + fn test_errors() -> Result<(), Box> { + let mut builder = ASGBuilder::default(); + + // Add five nodes + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + + println!("five empty nodes: {builder:?}"); + + // Errors in add_edge + + println!(); + println!("Testing errors in add_edge:"); + println!(); + + assert!(matches!( + builder.add_edge(0, 5, ()), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + println!("Right error for an index out of bounds as the target"); + + assert!(matches!( + builder.add_edge(10, 5, ()), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + println!("Right error for an index out of bounds as the source"); + + assert!(matches!( + builder.add_edge(10, 50, ()), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + println!("Right error for both indices out of bounds"); + + // Errors in remove_edge + + println!(); + println!("Testing errors in remove_edge:"); + println!(); + + assert!(matches!( + builder.remove_edge(0, 5, |_| true), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + println!("Right error for an index out of bounds as the target"); + + assert!(matches!( + builder.remove_edge(10, 5, |_| true), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + println!("Right error for an index out of bounds as the source"); + + assert!(matches!( + builder.remove_edge(10, 50, |_| true), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + println!("Right error for both indices out of bounds"); + + assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),)); + + println!("No errors for removing a non-existing edge"); + + println!(); + + let graph = builder.build(); + + println!("final graph: {graph:?}"); + + Ok(()) + } +} -- cgit v1.2.3-18-g5258