summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
Diffstat (limited to 'graph')
-rw-r--r--graph/src/builder.rs2
-rw-r--r--graph/src/error.rs3
-rw-r--r--graph/src/labelled/binary.rs273
-rw-r--r--graph/src/labelled/mod.rs4
-rw-r--r--graph/src/labelled/single.rs343
-rw-r--r--graph/src/lib.rs13
6 files changed, 292 insertions, 346 deletions
diff --git a/graph/src/builder.rs b/graph/src/builder.rs
index 4a480a5..5505e4f 100644
--- a/graph/src/builder.rs
+++ b/graph/src/builder.rs
@@ -77,7 +77,7 @@ pub trait BuilderMut {
fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_>;
/// Add a new vertex.
- fn add_vertex(&mut self, label: Self::Label) -> Result<usize, Error>;
+ fn add_vertex(&mut self, label: Self::Label) -> usize;
/// Add an edge from the source to the target.
fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>;
diff --git a/graph/src/error.rs b/graph/src/error.rs
index bf2714b..ce45acc 100644
--- a/graph/src/error.rs
+++ b/graph/src/error.rs
@@ -18,6 +18,8 @@ pub enum Error {
/// The graph does not permit duplicate edges but encounters a
/// repeated edge.
DuplicatedEdge(usize, usize),
+ /// The source node has no room to add a new edge.
+ FullNode(usize),
}
impl Display for Error {
@@ -35,6 +37,7 @@ impl Display for Error {
"No duplicate edges permitted, but found one from {source} to {target}"
)
}
+ Error::FullNode(index) => write!(f, "the node {index} has no room for new edges"),
}
}
}
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
new file mode 100644
index 0000000..439505d
--- /dev/null
+++ b/graph/src/labelled/binary.rs
@@ -0,0 +1,273 @@
+//! This file implements a labelled graph that can index vertices by
+//! labels and each node knows about its parents.
+
+use super::*;
+use crate::ParentsGraph;
+
+use std::collections::{HashMap as Map, HashSet as Set};
+
+use crate::builder::BuilderMut;
+
+/// A node has some children, some parents, and a label.
+#[derive(Debug, Clone)]
+struct PLNode<T: GraphLabel> {
+ children: Set<usize>,
+ // REVIEW: If performance for removing edges is a bottleneck, use
+ // a hash set here.
+ parents: Vec<usize>,
+ label: T,
+}
+
+impl<T: GraphLabel> PLNode<T> {
+ fn new(children: Set<usize>, parents: Vec<usize>, label: T) -> Self {
+ Self {
+ children,
+ parents,
+ label,
+ }
+ }
+}
+
+impl<T: GraphLabel + Default> Default for PLNode<T> {
+ #[inline]
+ fn default() -> Self {
+ let children = Default::default();
+ let parents = Default::default();
+ let label = Default::default();
+ Self {
+ children,
+ label,
+ parents,
+ }
+ }
+}
+
+/// A Parents-knowing, vertex-Labelled Graph.
+#[derive(Debug, Clone)]
+pub struct PLGraph<T: GraphLabel> {
+ nodes: Vec<PLNode<T>>,
+ label_index_map: Map<T, usize>,
+}
+
+impl<T: GraphLabel> Default for PLGraph<T> {
+ #[inline]
+ fn default() -> Self {
+ let nodes = Default::default();
+ let label_index_map = Default::default();
+ Self {
+ nodes,
+ label_index_map,
+ }
+ }
+}
+
+impl<T: GraphLabel> Graph for PLGraph<T> {
+ type Iter<'a> = std::iter::Copied<std::collections::hash_set::Iter<'a, usize>>
+ where
+ Self: '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> {
+ if let Some(node) = self.nodes.get(node_id) {
+ Ok(node.children.iter().copied())
+ } else {
+ Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+ }
+ }
+
+ #[inline]
+ fn degree(&self, node_id: usize) -> Result<usize, Error> {
+ if let Some(node) = self.nodes.get(node_id) {
+ Ok(node.children.len())
+ } else {
+ Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+ }
+ }
+
+ #[inline]
+ fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
+ if let Some(node) = self.nodes.get(node_id) {
+ Ok(node.children.is_empty())
+ } else {
+ Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+ }
+ }
+
+ fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
+ if let Some(node) = self.nodes.get(source) {
+ if !self.has_node(target) {
+ return Err(Error::IndexOutOfBounds(target, self.nodes.len()));
+ }
+
+ Ok(node.children.contains(&target))
+ } else {
+ Err(Error::IndexOutOfBounds(source, self.nodes.len()))
+ }
+ }
+
+ fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
+ unimplemented!("for later")
+ }
+
+ fn print_viz(&self, _filename: &str) -> Result<(), std::io::Error> {
+ todo!()
+ }
+}
+
+impl<T: GraphLabel> ParentsGraph for PLGraph<T> {
+ type Iter<'a> = std::iter::Copied<std::slice::Iter<'a, usize>>
+ where Self: 'a;
+
+ #[inline]
+ fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, Error> {
+ if let Some(node) = self.nodes.get(node_id) {
+ Ok(node.parents.iter().copied())
+ } else {
+ Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+ }
+ }
+}
+
+impl<T: GraphLabel> LabelGraph<T> for PLGraph<T> {
+ type Iter<'a> = std::iter::Empty<usize>
+ where
+ Self: 'a;
+
+ type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)>
+ where
+ Self: 'a,
+ T: 'a;
+
+ type EdgeLabelIter<'a> = std::iter::Empty<T>
+ where
+ Self: 'a,
+ T: 'a;
+
+ #[inline]
+ fn query_label(&self, label: T) -> Option<usize> {
+ self.label_index_map.get(&label).copied()
+ }
+
+ #[inline]
+ fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> {
+ if let Some(node) = self.nodes.get(node_id) {
+ Ok(Some(node.label))
+ } else {
+ Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
+ }
+ }
+
+ fn edge_label(&self, _source: usize, _target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
+ unimplemented!("Edges have no labels")
+ }
+
+ fn find_children_with_label(
+ &self,
+ _node_id: usize,
+ _label: &T,
+ ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error> {
+ unimplemented!("Edges have no labels")
+ }
+
+ fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> {
+ unimplemented!("Edges have no labels")
+ }
+
+ fn has_edge_label(&self, _node_id: usize, _label: &T, _target: usize) -> Result<bool, Error> {
+ unimplemented!("Edges have no labels")
+ }
+}
+
+/// A builder that modifies PLGraph in place.
+#[derive(Debug)]
+pub struct PLGBuilderMut<'a, T: GraphLabel> {
+ graph: &'a mut PLGraph<T>,
+}
+
+impl<'a, T: GraphLabel> BuilderMut for PLGBuilderMut<'a, T> {
+ type Label = T;
+
+ type Graph = PLGraph<T>;
+
+ type ResultBuilder<'b> = PLGBuilderMut<'b, T>
+ where
+ Self::Label: 'b;
+
+ fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> {
+ PLGBuilderMut { graph }
+ }
+
+ fn add_vertex(&mut self, label: Self::Label) -> usize {
+ if let Some(old) = self.graph.label_index_map.get(&label) {
+ *old
+ } else {
+ let new_node = PLNode::new(Default::default(), Default::default(), label);
+ self.graph.nodes.push(new_node);
+
+ let new_index = self.graph.nodes.len() - 1;
+
+ self.graph.label_index_map.insert(label, new_index);
+
+ new_index
+ }
+ }
+
+ fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
+ if self.graph.has_edge(source, target)? {
+ return Err(Error::DuplicatedEdge(source, target));
+ }
+
+ self.graph
+ .nodes
+ .get_mut(source)
+ .unwrap()
+ .children
+ .insert(target);
+
+ self.graph
+ .nodes
+ .get_mut(target)
+ .unwrap()
+ .parents
+ .push(source);
+
+ Ok(())
+ }
+
+ fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
+ where
+ F: Fn(Self::Label) -> bool,
+ {
+ if !self.graph.has_edge(source, target)? {
+ return Ok(());
+ }
+
+ self.graph
+ .nodes
+ .get_mut(source)
+ .unwrap()
+ .children
+ .remove(&target);
+
+ self.graph
+ .nodes
+ .get_mut(target)
+ .unwrap()
+ .parents
+ .retain(|parent| *parent != source);
+
+ Ok(())
+ }
+}
+
+// TODO: tests
diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs
index 61e3014..fa26bc4 100644
--- a/graph/src/labelled/mod.rs
+++ b/graph/src/labelled/mod.rs
@@ -15,6 +15,6 @@ pub mod double;
pub use double::{DLGBuilder, DLGraph};
-pub mod single;
+pub mod binary;
-pub use single::SLGraph;
+// pub use binary::BLGraph;
diff --git a/graph/src/labelled/single.rs b/graph/src/labelled/single.rs
deleted file mode 100644
index bed65c1..0000000
--- a/graph/src/labelled/single.rs
+++ /dev/null
@@ -1,343 +0,0 @@
-//! This file implements a labelled graph that can index vertices by
-//! labels.
-//!
-//! Since we do not have to index edges by labels, the labels can be
-//! stored simply by adjacency maps. This may save memory usage and
-//! improve performance, potentially.
-
-use super::*;
-
-use std::collections::{hash_map::Keys, HashMap as Map};
-
-use crate::builder::BuilderMut;
-
-/// The type of a node.
-#[derive(Debug, Clone, Default)]
-struct SLNode<T: GraphLabel> {
- /// The edges are stored as an association from the target node
- /// index to the label of the corresponding edge.
- ///
- /// An implication is that an edge can only have one label.
- children: Map<usize, T>,
- /// The label of this node.
- label: T,
-}
-
-impl<T: GraphLabel> SLNode<T> {
- fn new(children: Map<usize, T>, label: T) -> Self {
- Self { children, label }
- }
-
- /// This function just adds an edge, blindly.
- ///
- /// # Safety
- ///
- /// Only use this after making sure that `target` refers to a
- /// valid node, and there was no edge from this node to the node
- /// pointed to by `target` previously.
- unsafe fn add_edge(&mut self, target: usize, label: T) {
- self.children.insert(target, label);
- }
-}
-
-/// The type of labelled graphs implemented using adjacency maps.
-#[derive(Debug, Clone)]
-pub struct SLGraph<T: GraphLabel> {
- nodes: Vec<SLNode<T>>,
- label_index_map: Map<T, usize>,
-}
-
-impl<T: GraphLabel> Default for SLGraph<T> {
- fn default() -> Self {
- let nodes = Vec::new();
- let label_index_map = Default::default();
- Self {
- nodes,
- label_index_map,
- }
- }
-}
-
-impl<T: GraphLabel> Graph for SLGraph<T> {
- type Iter<'a> = std::iter::Copied<Keys<'a, usize, T>>
- where
- Self: '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> {
- if let Some(node) = self.nodes.get(node_id) {
- Ok(node.children.keys().copied())
- } else {
- Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
- }
- }
-
- #[inline]
- fn degree(&self, node_id: usize) -> Result<usize, Error> {
- if let Some(node) = self.nodes.get(node_id) {
- Ok(node.children.len())
- } else {
- Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
- }
- }
-
- #[inline]
- fn is_empty_node(&self, node_id: usize) -> Result<bool, Error> {
- if let Some(node) = self.nodes.get(node_id) {
- Ok(node.children.is_empty())
- } else {
- Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
- }
- }
-
- #[inline]
- fn has_edge(&self, source: usize, target: usize) -> Result<bool, Error> {
- let nodes_len = self.nodes.len();
-
- let node = if let Some(node) = self.nodes.get(source) {
- node
- } else {
- return Err(Error::IndexOutOfBounds(source, nodes_len));
- };
-
- if !self.has_node(target) {
- return Err(Error::IndexOutOfBounds(target, nodes_len));
- }
-
- Ok(node.children.contains_key(&target))
- }
-
- fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
- // In case this is not clear enough, I deliberately avoid
- // implementing this.
- unimplemented!()
- }
-}
-
-/// An iterator of edge labels.
-///
-/// This is used to avoid a box allocation.
-#[derive(Copy, Clone, Debug)]
-pub struct EdgeLabelIter<T: GraphLabel>(Option<T>);
-
-impl<T: GraphLabel> Iterator for EdgeLabelIter<T> {
- type Item = T;
-
- #[inline]
- fn next(&mut self) -> Option<Self::Item> {
- self.0.take()
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- let len = self.0.is_some() as usize;
-
- (len, Some(len))
- }
-}
-
-impl<T: GraphLabel> DoubleEndedIterator for EdgeLabelIter<T> {
- #[inline]
- fn next_back(&mut self) -> Option<Self::Item> {
- self.0.take()
- }
-}
-
-impl<T: GraphLabel> ExactSizeIterator for EdgeLabelIter<T> {
- #[inline]
- fn len(&self) -> usize {
- // Thanks to Clippy for teaching me about coercing a boolean
- // value to an integer.
- self.0.is_some() as usize
- }
-}
-
-impl<T: GraphLabel> LabelGraph<T> for SLGraph<T> {
- // The following two types are not used, as we do not need to
- // index edges by labels.
- type Iter<'a> = std::iter::Empty<usize>
- where
- Self: 'a;
-
- type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)>
- where
- Self: 'a,
- T: 'a;
-
- type EdgeLabelIter<'a> = EdgeLabelIter<T>
- where
- Self: 'a,
- T: 'a;
-
- #[inline]
- fn query_label(&self, label: T) -> Option<usize> {
- self.label_index_map.get(&label).copied()
- }
-
- #[inline]
- fn vertex_label(&self, node_id: usize) -> Result<Option<T>, Error> {
- if let Some(node) = self.nodes.get(node_id) {
- Ok(Some(node.label))
- } else {
- Err(Error::IndexOutOfBounds(node_id, self.nodes_len()))
- }
- }
-
- #[inline]
- fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
- let nodes_len = self.nodes.len();
-
- let node = if let Some(node) = self.nodes.get(source) {
- node
- } else {
- return Err(Error::IndexOutOfBounds(source, nodes_len));
- };
-
- if !self.has_node(target) {
- return Err(Error::IndexOutOfBounds(target, nodes_len));
- }
-
- Ok(EdgeLabelIter(node.children.get(&target).copied()))
- }
-
- fn find_children_with_label(
- &self,
- _node_id: usize,
- _label: &T,
- ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, Error> {
- unimplemented!()
- }
-
- fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, Error> {
- unimplemented!()
- }
-
- #[inline]
- fn has_edge_label(&self, node_id: usize, label: &T, target: usize) -> Result<bool, Error> {
- let nodes_len = self.nodes.len();
-
- let node = if let Some(node) = self.nodes.get(node_id) {
- node
- } else {
- return Err(Error::IndexOutOfBounds(node_id, nodes_len));
- };
-
- if !self.has_node(target) {
- return Err(Error::IndexOutOfBounds(target, nodes_len));
- }
-
- Ok(node.children.get(&target) == Some(label))
- }
-}
-
-/// The type of `builder_mut` builders for this type of graphs.
-#[derive(Debug)]
-pub struct SLGBuilderMut<'a, T: GraphLabel> {
- graph: &'a mut SLGraph<T>,
-}
-
-impl<'a, T: GraphLabel> BuilderMut for SLGBuilderMut<'a, T> {
- type Label = T;
-
- type Graph = SLGraph<T>;
-
- type ResultBuilder<'b> = SLGBuilderMut<'b, T>
- where
- T:'b;
-
- fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> {
- SLGBuilderMut { graph }
- }
-
- fn add_vertex(&mut self, label: T) -> Result<usize, Error> {
- if let Some(old_node) = self.graph.label_index_map.get(&label) {
- dbg!(label);
- return Err(Error::DuplicatedNode(*old_node));
- }
-
- self.graph
- .nodes
- .push(SLNode::new(Default::default(), label));
-
- let new = self.graph.nodes_len() - 1;
-
- self.graph.label_index_map.insert(label, new);
-
- Ok(new)
- }
-
- fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error> {
- let graph = &mut self.graph;
-
- let nodes_len = graph.nodes.len();
-
- // NOTE: We check the validity of `target` first because we
- // need to borrow graph mutably later, which would prevent us
- // from borrowing graph immutably to check the validity of
- // `target` then.
- if !graph.has_node(target) {
- return Err(Error::IndexOutOfBounds(target, nodes_len));
- }
-
- let node = if let Some(node) = graph.nodes.get_mut(source) {
- node
- } else {
- return Err(Error::IndexOutOfBounds(source, nodes_len));
- };
-
- if node.children.get(&target).is_some() {
- return Err(Error::DuplicatedEdge(source, target));
- }
-
- // We checked what we need to check, so this is safe.
- unsafe {
- node.add_edge(target, label);
- }
-
- Ok(())
- }
-
- fn remove_edge<F>(&mut self, source: usize, target: usize, predicate: F) -> Result<(), Error>
- where
- F: Fn(Self::Label) -> bool,
- {
- let graph = &mut self.graph;
-
- let nodes_len = graph.nodes.len();
-
- // NOTE: We check the validity of `target` first because we
- // need to borrow graph mutably later, which would prevent us
- // from borrowing graph immutably to check the validity of
- // `target` then.
- if !graph.has_node(target) {
- return Err(Error::IndexOutOfBounds(target, nodes_len));
- }
-
- let node = if let Some(node) = graph.nodes.get_mut(source) {
- node
- } else {
- return Err(Error::IndexOutOfBounds(source, nodes_len));
- };
-
- if let Some(child_label) = node.children.get(&target) {
- // There is only one label, so we just check this label.
- if predicate(*child_label) {
- node.children.remove(&target);
- }
-
- Ok(())
- } else {
- Err(Error::DuplicatedEdge(source, target))
- }
- }
-}
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 79f9646..26159c6 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -214,6 +214,19 @@ impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debu
{
}
+/// A parents-knowing graph can return an iterator of parents for any
+/// node.
+pub trait ParentsGraph: Graph {
+ /// The type of an iterator that goes through the parents of a
+ /// node.
+ type Iter<'a>: Iterator<Item = usize> + 'a
+ where
+ Self: 'a;
+
+ /// Return an iterator of parents for a node.
+ fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, Error>;
+}
+
/// A labelled graph is just a graph with labels associated to
/// vertices and / or edges.
///
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-09 23:48:10 +0000