From fba9a90cfc6aca2a26cce72f55fb261789139781 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 16 Oct 2026 14:01:01 +0800 Subject: new start Now I tested and discussed with claude, and had a working version of this project. The rest is to port the claude version to my own writings. So this serves as the starting point before that attempt. In the new attempt the design is better, and a number of bugs were found and supposedly fixed, so let us see how this goes at the end. --- graph/src/dfs.rs | 88 +++++++ graph/src/labelled/binary.rs | 78 +++++- graph/src/labelled/double.rs | 16 +- graph/src/labelled/mod.rs | 5 +- graph/src/labelled/simple.rs | 612 +++++++++++++++++++++++++++++++++++++------ graph/src/lib.rs | 52 +++- 6 files changed, 748 insertions(+), 103 deletions(-) create mode 100644 graph/src/dfs.rs (limited to 'graph') diff --git a/graph/src/dfs.rs b/graph/src/dfs.rs new file mode 100644 index 0000000..e9af3de --- /dev/null +++ b/graph/src/dfs.rs @@ -0,0 +1,88 @@ +//! This module implements a function to produce the depth-first order +//! for a graph. + +use super::*; + +use error::Error; + +/// Return a list of indices that are ordered according to a depth-first search. +/// +/// A node is only recorded at most once. And the search starts from +/// the `root`, so this in fact only includes the connected component +/// of the `root`. +pub fn dfs(g: &impl Graph, root: usize) -> Result, Error> { + // let g = g.borrow(); + + let nodes_len = g.nodes_len(); + + let mut result: Vec = Vec::with_capacity(nodes_len); + + let mut stack: Vec = Vec::with_capacity(nodes_len); + + stack.push(root); + + let mut seen_nodes: Vec = std::iter::repeat(false).take(nodes_len).collect(); + + while let Some(top) = stack.pop() { + match seen_nodes.get_mut(top) { + Some(reference) if !*reference => { + *reference = true; + + result.push(top); + + // REVIEW: Maybe I shall add a method + // `children_of_rev`. + + stack.extend(g.children_of(top)?.collect::>().into_iter().rev()); + } + None => { + return Err(Error::IndexOutOfBounds(top, nodes_len)); + } + _ => {} + } + } + + Ok(result) +} + +#[cfg(test)] +mod tests { + use super::*; + + use crate::labelled::simple::SLGBuilder; + + #[test] + fn test_dfs() -> Result<(), Box> { + let mut builder = SLGBuilder::::default(); + + // Add five nodes + builder.add_vertex(0); + builder.add_vertex(1); + builder.add_vertex(2); + builder.add_vertex(3); + builder.add_vertex(4); + + let dummy_label = 0usize; + + builder.add_edge(0, 1, dummy_label)?; + builder.add_edge(0, 4, dummy_label)?; + builder.add_edge(1, 4, dummy_label)?; + builder.add_edge(1, 2, dummy_label)?; + builder.add_edge(2, 3, dummy_label)?; + builder.add_edge(3, 4, dummy_label)?; + + // build a graph + + let graph = builder.build(); + + let dfs = dfs(&graph, 0)?; + + println!("dfs = {dfs:?}"); + + let answer = vec![0, 1, 4, 2, 3]; + + assert_eq!(answer, dfs); + + Ok(()) + } +} diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs index 862f25b..fecc295 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, RedirectGraph}; +use crate::{Parent, ParentsGraph, RedirectGraph, VLabelGraph}; use std::{ collections::{hash_map::Iter as MapIter, HashMap as Map}, @@ -223,7 +223,7 @@ impl Graph for PLGraph { for node in self.nodes() { post.push_str(&format!( " {node} [label = \"{node}:{}\"]\n", - match self.vertex_label(node) { + match VLabelGraph::vertex_label(self, node) { Ok(Some(label)) => { format!("{label}") } @@ -249,6 +249,7 @@ impl Graph for PLGraph { let mut file = std::fs::File::options() .write(true) .create(true) + .truncate(true) .open(&filename)?; use std::io::Write; @@ -405,6 +406,79 @@ impl RedirectGraph for PLGraph { } } +/// A delegation of iterators. +/// +/// This is used to avoid a boxed pointer to an iterator. +#[derive(Debug, Clone)] +pub struct PLVIter<'a, T: GraphLabel> { + iter: Iter<'a, usize>, + graph: &'a PLGraph, +} + +impl<'a, T: GraphLabel> PLVIter<'a, T> { + /// Return an iterator from a graph and a node. + pub fn try_new(graph: &'a PLGraph, node: usize) -> Result { + let iter = graph + .nodes + .get(node) + .ok_or(Error::IndexOutOfBounds(node, graph.nodes.len()))? + .children + .iter(); + + Ok(Self { iter, graph }) + } +} + +impl<'a, T: GraphLabel> Iterator for PLVIter<'a, T> { + type Item = (T, usize); + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().and_then(|child| { + VLabelGraph::vertex_label(self.graph, *child) + .ok() + .flatten() + .map(|label| (label, *child)) + }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let len = self.iter.len(); + + (len, Some(len)) + } +} + +impl<'a, T: GraphLabel> ExactSizeIterator for PLVIter<'a, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl VLabelGraph for PLGraph { + type TupleIter<'a> = PLVIter<'a,T> + where + Self: 'a, + T: 'a; + + fn vertex_label(&self, node_id: usize) -> Result, Error> { + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) + .map(|node| Some(node.label)) + } + + fn query_label(&self, label: T) -> Option { + self.label_index_map.get(&label).copied() + } + + fn verlabren_of(&self, node_id: usize) -> Result, Error> { + PLVIter::try_new(self, node_id) + } +} + impl LabelGraph for PLGraph { type Iter<'a> = std::iter::Empty where diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs index b01a13b..12d0e54 100644 --- a/graph/src/labelled/double.rs +++ b/graph/src/labelled/double.rs @@ -158,6 +158,7 @@ impl Graph for DLGraph { let mut file = std::fs::File::options() .write(true) .create(true) + .truncate(true) .open(&filename)?; use std::io::Write; @@ -408,21 +409,12 @@ impl LabelExtGraph for DLGraph { if !set.contains(&label) { flat.push((label, to)); by_target.get_mut(&to).unwrap().insert(label); - by_label - .entry(label) - .or_insert_with(Default::default) - .insert(to); + by_label.entry(label).or_default().insert(to); } } else { flat.push((label, to)); - by_target - .entry(to) - .or_insert_with(Default::default) - .insert(label); - by_label - .entry(label) - .or_insert_with(Default::default) - .insert(to); + by_target.entry(to).or_default().insert(label); + by_label.entry(label).or_default().insert(to); } } diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs index 13fd8c1..f0704e0 100644 --- a/graph/src/labelled/mod.rs +++ b/graph/src/labelled/mod.rs @@ -19,4 +19,7 @@ pub mod binary; pub use binary::{PLGBuilderMut, PLGraph}; pub mod simple; -pub use simple::{SLGBuilder, SLGraph}; +pub use simple::{ + // SLGBuilder , + SLGraph, +}; diff --git a/graph/src/labelled/simple.rs b/graph/src/labelled/simple.rs index b5388a9..5fb7641 100644 --- a/graph/src/labelled/simple.rs +++ b/graph/src/labelled/simple.rs @@ -8,49 +8,74 @@ use super::*; +use crate::VLabelGraph; + #[derive(Debug, Clone)] -struct SLNode { - children: Vec<(T, usize)>, +struct SLNode { + children: Box<[(T, usize)]>, + label: S, } -impl Default for SLNode { +impl Default for SLNode { fn default() -> Self { Self { - children: Vec::new(), + children: Box::new([]), + label: Default::default(), } } } -impl SLNode { - fn new(children: Vec<(T, usize)>) -> Self { - Self { children } +impl SLNode { + #[allow(dead_code)] + fn new(children: Box<[(T, usize)]>, label: S) -> Self { + Self { children, label } + } + + fn into_builder(self) -> SLBNode { + let label = self.label; + let children = self.children.into_vec(); + + SLBNode { children, label } + } + + fn to_builder(&self) -> SLBNode { + let label = self.label; + let children = self.children.to_vec(); + + SLBNode { children, label } } } /// Simple Labelled Graph. #[derive(Debug, Clone)] -pub struct SLGraph { - nodes: Vec>, +pub struct SLGraph { + nodes: Box<[SLNode]>, } -impl SLGraph { +impl SLGraph { /// Return a builder. #[inline] - pub fn builder(self) -> SLGBuilder { - SLGBuilder(self) + pub fn builder(self) -> SLGBuilder { + SLGBuilder { + nodes: as IntoIterator>::into_iter(self.nodes) + .map(SLNode::into_builder) + .collect(), + } } /// Return a builder from a reference. #[inline] - pub fn builder_ref(&self) -> SLGBuilder { - SLGBuilder(self.clone()) + pub fn builder_ref(&self) -> SLGBuilder { + SLGBuilder { + nodes: self.nodes.iter().map(SLNode::to_builder).collect(), + } } } -impl Default for SLGraph { +impl Default for SLGraph { #[inline] fn default() -> Self { - let nodes = Vec::new(); + let nodes = Box::new([]); Self { nodes } } @@ -89,9 +114,12 @@ impl<'a, T: GraphLabel> ExactSizeIterator for ChildrenIter<'a, T> { } } -impl Graph for SLGraph { +impl Graph for SLGraph { // Not using a boxed pointer is supposed to save some allocations. - type Iter<'a> = ChildrenIter<'a, T> where T: 'a; + type Iter<'a> = ChildrenIter<'a, T> + where + T: 'a, + S:'a; #[inline] fn is_empty(&self) -> bool { @@ -161,6 +189,10 @@ impl Graph for SLGraph { let mut post = String::new(); + for (node_id, node_label) in self.nodes.iter().map(|node| &node.label).enumerate() { + post.push_str(&format!(" {node_id} [label = \"{node_label}\"]\n")); + } + for (source, target) in self.edges() { for label in self.edge_label(source, target).unwrap() { post.push_str(&format!(" {source} -> {target} [label = \"{label}\"]\n")); @@ -178,6 +210,7 @@ impl Graph for SLGraph { let mut file = std::fs::File::options() .write(true) .create(true) + .truncate(true) .open(&filename)?; use std::io::Write; @@ -193,7 +226,112 @@ impl Graph for SLGraph { } } -impl LabelGraph for SLGraph { +/// An iterator delegation for children, and labels of children, of +/// nodes of `SLGraph`. +#[derive(Debug, Clone)] +pub struct VLChildrenIter<'a, S: GraphLabel, T: GraphLabel> { + iter: std::iter::Copied>, + graph: &'a SLGraph, +} + +impl<'a, S: GraphLabel, T: GraphLabel> VLChildrenIter<'a, S, T> { + fn new( + iter: std::iter::Copied>, + graph: &'a SLGraph, + ) -> Self { + Self { iter, graph } + } +} + +impl<'a, S: GraphLabel, T: GraphLabel> Iterator for VLChildrenIter<'a, S, T> { + type Item = (S, usize); + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().and_then(|(_, to)| { + let label = self.graph.nodes.get(to)?.label; + Some((label, to)) + }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +impl<'a, S: GraphLabel, T: GraphLabel> ExactSizeIterator for VLChildrenIter<'a, S, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl VLabelGraph for SLGraph { + type TupleIter<'a> = VLChildrenIter<'a, S, T> + where + Self: 'a, + T:'a, + S: 'a; + + fn vertex_label(&self, node_id: usize) -> Result, Error> { + Ok(Some( + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes_len()))? + .label, + )) + } + + fn verlabren_of(&self, node_id: usize) -> Result, Error> { + let iter = self + .nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))? + .children + .iter() + .copied(); + + Ok(Self::TupleIter::new(iter, self)) + } +} + +/// An iterator delegation for children of nodes of `SLGraph`. +/// +/// This iterates through labels and targets of edges simultaneously. +#[derive(Debug, Clone)] +pub struct ELChildrenIter<'a, T: GraphLabel> { + iter: std::iter::Copied>, +} + +impl<'a, T: GraphLabel> ELChildrenIter<'a, T> { + fn new(iter: std::iter::Copied>) -> Self { + Self { iter } + } +} + +impl<'a, T: GraphLabel> Iterator for ELChildrenIter<'a, T> { + type Item = (T, usize); + + #[inline] + fn next(&mut self) -> Option { + self.iter.next() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +impl<'a, T: GraphLabel> ExactSizeIterator for ELChildrenIter<'a, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl LabelGraph for SLGraph { type Iter<'a> = std::iter::Empty where Self:'a, @@ -204,7 +342,7 @@ impl LabelGraph for SLGraph { Self: 'a, T: 'a; - type TupleIter<'a> = std::iter::Copied> + type TupleIter<'a> = ELChildrenIter<'a, T> where Self: 'a, T: 'a; @@ -218,7 +356,7 @@ impl LabelGraph for SLGraph { self.nodes .get(node_id) .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len())) - .map(|node| node.children.iter().copied()) + .map(|node| ELChildrenIter::new(node.children.iter().copied())) } fn edge_label(&self, source: usize, target: usize) -> Result, Error> { @@ -276,9 +414,16 @@ impl LabelGraph for SLGraph { } } -impl LabelExtGraph for SLGraph { - #[inline] - fn extend(&mut self, edges: impl IntoIterator) -> Result { +impl SLGBuilder { + /// Add a new node with `edges` and `label`. + /// + /// If an edge from `edges` points to a non-existent node, return + /// an error. + pub fn extend( + &mut self, + label: S, + edges: impl IntoIterator, + ) -> Result { let mut children = Vec::new(); for (label, to) in edges { @@ -289,7 +434,7 @@ impl LabelExtGraph for SLGraph { children.push((label, to)); } - let new_node = SLNode::new(children); + let new_node = SLBNode::new(children, label); let new_index = self.nodes_len(); self.nodes.push(new_node); @@ -300,55 +445,326 @@ impl LabelExtGraph for SLGraph { // Builder for this implementation of graph +/// The type of nodes for builders. +#[derive(Debug, Clone)] +struct SLBNode { + children: Vec<(T, usize)>, + label: S, +} + +impl SLBNode { + fn new(children: Vec<(T, usize)>, label: S) -> Self { + Self { children, label } + } + + fn into_boxed(self) -> SLNode { + let label = self.label; + + let children = self.children.into_boxed_slice(); + SLNode { children, label } + } +} + /// A builder for simple labelled graphs. #[derive(Debug, Clone)] -pub struct SLGBuilder(SLGraph); +pub struct SLGBuilder { + nodes: Vec>, +} -impl Default for SLGBuilder { +impl Default for SLGBuilder { fn default() -> Self { - Self(Default::default()) + Self { nodes: Vec::new() } + } +} + +impl Graph for SLGBuilder { + // Not using a boxed pointer is supposed to save some allocations. + type Iter<'a> = ChildrenIter<'a, T> + where + T: 'a, + S:'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 (node_id, node_label) in self.nodes.iter().map(|node| &node.label).enumerate() { + post.push_str(&format!(" {node_id} [label = \"{node_label}\"]\n")); + } + + 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) + .truncate(true) + .open(&filename)?; + + use std::io::Write; + + file.write_all(result.as_bytes()) + } + + #[inline] + fn replace_by_builder(&mut self, _builder: impl Builder) { + unimplemented!() } } -impl Deref for SLGBuilder { - type Target = SLGraph; +/// An iterator delegation for children, and labels of children, of +/// nodes of `SLGBuilder`. +#[derive(Debug, Clone)] +pub struct VLBChildrenIter<'a, S: GraphLabel, T: GraphLabel> { + iter: std::iter::Copied>, + builder: &'a SLGBuilder, +} - fn deref(&self) -> &Self::Target { - &self.0 +impl<'a, S: GraphLabel, T: GraphLabel> VLBChildrenIter<'a, S, T> { + fn new( + iter: std::iter::Copied>, + builder: &'a SLGBuilder, + ) -> Self { + Self { iter, builder } } } -impl DerefMut for SLGBuilder { - fn deref_mut(&mut self) -> &mut Self::Target { - &mut self.0 +impl<'a, S: GraphLabel, T: GraphLabel> Iterator for VLBChildrenIter<'a, S, T> { + type Item = (S, usize); + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().and_then(|(_, to)| { + let label = self.builder.nodes.get(to)?.label; + Some((label, to)) + }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +impl<'a, S: GraphLabel, T: GraphLabel> ExactSizeIterator for VLBChildrenIter<'a, S, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() } } -impl Builder for SLGBuilder { - type Label = T; +impl VLabelGraph for SLGBuilder { + type TupleIter<'a> = VLBChildrenIter<'a, S,T> + where + Self: 'a, + T:'a, + S: 'a; + + fn vertex_label(&self, node_id: usize) -> Result, Error> { + Ok(Some( + self.nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes_len()))? + .label, + )) + } - type Result = SLGraph; + fn verlabren_of(&self, node_id: usize) -> Result, Error> { + let iter = self + .nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))? + .children + .iter() + .copied(); + + Ok(Self::TupleIter::new(iter, self)) + } +} + +impl LabelGraph for SLGBuilder { + 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> = ELChildrenIter<'a,T> + 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| ELChildrenIter::new(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 with_capacity(size: usize) -> Self { - Self(SLGraph { + 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 SLGBuilder { + /// Return a builder with a fixed capacity. + #[inline] + pub fn with_capacity(size: usize) -> Self { + SLGBuilder { nodes: Vec::with_capacity(size), - }) + } } + /// Add a vertex with a given label. #[inline] - fn add_vertex(&mut self) -> usize { - self.nodes.push(SLNode::default()); + pub fn add_vertex(&mut self, label: S) -> usize { + self.nodes.push(SLBNode::new(Vec::new(), label)); self.nodes.len() - 1 } + /// Add vertices with an iterator of labels. #[inline] - fn add_vertices(&mut self, n: usize) { + pub fn add_vertices(&mut self, labels: impl Iterator) { self.nodes - .extend(std::iter::repeat_with(Default::default).take(n)); + .extend(labels.map(|label| SLBNode::new(Vec::new(), label))); } - fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> { + /// Add an edge from the source to the target. + pub fn add_edge(&mut self, source: usize, target: usize, label: T) -> Result<(), Error> { let nodes_len = self.nodes.len(); let source_node = self @@ -365,14 +781,19 @@ impl Builder for SLGBuilder { Ok(()) } - fn remove_edge( + /// Remove an edge from the source to the target. + /// + /// Since some graphs are labelled, the users are allowed to pass + /// a predicate to determine if an edge from the source to the + /// target should be removed. + pub fn remove_edge( &mut self, source: usize, target: usize, mut predicate: F, ) -> Result<(), Error> where - F: FnMut(Self::Label) -> bool, + F: FnMut(T) -> bool, { let nodes_len = self.nodes.len(); @@ -392,12 +813,35 @@ impl Builder for SLGBuilder { Ok(()) } - fn build_ref(&self) -> Self::Result { - self.0.clone() + /// Convert the builder into a graph using a reference. + /// + /// This is similar to [`build`][Builder::build], but takes an + /// immutable reference of the builder, so that the builder can + /// still be used later on. + pub fn build_ref(&self) -> SLGraph { + let nodes = self + .nodes + .clone() + .into_iter() + .map(SLBNode::into_boxed) + .collect::>() + .into_boxed_slice(); + + SLGraph { nodes } } - fn build(self) -> Self::Result { - self.0 + /// Convert the builder into a graph. + /// + /// This is the purpose of having a builder. + pub fn build(self) -> SLGraph { + let nodes = self + .nodes + .into_iter() + .map(SLBNode::into_boxed) + .collect::>() + .into_boxed_slice(); + + SLGraph { nodes } } } @@ -408,15 +852,15 @@ mod simple_test { use std::collections::BTreeSet as Set; macro_rules! set { - () => { Set::::default() }; - ($($num:literal),*) => { - { - let mut set: Set = Set::default(); - $(set.insert($num);)* - set - } - }; - } + () => { Set::::default() }; + ($($num:literal),*) => { + { + let mut set: Set = Set::default(); + $(set.insert($num);)* + set + } + }; +} // macro_rules! map { // () => { Map::>::default() }; @@ -431,30 +875,36 @@ mod simple_test { #[test] fn test_graph_apis() -> Result<(), Error> { - let mut graph: SLGraph = Default::default(); + let mut builder: SLGBuilder = Default::default(); // testing empty graph - assert!(graph.is_empty()); + assert!(builder.is_empty()); // testing adding an empty node - assert_eq!(graph.extend(std::iter::empty())?, 0); + assert_eq!(builder.extend(0, std::iter::empty())?, 0); // testing nodes_len - assert_eq!(graph.nodes_len(), 1); + assert_eq!(builder.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); + assert_eq!(builder.extend(1, [(0, 0)].iter().copied())?, 1); + assert_eq!(builder.extend(2, [(1, 0), (1, 1)].iter().copied())?, 2); + assert_eq!(builder.extend(3, [(3, 0), (3, 2)].iter().copied())?, 3); + assert_eq!(builder.extend(4, [(1, 1), (1, 2)].iter().copied())?, 4); + assert_eq!( + builder.extend(5, [(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); + assert_eq!( + builder.extend(6, [(2, 1), (2, 3), (3, 2)].iter().copied())?, + 6 + ); + assert_eq!(builder.extend(7, [(3, 2), (3, 0)].iter().copied())?, 7); - let graph = graph; + let graph = builder.build(); // ensuring the correct length assert_eq!(graph.nodes_len(), 8); @@ -500,14 +950,10 @@ mod test_slgraph_builder { #[test] fn test_builder() -> Result<(), Box> { - let mut builder = SLGBuilder::::default(); + let mut builder = SLGBuilder::::default(); // Add five nodes - builder.add_vertex(); - builder.add_vertex(); - builder.add_vertex(); - builder.add_vertex(); - builder.add_vertex(); + builder.add_vertices(0..5); // Link each node to its successor and link the last node with // the first one to form a cycle. @@ -529,14 +975,10 @@ mod test_slgraph_builder { #[test] fn test_errors() -> Result<(), Box> { - let mut builder = SLGBuilder::default(); + let mut builder = SLGBuilder::::default(); // Add five nodes - builder.add_vertex(); - builder.add_vertex(); - builder.add_vertex(); - builder.add_vertex(); - builder.add_vertex(); + builder.add_vertices(0..5); // Errors in add_edge diff --git a/graph/src/lib.rs b/graph/src/lib.rs index 058d62c..36fc545 100644 --- a/graph/src/lib.rs +++ b/graph/src/lib.rs @@ -22,6 +22,7 @@ pub use adlist::ALGraph; pub mod labelled; +pub use labelled::simple::{SLGBuilder, SLGraph}; pub use labelled::DLGraph; pub use labelled::PLGraph; @@ -29,6 +30,8 @@ pub mod builder; pub use builder::Builder; +pub mod dfs; + use error::Error; /// The expected behaviour of an immutable graph. @@ -138,6 +141,7 @@ pub trait Graph: Default { let mut file = std::fs::File::options() .write(true) .create(true) + .truncate(true) .open(filename)?; use std::io::Write; @@ -290,8 +294,8 @@ pub trait RedirectGraph: Graph { /// This trait defines some convenient methods for accessing the /// labels of vertices. pub trait VLabelGraph: Graph { - /// A type that iterates through tuples of labels and targets of - /// edges. + /// A type that iterates through tuples of target labels and + /// target indices of edges. type TupleIter<'a>: Iterator + 'a where Self: 'a, @@ -321,13 +325,55 @@ pub trait VLabelGraph: Graph { } /// Return an iterator of tuples of vertex labels and indices of - /// targets edges out of a node. + /// targets for edges out of a node. /// /// The name is a weird new word created to stand as a /// simplification of the phrase "vertex label and children of". fn verlabren_of(&self, node_id: usize) -> Result, Error>; } +/// A graph whose edges are associated with labels. +/// +/// This trait defines some convenient methods for accessing the +/// labels of edges. +pub trait ELabelGraph: Graph { + /// A type that iterates through tuples of edge labels and target + /// indices of edges. + type TupleIter<'a>: Iterator + 'a + where + Self: 'a, + T: 'a; + + #[inline] + /// Return the label of an edge or an error if the node is + /// invalid. + /// + /// The default implementation always returns `None` after + /// checking the validity of the edge. + fn edge_label(&self, from: usize, to: usize) -> Result, Error> { + self.has_edge(from, to).map(|_| None) + } + + /// Return an iterator of tuples of edge labels and indices of + /// targets for edges out of a node. + /// + /// The name is a weird new word created to stand as a + /// simplification of the phrase "edge label and children of". + fn edlabren_of(&self, node_id: usize) -> Result, Error>; +} + +impl> ELabelGraph for G { + type TupleIter<'a> = >::TupleIter<'a> + where + Self: 'a, + T: 'a; + + #[inline] + fn edlabren_of(&self, node_id: usize) -> Result, Error> { + LabelGraph::tuples_of(self, node_id) + } +} + /// A labelled graph is just a graph with labels associated to /// vertices and / or edges. /// -- cgit v1.2.3-18-g5258