summaryrefslogtreecommitdiff
path: root/graph
diff options
context:
space:
mode:
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;
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-09 23:14:46 +0000