Merge pull request #171 from bluss/filter-map-try-3
StableGraph clear_edges, retain_edges
diff --git a/src/graph_impl/stable_graph/mod.rs b/src/graph_impl/stable_graph/mod.rs
index 9a1d1f6..294c420 100644
--- a/src/graph_impl/stable_graph/mod.rs
+++ b/src/graph_impl/stable_graph/mod.rs
@@ -212,6 +212,19 @@
self.g.clear();
}
+ /// Remove all edges
+ pub fn clear_edges(&mut self) {
+ self.edge_count = 0;
+ self.free_edge = EdgeIndex::end();
+ self.g.edges.clear();
+ // clear edges without touching the free list
+ for node in &mut self.g.nodes {
+ if let Some(_) = node.weight {
+ node.next = [EdgeIndex::end(), EdgeIndex::end()];
+ }
+ }
+ }
+
/// Return the number of nodes (vertices) in the graph.
///
/// Computes in **O(1)** time.
@@ -709,7 +722,7 @@
/// **e'** is the number of affected edges, including *n* calls to `.remove_edge()`
/// where *n* is the number of edges with an endpoint in a removed node.
pub fn retain_nodes<F>(&mut self, mut visit: F) where F: FnMut(Frozen<Self>, NodeIndex<Ix>) -> bool {
- for i in 0..self.g.node_count() {
+ for i in 0..self.node_bound() {
let ix = node_index(i);
if self.contains_node(ix) && !visit(Frozen(self), ix) {
self.remove_node(ix);
@@ -718,6 +731,31 @@
self.check_free_lists();
}
+ /// Keep all edges that return `true` from the `visit` closure,
+ /// remove the others.
+ ///
+ /// `visit` is provided a proxy reference to the graph, so that
+ /// the graph can be walked and associated data modified.
+ ///
+ /// The order edges are visited is not specified.
+ ///
+ /// The edge indices of the removed edes are invalidated, but none other.
+ /// Edge indices are invalidated as they would be following the removal of
+ /// each edge with an endpoint in a removed edge.
+ ///
+ /// Computes in **O(e'')** time, **e'** is the number of affected edges,
+ /// including the calls to `.remove_edge()` for each removed edge.
+ pub fn retain_edges<F>(&mut self, mut visit: F)
+ where F: FnMut(Frozen<Self>, EdgeIndex<Ix>) -> bool
+ {
+ for i in 0..self.edge_bound() {
+ let ix = edge_index(i);
+ if self.edge_weight(ix).is_some() && !visit(Frozen(self), ix) {
+ self.remove_edge(ix);
+ }
+ }
+ self.check_free_lists();
+ }
/// Create a new `StableGraph` from an iterable of edges.
///
diff --git a/tests/stable_graph.rs b/tests/stable_graph.rs
index 046587b..bc6b034 100644
--- a/tests/stable_graph.rs
+++ b/tests/stable_graph.rs
@@ -46,6 +46,18 @@
assert_eq!(g.node_bound(), 0);
}
+#[test]
+fn clear_edges() {
+ let mut gr = scc_graph();
+ gr.remove_node(n(1));
+ gr.clear_edges();
+ // check that we use the free list for the vacancies
+ assert_eq!(gr.add_node(()), n(1));
+ assert_eq!(gr.add_node(()), n(4));
+ assert!(gr.edge_references().next().is_none());
+ assert!(gr.node_indices().all(|i| gr.neighbors(i).next().is_none()));
+}
+
fn assert_sccs_eq(mut res: Vec<Vec<NodeIndex>>, normalized: Vec<Vec<NodeIndex>>) {
// normalize the result and compare with the answer.
for scc in &mut res {
