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