Module timely::progress::nested::reachability

Manages pointstamp reachability within a graph.

Timely dataflow is concerned with understanding and communicating the potential for capabilites to reach nodes in a directed graph, by following paths through the graph (along edges and through nodes). This module contains one abstraction for managing this information.

Examples

use timely::progress::frontier::Antichain;
use timely::progress::nested::subgraph::{Source, Target};
use timely::progress::nested::reachability::{Builder, Tracker};

// allocate a new empty topology builder.
let mut builder = Builder::<usize>::new();
 
// Each node with one input connected to one output.
builder.add_node(0, 1, 1, vec![vec![Antichain::from_elem(0)]]);
builder.add_node(1, 1, 1, vec![vec![Antichain::from_elem(0)]]);
builder.add_node(2, 1, 1, vec![vec![Antichain::from_elem(1)]]);

// Connect nodes in sequence, looping around to the first from the last.
builder.add_edge(Source { index: 0, port: 0}, Target { index: 1, port: 0} );
builder.add_edge(Source { index: 1, port: 0}, Target { index: 2, port: 0} );
builder.add_edge(Source { index: 2, port: 0}, Target { index: 0, port: 0} );

// Construct a reachability tracker.
let mut tracker = Tracker::allocate_from(builder.summarize());

// Introduce a pointstamp at the output of the first node.
tracker.update_source(Source { index: 0, port: 0}, 17, 1);

// Propagate changes; until this call updates are simply buffered.
tracker.propagate_all();

// Propagated changes should have a single element, incremented for node zero.
assert_eq!(tracker.pushed_mut(0)[0].drain().collect::<Vec<_>>(), vec![(18, 1)]);
assert_eq!(tracker.pushed_mut(1)[0].drain().collect::<Vec<_>>(), vec![(17, 1)]);
assert_eq!(tracker.pushed_mut(2)[0].drain().collect::<Vec<_>>(), vec![(17, 1)]);

Structs

Builder	A topology builder, which can summarize reachability along paths.
Summary	A summary of minimal path summaries in a timely dataflow graph.
Tracker	An interactive tracker of propagated reachability information.