diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/src/adlist.rs | 242 | ||||
| -rw-r--r-- | graph/src/adset.rs | 216 | ||||
| -rw-r--r-- | graph/src/builder.rs | 53 | ||||
| -rw-r--r-- | graph/src/error.rs | 9 | ||||
| -rw-r--r-- | graph/src/labelled.rs | 390 | ||||
| -rw-r--r-- | graph/src/lib.rs | 133 |
6 files changed, 1027 insertions, 16 deletions
diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs index 18ad770..6c1dcd0 100644 --- a/graph/src/adlist.rs +++ b/graph/src/adlist.rs @@ -3,8 +3,9 @@ //! [`Graph`][super::Graph]. This data type represents graphs using //! adjacency lists internally. -use super::{ExtGraph, Graph}; -use crate::error::Error; +use std::ops::{Deref, DerefMut}; + +use crate::{builder::Builder, error::Error, ExtGraph, Graph}; // #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)] // struct ALEdge { @@ -80,6 +81,13 @@ impl Graph for ALGraph { Ok(self.nodes.get(source).unwrap().children.contains(&target)) } } + + #[inline] + fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>) { + let graph = builder.build(); + + self.nodes = graph.nodes; + } } impl ExtGraph for ALGraph { @@ -102,11 +110,115 @@ impl ExtGraph for ALGraph { } } -// TODO: Add a way to build a graph by its raw adjacency list representation. impl From<Vec<Vec<usize>>> for ALGraph { fn from(adlist: Vec<Vec<usize>>) -> Self { - let nodes: Vec<ALNode> = adlist.iter().cloned().map(ALNode::new).collect(); - Self { nodes } + Self { + nodes: adlist.into_iter().map(ALNode::new).collect(), + } + } +} + +// Builder for this implementation of graph + +/// A builder for adjacency list graphs. +#[derive(Debug, Default, Clone)] +pub struct ALGBuilder(ALGraph); + +impl Deref for ALGBuilder { + type Target = ALGraph; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl DerefMut for ALGBuilder { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl Builder for ALGBuilder { + type Label = (); + + type Result = ALGraph; + + fn with_capacity(size: usize) -> Self { + Self(ALGraph { + nodes: Vec::with_capacity(size), + }) + } + + #[inline] + fn add_vertex(&mut self) -> usize { + self.nodes.push(ALNode::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.push(target); + + Ok(()) + } + + /// 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. + /// + /// # Performance note + /// + /// It is possible that the target appears more than once in the + /// vector of children, so we have to remove every instance of + /// target. + /// + /// Since I do not think builders should be used for performance + /// critical tasks, this is fine. + /// + /// If one desires more performance, maybe + /// [`ASGraph`][crate::ASGraph] is a good choice. + /// + /// Of course, if one just wants to use adjacency list + /// representation and wants a performant builder, one can + /// implement a customized builder. + fn remove_edge<F>(&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.retain(|child| *child != target); + + Ok(()) + } + + fn build(self) -> Self::Result { + self.0 + } + + fn build_ref(&self) -> Self::Result { + self.0.clone() } } @@ -187,3 +299,123 @@ mod algraph_test { Ok(()) } } + +#[cfg(test)] +mod test_algraph_builder { + use super::*; + + #[test] + fn test_builder() -> Result<(), Box<dyn std::error::Error>> { + let mut builder = ALGBuilder::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<dyn std::error::Error>> { + let mut builder = ALGBuilder::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(()) + } +} 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<Result = Self>) { + 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<F>(&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<dyn std::error::Error>> { + 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<dyn std::error::Error>> { + 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(()) + } +} diff --git a/graph/src/builder.rs b/graph/src/builder.rs new file mode 100644 index 0000000..ce85cce --- /dev/null +++ b/graph/src/builder.rs @@ -0,0 +1,53 @@ +//! This file defines the expected behaviours of a builder of graphs. + +use crate::{error::Error, Graph}; + +/// A builder is actually just a graph that can be altered in more +/// ways than an extension graph can. It should not have any methods +/// from the Graph trait, though, as we shall convert a builder to a +/// normal final graph before using it. +pub trait Builder: Default { + /// Some graphs are labelled. This type should be the type of the + /// labels. + type Label; + + /// The type of the result graph. + type Result: Graph; + + /// Construct an empty builder with the capacity to hold a given + /// number of nodes. + /// + /// Implementations may ignore this method, where the default + /// implementation just calls `Default::default`. + #[inline] + fn with_capacity(_size: usize) -> Self { + Self::default() + } + + /// Add a vertex without children. + fn add_vertex(&mut self) -> usize; + + /// Add an edge from the source to the target. + fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>; + + /// 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. + fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error> + where + F: Fn(Self::Label) -> bool; + + /// Convert the builder into a graph. + /// + /// This is the purpose of having a builder. + fn build(self) -> Self::Result; + + /// 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. + fn build_ref(&self) -> Self::Result; +} diff --git a/graph/src/error.rs b/graph/src/error.rs index 2162685..3600005 100644 --- a/graph/src/error.rs +++ b/graph/src/error.rs @@ -1,16 +1,20 @@ #![warn(missing_docs)] //! This file implements the error data type of the graph library. -use std::fmt::{self, Display}; +use core::fmt::{self, Display}; /// The error type for methods of the trait [`Graph`][`super::Graph`]. -#[derive(Debug, Clone, PartialEq, Eq, Ord, PartialOrd)] +#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd)] +#[non_exhaustive] pub enum Error { /// The index is out of bounds. /// /// The first component is the index that is out of bounds, and /// the second component is the current length of nodes. IndexOutOfBounds(usize, usize), + /// The graph does not permit duplicate nodes but encounters a + /// repeated node + DuplicatedNode, } impl Display for Error { @@ -19,6 +23,7 @@ impl Display for Error { Error::IndexOutOfBounds(index, len) => { write!(f, "index {index} out of bounds {len} ") } + Error::DuplicatedNode => write!(f, "No duplicate nodes permitted, but found one"), } } } diff --git a/graph/src/labelled.rs b/graph/src/labelled.rs index d02e301..d0a02d0 100644 --- a/graph/src/labelled.rs +++ b/graph/src/labelled.rs @@ -7,10 +7,9 @@ //! needs to be implemented efficiently, we store the mappings between //! labels and edges in both directions. -#[allow(unused_imports)] -use super::{Graph, GraphLabel, LabelExtGraph, LabelGraph}; -#[allow(unused_imports)] -use crate::error::Error; +use std::ops::{Deref, DerefMut}; + +use crate::{builder::Builder, error::Error, Graph, GraphLabel, LabelExtGraph, LabelGraph}; // We use BTreeMap and BTreeSet here as we need to exclude duplicate // edge sets, while an ordinary hashmap and hashset do not allow @@ -21,13 +20,23 @@ use std::collections::{ BTreeMap as Map, BTreeSet as Set, HashMap as HMap, }; -#[derive(Debug, Clone, Default)] +#[derive(Debug, Clone)] struct DLNode<T: GraphLabel> { by_target: Map<usize, Set<T>>, by_label: Map<T, Set<usize>>, flat: Vec<(T, usize)>, } +impl<T: GraphLabel> Default for DLNode<T> { + fn default() -> Self { + Self { + by_target: Default::default(), + by_label: Default::default(), + flat: Default::default(), + } + } +} + impl<T: GraphLabel> DLNode<T> { fn new( by_target: Map<usize, Set<T>>, @@ -66,6 +75,18 @@ impl<T: GraphLabel> DLGraph<T> { edges_table: HMap::default(), } } + + /// Return a builder. + #[inline] + pub fn builder(self) -> DLGBuilder<T> { + DLGBuilder(self) + } + + /// Return a builder from a reference. + #[inline] + pub fn builder_ref(&self) -> DLGBuilder<T> { + DLGBuilder(self.clone()) + } } impl<T: GraphLabel> Default for DLGraph<T> { @@ -129,6 +150,49 @@ impl<T: GraphLabel> Graph for DLGraph<T> { None => Err(Error::IndexOutOfBounds(source, self.nodes.len())), } } + + fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> { + let preamble = "digraph nfa { + fontname=\"Helvetica,Arial,sans-serif\" + node [fontname=\"Helvetica,Arial,sans-serif\"] + edge [fontname=\"Helvetica,Arial,sans-serif\"] + rankdir=LR;\n"; + + let mut post = String::new(); + + use std::fmt::Write as FWrite; + + for (source, target) in self.edges() { + for label in self.edge_label(source, target).unwrap() { + let _ = writeln!(post, " {source} -> {target} [label = \"{label}\"]"); + } + } + + 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; + self.edges_table = new_graph.edges_table; + } } /// A delegation of iterators. @@ -261,6 +325,25 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> { None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())), } } + + 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)); + } + + if let Some(labels) = node.by_target.get(&target) { + Ok(labels.contains(label)) + } else { + Ok(false) + } + } + None => Err(Error::IndexOutOfBounds(node_id, nodes_len)), + } + } } impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> { @@ -315,6 +398,181 @@ impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> { } } +// Builder for this implementation of graph + +/// A builder for labelled adjacency doubly linked graphs. +#[derive(Debug, Clone)] +pub struct DLGBuilder<T: GraphLabel>(DLGraph<T>); + +impl<T: GraphLabel> Default for DLGBuilder<T> { + fn default() -> Self { + Self(Default::default()) + } +} + +impl<T: GraphLabel> Deref for DLGBuilder<T> { + type Target = DLGraph<T>; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl<T: GraphLabel> DerefMut for DLGBuilder<T> { + fn deref_mut(&mut self) -> &mut Self::Target { + &mut self.0 + } +} + +impl<T: GraphLabel> Builder for DLGBuilder<T> { + type Label = T; + + type Result = DLGraph<T>; + + #[inline] + fn with_capacity(size: usize) -> Self { + Self(DLGraph { + nodes: Vec::with_capacity(size), + edges_table: Default::default(), + }) + } + + #[inline] + fn add_vertex(&mut self) -> usize { + self.nodes.push(DLNode::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_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)); + } + + let new_edge_p = !matches!( + source_node + .by_target + .get(&target) + .map(|set| set.contains(&label)), + Some(true) + ); + + if new_edge_p { + let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect(); + + source_node + .by_target + .entry(target) + .or_insert_with(Set::default) + .insert(label); + + source_node + .by_label + .entry(label) + .or_insert_with(Set::default) + .insert(target); + + source_node.flat.push((label, target)); + + let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect(); + + // When source_node is in use, we cannot borrow self + // mutably again, so we move the following two statements + // to after all uses of source_node. + + self.edges_table.remove(&old_children_set); + + self.edges_table.insert(new_children_set, source); + } + + Ok(()) + } + + fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error> + where + F: Fn(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)); + } + + if let Some(target_labels_set) = source_node.by_target.get(&target) { + let mut to_remove = Vec::new(); + + for label in target_labels_set.iter() { + if predicate(*label) { + to_remove.push(*label); + } + } + + if !to_remove.is_empty() { + let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect(); + + for label in to_remove.iter().copied() { + // This must be "Some", as the outer "if" checks + source_node + .by_target + .get_mut(&target) + .map(|set| set.remove(&label)); + + source_node + .by_label + .get_mut(&label) + .map(|set| set.remove(&target)); + + source_node.flat.retain(|(child_label, child_target)| { + (*child_label, *child_target) != (label, target) + }); + } + + // If after removal no labels remain for the target, + // we remove the edge entirely, to avoid false empty + // edges. + if source_node.flat.is_empty() { + source_node.by_target.remove(&target); + + for label in to_remove.iter() { + source_node.by_label.remove(label); + } + } + + let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect(); + + // When source_node is in use, we cannot borrow self + // mutably again, so we move the following two + // statements to after all uses of source_node. + + self.edges_table.remove(&old_children_set); + + self.edges_table.insert(new_children_set, source); + } + } + + Ok(()) + } + + fn build_ref(&self) -> Self::Result { + self.0.clone() + } + + fn build(self) -> Self::Result { + self.0 + } +} + #[cfg(test)] mod label_test { use super::*; @@ -424,3 +682,125 @@ mod label_test { Ok(()) } } + +// TODO: Test print_viz + +#[cfg(test)] +mod test_dlgraph_builder { + use super::*; + + #[test] + fn test_builder() -> Result<(), Box<dyn std::error::Error>> { + let mut builder = DLGBuilder::<usize>::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 { i + 1 } else { 0 }, i)?; + } + + 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<dyn std::error::Error>> { + let mut builder = DLGBuilder::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, 0), + Err(Error::IndexOutOfBounds(5, 5)) + )); + + println!("Right error for an index out of bounds as the target"); + + assert!(matches!( + builder.add_edge(10, 5, 0), + Err(Error::IndexOutOfBounds(10, 5)) + )); + + println!("Right error for an index out of bounds as the source"); + + assert!(matches!( + builder.add_edge(10, 50, 0), + 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(()) + } +} diff --git a/graph/src/lib.rs b/graph/src/lib.rs index 7b74ee1..2d23af3 100644 --- a/graph/src/lib.rs +++ b/graph/src/lib.rs @@ -8,6 +8,8 @@ use std::hash::Hash; +use core::fmt::{Debug, Display}; + pub mod error; pub mod adset; @@ -22,6 +24,10 @@ pub mod labelled; pub use labelled::DLGraph; +pub mod builder; + +pub use builder::Builder; + use error::Error; /// The expected behaviour of an immutable graph. @@ -101,6 +107,83 @@ pub trait Graph: Default { /// Return an error if either the source or the target is an /// invalid node. fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error>; + + /// Output the edges into a graphviz file. + fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> { + let preamble = "digraph nfa { + fontname=\"Helvetica,Arial,sans-serif\" + node [fontname=\"Helvetica,Arial,sans-serif\"] + edge [fontname=\"Helvetica,Arial,sans-serif\"] + rankdir=LR;\n"; + + let mut post = String::new(); + + use std::fmt::Write as FWrite; + + for (source, target) in self.edges() { + let _ = writeln!(post, "{source} -> {target}"); + } + + 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()) + } + + /// Returns whether or not the graph contains cycles. + /// + /// If, and only if, the graph contains invalid nodes, an error + /// will be signalled. + fn contains_cycles(&self) -> Result<bool, Error> { + use std::collections::HashSet; + + let mut seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len()); + + for node in self.nodes() { + if seen_nodes.contains(&node) { + continue; + } + + let mut edges_seen_nodes: HashSet<usize> = HashSet::with_capacity(self.nodes_len()); + + let mut stack = Vec::with_capacity(self.nodes_len()); + stack.push(node); + + while let Some(top) = stack.pop() { + if edges_seen_nodes.contains(&top) { + // a cycle is found + return Ok(true); + } + + edges_seen_nodes.insert(top); + + let mut local_stack: Vec<usize> = self.children_of(top)?.collect(); + + local_stack.reverse(); + + stack.extend(local_stack); + } + + seen_nodes.extend(edges_seen_nodes); + } + + Ok(false) + } + + /// Replace the contents of the graph by a builder. + fn replace_by_builder(&mut self, builder: impl Builder<Result = Self>); } /// A graph that can be extended, but not mutated, in the sense that @@ -121,9 +204,15 @@ pub trait ExtGraph: Graph { } /// The type of labels should be comparable and hashable. -pub trait GraphLabel: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd {} +pub trait GraphLabel: + Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug +{ +} -impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd> GraphLabel for T {} +impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debug> GraphLabel + for T +{ +} /// A labelled graph is just a graph with labels associated to /// vertices and / or edges. @@ -182,6 +271,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 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>; } /// A labelled graph that can be extended, but not mutated, in the @@ -201,3 +294,39 @@ pub trait LabelExtGraph<T: GraphLabel>: LabelGraph<T> { /// an error. fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error>; } + +#[cfg(test)] +mod test_cycle_detection { + use super::{builder::Builder, labelled::DLGBuilder, Graph}; + + #[test] + fn test() -> Result<(), Box<dyn std::error::Error>> { + let mut builder: DLGBuilder<usize> = DLGBuilder::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)?; + } + + let graph = builder.build_ref(); + + assert_eq!(graph.contains_cycles()?, true); + + // Remove the link from the last node to the first node. + builder.remove_edge(4, 0, |_| true)?; + + let graph = builder.build(); + + assert_eq!(graph.contains_cycles()?, false); + + Ok(()) + } +} |