Module timely::progress::nested::reachability_neu

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_neu::{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 = builder.build();

// 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();

let mut results = tracker.pushed().drain().collect::<Vec<_>>();
results.sort();

assert_eq!(results.len(), 3);
assert_eq!(results[0], ((Target { index: 0, port: 0 }, 18), 1));
assert_eq!(results[1], ((Target { index: 1, port: 0 }, 17), 1));
assert_eq!(results[2], ((Target { index: 2, port: 0 }, 17), 1));

// 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();

let mut results = tracker.pushed().drain().collect::<Vec<_>>();
results.sort();

assert_eq!(results.len(), 3);
assert_eq!(results[0], ((Target { index: 0, port: 0 }, 18), -1));
assert_eq!(results[1], ((Target { index: 1, port: 0 }, 17), -1));
assert_eq!(results[2], ((Target { index: 2, port: 0 }, 17), -1));

Structs

Builder	A topology builder, which can summarize reachability along paths.
Tracker	An interactive tracker of propagated reachability information.