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,
30    G::Timestamp: Lattice+Ord,
31    N: ExchangeData+Hash,
32    Tr: for<'a> TraceReader<Key<'a>=&'a N, Val<'a>=&'a N, Time=G::Timestamp, Diff=isize>+Clone+'static,
33{
34    // initialize roots as reaching themselves at distance 0
35    let nodes = roots.map(|x| (x, 0));
36
37    // repeatedly update minimal distances each node can be reached from each root
38    nodes.iterate(|inner| {
39
40        let edges = edges.enter(&inner.scope());
41        let nodes = nodes.enter(&inner.scope());
42
43        inner.join_core(&edges, |_k,l,d| Some((d.clone(), l+1)))
44             .concat(&nodes)
45             .reduce(|_, s, t| t.push((*s[0].0, 1)))
46     })
47}
differential_dataflow/algorithms/graphs/bfs.rs

differential_dataflow/algorithms/graphs/
bfs.rs
