summaryrefslogtreecommitdiff
path: root/graph/src/labelled.rs
diff options
context:
space:
mode:
Diffstat (limited to 'graph/src/labelled.rs')
-rw-r--r--graph/src/labelled.rs426
1 files changed, 426 insertions, 0 deletions
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<T: GraphLabel> {
+ by_target: Map<usize, Set<T>>,
+ by_label: Map<T, Set<usize>>,
+ flat: Vec<(T, usize)>,
+}
+
+impl<T: GraphLabel> DLNode<T> {
+ fn new(
+ by_target: Map<usize, Set<T>>,
+ by_label: Map<T, Set<usize>>,
+ flat: Vec<(T, usize)>,
+ ) -> Self {
+ Self {
+ by_target,
+ by_label,
+ flat,
+ }
+ }
+}
+
+/// Mapping a set of edges to an index of node.
+type EdgeMap<T> = HMap<Set<(T, usize)>, 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<T: GraphLabel> {
+ nodes: Vec<DLNode<T>>,
+ edges_table: EdgeMap<T>,
+}
+
+impl<T: GraphLabel> DLGraph<T> {
+ #[inline]
+ /// Return an empty graph.
+ pub fn new() -> Self {
+ Self {
+ nodes: Vec::new(),
+ edges_table: HMap::default(),
+ }
+ }
+}
+
+impl<T: GraphLabel> Default for DLGraph<T> {
+ #[inline]
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl<T: GraphLabel> Graph for DLGraph<T> {
+ // Not using a boxed pointer is supposed to save some allocations.
+ type Iter<'a> = std::iter::Copied<Keys<'a, usize, Set<T>>> 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<Self::Iter<'_>, 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<usize, Error> {
+ 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<bool, Error> {
+ 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<bool, Error> {
+ 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<std::iter::Copied<Iter<'a, usize>>>,
+}
+
+impl<'a> Iterator for LabelIndexIter<'a> {
+ type Item = usize;
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ self.iter.as_mut().map(|iterator| iterator.next()).flatten()
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ 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<Iter<'a, usize>>) -> Self {
+ let iter = Some(iter);
+ Self { iter }
+ }
+}
+
+// A convenience method
+impl<'a> From<&'a Set<usize>> for LabelIndexIter<'a> {
+ fn from(set: &'a Set<usize>) -> 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<usize>>,
+}
+
+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<usize>>) -> Self {
+ Self { iter }
+ }
+}
+
+impl<'a, T> Iterator for LabelIter<'a, T> {
+ type Item = (&'a T, LabelIndexIter<'a>);
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ self.iter.next().map(|(label, set)| (label, set.into()))
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
+ 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<Vec<T>, 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<<Self as LabelGraph<T>>::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<Self::LabelIter<'_>, 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<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
+ fn extend(&mut self, edges: impl IntoIterator<Item = (T, usize)>) -> Result<usize, Error> {
+ let mut by_target: Map<usize, Set<T>> = Map::default();
+ let mut by_label: Map<T, Set<usize>> = 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::<usize>::default() };
+ ($($num:literal),*) => {
+ {
+ let mut set: Set<usize> = Set::default();
+ $(set.insert($num);)*
+ set
+ }
+ };
+ }
+
+ macro_rules! map {
+ () => { Map::<usize, Set<usize>>::default() };
+ ($(($key:literal, $value:expr)),*) => {
+ {
+ let mut map: Map<usize, Set<usize>> = Map::default();
+ $(map.insert($key, $value);)*
+ map
+ }
+ };
+ }
+
+ #[test]
+ fn test_graph_apis() -> Result<(), Error> {
+ let mut graph: DLGraph<usize> = 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<_>>(), set!(1, 3, 2));
+
+ // testing find_children_with_label
+ assert_eq!(
+ graph.find_children_with_label(5, &2)?.collect::<Set<_>>(),
+ set!(1, 3)
+ );
+
+ // testing edge_label
+ assert_eq!(
+ graph.edge_label(5, 2)?.into_iter().collect::<Set<_>>(),
+ 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<usize, Set<usize>> = 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(())
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-09 23:49:37 +0000