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.

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>;
+}