algograph/graph/
selected_subgraph.rs

1use crate::graph::*;
2use ahash::RandomState;
3use std::collections::HashSet;
4
5/// A subgraph with selected vertices and edges.
6///
7/// Removing vertices and edges from a [SelectedSubgraph] just unselects them.
8/// Therefore, shrinking a [SelectedSubgraph] keeps the underlying graph unchanged.
9pub struct SelectedSubgraph<'a, G> {
10    lower_graph: &'a G,
11    selected_vertices: HashSet<VertexId, RandomState>,
12    selected_edges: HashSet<EdgeId, RandomState>,
13}
14
15impl<'a, G> DirectedOrNot for SelectedSubgraph<'a, G>
16where
17    G: DirectedOrNot,
18{
19    const DIRECTED_OR_NOT: bool = G::DIRECTED_OR_NOT;
20}
21
22impl<'a, G> Subgraph for SelectedSubgraph<'a, G>
23where
24    G: QueryableGraph,
25{
26    type LowerGraph = &'a G;
27
28    fn new(lower_graph: Self::LowerGraph) -> Self {
29        Self {
30            lower_graph,
31            selected_vertices: HashSet::with_hasher(RandomState::new()),
32            selected_edges: HashSet::with_hasher(RandomState::new()),
33        }
34    }
35
36    fn disclose_vertex(&mut self, v: VertexId) -> &mut Self {
37        self.selected_vertices.insert(v);
38        self
39    }
40
41    fn disclose_edge(&mut self, e: EdgeId) -> &mut Self {
42        if let Some(edge) = self.lower_graph.find_edge(&e) {
43            self.selected_edges.insert(e);
44            self.disclose_vertex(edge.source).disclose_vertex(edge.sink);
45        }
46        self
47    }
48}
49
50impl<'a, G> QueryableGraph for SelectedSubgraph<'a, G>
51where
52    G: QueryableGraph,
53{
54    fn vertex_size(&self) -> usize {
55        self.selected_vertices.len()
56    }
57
58    fn iter_vertices(&self) -> Box<dyn Iterator<Item = VertexId> + '_> {
59        let it = self.selected_vertices.iter().copied();
60        Box::new(it)
61    }
62
63    fn contains_vertex(&self, v: &VertexId) -> bool {
64        self.selected_vertices.contains(v)
65    }
66
67    fn edges_connecting(
68        &self,
69        source: &VertexId,
70        sink: &VertexId,
71    ) -> Box<dyn Iterator<Item = crate::graph::Edge> + '_> {
72        let it = self
73            .lower_graph
74            .edges_connecting(source, sink)
75            .filter(|e| self.selected_edges.contains(&e.id));
76        Box::new(it)
77    }
78
79    fn edge_size(&self) -> usize {
80        self.selected_edges.len()
81    }
82
83    fn iter_edges(&self) -> Box<dyn Iterator<Item = crate::graph::Edge> + '_> {
84        let it = self
85            .selected_edges
86            .iter()
87            .map(|e| self.lower_graph.find_edge(e).unwrap());
88        Box::new(it)
89    }
90
91    fn contains_edge(&self, e: &EdgeId) -> bool {
92        self.selected_edges.contains(e)
93    }
94
95    fn find_edge(&self, e: &EdgeId) -> Option<crate::graph::Edge> {
96        if !self.selected_edges.contains(e) {
97            return None;
98        }
99        self.lower_graph.find_edge(e)
100    }
101
102    fn in_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = crate::graph::Edge> + '_> {
103        let it = self
104            .lower_graph
105            .in_edges(v)
106            .filter(|e| self.selected_edges.contains(&e.id));
107        Box::new(it)
108    }
109
110    fn out_edges(&self, v: &VertexId) -> Box<dyn Iterator<Item = crate::graph::Edge> + '_> {
111        let it = self
112            .lower_graph
113            .out_edges(v)
114            .filter(|e| self.selected_edges.contains(&e.id));
115        Box::new(it)
116    }
117}
118
119impl<'a, G> EdgeShrinkableGraph for SelectedSubgraph<'a, G>
120where
121    G: QueryableGraph,
122{
123    fn remove_edge(&mut self, edge: &EdgeId) -> Option<crate::graph::Edge> {
124        if self.selected_edges.remove(edge) {
125            self.lower_graph.find_edge(edge)
126        } else {
127            None
128        }
129    }
130}
131
132impl<'a, G> VertexShrinkableGraph for SelectedSubgraph<'a, G>
133where
134    G: QueryableGraph,
135{
136    fn remove_vertex(
137        &mut self,
138        vertex: &VertexId,
139    ) -> Box<dyn Iterator<Item = crate::graph::Edge> + 'static> {
140        if self.selected_vertices.remove(vertex) {
141            let edges: HashSet<Edge, RandomState> = self
142                .lower_graph
143                .in_edges(vertex)
144                .chain(self.lower_graph.out_edges(vertex))
145                .filter(|e| self.selected_edges.contains(&e.id))
146                .collect();
147            for e in edges.iter() {
148                self.selected_edges.remove(&e.id);
149            }
150            Box::new(edges.into_iter())
151        } else {
152            Box::new(std::iter::empty())
153        }
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use super::*;
160    use crate::graph::directed::*;
161    use quickcheck_macros::quickcheck;
162
163    #[quickcheck]
164    fn selected_subgraph(ops: Ops) {
165        let (add, remove): (Vec<_>, Vec<_>) = ops.iter().cloned().partition(|op| match op {
166            Op::AddVertex(_) => true,
167            Op::AddEdge(_) => true,
168            Op::RemoveVertex(_) => false,
169            Op::RemoveEdge(_) => false,
170        });
171        let add_ops = Ops { ops: add };
172        let remove_ops = Ops { ops: remove };
173        let base: MappedGraph<TreeBackedGraph> = (&add_ops).into();
174        let oracle = {
175            let mut oracle = base.clone();
176            oracle.apply(&remove_ops);
177            oracle
178        };
179        let trial = {
180            let mut trial = MappedGraph {
181                graph: {
182                    let mut g = SelectedSubgraph::new(&base.graph);
183                    for e in base.graph.iter_edges() {
184                        g.disclose_edge(e.id);
185                    }
186                    for v in base.graph.iter_vertices() {
187                        g.disclose_vertex(v);
188                    }
189                    g
190                },
191                vmap: base.vmap.clone(),
192                emap: base.emap.clone(),
193            };
194            for op in remove_ops.iter() {
195                match op {
196                    Op::RemoveVertex(vid) => {
197                        if let Some(my_vid) = trial.vmap.get_by_right(vid) {
198                            for e in trial.graph.remove_vertex(my_vid) {
199                                trial.emap.remove_by_left(&e.id);
200                            }
201                        }
202                    }
203                    Op::RemoveEdge(eid) => {
204                        if let Some(my_eid) = trial.emap.get_by_right(eid) {
205                            trial.graph.remove_edge(my_eid);
206                        }
207                    }
208                    _ => unreachable!(),
209                }
210            }
211            trial
212        };
213        assert_eq!(oracle, trial);
214    }
215}
algograph/graph/selected_subgraph.rs

algograph/graph/
selected_subgraph.rs
