From f28155105134b90fd86049c65478d307e0d8dbbc Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sat, 28 Jan 2023 10:17:24 +0800 Subject: 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. --- graph/src/labelled/double.rs | 126 +++++++++++-------------------------------- 1 file changed, 30 insertions(+), 96 deletions(-) (limited to 'graph/src/labelled/double.rs') 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 DLNode { } } -/// Mapping a set of edges to an index of node. -type EdgeMap = HMap, 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 { nodes: Vec>, - edges_table: EdgeMap, } impl DLGraph { - #[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 { @@ -89,7 +68,9 @@ impl DLGraph { impl Default for DLGraph { #[inline] fn default() -> Self { - Self::new() + let nodes = Vec::new(); + + Self { nodes } } } @@ -160,11 +141,9 @@ impl Graph for DLGraph { 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 Graph for DLGraph { let new_graph = builder.build(); self.nodes = new_graph.nodes; - self.edges_table = new_graph.edges_table; } } @@ -336,10 +314,10 @@ impl LabelGraph for DLGraph { 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, Error> { if self.has_edge(source, target)? { @@ -438,19 +416,12 @@ impl LabelExtGraph for DLGraph { } } - 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 Builder for DLGBuilder { fn with_capacity(size: usize) -> Self { Self(DLGraph { nodes: Vec::with_capacity(size), - edges_table: Default::default(), }) } @@ -526,8 +496,6 @@ impl Builder for DLGBuilder { ); 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 Builder for DLGBuilder { .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 Builder for DLGBuilder { } 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 Builder for DLGBuilder { }); } - // 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!(1, 3, 2)); @@ -723,8 +657,8 @@ mod label_test { // testing edge_label assert_eq!(graph.edge_label(5, 2)?.collect::>(), 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(()) -- cgit v1.2.3-18-g5258