differential_dataflow/algorithms/graphs/
bfs.rs

1//! Breadth-first distance labeling.
2
3use std::hash::Hash;
4
5use timely::dataflow::*;
6
7use crate::{Collection, ExchangeData};
8use crate::operators::*;
9use crate::lattice::Lattice;
10
11/// Returns pairs (node, dist) indicating distance of each node from a root.
12pub fn bfs<G, N>(edges: &Collection<G, (N,N)>, roots: &Collection<G, N>) -> Collection<G, (N,u32)>
13where
14    G: Scope<Timestamp: Lattice+Ord>,
15    N: ExchangeData+Hash,
16{
17    use crate::operators::arrange::arrangement::ArrangeByKey;
18    let edges = edges.arrange_by_key();
19    bfs_arranged(&edges, roots)
20}
21
22use crate::trace::TraceReader;
23use crate::operators::arrange::Arranged;
24
25/// Returns pairs (node, dist) indicating distance of each node from a root.
26pub fn bfs_arranged<G, N, Tr>(edges: &Arranged<G, Tr>, roots: &Collection<G, N>) -> Collection<G, (N, u32)>
27where
28    G: Scope<Timestamp=Tr::Time>,
29    N: ExchangeData+Hash,
30    Tr: for<'a> TraceReader<Key<'a>=&'a N, Val<'a>=&'a N, Diff=isize>+Clone+'static,
31{
32    // initialize roots as reaching themselves at distance 0
33    let nodes = roots.map(|x| (x, 0));
34
35    // repeatedly update minimal distances each node can be reached from each root
36    nodes.iterate(|inner| {
37
38        let edges = edges.enter(&inner.scope());
39        let nodes = nodes.enter(&inner.scope());
40
41        inner.join_core(&edges, |_k,l,d| Some((d.clone(), l+1)))
42             .concat(&nodes)
43             .reduce(|_, s, t| t.push((*s[0].0, 1)))
44     })
45}
differential_dataflow/algorithms/graphs/bfs.rs

differential_dataflow/algorithms/graphs/
bfs.rs
