traitgraph/implementation/subgraphs/
bit_vector_subgraph.rs

1use crate::implementation::subgraphs::filter_iterators::{
2    FilterEdgeIndexIterator, FilterNeighborIterator,
3};
4use crate::index::GraphIndex;
5use crate::interface::subgraph::{EmptyConstructibleSubgraph, MutableSubgraph, SubgraphBase};
6use crate::interface::{Edge, GraphBase, ImmutableGraphContainer, NavigableGraph};
7use bitvec::bitvec;
8use bitvec::vec::BitVec;
9
10/// A subgraph that stores the presence or absence of a node or edge using bitvectors.
11pub struct BitVectorSubgraph<'a, Graph> {
12    parent_graph: &'a Graph,
13    present_nodes: BitVec,
14    present_edges: BitVec,
15}
16
17impl<'a, Graph: SubgraphBase> BitVectorSubgraph<'a, Graph>
18where
19    Graph::RootGraph: ImmutableGraphContainer,
20{
21    /// Constructs a new instance decorating the given graph.
22    /// The subgraph is initialised empty.
23    pub fn new_empty(parent_graph: &'a Graph) -> Self {
24        Self {
25            parent_graph,
26            present_nodes: bitvec![0; parent_graph.root().node_count()],
27            present_edges: bitvec![0; parent_graph.root().edge_count()],
28        }
29    }
30}
31
32impl<Graph: GraphBase> GraphBase for BitVectorSubgraph<'_, Graph> {
33    type NodeData = Graph::NodeData;
34    type EdgeData = Graph::EdgeData;
35    type OptionalNodeIndex = Graph::OptionalNodeIndex;
36    type OptionalEdgeIndex = Graph::OptionalEdgeIndex;
37    type NodeIndex = Graph::NodeIndex;
38    type EdgeIndex = Graph::EdgeIndex;
39}
40
41impl<Graph: ImmutableGraphContainer> ImmutableGraphContainer for BitVectorSubgraph<'_, Graph> {
42    type NodeIndices<'a>
43        = std::iter::Filter<Graph::NodeIndices<'a>, Box<dyn 'a + Fn(&Graph::NodeIndex) -> bool>>
44    where
45        Self: 'a,
46        Graph: 'a;
47    type EdgeIndices<'a>
48        = std::iter::Filter<Graph::EdgeIndices<'a>, Box<dyn 'a + Fn(&Graph::EdgeIndex) -> bool>>
49    where
50        Self: 'a,
51        Graph: 'a;
52
53    fn node_indices(&self) -> Self::NodeIndices<'_> {
54        self.parent_graph
55            .node_indices()
56            .filter(Box::new(|&node_index| self.contains_node_index(node_index)))
57    }
58
59    fn edge_indices(&self) -> Self::EdgeIndices<'_> {
60        self.parent_graph
61            .edge_indices()
62            .filter(Box::new(|&edge_index| self.contains_edge_index(edge_index)))
63    }
64    type NodeIndicesCopied = std::vec::IntoIter<Graph::NodeIndex>;
65    type EdgeIndicesCopied = std::vec::IntoIter<Graph::EdgeIndex>;
66    fn node_indices_copied(&self) -> Self::NodeIndicesCopied {
67        self.node_indices().collect::<Vec<_>>().into_iter()
68    }
69
70    fn edge_indices_copied(&self) -> Self::EdgeIndicesCopied {
71        self.edge_indices().collect::<Vec<_>>().into_iter()
72    }
73
74    fn contains_node_index(&self, node_id: Self::NodeIndex) -> bool {
75        debug_assert!(
76            self.parent_graph.contains_node_index(node_id)
77                || !self.present_nodes[node_id.as_usize()]
78        );
79        self.present_nodes[node_id.as_usize()]
80    }
81
82    fn contains_edge_index(&self, edge_id: Self::EdgeIndex) -> bool {
83        debug_assert!(
84            self.parent_graph.contains_edge_index(edge_id)
85                || !self.present_edges[edge_id.as_usize()]
86        );
87        self.present_edges[edge_id.as_usize()]
88    }
89
90    fn node_count(&self) -> usize {
91        self.node_indices().count()
92    }
93
94    fn edge_count(&self) -> usize {
95        self.edge_indices().count()
96    }
97
98    fn node_data(&self, node_id: Self::NodeIndex) -> &Self::NodeData {
99        debug_assert!(self.contains_node_index(node_id));
100        self.parent_graph.node_data(node_id)
101    }
102
103    fn edge_data(&self, edge_id: Self::EdgeIndex) -> &Self::EdgeData {
104        debug_assert!(self.contains_edge_index(edge_id));
105        self.parent_graph.edge_data(edge_id)
106    }
107
108    fn edge_endpoints(&self, edge_id: Self::EdgeIndex) -> Edge<Self::NodeIndex> {
109        debug_assert!(self.contains_edge_index(edge_id));
110        self.parent_graph.edge_endpoints(edge_id)
111    }
112}
113
114impl<Graph: NavigableGraph> NavigableGraph for BitVectorSubgraph<'_, Graph> {
115    type OutNeighbors<'a>
116        = FilterNeighborIterator<'a, <Graph as NavigableGraph>::OutNeighbors<'a>, Self>
117    where
118        Self: 'a;
119    type InNeighbors<'a>
120        = FilterNeighborIterator<'a, <Graph as NavigableGraph>::InNeighbors<'a>, Self>
121    where
122        Self: 'a;
123    type EdgesBetween<'a>
124        = FilterEdgeIndexIterator<'a, <Graph as NavigableGraph>::EdgesBetween<'a>, Self>
125    where
126        Self: 'a;
127
128    fn out_neighbors(&self, node_id: Self::NodeIndex) -> Self::OutNeighbors<'_> {
129        FilterNeighborIterator::new(self.parent_graph.out_neighbors(node_id), self)
130    }
131
132    fn in_neighbors(&self, node_id: Self::NodeIndex) -> Self::InNeighbors<'_> {
133        FilterNeighborIterator::new(self.parent_graph.in_neighbors(node_id), self)
134    }
135
136    fn edges_between(
137        &self,
138        from_node_id: Self::NodeIndex,
139        to_node_id: Self::NodeIndex,
140    ) -> Self::EdgesBetween<'_> {
141        FilterEdgeIndexIterator::new(
142            self.parent_graph.edges_between(from_node_id, to_node_id),
143            self,
144        )
145    }
146}
147
148impl<Graph: SubgraphBase> SubgraphBase for BitVectorSubgraph<'_, Graph> {
149    type RootGraph = Graph::RootGraph;
150
151    fn root(&self) -> &Self::RootGraph {
152        self.parent_graph.root()
153    }
154}
155
156impl<Graph: ImmutableGraphContainer + SubgraphBase> MutableSubgraph for BitVectorSubgraph<'_, Graph>
157where
158    Self: GraphBase<
159        NodeIndex = <Graph as GraphBase>::NodeIndex,
160        EdgeIndex = <Graph as GraphBase>::EdgeIndex,
161    >,
162{
163    fn clear(&mut self) {
164        self.present_nodes.fill(false);
165        self.present_edges.fill(false);
166    }
167
168    fn fill(&mut self) {
169        self.parent_graph
170            .node_indices()
171            .for_each(|node_index| self.enable_node(node_index));
172        self.parent_graph
173            .edge_indices()
174            .for_each(|edge_index| self.enable_edge(edge_index));
175    }
176
177    fn enable_node(
178        &mut self,
179        node_index: <<Self as SubgraphBase>::RootGraph as GraphBase>::NodeIndex,
180    ) {
181        debug_assert!(self.parent_graph.contains_node_index(node_index));
182        self.present_nodes.set(node_index.as_usize(), true);
183    }
184
185    fn enable_edge(
186        &mut self,
187        edge_index: <<Self as SubgraphBase>::RootGraph as GraphBase>::EdgeIndex,
188    ) {
189        debug_assert!(self.parent_graph.contains_edge_index(edge_index));
190        self.present_edges.set(edge_index.as_usize(), true);
191    }
192
193    fn disable_node(
194        &mut self,
195        node_index: <<Self as SubgraphBase>::RootGraph as GraphBase>::NodeIndex,
196    ) {
197        debug_assert!(self.parent_graph.contains_node_index(node_index));
198        self.present_nodes.set(node_index.as_usize(), false);
199    }
200
201    fn disable_edge(
202        &mut self,
203        edge_index: <<Self as SubgraphBase>::RootGraph as GraphBase>::EdgeIndex,
204    ) {
205        debug_assert!(self.parent_graph.contains_edge_index(edge_index));
206        self.present_edges.set(edge_index.as_usize(), false);
207    }
208}
209
210impl<'a, Graph: ImmutableGraphContainer + SubgraphBase> EmptyConstructibleSubgraph<'a>
211    for BitVectorSubgraph<'a, Graph>
212where
213    Self: SubgraphBase<RootGraph = Graph>,
214{
215    fn new_empty(root_graph: &'a <Self as SubgraphBase>::RootGraph) -> Self {
216        Self {
217            parent_graph: root_graph,
218            present_nodes: bitvec![0; root_graph.node_count()],
219            present_edges: bitvec![0; root_graph.edge_count()],
220        }
221    }
222}
223
224#[cfg(test)]
225mod tests {
226    use crate::implementation::petgraph_impl::PetGraph;
227    use crate::implementation::subgraphs::bit_vector_subgraph::BitVectorSubgraph;
228    use crate::interface::subgraph::MutableSubgraph;
229    use crate::interface::{ImmutableGraphContainer, MutableGraphContainer};
230    use bitvec::bitvec;
231
232    #[test]
233    fn test_bitvec_construction() {
234        let bv = bitvec![0; 12];
235        assert_eq!(bv.len(), 12);
236        assert_eq!(bv.iter_ones().sum::<usize>(), 0);
237        assert_eq!(bv.iter_zeros().sum::<usize>(), (0..12).sum());
238    }
239
240    #[test]
241    fn test_clear() {
242        let mut graph = PetGraph::new();
243        let n: Vec<_> = (0..10).map(|i| graph.add_node(i)).collect();
244        let e: Vec<_> = (0..9)
245            .map(|i| graph.add_edge(n[i], n[i + 1], i + 100))
246            .collect();
247        let mut subgraph = BitVectorSubgraph::new_empty(&graph);
248        assert!(subgraph.node_indices().next().is_none());
249        assert!(subgraph.edge_indices().next().is_none());
250
251        subgraph.enable_node(n[2]);
252        subgraph.enable_node(n[3]);
253        subgraph.enable_edge(e[2]);
254        assert_eq!(
255            subgraph.node_indices().collect::<Vec<_>>(),
256            n[2..4].to_vec()
257        );
258        assert_eq!(
259            subgraph.edge_indices().collect::<Vec<_>>(),
260            e[2..3].to_vec()
261        );
262
263        subgraph.clear();
264        assert!(subgraph.node_indices().next().is_none());
265        assert!(subgraph.edge_indices().next().is_none());
266    }
267}
traitgraph/implementation/subgraphs/bit_vector_subgraph.rs

traitgraph/implementation/subgraphs/
bit_vector_subgraph.rs
