diff options
Diffstat (limited to 'graph/src/lib.rs')
| -rw-r--r-- | graph/src/lib.rs | 203 |
1 files changed, 203 insertions, 0 deletions
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<Item = usize> + '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<usize> { + 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<dyn Iterator<Item = usize> + '_> { + 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<Self::Iter<'_>, 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<dyn Iterator<Item = (usize, usize)> + '_> { + 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<usize, Error>; + + /// 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<bool, Error>; + + /// 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<bool, Error>; +} + +/// 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<Item = usize>) -> Result<usize, Error>; +} + +/// The type of labels should be comparable and hashable. +pub trait GraphLabel: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd {} + +impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd> 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<T: GraphLabel>: Graph { + /// A type that iterates through the node indices. + type Iter<'a>: Iterator<Item = usize> + 'a + where + Self: 'a; + + /// A type that iterates through labels. + type LabelIter<'a>: Iterator<Item = (&'a T, <Self as LabelGraph<T>>::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<Option<T>, 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<Vec<T>, 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<<Self as LabelGraph<T>>::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<Self::LabelIter<'_>, 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<T: GraphLabel>: LabelGraph<T> { + /// 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<Item = (T, usize)>) -> Result<usize, Error>; +} |