a commit before the forst query

I think the main functionalities are already there, but the lack of
querying capabilities makes this not very useful at the moment.

This commit is right before an attempt to add this missing piece.

1 files changed, 62 insertions, 3 deletions

diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index e27ace0..058d62c 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -276,6 +276,58 @@ pub trait RedirectGraph: Graph {
     ) -> Result<(), Error>;
 }
 
+// TODO: Design traits for vertex-labelled, edge-labelled, and
+// both-labelled graphs separately.
+//
+// This is needed because we need better iterators to return labels
+// simultaneously with children nodes.  This can then reduce the
+// number of checking bounds when iterating.  I think this is the
+// right way of doing things, and can help with the performance as
+// well.
+
+/// A graph whose vertices are associated with labels.
+///
+/// This trait defines some convenient methods for accessing the
+/// labels of vertices.
+pub trait VLabelGraph<T: GraphLabel>: Graph {
+    /// A type that iterates through tuples of labels and targets of
+    /// edges.
+    type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a
+    where
+        Self: 'a,
+        T: 'a;
+
+    /// Query the graph for a label, and return the node index if
+    /// this operation is supported.
+    ///
+    /// The default implementation always returns `None`.
+    #[inline]
+    fn query_label(&self, _label: T) -> Option<usize> {
+        None
+    }
+
+    #[inline]
+    /// Return the label of a vertex or an error if the node is
+    /// invalid.
+    ///
+    /// The default implementation always returns `None` after
+    /// checking the validity of `node_id`.
+    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()))
+        }
+    }
+
+    /// Return an iterator of tuples of vertex labels and indices of
+    /// targets edges out of a node.
+    ///
+    /// The name is a weird new word created to stand as a
+    /// simplification of the phrase "vertex label and children of".
+    fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, Error>;
+}
+
 /// A labelled graph is just a graph with labels associated to
 /// vertices and / or edges.
 ///
@@ -289,9 +341,12 @@ pub trait LabelGraph<T: GraphLabel>: Graph {
     where
         Self: 'a;
 
-    // TODO: Add a type that iterates through children and labels of
-    // children simultaneously.  This can reduce the number of bounds
-    // checking.
+    /// A type that iterates through tuples of labels and targets of
+    /// edges.
+    type TupleIter<'a>: Iterator<Item = (T, usize)> + 'a
+    where
+        Self: 'a,
+        T: 'a;
 
     /// A type that iterates through labels.
     type LabelIter<'a>: Iterator<Item = (&'a T, <Self as LabelGraph<T>>::Iter<'a>)> + 'a
@@ -347,6 +402,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 an iterator of tuples of edge labels and targets of
+    /// edges out of a node.
+    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, 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>;