summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-28 10:17:24 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-28 10:22:57 +0800
commitf28155105134b90fd86049c65478d307e0d8dbbc (patch)
tree72b3b4872d5dba89413eca70bcaae9e421def7ee /graph
parente8ea01319b3a9032a3f4f69f65e9ca96562b87b9 (diff)
a prototype of an item derivation forest
It seems to be complete now, but still awaits more tests to see where the errors are, which should be plenty, haha.
Diffstat (limited to 'graph')
-rw-r--r--graph/src/labelled/double.rs126
-rw-r--r--graph/src/labelled/mod.rs2
2 files changed, 30 insertions, 98 deletions
diff --git a/graph/src/labelled/double.rs b/graph/src/labelled/double.rs
index 174c8ef..ab2b27c 100644
--- a/graph/src/labelled/double.rs
+++ b/graph/src/labelled/double.rs
@@ -8,13 +8,10 @@
use super::*;
-// 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,
+ hash_map::{Iter as MapIter, Keys},
+ hash_set::Iter,
+ HashMap as Map, HashSet as Set,
};
#[derive(Debug, Clone)]
@@ -48,31 +45,13 @@ impl<T: GraphLabel> DLNode<T> {
}
}
-/// 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(),
- }
- }
-
/// Return a builder.
#[inline]
pub fn builder(self) -> DLGBuilder<T> {
@@ -89,7 +68,9 @@ impl<T: GraphLabel> DLGraph<T> {
impl<T: GraphLabel> Default for DLGraph<T> {
#[inline]
fn default() -> Self {
- Self::new()
+ let nodes = Vec::new();
+
+ Self { nodes }
}
}
@@ -160,11 +141,9 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
let mut post = String::new();
- use std::fmt::Write as FWrite;
-
for (source, target) in self.edges() {
for label in self.edge_label(source, target).unwrap() {
- let _ = writeln!(post, " {source} -> {target} [label = \"{label}\"]");
+ post.push_str(&format!(" {source} -> {target} [label = \"{label}\"]\n"));
}
}
@@ -191,7 +170,6 @@ impl<T: GraphLabel> Graph for DLGraph<T> {
let new_graph = builder.build();
self.nodes = new_graph.nodes;
- self.edges_table = new_graph.edges_table;
}
}
@@ -336,10 +314,10 @@ impl<T: GraphLabel> LabelGraph<T> for DLGraph<T> {
type LabelIter<'a> = LabelIter<'a,T> where T: 'a;
- type EdgeLabelIter<'a> = EdgeLabelIter<'a,T>
+ type EdgeLabelIter<'a> = EdgeLabelIter<'a, T>
where
Self: 'a,
- T: 'a + Copy + Clone;
+ T: 'a;
fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, Error> {
if self.has_edge(source, target)? {
@@ -438,19 +416,12 @@ impl<T: GraphLabel> LabelExtGraph<T> for DLGraph<T> {
}
}
- 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);
+ let new_node = DLNode::new(by_target, by_label, flat);
+ let new_index = self.nodes_len();
- self.nodes.push(new_node);
+ self.nodes.push(new_node);
- Ok(new_index)
- }
- }
+ Ok(new_index)
}
}
@@ -489,7 +460,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
fn with_capacity(size: usize) -> Self {
Self(DLGraph {
nodes: Vec::with_capacity(size),
- edges_table: Default::default(),
})
}
@@ -526,8 +496,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
);
if new_edge_p {
- let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
source_node
.by_target
.entry(target)
@@ -541,16 +509,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
.insert(target);
source_node.flat.push((label, target));
-
- let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
- // When source_node is in use, we cannot borrow self
- // mutably again, so we move the following two statements
- // to after all uses of source_node.
-
- self.edges_table.remove(&old_children_set);
-
- self.edges_table.insert(new_children_set, source);
}
Ok(())
@@ -586,8 +544,6 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
}
if !to_remove.is_empty() {
- let old_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
for label in to_remove.iter().copied() {
// This must be "Some", as the outer "if" checks
source_node
@@ -605,41 +561,19 @@ impl<T: GraphLabel> Builder for DLGBuilder<T> {
});
}
- // If after removal no labels remain for the target,
- // we remove the edge entirely, to avoid false empty
- // edges.
-
- if let Some(set) = source_node.by_target.get(&target) {
- if set.is_empty() {
- source_node.by_target.remove(&target);
- }
+ if matches!(source_node.by_target.get(&target),
+ Some(set) if set.is_empty())
+ {
+ source_node.by_target.remove(&target);
}
for label in to_remove.iter() {
- if let Some(set) = source_node.by_label.get(label) {
- if set.is_empty() {
- source_node.by_label.remove(label);
- }
+ if matches!(source_node.by_label.get(label),
+ Some(set) if set.is_empty())
+ {
+ source_node.by_label.remove(label);
}
}
-
- // if source_node.flat.is_empty() {
- // source_node.by_target.remove(&target);
-
- // for label in to_remove.iter() {
- // source_node.by_label.remove(label);
- // }
- // }
-
- let new_children_set: Set<(T, usize)> = source_node.flat.iter().copied().collect();
-
- // When source_node is in use, we cannot borrow self
- // mutably again, so we move the following two
- // statements to after all uses of source_node.
-
- self.edges_table.remove(&old_children_set);
-
- self.edges_table.insert(new_children_set, source);
}
}
@@ -703,13 +637,13 @@ mod label_test {
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);
+ assert_eq!(graph.extend([(2, 1), (2, 3), (3, 2)].iter().copied())?, 6);
+ assert_eq!(graph.extend([(3, 2), (3, 0)].iter().copied())?, 7);
let graph = graph;
// ensuring the correct length
- assert_eq!(graph.nodes_len(), 6);
+ assert_eq!(graph.nodes_len(), 8);
// testing children_of
assert_eq!(graph.children_of(5)?.collect::<Set<_>>(), set!(1, 3, 2));
@@ -723,8 +657,8 @@ mod label_test {
// testing edge_label
assert_eq!(graph.edge_label(5, 2)?.collect::<Set<_>>(), set!(3));
assert!(matches!(
- graph.edge_label(6, 2),
- Err(Error::IndexOutOfBounds(6, 6))
+ graph.edge_label(8, 2),
+ Err(Error::IndexOutOfBounds(8, 8))
));
// testing degree
@@ -738,8 +672,8 @@ mod label_test {
assert!(graph.has_edge(3, 2)?);
assert!(!graph.has_edge(3, 1)?);
assert!(matches!(
- graph.has_edge(3, 6),
- Err(Error::IndexOutOfBounds(6, 6))
+ graph.has_edge(3, 8),
+ Err(Error::IndexOutOfBounds(8, 8))
));
// testing labels_of
@@ -754,8 +688,8 @@ mod label_test {
assert_eq!(label_map, compare_map);
assert!(matches!(
- graph.labels_of(6),
- Err(Error::IndexOutOfBounds(6, 6))
+ graph.labels_of(8),
+ Err(Error::IndexOutOfBounds(8, 8))
));
Ok(())
diff --git a/graph/src/labelled/mod.rs b/graph/src/labelled/mod.rs
index 2bbc7ec..fb7b405 100644
--- a/graph/src/labelled/mod.rs
+++ b/graph/src/labelled/mod.rs
@@ -17,5 +17,3 @@ pub use double::{DLGBuilder, DLGraph};
pub mod binary;
pub use binary::{PLGBuilderMut, PLGraph};
-
-// pub use binary::BLGraph;