From cb7bcfad4ab0041aaf3fde3185e27ee46bb37788 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Tue, 15 Nov 2022 12:01:28 +0800 Subject: Initial commit Basic GNU standard files are added, and we now stop worrying about monadic anamorphisms. The current focus is on testing the correctness of the algorithm, so I need convenient support for manipulating, interpreting, examining, and per chance animating nondeterministic automata. --- graph/Cargo.toml | 12 ++ graph/Makefile.am | 12 ++ graph/src/adlist.rs | 181 +++++++++++++++++++++ graph/src/adset.rs | 229 +++++++++++++++++++++++++++ graph/src/error.rs | 26 +++ graph/src/labelled.rs | 426 ++++++++++++++++++++++++++++++++++++++++++++++++++ graph/src/lib.rs | 203 ++++++++++++++++++++++++ 7 files changed, 1089 insertions(+) create mode 100644 graph/Cargo.toml create mode 100644 graph/Makefile.am create mode 100644 graph/src/adlist.rs create mode 100644 graph/src/adset.rs create mode 100644 graph/src/error.rs create mode 100644 graph/src/labelled.rs create mode 100644 graph/src/lib.rs (limited to 'graph') diff --git a/graph/Cargo.toml b/graph/Cargo.toml new file mode 100644 index 0000000..d8f0622 --- /dev/null +++ b/graph/Cargo.toml @@ -0,0 +1,12 @@ +[package] +name = "graph" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] + +[features] + + diff --git a/graph/Makefile.am b/graph/Makefile.am new file mode 100644 index 0000000..776b911 --- /dev/null +++ b/graph/Makefile.am @@ -0,0 +1,12 @@ +.PHONY: dev rel + +all: dev + +dev: + @CARGO@ build + +rel: + @CARGO@ build --release + +clean: + @CARGO@ clean diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs new file mode 100644 index 0000000..c16ceb2 --- /dev/null +++ b/graph/src/adlist.rs @@ -0,0 +1,181 @@ +#![warn(missing_docs)] +//! This file implements a data type that implements the trait +//! [`Graph`][super::Graph]. This data type represents graphs using +//! adjacency lists internally. + +use super::{ExtGraph, Graph}; +use crate::error::Error; + +// #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)] +// struct ALEdge { +// to: usize, +// } + +// impl ALEdge { +// fn new(to: usize) -> Self { +// Self { to } +// } +// } + +#[derive(Debug, Clone, Default)] +struct ALNode { + children: Vec, +} + +impl ALNode { + fn new(children: Vec) -> Self { + Self { children } + } +} + +/// The graph implemented using adjacency lists. +#[derive(Debug, Clone, Default)] +pub struct ALGraph { + nodes: Vec, +} + +impl Graph for ALGraph { + type Iter<'a> = std::iter::Copied>; + + #[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(node.children.iter().copied()), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())), + } + } + + #[inline] + fn degree(&self, node_id: usize) -> Result { + 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 { + match self.nodes.get(node_id) { + Some(node) => Ok(node.children.is_empty()), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes_len())), + } + } + + fn has_edge(&self, source: usize, target: usize) -> Result { + 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(&target)) + } + } +} + +impl ExtGraph for ALGraph { + fn extend(&mut self, edges: impl IntoIterator) -> Result { + let mut new_node_children = Vec::new(); + + 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.push(edge_to); + } + + let new_node = ALNode::new(new_node_children); + + self.nodes.push(new_node); + + Ok(self.nodes.len() - 1) + } +} + +#[cfg(test)] +mod algraph_test { + use super::*; + + #[test] + fn test_graph_apis() -> Result<(), Error> { + let mut graph = ALGraph::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::>(), vec![1, 2, 3]); + + 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 = ALGraph::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 = ALGraph::default(); + + graph.extend(std::iter::empty())?; + + graph.extend([0].iter().copied())?; + + assert_eq!( + graph.extend([2].iter().copied()), + Err(Error::IndexOutOfBounds(2, 2)) + ); + + Ok(()) + } +} 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, +} + +impl ASNode { + fn new(children: Set) -> Self { + Self { children } + } +} + +/// The graph implemented using adjacency sets. +#[derive(Debug, Clone, Default)] +pub struct ASGraph { + nodes: Vec, +} + +/// 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.iter.next().map(|edge| edge.to) + } + + fn size_hint(&self) -> (usize, Option) { + 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, 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 { + 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 { + 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 { + 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) -> Result { + 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::>(), { + 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(()) + } +} diff --git a/graph/src/error.rs b/graph/src/error.rs new file mode 100644 index 0000000..2162685 --- /dev/null +++ b/graph/src/error.rs @@ -0,0 +1,26 @@ +#![warn(missing_docs)] +//! This file implements the error data type of the graph library. + +use std::fmt::{self, Display}; + +/// The error type for methods of the trait [`Graph`][`super::Graph`]. +#[derive(Debug, Clone, PartialEq, Eq, Ord, PartialOrd)] +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), +} + +impl Display for Error { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Error::IndexOutOfBounds(index, len) => { + write!(f, "index {index} out of bounds {len} ") + } + } + } +} + +impl std::error::Error for Error {} diff --git a/graph/src/labelled.rs b/graph/src/labelled.rs new file mode 100644 index 0000000..1cb2461 --- /dev/null +++ b/graph/src/labelled.rs @@ -0,0 +1,426 @@ +#![warn(missing_docs)] +//! This file implements a labelled graph. See the +//! [trait][super::LabelGraph] for details. +//! +//! Since the method +//! [`find_children_with_label`][super::LabelGraph::find_children_with_label] +//! 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; + +// We use BTreeMap and BTreeSet here as we need to exclude duplicate +// edge sets, while an ordinary hashmap and hashset do not allow +// hashing. +use std::collections::{ + btree_map::{Iter as MapIter, Keys}, + btree_set::Iter, + BTreeMap as Map, BTreeSet as Set, HashMap as HMap, +}; + +#[derive(Debug, Clone, Default)] +struct DLNode { + by_target: Map>, + by_label: Map>, + flat: Vec<(T, usize)>, +} + +impl DLNode { + fn new( + by_target: Map>, + by_label: Map>, + flat: Vec<(T, usize)>, + ) -> Self { + Self { + by_target, + by_label, + flat, + } + } +} + +/// Mapping a set of edges to an index of node. +type EdgeMap = HMap, usize>; + +/// Double direction Labelled Graph. +/// +/// Each node is supposed to have a unique edge set. Constructing +/// methods such as from the trait +/// [`LabelExtGraph`][super::LabelExtGraph] already handles the +/// elimination of duplication. +#[derive(Debug, Clone)] +pub struct DLGraph { + nodes: Vec>, + edges_table: EdgeMap, +} + +impl DLGraph { + #[inline] + /// Return an empty graph. + pub fn new() -> Self { + Self { + nodes: Vec::new(), + edges_table: HMap::default(), + } + } +} + +impl Default for DLGraph { + #[inline] + fn default() -> Self { + Self::new() + } +} + +impl Graph for DLGraph { + // Not using a boxed pointer is supposed to save some allocations. + type Iter<'a> = std::iter::Copied>> 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, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(node.by_target.keys().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.flat.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.flat.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() { + return Err(Error::IndexOutOfBounds(target, self.nodes.len())); + } + + Ok(source_node.by_target.contains_key(&target)) + } + None => Err(Error::IndexOutOfBounds(source, self.nodes.len())), + } + } +} + +/// A delegation of iterators. +/// +/// This is used to avoid a boxed pointer to an iterator. +#[derive(Default, Debug)] +pub struct LabelIndexIter<'a> { + iter: Option>>, +} + +impl<'a> Iterator for LabelIndexIter<'a> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option { + self.iter.as_mut().map(|iterator| iterator.next()).flatten() + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + match &self.iter { + Some(iter) => iter.size_hint(), + None => (0, Some(0)), + } + } +} + +impl<'a> ExactSizeIterator for LabelIndexIter<'a> { + #[inline] + fn len(&self) -> usize { + match &self.iter { + Some(iter) => iter.len(), + None => 0, + } + } +} + +impl<'a> LabelIndexIter<'a> { + fn new(iter: std::iter::Copied>) -> Self { + let iter = Some(iter); + Self { iter } + } +} + +// A convenience method +impl<'a> From<&'a Set> for LabelIndexIter<'a> { + fn from(set: &'a Set) -> Self { + Self::new(set.iter().copied()) + } +} + +#[derive(Debug)] +/// A delegation of iterators. +/// +/// This is used to avoid a boxed pointer to an iterator. +pub struct LabelIter<'a, T> { + iter: MapIter<'a, T, Set>, +} + +impl<'a, T> ExactSizeIterator for LabelIter<'a, T> { + #[inline] + fn len(&self) -> usize { + self.iter.len() + } +} + +impl<'a, T> LabelIter<'a, T> { + fn new(iter: MapIter<'a, T, Set>) -> Self { + Self { iter } + } +} + +impl<'a, T> Iterator for LabelIter<'a, T> { + type Item = (&'a T, LabelIndexIter<'a>); + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().map(|(label, set)| (label, set.into())) + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +impl LabelGraph for DLGraph { + type Iter<'a> = LabelIndexIter<'a> where T: 'a; + + type LabelIter<'a> = LabelIter<'a,T> where T: 'a; + + fn edge_label(&self, source: usize, target: usize) -> Result, Error> { + if self.has_edge(source, target)? { + Ok(self + .nodes + .get(source) + .unwrap() + .by_target + .get(&target) + .unwrap() + .iter() + .copied() + .collect()) + } else { + Ok(Vec::new()) + } + } + + fn find_children_with_label( + &self, + node_id: usize, + label: &T, + ) -> Result<>::Iter<'_>, Error> { + match self + .nodes + .get(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, self.nodes.len()))? + .by_label + .get(label) + { + Some(set) => Ok(set.into()), + None => Ok(Default::default()), + } + } + + #[inline] + fn labels_of(&self, node_id: usize) -> Result, Error> { + match self.nodes.get(node_id) { + Some(node) => Ok(Self::LabelIter::new(node.by_label.iter())), + None => Err(Error::IndexOutOfBounds(node_id, self.nodes.len())), + } + } +} + +impl LabelExtGraph for DLGraph { + fn extend(&mut self, edges: impl IntoIterator) -> Result { + let mut by_target: Map> = Map::default(); + let mut by_label: Map> = Map::default(); + let mut flat = Vec::new(); + let mut edges_set = Set::new(); + + for (label, to) in edges { + if !self.has_node(to) { + return Err(Error::IndexOutOfBounds(to, self.nodes.len())); + } + + edges_set.insert((label, to)); + + if let Some(set) = by_target.get(&to) { + 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); + } + } 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); + } + } + + match self.edges_table.get(&edges_set) { + Some(old_index) => Ok(*old_index), + None => { + let new_node = DLNode::new(by_target, by_label, flat); + let new_index = self.nodes_len(); + + self.edges_table.insert(edges_set, new_index); + + self.nodes.push(new_node); + + Ok(new_index) + } + } + } +} + +#[cfg(test)] +mod label_test { + use super::*; + + macro_rules! set { + () => { Set::::default() }; + ($($num:literal),*) => { + { + let mut set: Set = Set::default(); + $(set.insert($num);)* + set + } + }; + } + + macro_rules! map { + () => { Map::>::default() }; + ($(($key:literal, $value:expr)),*) => { + { + let mut map: Map> = Map::default(); + $(map.insert($key, $value);)* + map + } + }; + } + + #[test] + fn test_graph_apis() -> Result<(), Error> { + let mut graph: DLGraph = 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())?, 5); + assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 3); + + let graph = graph; + + // ensuring the correct length + assert_eq!(graph.nodes_len(), 6); + + // testing children_of + assert_eq!(graph.children_of(5)?.collect::>(), set!(1, 3, 2)); + + // testing find_children_with_label + assert_eq!( + graph.find_children_with_label(5, &2)?.collect::>(), + set!(1, 3) + ); + + // testing edge_label + assert_eq!( + graph.edge_label(5, 2)?.into_iter().collect::>(), + set!(3) + ); + assert!(matches!( + graph.edge_label(6, 2), + Err(Error::IndexOutOfBounds(6, 6)) + )); + + // 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, 6), + Err(Error::IndexOutOfBounds(6, 6)) + )); + + // testing labels_of + let mut label_map: Map> = Map::default(); + + for (label, children) in graph.labels_of(5)? { + label_map.insert(*label, children.collect()); + } + + let compare_map = map!((2, set!(1, 3)), (3, set!(2))); + + assert_eq!(label_map, compare_map); + + assert!(matches!( + graph.labels_of(6), + Err(Error::IndexOutOfBounds(6, 6)) + )); + + Ok(()) + } +} diff --git a/graph/src/lib.rs b/graph/src/lib.rs new file mode 100644 index 0000000..7b74ee1 --- /dev/null +++ b/graph/src/lib.rs @@ -0,0 +1,203 @@ +#![warn(missing_docs)] +//! This crate implements a trait API for graphs that the crate "rep" +//! needs. +//! +//! Also a default implementation for the trait is provided, so that +//! by default no external crates are needed, whereas it is easy to +//! use external crates, if so derired. + +use std::hash::Hash; + +pub mod error; + +pub mod adset; + +pub use adset::ASGraph; + +pub mod adlist; + +pub use adlist::ALGraph; + +pub mod labelled; + +pub use labelled::DLGraph; + +use error::Error; + +/// The expected behaviour of an immutable graph. +pub trait Graph: Default { + /// A type that iterates through the node indices. + type Iter<'a>: Iterator + 'a + where + Self: 'a; + + /// Return true if and only if the graph has no nodes. + fn is_empty(&self) -> bool; + + /// Return the length of nodes in the graph. + fn nodes_len(&self) -> usize; + + #[inline] + /// Return the length of edges in the graph. + /// + /// This is optional. Implementations need not support this. + fn edges_len(&self) -> Option { + None + } + + #[inline] + /// Return an iterator of nodes represented as unsigned integers. + /// + /// If a custom application needs to have labels on nodes, just + /// associate the label to the node internally, and define an + /// extension trait that allows querying those additional labels. + /// + /// This design choice is based on the idea that this library + /// should be minimal and only provide the core of a graph. As a + /// label is not really core, it is not included here. + fn nodes(&self) -> Box + '_> { + Box::new(0..self.nodes_len()) + } + + /// Return an iterator of edges going out of a node. + /// + /// Return an error if the node is not known to the graph. + fn children_of(&self, node_id: usize) -> Result, Error>; + + #[inline] + /// Return an iterator of edges represented as pairs (FROM, TO). + /// + /// The default implementation iterates through the nodes and then + /// iterates through their children. If the implementation has a + /// more efficient method, overwrite this method. + fn edges(&self) -> Box + '_> { + Box::new(self.nodes().flat_map(|node| { + self.children_of(node) + // If this node is invalid, this means the + // implementation of `nodes` is wrong, so it is + // appropriate to panic here. + .unwrap() + .map(move |child| (node, child)) + })) + } + + #[inline] + /// Return true if and only if the node is in the graph. + fn has_node(&self, node_id: usize) -> bool { + (0..self.nodes_len()).contains(&node_id) + } + + /// Return the number of "children" of a node, or an error if the + /// node is not a member of the graph. + fn degree(&self, node_id: usize) -> Result; + + /// Return a boolean indicating if the node has no children, or an + /// error if the node is not a member of the graph. + fn is_empty_node(&self, node_id: usize) -> Result; + + /// Return true if and only if there is an edge from the source to + /// the target. + /// + /// Return an error if either the source or the target is an + /// invalid node. + fn has_edge(&self, source: usize, target: usize) -> Result; +} + +/// A graph that can be extended, but not mutated, in the sense that +/// existing nodes and edges will not be modified nor removed, but new +/// nodes can be added. The index of the new node will be returned. +/// +/// Implementations can choose to keep a set of sets of edges, so that +/// new nodes will not have duplicate edge sets. In this case, the +/// returned new node index is not necessarily equal to +/// self.nodes_len() - 1, and hence the return type is designed in +/// this way. +pub trait ExtGraph: Graph { + /// Add a new node with `edges`. + /// + /// If an edge from `edges` points to a non-existent node, return + /// an error. + fn extend(&mut self, edges: impl IntoIterator) -> Result; +} + +/// The type of labels should be comparable and hashable. +pub trait GraphLabel: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd {} + +impl GraphLabel for T {} + +/// A labelled graph is just a graph with labels associated to +/// vertices and / or edges. +/// +/// This trait defines what the package needs out of a labelled graph. +/// +/// Any implementation should be able to handle a set of types for +/// labels, so this trait is generic over the label type. +pub trait LabelGraph: Graph { + /// A type that iterates through the node indices. + type Iter<'a>: Iterator + 'a + where + Self: 'a; + + /// A type that iterates through labels. + type LabelIter<'a>: Iterator>::Iter<'a>)> + 'a + where + Self: 'a, + T: 'a; + + #[inline] + /// Return the label of a vertex or an error if the node is + /// invalid. + /// + /// The default implementation always returns None for a valid + /// node. + fn vertex_label(&self, node_id: usize) -> Result, Error> { + if self.has_node(node_id) { + Ok(None) + } else { + Err(Error::IndexOutOfBounds(node_id, self.nodes_len())) + } + } + + #[inline] + /// Return the label of an edge or an error if some node is + /// invalid. + /// + /// The default implementation always returns an empty vector for + /// valid nodes. + fn edge_label(&self, source: usize, target: usize) -> Result, Error> { + self.has_edge(source, target).map(|_| Vec::new()) + } + + /// Return an iterator of edges out of a node, whose associated + /// label is as given. + /// + /// The efficiency of this method matters in implementations. + fn find_children_with_label( + &self, + node_id: usize, + label: &T, + ) -> Result<>::Iter<'_>, Error>; + + /// Return an iterator of labels of edges out of a node. + /// + /// The efficiency of this method matters in implementations. + fn labels_of(&self, node_id: usize) -> Result, Error>; +} + +/// A labelled graph that can be extended, but not mutated, in the +/// sense that existing nodes and edges will not be modified nor +/// removed, but new nodes can be added. The index of the new node +/// will be returned. +/// +/// Implementations can choose to keep a set of sets of edges, so that +/// new nodes will not have duplicate edge sets. In this case, the +/// returned new node index is not necessarily equal to +/// self.nodes_len() - 1, and hence the return type is designed in +/// this way. +pub trait LabelExtGraph: LabelGraph { + /// Add a new node with `edges`. + /// + /// If an edge from `edges` points to a non-existent node, return + /// an error. + fn extend(&mut self, edges: impl IntoIterator) -> Result; +} -- cgit v1.2.3-18-g5258