diff options
Diffstat (limited to 'graph/src/adset.rs')
| -rw-r--r-- | graph/src/adset.rs | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/graph/src/adset.rs b/graph/src/adset.rs new file mode 100644 index 0000000..58fed4c --- /dev/null +++ b/graph/src/adset.rs @@ -0,0 +1,229 @@ +#![warn(missing_docs)] +//! This file implements a data type that implements the trait +//! [`Graph`][super::Graph]. This data type represents graphs using +//! adjacency sets internally. +//! +//! I need this because the derivatives languages should not allow +//! 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; + +// If one wants to use another implementation for a set, import that +// as Set, and nothing else needs to be changed, ideally. +use std::collections::{hash_set::Iter, HashSet as Set}; + +#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] +struct ASEdge { + to: usize, +} + +impl ASEdge { + fn new(to: usize) -> Self { + Self { to } + } +} + +#[derive(Debug, Clone, Default)] +struct ASNode { + children: Set<ASEdge>, +} + +impl ASNode { + fn new(children: Set<ASEdge>) -> Self { + Self { children } + } +} + +/// The graph implemented using adjacency sets. +#[derive(Debug, Clone, Default)] +pub struct ASGraph { + nodes: Vec<ASNode>, +} + +/// A delegation of iterators. +/// +/// This is here to avoid using a boxed pointer, in order to save some +/// allocations. +pub struct ASIter<'a> { + iter: Iter<'a, ASEdge>, +} + +impl<'a> Iterator for ASIter<'a> { + type Item = usize; + + fn next(&mut self) -> Option<Self::Item> { + self.iter.next().map(|edge| edge.to) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } +} + +impl<'a> ExactSizeIterator for ASIter<'a> { + fn len(&self) -> usize { + self.iter.len() + } +} + +impl Graph for ASGraph { + type Iter<'a> = ASIter<'a>; + + #[inline] + fn is_empty(&self) -> bool { + self.nodes.is_empty() + } + + #[inline] + fn nodes_len(&self) -> usize { + self.nodes.len() + } + + fn children_of(&self, node_id: usize) -> Result<Self::Iter<'_>, Error> { + match self.nodes.get(node_id) { + Some(node) => { + let iter = node.children.iter(); + Ok(Self::Iter { iter }) + } + None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())), + } + } + + #[inline] + fn degree(&self, node_id: usize) -> Result<usize, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(node.children.len()), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())), + } + } + + #[inline] + fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(node.children.is_empty()), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())), + } + } + + #[inline] + fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> { + if !self.has_node(source) { + Err(Error::IndexOutOfBounds(source, self.nodes_len())) + } else if !self.has_node(target) { + Err(Error::IndexOutOfBounds(target, self.nodes_len())) + } else { + Ok(self + .nodes + .get(source) + .unwrap() + .children + .contains(&ASEdge::new(target))) + } + } +} + +impl ExtGraph for ASGraph { + fn extend(&mut self, edges: impl IntoIterator<Item = usize>) -> Result<usize, Error> { + let mut new_node_children = Set::default(); + + for edge_to in edges.into_iter() { + if !self.has_node(edge_to) { + return Err(Error::IndexOutOfBounds(edge_to, self.nodes_len())); + } + + new_node_children.insert(ASEdge::new(edge_to)); + } + + let new_node = ASNode::new(new_node_children); + + self.nodes.push(new_node); + + Ok(self.nodes.len() - 1) + } +} + +#[cfg(test)] +mod asgraph_test { + use super::*; + + #[test] + fn test_graph_apis() -> Result<(), Error> { + let mut graph = ASGraph::default(); + + assert!(graph.is_empty()); + + graph.extend(std::iter::empty())?; + + graph.extend([0].iter().copied())?; + graph.extend([0, 1].iter().copied())?; + graph.extend([0, 2].iter().copied())?; + graph.extend([1, 2].iter().copied())?; + graph.extend([1, 2, 3].iter().copied())?; + + let graph = graph; + + assert_eq!(graph.nodes_len(), 6); + + assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), { + let mut set = Set::default(); + set.insert(1); + set.insert(3); + set.insert(2); + set + }); + + assert_eq!(graph.degree(4)?, 2); + + assert!(graph.is_empty_node(0)?); + assert!(!graph.is_empty_node(1)?); + + assert!(graph.has_edge(3, 2)?); + assert!(!graph.has_edge(3, 1)?); + assert_eq!(graph.has_edge(3, 6), Err(Error::IndexOutOfBounds(6, 6))); + + Ok(()) + } + + #[test] + fn test_extending_algraph_normal() -> Result<(), Error> { + let mut graph = ASGraph::default(); + + let new = graph.extend(std::iter::empty())?; + + println!("new index = {new}"); + + println!("new graph = {graph:?}"); + + let new = graph.extend([0].iter().copied())?; + + println!("new index = {new}"); + + println!("new graph = {graph:?}"); + + let new = graph.extend([0, 1].iter().copied())?; + + println!("new index = {new}"); + + println!("new graph = {graph:?}"); + + Ok(()) + } + + #[test] + fn test_extending_algraph_error() -> Result<(), Error> { + let mut graph = ASGraph::default(); + + graph.extend(std::iter::empty())?; + + graph.extend([0].iter().copied())?; + + assert_eq!( + graph.extend([2].iter().copied()), + Err(Error::IndexOutOfBounds(2, 2)) + ); + + Ok(()) + } +} |