summaryrefslogtreecommitdiff
path: root/graph/src
diff options
context:
space:
mode:
Diffstat (limited to 'graph/src')
-rw-r--r--graph/src/adlist.rs104
-rw-r--r--graph/src/builder.rs5
-rw-r--r--graph/src/labelled/binary.rs4
3 files changed, 110 insertions, 3 deletions
diff --git a/graph/src/adlist.rs b/graph/src/adlist.rs
index ba3077e..d36b250 100644
--- a/graph/src/adlist.rs
+++ b/graph/src/adlist.rs
@@ -3,9 +3,16 @@
//! [`Graph`][super::Graph]. This data type represents graphs using
//! adjacency lists internally.
-use std::ops::{Deref, DerefMut};
+use std::{
+ borrow::{Borrow, BorrowMut},
+ ops::{Deref, DerefMut},
+};
-use crate::{builder::Builder, error::Error, ExtGraph, Graph};
+use crate::{
+ builder::{Builder, BuilderMut},
+ error::Error,
+ ExtGraph, Graph,
+};
// #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
// struct ALEdge {
@@ -118,6 +125,99 @@ impl From<Vec<Vec<usize>>> for ALGraph {
}
}
+/// A builder that modifies ALGraph in place.
+#[derive(Debug)]
+pub struct ALGBuilderMut<'a> {
+ graph: &'a mut ALGraph,
+}
+
+impl<'a> std::ops::Deref for ALGBuilderMut<'a> {
+ type Target = ALGraph;
+
+ fn deref(&self) -> &Self::Target {
+ self.graph.borrow()
+ }
+}
+
+impl<'a> std::ops::DerefMut for ALGBuilderMut<'a> {
+ fn deref_mut(&mut self) -> &mut Self::Target {
+ self.graph.borrow_mut()
+ }
+}
+
+impl<'a> BuilderMut for ALGBuilderMut<'a> {
+ type Label = ();
+
+ type Graph = ALGraph;
+
+ type ResultBuilder<'b> = ALGBuilderMut<'b>
+ where
+ Self::Label: 'b;
+
+ fn from_graph_mut(graph: &mut Self::Graph) -> Self::ResultBuilder<'_> {
+ ALGBuilderMut { graph }
+ }
+
+ fn add_vertex(&mut self, _label: Self::Label) -> usize {
+ self.nodes.push(Default::default());
+
+ self.nodes.len() - 1
+ }
+
+ fn add_edge(&mut self, source: usize, target: usize, _label: Self::Label) -> Result<(), Error> {
+ if self.graph.has_edge(source, target)? {
+ return Ok(());
+ }
+
+ self.graph
+ .nodes
+ .get_mut(source)
+ .unwrap()
+ .children
+ .push(target);
+
+ Ok(())
+ }
+
+ fn append(&mut self, other: Self::Graph) {
+ let self_len = self.nodes_len();
+
+ self.graph
+ .nodes
+ .extend(other.nodes.into_iter().map(|mut node| {
+ for child in node.children.iter_mut() {
+ *child += self_len;
+ }
+
+ node
+ }));
+ }
+
+ fn set_label(&mut self, _node_id: usize, _label: Self::Label) -> Result<(), Error> {
+ Ok(())
+ }
+
+ fn remove_edge<F>(&mut self, source: usize, target: usize, _predicate: F) -> Result<(), Error>
+ where
+ F: FnMut(Self::Label) -> bool,
+ {
+ let nodes_len = self.nodes.len();
+
+ let source_children = self
+ .nodes
+ .get_mut(source)
+ .ok_or(Error::IndexOutOfBounds(source, nodes_len))?;
+
+ if !(0..nodes_len).contains(&target) {
+ return Err(Error::IndexOutOfBounds(target, nodes_len));
+ }
+
+ source_children.children.retain(|child| *child != target);
+
+ Ok(())
+ }
+}
+
// Builder for this implementation of graph
/// A builder for adjacency list graphs.
diff --git a/graph/src/builder.rs b/graph/src/builder.rs
index c5f9252..1278e26 100644
--- a/graph/src/builder.rs
+++ b/graph/src/builder.rs
@@ -82,6 +82,11 @@ pub trait BuilderMut {
/// Add an edge from the source to the target.
fn add_edge(&mut self, source: usize, target: usize, label: Self::Label) -> Result<(), Error>;
+ /// Append another graph to this builder.
+ fn append(&mut self, _other: Self::Graph) {
+ unimplemented!()
+ }
+
/// Set the label of an existing node to a new label.
fn set_label(&mut self, node_id: usize, label: Self::Label) -> Result<(), Error>;
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index 9f3afa8..ccbd5cb 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -214,9 +214,11 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
let mut post = String::new();
- // FIXME: Find a way to print only used nodes. Maybe remove
+ // SOLVED: Find a way to print only used nodes. Maybe remove
// unwanted edges from unwanted nodes, so that we can print
// out only those used nodes.
+ //
+ // This is solved as we can extract the forest out.
for node in self.nodes() {
post.push_str(&format!(