summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-20 13:48:26 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-20 13:48:26 +0800
commit18d7955b7d84c00467ede38baae53f4ce1fb6908 (patch)
tree97d0746b82816a21d980636e50f8cdbeb804b518 /graph
parent8f8d3d1a3c276be4be2e5d2e767ada564c47279a (diff)
chain: a prototype is added.
I have an ostensibly working prototype now. Further tests are needed to make sure that the algorithm meets the time complexity requirement, though.
Diffstat (limited to 'graph')
-rw-r--r--graph/src/error.rs3
-rw-r--r--graph/src/labelled/binary.rs44
-rw-r--r--graph/src/labelled/double.rs14
-rw-r--r--graph/src/lib.rs10
4 files changed, 56 insertions, 15 deletions
diff --git a/graph/src/error.rs b/graph/src/error.rs
index ce45acc..bf2714b 100644
--- a/graph/src/error.rs
+++ b/graph/src/error.rs
@@ -18,8 +18,6 @@ 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 {
@@ -37,7 +35,6 @@ 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
index bfd8109..e3e1943 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -19,18 +19,22 @@ struct PLChildren {
}
impl PLChildren {
+ #[inline]
fn iter(&self) -> Iter<'_, usize> {
self.children.iter()
}
+ #[inline]
fn len(&self) -> usize {
self.children.len()
}
+ #[inline]
fn is_empty(&self) -> bool {
self.children.is_empty()
}
+ #[inline]
fn contains(&self, key: &usize) -> bool {
self.indices.contains_key(key)
}
@@ -73,6 +77,15 @@ impl PLChildren {
self.children.remove(key_index);
}
+
+ /// Retrieve the `n`-th child.
+ #[inline]
+ fn nth(&self, n: usize) -> Result<usize, Error> {
+ self.children
+ .get(n)
+ .copied()
+ .ok_or(Error::IndexOutOfBounds(n, self.children.len()))
+ }
}
/// A node has some children, some parents, and a label.
@@ -187,7 +200,7 @@ impl<T: GraphLabel> Graph for PLGraph<T> {
}
fn replace_by_builder(&mut self, _builder: impl Builder<Result = Self>) {
- todo!()
+ unimplemented!("use a `PLGBuilderMut` instead")
}
fn print_viz(&self, _filename: &str) -> Result<(), std::io::Error> {
@@ -246,6 +259,31 @@ impl<T: GraphLabel> ParentsGraph for PLGraph<T> {
Err(Error::IndexOutOfBounds(node_id, self.nodes.len()))
}
}
+
+ #[inline]
+ fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, Error> {
+ if let Some(node) = self.nodes.get(node_id) {
+ node.children.nth(n)
+ } else {
+ Err(Error::IndexOutOfBounds(node_id, self.nodes_len()))
+ }
+ }
+
+ #[inline]
+ fn edge_to_parent(&self, source: usize, target: usize) -> Result<Option<Parent>, Error> {
+ if !self.has_edge(source, target)? {
+ return Ok(None);
+ }
+
+ Ok(self
+ .nodes
+ .get(source)
+ .unwrap()
+ .children
+ .indices
+ .get(&target)
+ .map(|index| Parent::new(source, *index)))
+ }
}
impl<T: GraphLabel> RedirectGraph for PLGraph<T> {
@@ -378,13 +416,13 @@ impl<'a, T: GraphLabel> std::ops::Deref for PLGBuilderMut<'a, T> {
type Target = PLGraph<T>;
fn deref(&self) -> &Self::Target {
- &self.graph
+ self.graph
}
}
impl<'a, T: GraphLabel> std::ops::DerefMut for PLGBuilderMut<'a, T> {
fn deref_mut(&mut self) -> &mut Self::Target {
- &mut self.graph
+ self.graph
}
}
diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs
index 4ab8a38..174c8ef 100644
--- a/graph/src/labelled/double.rs
+++ b/graph/src/labelled/double.rs
@@ -150,6 +150,8 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
}
fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> {
+ let filename = format!("output/{filename}");
+
let preamble = "digraph nfa {
fontname=\"Helvetica,Arial,sans-serif\"
node [fontname=\"Helvetica,Arial,sans-serif\"]
@@ -170,14 +172,14 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
let result = format!("{preamble}{post}");
- if std::fs::metadata(filename).is_ok() {
- std::fs::remove_file(filename)?;
+ if std::fs::metadata(&filename).is_ok() {
+ std::fs::remove_file(&filename)?;
}
let mut file = std::fs::File::options()
.write(true)
.create(true)
- .open(filename)?;
+ .open(&filename)?;
use std::io::Write;
@@ -206,7 +208,7 @@ impl<'a> Iterator for LabelIndexIter<'a> {
#[inline]
fn next(&mut self) -> Option<Self::Item> {
- self.iter.as_mut().and_then(|iterator| iterator.next())
+ self.iter.as_mut().and_then(Iterator::next)
}
#[inline]
@@ -242,7 +244,7 @@ impl<'a> From<&'a Set<usize>> for LabelIndexIter<'a> {
}
}
-#[derive(Debug)]
+#[derive(Debug, Clone)]
/// A delegation of iterators.
///
/// This is used to avoid a boxed pointer to an iterator.
@@ -278,7 +280,7 @@ impl<'a, T> Iterator for LabelIter<'a, T> {
}
/// This is used to avoid a boxed pointer to an iterator.
-#[derive(Debug)]
+#[derive(Debug, Clone)]
pub struct EdgeLabelIter<'a, T> {
iter: Option<Iter<'a, T>>,
}
diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 6af7889..2a0c50d 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -251,10 +251,14 @@ pub trait ParentsGraph: Graph {
/// Return an iterator of parents for a node.
fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, Error>;
-}
-// TODO: Design a trait of graphs which can "replace" a certain child
-// by another child. To re-direct children, so to speak.
+ /// We need to be able to retrieve the `n`-the child, for the edge
+ /// index to be of any use.
+ fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, Error>;
+
+ /// Convert an edge to a `Parent` construct.
+ fn edge_to_parent(&self, source: usize, target: usize) -> Result<Option<Parent>, Error>;
+}
/// An /exended/ graph in the sense that it offers the ability to
/// "redirect" children of a node to another node.