diff options
Diffstat (limited to 'graph/src')
| -rw-r--r-- | graph/src/labelled/binary.rs | 9 | ||||
| -rw-r--r-- | graph/src/labelled/double.rs | 10 | ||||
| -rw-r--r-- | graph/src/labelled/mod.rs | 3 | ||||
| -rw-r--r-- | graph/src/labelled/simple.rs | 579 | ||||
| -rw-r--r-- | graph/src/lib.rs | 65 |
5 files changed, 663 insertions, 3 deletions
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<T: GraphLabel> LabelGraph<T> for PLGraph<T> { 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<usize> { self.label_index_map.get(&label).copied() @@ -446,6 +451,10 @@ impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> { unimplemented!("Edges have no labels") } + fn tuples_of(&self, _node_id: usize) -> Result<Self::TupleIter<'_>, Error> { + unimplemented!("Edges have no labels") + } + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, 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<T: GraphLabel> LabelGraph<T> for DLGraph<T> { Self: 'a, T: 'a; + type TupleIter<'a> = std::iter::Copied<std::slice::Iter<'a, (T, usize)>> where Self: 'a, T:'a; + fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> { if self.has_edge(source, target)? { Ok(EdgeLabelIter::new( @@ -353,6 +355,14 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> { } #[inline] + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, 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<Self::LabelIter<'_>, Error> { match self.nodes.get(node_id) { Some(node) => Ok(Self::LabelIter::new(node.by_label.iter())), 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<T: GraphLabel> { + children: Vec<(T, usize)>, +} + +impl<T: GraphLabel> Default for SLNode<T> { + fn default() -> Self { + Self { + children: Vec::new(), + } + } +} + +impl<T: GraphLabel> SLNode<T> { + fn new(children: Vec<(T, usize)>) -> Self { + Self { children } + } +} + +/// Simple Labelled Graph. +#[derive(Debug, Clone)] +pub struct SLGraph<T: GraphLabel> { + nodes: Vec<SLNode<T>>, +} + +impl<T: GraphLabel> SLGraph<T> { + /// Return a builder. + #[inline] + pub fn builder(self) -> SLGBuilder<T> { + SLGBuilder(self) + } + + /// Return a builder from a reference. + #[inline] + pub fn builder_ref(&self) -> SLGBuilder<T> { + SLGBuilder(self.clone()) + } +} + +impl<T: GraphLabel> Default for SLGraph<T> { + #[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<std::slice::Iter<'a, (T, usize)>>, +} + +impl<'a, T: GraphLabel> ChildrenIter<'a, T> { + fn new(iter: std::iter::Copied<std::slice::Iter<'a, (T, usize)>>) -> Self { + Self { iter } + } +} + +impl<'a, T: GraphLabel> Iterator for ChildrenIter<'a, T> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + self.iter.next().map(|(_, to)| to) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a, T: GraphLabel> ExactSizeIterator for ChildrenIter<'a, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<T: GraphLabel> Graph for SLGraph<T> { + // 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<Self::Iter<'_>, 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<usize, Error> { + 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<bool, Error> { + 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<bool, Error> { + 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<Result = Self>) { + let new_graph = builder.build(); + + self.nodes = new_graph.nodes; + } +} + +impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> { + type Iter<'a> = std::iter::Empty<usize> + where + Self:'a, + T:'a; + + type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + where + Self: 'a, + T: 'a; + + type TupleIter<'a> = std::iter::Copied<std::slice::Iter<'a, (T, usize)>> + where + Self: 'a, + T: 'a; + + type EdgeLabelIter<'a> = std::option::IntoIter<T> + where + Self: 'a, + T: 'a; + + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, 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<Self::EdgeLabelIter<'_>, 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<<Self as LabelGraph<T>>::Iter<'_>, Error> { + unimplemented!("Unsupported operation") + } + + fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> { + unimplemented!("Unsupported operation") + } + + #[inline] + fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error> { + 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<T: GraphLabel> LabelExtGraph<T> for SLGraph<T> { + #[inline] + fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error> { + 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<T: GraphLabel>(SLGraph<T>); + +impl<T: GraphLabel> Default for SLGBuilder<T> { + fn default() -> Self { + Self(Default::default()) + } +} + +impl<T: GraphLabel> Deref for SLGBuilder<T> { + type Target = SLGraph<T>; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl<T: GraphLabel> DerefMut for SLGBuilder<T> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl<T: GraphLabel> Builder for SLGBuilder<T> { + type Label = T; + + type Result = SLGraph<T>; + + #[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<F>( + &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::<usize>::default() }; + ($($num:literal),*) => { + { + let mut set: Set<usize> = Set::default(); + $(set.insert($num);)* + set + } + }; + } + + // macro_rules! map { + // () => { Map::<usize, Set<usize>>::default() }; + // ($(($key:literal, $value:expr)),*) => { + // { + // let mut map: Map<usize, Set<usize>> = Map::default(); + // $(map.insert($key, $value);)* + // map + // } + // }; + // } + + #[test] + fn test_graph_apis() -> Result<(), Error> { + let mut graph: SLGraph<usize> = 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<_>>(), 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<_>>(), 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<dyn std::error::Error>> { + let mut builder = SLGBuilder::<usize>::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<dyn std::error::Error>> { + 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(()) + } +} diff --git a/graph/src/lib.rs b/graph/src/lib.rs index e27ace0..058d62c 100644 --- a/graph/src/lib.rs +++ b/graph/src/lib.rs @@ -276,6 +276,58 @@ pub trait RedirectGraph: Graph { ) -> Result<(), Error>; } +// TODO: Design traits for vertex-labelled, edge-labelled, and +// both-labelled graphs separately. +// +// This is needed because we need better iterators to return labels +// simultaneously with children nodes. This can then reduce the +// number of checking bounds when iterating. I think this is the +// right way of doing things, and can help with the performance as +// well. + +/// A graph whose vertices are associated with labels. +/// +/// This trait defines some convenient methods for accessing the +/// labels of vertices. +pub trait VLabelGraph<T: GraphLabel>: Graph { + /// A type that iterates through tuples of labels and targets of + /// edges. + type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a + where + Self: 'a, + T: 'a; + + /// Query the graph for a label, and return the node index if + /// this operation is supported. + /// + /// The default implementation always returns `None`. + #[inline] + fn query_label(&self, _label: T) -> Option<usize> { + None + } + + #[inline] + /// Return the label of a vertex or an error if the node is + /// invalid. + /// + /// The default implementation always returns `None` after + /// checking the validity of `node_id`. + fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> { + if self.has_node(node_id) { + Ok(None) + } else { + Err(Error::IndexOutOfBounds(node_id, self.nodes_len())) + } + } + + /// Return an iterator of tuples of vertex labels and indices of + /// targets 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<Self::TupleIter<'_>, Error>; +} + /// A labelled graph is just a graph with labels associated to /// vertices and / or edges. /// @@ -289,9 +341,12 @@ pub trait LabelGraph<T: GraphLabel>: Graph { where Self: 'a; - // TODO: Add a type that iterates through children and labels of - // children simultaneously. This can reduce the number of bounds - // checking. + /// A type that iterates through tuples of labels and targets of + /// edges. + type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a + where + Self: 'a, + T: 'a; /// A type that iterates through labels. type LabelIter<'a>: Iterator<Item = (&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + 'a @@ -347,6 +402,10 @@ pub trait LabelGraph<T: GraphLabel>: Graph { /// The efficiency of this method matters in implementations. fn labels_of(&self, node_id: usize) -> Result<Self::LabelIter<'_>, Error>; + /// Return an iterator of tuples of edge labels and targets of + /// edges out of a node. + fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error>; + /// Return true if and only if the node has an edge with the given /// label and target. fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error>; |