summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2022-12-23 00:36:31 +0800
committerJSDurand <mmemmew@gmail.com>2022-12-23 00:36:31 +0800
commit8463dd24f815fe2b8f25fe9763e0a43023bfbb20 (patch)
tree343eea3c634efbbf72c64ed5dd778ecce60c3eea /graph
parent9f1c88b863e247da3cd60d2792a7a13b18e25e53 (diff)
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.
Diffstat (limited to 'graph')
-rw-r--r--graph/src/adlist.rs242
-rw-r--r--graph/src/adset.rs216
-rw-r--r--graph/src/builder.rs53
-rw-r--r--graph/src/error.rs9
-rw-r--r--graph/src/labelled.rs390
-rw-r--r--graph/src/lib.rs133
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(())
+ }
+}