petgraph/visit/
filter.rs

1
2use prelude::*;
3
4use fixedbitset::FixedBitSet;
5use std::collections::HashSet;
6use std::marker::PhantomData;
7
8use visit::{
9    GraphBase,
10    GraphProp,
11    IntoEdgeReferences,
12    IntoEdges,
13    IntoNeighbors,
14    IntoNeighborsDirected,
15    IntoNodeIdentifiers,
16    IntoNodeReferences,
17    NodeIndexable,
18    NodeRef,
19    VisitMap,
20    Visitable,
21};
22use visit::{Data, NodeCompactIndexable, NodeCount};
23use data::{DataMap};
24
25/// A graph filter for nodes.
26pub trait FilterNode<N>
27{
28    /// Return true to have the node be part of the graph
29    fn include_node(&self, node: N) -> bool;
30}
31
32impl<F, N> FilterNode<N> for F
33    where F: Fn(N) -> bool,
34{
35    fn include_node(&self, n: N) -> bool {
36        (*self)(n)
37    }
38}
39
40/// This filter includes the nodes that are contained in the set.
41impl<N> FilterNode<N> for FixedBitSet
42    where FixedBitSet: VisitMap<N>,
43{
44    fn include_node(&self, n: N) -> bool {
45        self.is_visited(&n)
46    }
47}
48
49/// This filter includes the nodes that are contained in the set.
50impl<N, S> FilterNode<N> for HashSet<N, S>
51    where HashSet<N, S>: VisitMap<N>,
52{
53    fn include_node(&self, n: N) -> bool {
54        self.is_visited(&n)
55    }
56}
57
58/// A node-filtering graph adaptor.
59#[derive(Copy, Clone, Debug)]
60pub struct NodeFiltered<G, F>(pub G, pub F);
61
62impl<F, G> NodeFiltered<G, F>
63    where G: GraphBase,
64          F: Fn(G::NodeId) -> bool,
65{
66    /// Create an `NodeFiltered` adaptor from the closure `filter`.
67    pub fn from_fn(graph: G, filter: F) -> Self {
68        NodeFiltered(graph, filter)
69    }
70}
71
72impl<G, F> GraphBase for NodeFiltered<G, F> where G: GraphBase {
73    type NodeId = G::NodeId;
74    type EdgeId = G::EdgeId;
75}
76
77impl<'a, G, F> IntoNeighbors for &'a NodeFiltered<G, F>
78    where G: IntoNeighbors,
79          F: FilterNode<G::NodeId>,
80{
81    type Neighbors = NodeFilteredNeighbors<'a, G::Neighbors, F>;
82    fn neighbors(self, n: G::NodeId) -> Self::Neighbors {
83        NodeFilteredNeighbors {
84            include_source: self.1.include_node(n),
85            iter: self.0.neighbors(n),
86            f: &self.1,
87        }
88    }
89}
90
91/// A filtered neighbors iterator.
92pub struct NodeFilteredNeighbors<'a, I, F: 'a>
93{
94    include_source: bool,
95    iter: I,
96    f: &'a F,
97}
98
99impl<'a, I, F> Iterator for NodeFilteredNeighbors<'a, I, F>
100    where I: Iterator,
101          I::Item: Copy,
102          F: FilterNode<I::Item>,
103{
104    type Item = I::Item;
105    fn next(&mut self) -> Option<Self::Item> {
106        let f = self.f;
107        if !self.include_source {
108            None
109        } else {
110            self.iter.find(move |&target| f.include_node(target))
111        }
112    }
113}
114
115impl<'a, G, F> IntoNeighborsDirected for &'a NodeFiltered<G, F>
116    where G: IntoNeighborsDirected,
117          F: FilterNode<G::NodeId>,
118{
119    type NeighborsDirected = NodeFilteredNeighbors<'a, G::NeighborsDirected, F>;
120    fn neighbors_directed(self, n: G::NodeId, dir: Direction)
121        -> Self::NeighborsDirected {
122        NodeFilteredNeighbors {
123            include_source: self.1.include_node(n),
124            iter: self.0.neighbors_directed(n, dir),
125            f: &self.1,
126        }
127    }
128}
129
130impl<'a, G, F> IntoNodeIdentifiers for &'a NodeFiltered<G, F>
131    where G: IntoNodeIdentifiers,
132          F: FilterNode<G::NodeId>,
133{
134    type NodeIdentifiers = NodeFilteredNeighbors<'a, G::NodeIdentifiers, F>;
135    fn node_identifiers(self) -> Self::NodeIdentifiers {
136        NodeFilteredNeighbors {
137            include_source: true,
138            iter: self.0.node_identifiers(),
139            f: &self.1,
140        }
141    }
142}
143
144impl<'a, G, F> IntoNodeReferences for &'a NodeFiltered<G, F>
145    where G: IntoNodeReferences,
146          F: FilterNode<G::NodeId>,
147{
148    type NodeRef = G::NodeRef;
149    type NodeReferences = NodeFilteredNodes<'a, G::NodeReferences, F>;
150    fn node_references(self) -> Self::NodeReferences {
151        NodeFilteredNodes {
152            include_source: true,
153            iter: self.0.node_references(),
154            f: &self.1,
155        }
156    }
157}
158
159/// A filtered node references iterator.
160pub struct NodeFilteredNodes<'a, I, F: 'a>
161{
162    include_source: bool,
163    iter: I,
164    f: &'a F,
165}
166
167impl<'a, I, F> Iterator for NodeFilteredNodes<'a, I, F>
168    where I: Iterator,
169          I::Item: Copy + NodeRef,
170          F: FilterNode<<I::Item as NodeRef>::NodeId>,
171{
172    type Item = I::Item;
173    fn next(&mut self) -> Option<Self::Item> {
174        let f = self.f;
175        if !self.include_source {
176            None
177        } else {
178            self.iter.find(move |&target| f.include_node(target.id()))
179        }
180    }
181}
182
183impl<'a, G, F> IntoEdgeReferences for &'a NodeFiltered<G, F>
184    where G: IntoEdgeReferences,
185          F: FilterNode<G::NodeId>,
186{
187    type EdgeRef = G::EdgeRef;
188    type EdgeReferences = NodeFilteredEdgeReferences<'a, G, G::EdgeReferences, F>;
189    fn edge_references(self) -> Self::EdgeReferences {
190        NodeFilteredEdgeReferences {
191            graph: PhantomData,
192            iter: self.0.edge_references(),
193            f: &self.1,
194        }
195    }
196}
197
198/// A filtered edges iterator.
199pub struct NodeFilteredEdgeReferences<'a, G, I, F: 'a>
200{
201    graph: PhantomData<G>,
202    iter: I,
203    f: &'a F,
204}
205
206impl<'a, G, I, F> Iterator for NodeFilteredEdgeReferences<'a, G, I, F>
207    where F: FilterNode<G::NodeId>,
208          G: IntoEdgeReferences,
209          I: Iterator<Item=G::EdgeRef>,
210{
211    type Item = I::Item;
212    fn next(&mut self) -> Option<Self::Item> {
213        let f = self.f;
214        self.iter.find(move |&edge| f.include_node(edge.source()) &&
215                                    f.include_node(edge.target()))
216    }
217}
218
219impl<'a, G, F> IntoEdges for &'a NodeFiltered<G, F>
220    where G: IntoEdges,
221          F: FilterNode<G::NodeId>,
222{
223    type Edges = NodeFilteredEdges<'a, G, G::Edges, F>;
224    fn edges(self, a: G::NodeId) -> Self::Edges {
225        NodeFilteredEdges {
226            graph: PhantomData,
227            include_source: self.1.include_node(a),
228            iter: self.0.edges(a),
229            f: &self.1,
230        }
231    }
232}
233
234
235/// A filtered edges iterator.
236pub struct NodeFilteredEdges<'a, G, I, F: 'a>
237{
238    graph: PhantomData<G>,
239    include_source: bool,
240    iter: I,
241    f: &'a F,
242}
243
244
245impl<'a, G, I, F> Iterator for NodeFilteredEdges<'a, G, I, F>
246    where F: FilterNode<G::NodeId>,
247          G: IntoEdges,
248          I: Iterator<Item=G::EdgeRef>,
249{
250    type Item = I::Item;
251    fn next(&mut self) -> Option<Self::Item> {
252        if !self.include_source {
253            None
254        } else {
255            let f = self.f;
256            self.iter.find(move |&edge| f.include_node(edge.target()))
257        }
258    }
259}
260
261impl<G, F> DataMap for NodeFiltered<G, F>
262    where G: DataMap,
263          F: FilterNode<G::NodeId>,
264{
265    fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
266        if self.1.include_node(id) {
267            self.0.node_weight(id)
268        } else {
269            None
270        }
271    }
272
273    fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
274        self.0.edge_weight(id)
275    }
276}
277
278macro_rules! access0 {
279    ($e:expr) => ($e.0)
280}
281
282Data!{delegate_impl [[G, F], G, NodeFiltered<G, F>, access0]}
283NodeIndexable!{delegate_impl [[G, F], G, NodeFiltered<G, F>, access0]}
284GraphProp!{delegate_impl [[G, F], G, NodeFiltered<G, F>, access0]}
285Visitable!{delegate_impl [[G, F], G, NodeFiltered<G, F>, access0]}
286
287/// A graph filter for edges
288pub trait FilterEdge<Edge> {
289    /// Return true to have the edge be part of the graph
290    fn include_edge(&self, edge: Edge) -> bool;
291}
292
293impl<F, N> FilterEdge<N> for F
294    where F: Fn(N) -> bool,
295{
296    fn include_edge(&self, n: N) -> bool {
297        (*self)(n)
298    }
299}
300
301/// An edge-filtering graph adaptor.
302///
303/// The adaptor may filter out edges. The filter implements the trait
304/// `FilterEdge`. Closures of type `Fn(G::EdgeRef) -> bool` already
305/// implement this trait.
306///
307/// The filter may use edge source, target, id, and weight to select whether to
308/// include the edge or not.
309#[derive(Copy, Clone, Debug)]
310pub struct EdgeFiltered<G, F>(pub G, pub F);
311
312impl<F, G> EdgeFiltered<G, F>
313    where G: IntoEdgeReferences,
314          F: Fn(G::EdgeRef) -> bool,
315{
316    /// Create an `EdgeFiltered` adaptor from the closure `filter`.
317    pub fn from_fn(graph: G, filter: F) -> Self {
318        EdgeFiltered(graph, filter)
319    }
320}
321
322impl<G, F> GraphBase for EdgeFiltered<G, F> where G: GraphBase {
323    type NodeId = G::NodeId;
324    type EdgeId = G::EdgeId;
325}
326
327impl<'a, G, F> IntoNeighbors for &'a EdgeFiltered<G, F>
328    where G: IntoEdges,
329          F: FilterEdge<G::EdgeRef>,
330{
331    type Neighbors = EdgeFilteredNeighbors<'a, G, F>;
332    fn neighbors(self, n: G::NodeId) -> Self::Neighbors {
333        EdgeFilteredNeighbors {
334            iter: self.0.edges(n),
335            f: &self.1,
336        }
337    }
338}
339
340/// A filtered neighbors iterator.
341pub struct EdgeFilteredNeighbors<'a, G, F: 'a>
342    where G: IntoEdges,
343{
344    iter: G::Edges,
345    f: &'a F,
346}
347
348impl<'a, G, F> Iterator for EdgeFilteredNeighbors<'a, G, F>
349    where F: FilterEdge<G::EdgeRef>,
350          G: IntoEdges,
351{
352    type Item = G::NodeId;
353    fn next(&mut self) -> Option<Self::Item> {
354        let f = self.f;
355        (&mut self.iter).filter_map(move |edge| {
356            if f.include_edge(edge) {
357                Some(edge.target())
358            } else { None }
359        }).next()
360    }
361}
362
363impl<'a, G, F> IntoEdgeReferences for &'a EdgeFiltered<G, F>
364    where G: IntoEdgeReferences,
365          F: FilterEdge<G::EdgeRef>,
366{
367    type EdgeRef = G::EdgeRef;
368    type EdgeReferences = EdgeFilteredEdges<'a, G, G::EdgeReferences, F>;
369    fn edge_references(self) -> Self::EdgeReferences {
370        EdgeFilteredEdges {
371            graph: PhantomData,
372            iter: self.0.edge_references(),
373            f: &self.1,
374        }
375    }
376}
377
378impl<'a, G, F> IntoEdges for &'a EdgeFiltered<G, F>
379    where G: IntoEdges,
380          F: FilterEdge<G::EdgeRef>,
381{
382    type Edges = EdgeFilteredEdges<'a, G, G::Edges, F>;
383    fn edges(self, n: G::NodeId) -> Self::Edges {
384        EdgeFilteredEdges {
385            graph: PhantomData,
386            iter: self.0.edges(n),
387            f: &self.1,
388        }
389    }
390}
391
392/// A filtered edges iterator.
393pub struct EdgeFilteredEdges<'a, G, I, F: 'a>
394{
395    graph: PhantomData<G>,
396    iter: I,
397    f: &'a F,
398}
399
400impl<'a, G, I, F> Iterator for EdgeFilteredEdges<'a, G, I, F>
401    where F: FilterEdge<G::EdgeRef>,
402          G: IntoEdgeReferences,
403          I: Iterator<Item=G::EdgeRef>,
404{
405    type Item = I::Item;
406    fn next(&mut self) -> Option<Self::Item> {
407        let f = self.f;
408        self.iter.find(move |&edge| f.include_edge(edge))
409    }
410}
411
412Data!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
413GraphProp!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
414IntoNodeIdentifiers!{delegate_impl [['a, G, F], G, &'a EdgeFiltered<G, F>, access0]}
415IntoNodeReferences!{delegate_impl [['a, G, F], G, &'a EdgeFiltered<G, F>, access0]}
416NodeCompactIndexable!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
417NodeCount!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
418NodeIndexable!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
419Visitable!{delegate_impl [[G, F], G, EdgeFiltered<G, F>, access0]}
petgraph/visit/filter.rs

petgraph/visit/
filter.rs
