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