graphbench/
iterators.rs

1use fxhash::{FxHashMap, FxHashSet};
2
3use crate::graph::*;
4use crate::reachgraph::{ReachGraph, Reachables};
5use std::hash::Hash;
6
7use crate::editgraph::EditGraph;
8
9pub type VertexIterator<'a> = std::collections::hash_map::Keys<'a, Vertex, FxHashSet<Vertex>>;
10pub type NVertexIterator<'a> = std::collections::hash_set::Iter<'a, Vertex>;
11
12use crate::dtfgraph::{DTFNode, DTFGraph};
13
14pub type InArcIterator<'a> = std::collections::hash_set::Iter<'a, Vertex>;
15pub type DTFVertexIterator<'a> = std::collections::hash_map::Keys<'a, Vertex, DTFNode>;
16
17/// Neighbourhood iterators for graphs. At each step, the iterator
18/// returns a pair $(v,N(v))$.
19pub struct NeighIterator<'a, G> where G: Graph  {
20    graph: &'a G,
21    v_it: Box<dyn Iterator<Item=&'a Vertex> + 'a>
22}
23
24impl<'a, G> NeighIterator<'a, G> where G: Graph  {
25    pub fn new(graph: &'a G) -> NeighIterator<'a, G> {
26        NeighIterator { graph, v_it: graph.vertices() }
27    }
28}
29
30impl<'a, G> Iterator for NeighIterator<'a, G> where G: Graph {
31    type Item = (Vertex, Box<dyn Iterator<Item=&'a Vertex> + 'a>);
32
33    fn next(&mut self) -> Option<Self::Item> {
34        let v = *self.v_it.next()?;
35        let N = self.graph.neighbours(&v);
36
37        Some((v, N))
38    }
39}
40
41/// Neighbourhood iterators for digraphs which eithe returns all in- or all 
42/// out-neighbourhoods. At each step, the iterator returns a pair $(v,N^-(v))$ when in
43/// in-neighbourhood mode and $(v,N^+(V))$ when in out-neighbourhood mode.
44pub struct DiNeighIterator<'a, G> where G: Graph {
45    graph: &'a G,
46    v_it: Box<dyn Iterator<Item=&'a Vertex> + 'a>,
47    mode: DiNeighIteratorMode
48}
49
50enum DiNeighIteratorMode {In, Out}
51
52impl<'a, D: Digraph> DiNeighIterator<'a, D> {
53    pub fn new_in(graph: &'a D) -> DiNeighIterator<'a, D> {
54        DiNeighIterator { graph, mode: DiNeighIteratorMode::In, v_it: graph.vertices() }
55    }
56
57    pub fn new_out(graph: &'a D) -> DiNeighIterator<'a, D> {
58        DiNeighIterator { graph, mode: DiNeighIteratorMode::Out, v_it: graph.vertices() }
59    }
60}
61
62impl<'a, D> Iterator for DiNeighIterator<'a, D> where D: Digraph {
63    type Item = (Vertex, Box<dyn Iterator<Item=&'a Vertex> + 'a>);
64
65    fn next(&mut self) -> Option<Self::Item> {
66        let v = *self.v_it.next()?;
67        match &self.mode {
68            DiNeighIteratorMode::In =>  {let N = self.graph.in_neighbours(&v);
69                    Some((v, N))},
70            DiNeighIteratorMode::Out => {let N = self.graph.out_neighbours(&v);
71                    Some((v, N))}
72        }
73    }
74}
75
76/// Allows construction of a [NeighIterator].
77/// 
78/// Has a default implementation for [Graph].
79pub trait NeighIterable<G> where G: Graph {
80    /// Returns a [NeighIterator] for the graph.
81    fn neighbourhoods(&self) -> NeighIterator<G>;
82}
83
84impl<G> NeighIterable<G> for G where G: Graph {
85    fn neighbourhoods(&self) -> NeighIterator<G> {
86        NeighIterator::<G>::new(self)
87    }
88}
89
90
91/// Allows construction of a [DiNeighIterator].
92/// 
93/// Has a default implementation for [Digraph].
94pub trait DiNeighIterable<D> where D: Digraph {
95    /// Returns a [DiNeighIterator] over all in-neighbourhoods of this graph.
96    fn in_neighbourhoods(&self) -> DiNeighIterator<D>;
97    
98    /// Returns a [DiNeighIterator] over all out-neighbourhoods of this graph.
99    fn out_neighbourhoods(&self) -> DiNeighIterator<D>;
100}
101
102impl<D> DiNeighIterable<D> for D where D: Digraph {
103    fn in_neighbourhoods(&self) -> DiNeighIterator<D> {
104        DiNeighIterator::<D>::new_in(self)
105    }
106
107    fn out_neighbourhoods(&self) -> DiNeighIterator<D> {
108        DiNeighIterator::<D>::new_out(self)
109    }
110}
111
112/// Edge iterator for graphs. Each edge is returned with the smaller
113/// vertex first, so the edge $\\{15,3\\}$ would be returned as $(3,15)$.
114/// 
115/// The associated trait EdgeIterable is implemented for generic graphs
116/// to provide the method `edges(...)` to create an `EdgeIterator`.
117pub struct EdgeIterator<'a, G> where G: Graph {
118    N_it: NeighIterator<'a, G>,
119    curr_v: Option<Vertex>,
120    curr_it: Option<Box<dyn Iterator<Item=&'a Vertex> + 'a>>,
121}
122
123impl<'a, G> EdgeIterator<'a, G> where G: Graph {
124    pub fn new(graph: &'a G) -> EdgeIterator<'a, G> {
125        let mut res = EdgeIterator {
126            N_it: graph.neighbourhoods(),
127            curr_v: None,
128            curr_it: None,
129        };
130        res.advance();
131        res
132    }
133
134    fn advance(&mut self) {
135        if let Some((v, it)) = self.N_it.next() {
136            self.curr_v = Some(v);
137            self.curr_it = Some(it);
138        } else {
139            self.curr_it = None;
140        }
141    }
142}
143
144impl<'a, G> Iterator for EdgeIterator<'a, G> where G: Graph {
145    type Item = (Vertex, Vertex);
146
147    fn next(&mut self) -> Option<Self::Item> {
148        while self.curr_it.is_some() {
149            let uu = {
150                let uu = self.curr_it.as_mut().unwrap().next();
151                if uu.is_none() {
152                    self.advance();
153                    continue;
154                }
155                uu
156            };
157
158            // Tie-breaking so we only return every edge once
159            let u = *uu.unwrap();
160            let v = self.curr_v.as_ref().unwrap();
161            if v > &u {
162                continue;
163            }
164            return Some((*v, u));
165        }
166
167        None
168    }
169}
170
171/// Allows construction of [EdgeIterator].
172/// 
173/// This trait has a default implementation for [Graph].
174pub trait EdgeIterable<G> where G: Graph {
175    /// Returns an [EdgeIterator] over the edges of this graph.
176    fn edges(&self) -> EdgeIterator<G>;
177}
178
179impl<G> EdgeIterable<G> for G where G: Graph {
180    fn edges(&self) -> EdgeIterator<G> {
181        EdgeIterator::<G>::new(self)
182    }
183}
184
185/// An iterator that returns all vertices and edges of the graph.
186/// 
187/// This trait has a default implementation for [Graph].
188pub struct MixedIterator<'a, G> where G: Graph {
189    N_it: NeighIterator<'a, G>,
190    returned_v: bool,
191    curr_v: Option<Vertex>,
192    curr_it: Option<Box<dyn Iterator<Item=&'a Vertex> + 'a>>,
193}
194
195impl<'a, G> MixedIterator<'a, G> where G: Graph {
196    pub fn new(graph: &'a G) -> MixedIterator<'a, G> {
197        let mut res = MixedIterator {
198            N_it: graph.neighbourhoods(),
199            returned_v: false,
200            curr_v: None,
201            curr_it: None,
202        };
203        res.advance();
204        res
205    }
206
207    fn advance(&mut self) {
208        self.returned_v = false;        
209        if let Some((v, it)) = self.N_it.next() {
210            self.curr_v = Some(v);
211            self.curr_it = Some(it);
212        } else {
213            self.curr_v = None;
214            self.curr_it = None;
215        }
216    }
217}
218
219impl<'a, G> Iterator for MixedIterator<'a, G> where G: Graph {
220    type Item = VertexOrEdge;
221
222    fn next(&mut self) -> Option<Self::Item> {
223        while let (Some(v), Some(it)) = (self.curr_v, &mut self.curr_it) {
224            // Return vertex
225            if !self.returned_v {
226                self.returned_v = true;
227                return Some(VertexOrEdge::V(v));
228            }
229
230            // Otherwise return edge
231            for u in it.by_ref() {
232                // Tie-break so we do not return edges multiple times
233                if v < *u {
234                    return Some(VertexOrEdge::E( (v,*u) ));
235                }
236            }
237
238            self.advance();
239        } 
240
241        None
242    }
243}
244
245pub trait MixedIterable<G> where G: Graph {
246    /// Returns an [EdgeIterator] over the edges of this graph.
247    fn vertices_and_edges(&self) -> MixedIterator<G>;
248}
249
250impl<G> MixedIterable<G> for G where G: Graph {
251    fn vertices_and_edges(&self) -> MixedIterator<G> {
252        MixedIterator::<G>::new(self)
253    }
254}
255
256
257/// Similar to [EdgeIterator] but for arcs of digraphs.
258pub struct ArcIterator<'a, D> where D: Digraph {
259    N_it: DiNeighIterator<'a, D>,
260    curr_v: Option<Vertex>,
261    curr_it: Option<Box<dyn Iterator<Item=&'a Vertex> + 'a>>,
262}
263
264impl<'a, D> ArcIterator<'a, D> where D: Digraph{
265    pub fn new(graph: &'a D) -> ArcIterator<'a, D> {
266        let mut res = ArcIterator {
267            N_it: graph.in_neighbourhoods(),
268            curr_v: None,
269            curr_it: None,
270        };
271        res.advance();
272        res
273    }
274
275    fn advance(&mut self) {
276        if let Some((v, it)) = self.N_it.next() {
277            self.curr_v = Some(v);
278            self.curr_it = Some(it);
279        } else {
280            self.curr_it = None;
281        }
282    }
283}
284
285impl<'a, D> Iterator for ArcIterator<'a, D> where D: Digraph  {
286    type Item = (Vertex, Vertex);
287
288    fn next(&mut self) -> Option<Self::Item> {
289        while self.curr_it.is_some() {
290            let uu = {
291                let uu = self.curr_it.as_mut().unwrap().next();
292                if uu.is_none() {
293                    self.advance();
294                    continue;
295                }
296                uu
297            };
298
299            // Tie-breaking so we only return every edge once
300            let u = *uu.unwrap();
301            return Some((*self.curr_v.as_ref().unwrap(), u));
302        }
303
304        None
305    }
306}
307
308/// Allows construction of [ArcIterator].
309/// 
310/// This trait has a default implementation for [Digraph].
311pub trait ArcIterable<D> where D: Digraph {
312    /// Returns an [ArcIterator] over the arcs of this digraph.
313    fn arcs(&self) -> ArcIterator<D>;
314}
315
316impl<D> ArcIterable<D> for D where D: Digraph {
317    fn arcs(&self) -> ArcIterator<D> {
318        ArcIterator::<D>::new(self)
319    }
320}
321
322/// Neighbourhood iterator for [DTFGraph]. At each step, the iterator returns
323/// a pair $(v,X)$ where $X$ is a certain subset of the in-neighbours of $v$.
324/// If the iterator is in 'all depths' mode, $X$ is simply $v$'s in-neighbourhood.
325/// If the iterator operates on one specific depth $d$, then $X$ contains all
326/// vertices that can reach $v$ via an arc of weight $d$.
327pub struct DTFNIterator<'a> {
328    G: &'a DTFGraph,
329    v_it: Box<dyn Iterator<Item=&'a Vertex> + 'a>,
330    depth: Option<usize>,
331}
332
333impl<'a> DTFNIterator<'a> {
334    /// Constructs a [DTFNIterator] in all-depths mode.
335    pub fn all_depths(G: &'a DTFGraph) -> DTFNIterator<'a> {
336        DTFNIterator {
337            G,
338            v_it: G.vertices(),
339            depth: None,
340        }
341    }
342
343    /// Constructs a [DTFNIterator] which only returns in-neighbours at `depth`.
344    pub fn fixed_depth(G: &'a DTFGraph, depth: usize) -> DTFNIterator<'a> {
345        DTFNIterator {
346            G,
347            v_it: G.vertices(),
348            depth: Some(depth),
349        }
350    }
351}
352
353impl<'a> Iterator for DTFNIterator<'a> {
354    type Item = (Vertex, Box<dyn Iterator<Item=&'a Vertex> + 'a>);
355
356    fn next(&mut self) -> Option<Self::Item> {
357        if let Some(depth) = self.depth {
358            let v = *self.v_it.next()?;
359            let N = self.G.in_neighbours_at(&v, depth);
360
361            Some((v, N))
362        } else {
363            let v = *self.v_it.next()?;
364            let N = self.G.in_neighbours(&v);
365
366            Some((v, N))
367        }
368    }
369}
370
371/// Arc iterator for [DTFGraph]. If the iterator is in 'all depths' mode it 
372/// iterates over all arcs of the augmentation. If the iterator operates on one 
373/// specific depth $d$ then it only return arcs with weight (depth) $d$.
374pub struct DTFArcIterator<'a> {
375    N_it: DTFNIterator<'a>,
376    curr_v: Vertex,
377    curr_it: Option<Box<dyn Iterator<Item=&'a Vertex> + 'a>>,
378}
379
380impl<'a> DTFArcIterator<'a> {
381    pub fn all_depths(G: &'a DTFGraph) -> DTFArcIterator {
382        let mut res = DTFArcIterator {
383            N_it: G.in_neighbourhoods_iter(),
384            curr_v: std::u32::MAX,
385            curr_it: None,
386        };
387        res.advance();
388        res
389    }
390
391    pub fn fixed_depth(G: &'a DTFGraph, depth:usize) -> DTFArcIterator {
392        let mut res = DTFArcIterator {
393            N_it: G.in_neighbourhoods_iter_at(depth),
394            curr_v: std::u32::MAX,
395            curr_it: None,
396        };
397        res.advance();
398        res
399    }
400
401    fn advance(&mut self) {
402        if let Some((v, it)) = self.N_it.next() {
403            self.curr_v = v;
404            self.curr_it = Some(it);
405        } else {
406            self.curr_it = None;
407        }
408    }
409}
410
411impl<'a> Iterator for DTFArcIterator<'a> {
412    type Item = Arc;
413
414    fn next(&mut self) -> Option<Self::Item> {
415        while self.curr_it.is_some() {
416            let uu = self.curr_it.as_mut().unwrap().next();
417            if uu.is_none() {
418                self.advance();
419                continue;
420            }
421
422            // Tie-breaking so we only return every edge once
423            let u = *uu.unwrap();
424            if self.curr_v > u {
425                continue;
426            }
427            return Some((self.curr_v, u));
428        }
429
430        None
431    }
432}
433
434
435/// Left-neighbourhood iterators for linear graphs. At each step, the iterator
436/// returns a pair $(v,L(v))$. 
437pub struct LeftNeighIterator<'a, L> where L: LinearGraph  {
438    graph: &'a L,
439    v_it: Box<dyn Iterator<Item=&'a Vertex> + 'a>
440}
441
442impl<'a, L> LeftNeighIterator<'a, L> where L: LinearGraph  {
443    pub fn new(graph: &'a L) -> LeftNeighIterator<'a, L> {
444        LeftNeighIterator { graph, v_it: graph.vertices() }
445    }
446}
447
448impl<'a, L> Iterator for LeftNeighIterator<'a, L> where L: LinearGraph  {
449    type Item = (Vertex, Vec<u32>);
450
451    fn next(&mut self) -> Option<Self::Item> {
452        let v = *self.v_it.next()?;
453        let N = self.graph.left_neighbours(&v);
454
455        Some((v, N))
456    }
457}
458
459/// Allows construction of a [LeftNeighIterator].
460/// 
461/// Has a default implementation for [LinearGraph].
462pub trait LeftNeighIterable<L> where L: LinearGraph {
463    /// Returns a [NeighIterator] for the graph.
464    fn left_neighbourhoods(&self) -> LeftNeighIterator<L>;
465}
466
467impl<L> LeftNeighIterable<L> for L where L: LinearGraph {
468    fn left_neighbourhoods(&self) -> LeftNeighIterator<L> {
469        LeftNeighIterator::<L>::new(self)
470    }
471}
472
473
474//  #######                            
475//     #    ######  ####  #####  ####  
476//     #    #      #        #   #      
477//     #    #####   ####    #    ####  
478//     #    #           #   #        # 
479//     #    #      #    #   #   #    # 
480//     #    ######  ####    #    ####  
481
482#[cfg(test)]
483mod test {
484    use super::*;
485    use crate::graph::*;
486    use crate::editgraph::*;
487    use crate::ordgraph::*;
488
489    #[test] 
490    fn edge_iterator() {
491        let G = EditGraph::clique(4);
492        let edges:EdgeSet = G.edges().collect();
493        let test:EdgeSet = vec![(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)].into_iter().collect();
494        assert_eq!(edges,test);
495    }
496
497    #[test] 
498    fn N_iterator() {
499        let G = EditGraph::biclique(2,2);
500        for (v,N) in G.neighbourhoods() {
501            let N:VertexSet = N.cloned().collect();
502            assert_eq!(G.degree(&v) as usize, N.len());
503            for u in N {
504                assert!(G.adjacent(&u, &v));
505            }
506        }
507    }    
508
509    #[test] 
510    fn mixed_iterator() {
511        let G = EditGraph::biclique(4,5);
512        let members:MixedSet = G.vertices_and_edges().collect();
513        let vertices:VertexSet = members.iter()
514                        .cloned()
515                        .filter_map(VertexOrEdge::as_vertex)
516                        .collect();
517        let edges:EdgeSet = members.iter()
518                        .filter_map(|m| if let VertexOrEdge::E((u,v)) = m { Some((*u,*v)) } else { None })
519                        .collect();      
520        assert_eq!(vertices, VertexSet::from_iter(G.vertices().cloned())); 
521        assert_eq!(edges, EdgeSet::from_iter(G.edges().map(|e| e )));                  
522    }        
523    
524    #[test]
525    fn wreach_iterator() {
526        const R:usize = 5;
527        let G = EditGraph::from_txt("./resources/karate.txt").unwrap();
528        let O = OrdGraph::by_degeneracy(&G);
529        let W = O.to_wreach_graph::<R>();
530        
531        for (v,reachables) in W.iter() {
532            assert_eq!(v, reachables.from);
533            assert_eq!(reachables, W.reachables(&v));
534        }
535        
536    }
537}
graphbench/iterators.rs

graphbench/
iterators.rs
