From 3ae0cf9898485a2ec35df7d23cd274e7dea5796d Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 8 Jan 2024 16:13:19 +0800 Subject: a commit before the forst query I think the main functionalities are already there, but the lack of querying capabilities makes this not very useful at the moment. This commit is right before an attempt to add this missing piece. --- graph/src/labelled/binary.rs | 9 + graph/src/labelled/double.rs | 10 + graph/src/labelled/mod.rs | 3 + graph/src/labelled/simple.rs | 579 +++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 601 insertions(+) create mode 100644 graph/src/labelled/simple.rs (limited to 'graph/src/labelled') diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs index 5120522..862f25b 100644 --- a/graph/src/labelled/binary.rs +++ b/graph/src/labelled/binary.rs @@ -420,6 +420,11 @@ impl LabelGraph for PLGraph { Self: 'a, T: 'a; + type TupleIter<'a> = std::iter::Empty<(T, usize)> + where + Self: 'a, + T: 'a; + #[inline] fn query_label(&self, label: T) -> Option { self.label_index_map.get(&label).copied() @@ -446,6 +451,10 @@ impl LabelGraph for PLGraph { unimplemented!("Edges have no labels") } + fn tuples_of(&self, _node_id: usize) -> Result, Error> { + unimplemented!("Edges have no labels") + } + fn labels_of(&self, _node_id: usize) -> Result, Error> { unimplemented!("Edges have no labels") } diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs index a641c74..b01a13b 100644 --- a/graph/src/labelled/double.rs +++ b/graph/src/labelled/double.rs @@ -319,6 +319,8 @@ impl LabelGraph for DLGraph { Self: 'a, T: 'a; + type TupleIter<'a> = std::iter::Copied> where Self: 'a, T:'a; + fn edge_label(&self, source: usize, target: usize) -> Result, Error> { if self.has_edge(source, target)? { Ok(EdgeLabelIter::new( @@ -352,6 +354,14 @@ impl LabelGraph for DLGraph { } } + #[inline] + fn tuples_of(&self, node_id: usize) -> Result, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(node.flat.iter().copied()), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())), + } + } + #[inline] fn labels_of(&self, node_id: usize) -> Result, Error> { match self.nodes.get(node_id) { diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs index fb7b405..13fd8c1 100644 --- a/graph/src/labelled/mod.rs +++ b/graph/src/labelled/mod.rs @@ -17,3 +17,6 @@ pub use double::{DLGBuilder, DLGraph}; pub mod binary; pub use binary::{PLGBuilderMut, PLGraph}; + +pub mod simple; +pub use simple::{SLGBuilder, SLGraph}; diff --git a/graph/src/labelled/simple.rs b/graph/src/labelled/simple.rs new file mode 100644 index 0000000..b5388a9 --- /dev/null +++ b/graph/src/labelled/simple.rs @@ -0,0 +1,579 @@ +//! This file implements a simple labelled graph without extra +//! functionalities. +//! +//! Neither the method +//! [`find_children_with_label`][crate::LabelGraph::find_children_with_label] +//! nor the method [`labels_of`][crate::LabelGraph::labels_of] are +//! implemented efficiently. + +use super::*; + +#[derive(Debug, Clone)] +struct SLNode { + children: Vec<(T, usize)>, +} + +impl Default for SLNode { + fn default() -> Self { + Self { + children: Vec::new(), + } + } +} + +impl SLNode { + fn new(children: Vec<(T, usize)>) -> Self { + Self { children } + } +} + +/// Simple Labelled Graph. +#[derive(Debug, Clone)] +pub struct SLGraph { + nodes: Vec>, +} + +impl SLGraph { + /// Return a builder. + #[inline] + pub fn builder(self) -> SLGBuilder { + SLGBuilder(self) + } + + /// Return a builder from a reference. + #[inline] + pub fn builder_ref(&self) -> SLGBuilder { + SLGBuilder(self.clone()) + } +} + +impl Default for SLGraph { + #[inline] + fn default() -> Self { + let nodes = Vec::new(); + + Self { nodes } + } +} + +/// An iterator delegation for children of nodes of `SLGraph`. +#[derive(Debug, Clone)] +pub struct ChildrenIter<'a, T: GraphLabel> { + iter: std::iter::Copied>, +} + +impl<'a, T: GraphLabel> ChildrenIter<'a, T> { + fn new(iter: std::iter::Copied>) -> Self { + Self { iter } + } +} + +impl<'a, T: GraphLabel> Iterator for ChildrenIter<'a, T> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().map(|(_, to)| to) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +impl<'a, T: GraphLabel> ExactSizeIterator for ChildrenIter<'a, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl Graph for SLGraph { + // Not using a boxed pointer is supposed to save some allocations. + type Iter<'a> = ChildrenIter<'a, T> where T: 'a; + + #[inline] + fn is_empty(&self) -> bool { + self.nodes.is_empty() + } + + #[inline] + fn nodes_len(&self) -> usize { + self.nodes.len() + } + + #[inline] + fn children_of(&self, node_id: usize) -> Result, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(ChildrenIter::new(node.children.iter().copied())), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())), + } + } + + #[inline] + /// Return the number of "children" of a node, or an error if the + /// node is not a member of the graph. + /// + /// This counts edges with different labels as different edges. + fn degree(&self, node_id: usize) -> Result { + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) + .map(|node| node.children.len()) + } + + #[inline] + fn is_empty_node(&self, node_id: usize) -> Result { + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) + .map(|node| node.children.is_empty()) + } + + fn has_edge(&self, source: usize, target: usize) -> Result { + match self.nodes.get(source) { + Some(source_node) => { + if self.nodes.get(target).is_none() { + Err(Error::IndexOutOfBounds(target, self.nodes.len())) + } else { + for (_, to) in source_node.children.iter() { + if *to == target { + return Ok(true); + } + } + + Ok(false) + } + } + None => Err(Error::IndexOutOfBounds(source, self.nodes.len())), + } + } + + 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\", ordering=out] + edge [fontname=\"Helvetica,Arial,sans-serif\"] + rankdir=LR;\n"; + + let mut post = String::new(); + + for (source, target) in self.edges() { + for label in self.edge_label(source, target).unwrap() { + post.push_str(&format!(" {source} -> {target} [label = \"{label}\"]\n")); + } + } + + post.push_str("}\n"); + + let result = format!("{preamble}{post}"); + + 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)?; + + use std::io::Write; + + file.write_all(result.as_bytes()) + } + + #[inline] + fn replace_by_builder(&mut self, builder: impl Builder) { + let new_graph = builder.build(); + + self.nodes = new_graph.nodes; + } +} + +impl LabelGraph for SLGraph { + type Iter<'a> = std::iter::Empty + where + Self:'a, + T:'a; + + type LabelIter<'a> = std::iter::Empty<(&'a T, >::Iter<'a>)> + where + Self: 'a, + T: 'a; + + type TupleIter<'a> = std::iter::Copied> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::option::IntoIter + where + Self: 'a, + T: 'a; + + fn tuples_of(&self, node_id: usize) -> Result, Error> { + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) + .map(|node| node.children.iter().copied()) + } + + fn edge_label(&self, source: usize, target: usize) -> Result, Error> { + let nodes_len = self.nodes.len(); + + if let Some(source_node) = self.nodes.get(source) { + if !(0..nodes_len).contains(&target) { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + for (label, end) in source_node.children.iter() { + if *end == target { + return Ok(Some(*label).into_iter()); + } + } + + Ok(None.into_iter()) + } else { + Err(Error::IndexOutOfBounds(source, nodes_len)) + } + } + + fn find_children_with_label( + &self, + _node_id: usize, + _label: &T, + ) -> Result<>::Iter<'_>, Error> { + unimplemented!("Unsupported operation") + } + + fn labels_of(&self, _node_id: usize) -> Result, Error> { + unimplemented!("Unsupported operation") + } + + #[inline] + fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result { + let nodes_len = self.nodes.len(); + + match self.nodes.get(node_id) { + Some(node) => { + if target >= nodes_len { + return Err(Error::IndexOutOfBounds(target, nodes_len)); + } + + for (edge_label, end) in node.children.iter() { + if *edge_label == *label && *end == target { + return Ok(true); + } + } + + Ok(false) + } + None => Err(Error::IndexOutOfBounds(node_id, nodes_len)), + } + } +} + +impl LabelExtGraph for SLGraph { + #[inline] + fn extend(&mut self, edges: impl IntoIterator) -> Result { + let mut children = Vec::new(); + + for (label, to) in edges { + if !self.has_node(to) { + return Err(Error::IndexOutOfBounds(to, self.nodes.len())); + } + + children.push((label, to)); + } + + let new_node = SLNode::new(children); + let new_index = self.nodes_len(); + + self.nodes.push(new_node); + + Ok(new_index) + } +} + +// Builder for this implementation of graph + +/// A builder for simple labelled graphs. +#[derive(Debug, Clone)] +pub struct SLGBuilder(SLGraph); + +impl Default for SLGBuilder { + fn default() -> Self { + Self(Default::default()) + } +} + +impl Deref for SLGBuilder { + type Target = SLGraph; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl DerefMut for SLGBuilder { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl Builder for SLGBuilder { + type Label = T; + + type Result = SLGraph; + + #[inline] + fn with_capacity(size: usize) -> Self { + Self(SLGraph { + nodes: Vec::with_capacity(size), + }) + } + + #[inline] + fn add_vertex(&mut self) -> usize { + self.nodes.push(SLNode::default()); + self.nodes.len() - 1 + } + + #[inline] + fn add_vertices(&mut self, n: usize) { + self.nodes + .extend(std::iter::repeat_with(Default::default).take(n)); + } + + fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> { + let nodes_len = self.nodes.len(); + + let source_node = 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_node.children.push((label, target)); + + Ok(()) + } + + fn remove_edge( + &mut self, + source: usize, + target: usize, + mut predicate: F, + ) -> Result<(), Error> + where + F: FnMut(Self::Label) -> bool, + { + let nodes_len = self.nodes.len(); + + let source_node = 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_node + .children + .retain(|(label, end)| !(*end == target && predicate(*label))); + + Ok(()) + } + + fn build_ref(&self) -> Self::Result { + self.0.clone() + } + + fn build(self) -> Self::Result { + self.0 + } +} + +#[cfg(test)] +mod simple_test { + use super::*; + + use std::collections::BTreeSet as Set; + + macro_rules! set { + () => { Set::::default() }; + ($($num:literal),*) => { + { + let mut set: Set = Set::default(); + $(set.insert($num);)* + set + } + }; + } + + // macro_rules! map { + // () => { Map::>::default() }; + // ($(($key:literal, $value:expr)),*) => { + // { + // let mut map: Map> = Map::default(); + // $(map.insert($key, $value);)* + // map + // } + // }; + // } + + #[test] + fn test_graph_apis() -> Result<(), Error> { + let mut graph: SLGraph = Default::default(); + + // testing empty graph + assert!(graph.is_empty()); + + // testing adding an empty node + assert_eq!(graph.extend(std::iter::empty())?, 0); + + // testing nodes_len + assert_eq!(graph.nodes_len(), 1); + + // testing extension + + assert_eq!(graph.extend([(0, 0)].iter().copied())?, 1); + assert_eq!(graph.extend([(1, 0), (1, 1)].iter().copied())?, 2); + assert_eq!(graph.extend([(3, 0), (3, 2)].iter().copied())?, 3); + assert_eq!(graph.extend([(1, 1), (1, 2)].iter().copied())?, 4); + assert_eq!(graph.extend([(2, 1), (3, 2), (2, 3)].iter().copied())?, 5); + + // testing adding a duplicated edge set + assert_eq!(graph.extend([(2, 1), (2, 3), (3, 2)].iter().copied())?, 6); + assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 7); + + let graph = graph; + + // ensuring the correct length + assert_eq!(graph.nodes_len(), 8); + + // testing children_of + assert_eq!(graph.children_of(5)?.collect::>(), set!(1, 3, 2)); + + // testing find_children_with_label + assert!(std::panic::catch_unwind(|| { graph.find_children_with_label(5, &2) }).is_err()); + + // testing edge_label + assert_eq!(graph.edge_label(5, 2)?.collect::>(), set!(3)); + assert!(matches!( + graph.edge_label(8, 2), + Err(Error::IndexOutOfBounds(8, 8)) + )); + + // testing degree + assert_eq!(graph.degree(4)?, 2); + + // testing is_empty_node + assert!(graph.is_empty_node(0)?); + assert!(!graph.is_empty_node(1)?); + + // testing has_edge + assert!(graph.has_edge(3, 2)?); + assert!(!graph.has_edge(3, 1)?); + assert!(matches!( + graph.has_edge(3, 8), + Err(Error::IndexOutOfBounds(8, 8)) + )); + + // testing labels_of + assert!(std::panic::catch_unwind(|| { graph.labels_of(5) }).is_err()); + + Ok(()) + } +} + +#[cfg(test)] +mod test_slgraph_builder { + use super::*; + + #[test] + fn test_builder() -> Result<(), Box> { + let mut builder = SLGBuilder::::default(); + + // Add five nodes + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + + // 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 { i + 1 } else { 0 }, i)?; + } + + // Remove the link from the last node to the first node. + builder.remove_edge(4, 0, |_| true)?; + + // build a graph + + let graph = builder.build(); + + println!("final graph: {graph:?}"); + + Ok(()) + } + + #[test] + fn test_errors() -> Result<(), Box> { + let mut builder = SLGBuilder::default(); + + // Add five nodes + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + builder.add_vertex(); + + // Errors in add_edge + + assert!(matches!( + builder.add_edge(0, 5, 0), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + assert!(matches!( + builder.add_edge(10, 5, 0), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + assert!(matches!( + builder.add_edge(10, 50, 0), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + // Errors in remove_edge + + assert!(matches!( + builder.remove_edge(0, 5, |_| true), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + assert!(matches!( + builder.remove_edge(10, 5, |_| true), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + assert!(matches!( + builder.remove_edge(10, 50, |_| true), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + assert!(matches!(builder.remove_edge(0, 1, |_| true), Ok(()),)); + + Ok(()) + } +} -- cgit v1.2.3-18-g5258