[−][src]Module timely::progress::reachability
Manages pointstamp reachability within a timely dataflow graph.
Timely dataflow is concerned with understanding and communicating the potential for capabilities 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::{Location, Port}; use timely::progress::frontier::Antichain; use timely::progress::{Source, Target}; use timely::progress::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, _) = 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() .filter(|((location, time), delta)| location.is_target()) .collect::<Vec<_>>(); results.sort(); println!("{:?}", results); assert_eq!(results.len(), 3); assert_eq!(results[0], ((Location::new_target(0, 0), 18), 1)); assert_eq!(results[1], ((Location::new_target(1, 0), 17), 1)); assert_eq!(results[2], ((Location::new_target(2, 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() .filter(|((location, time), delta)| location.is_target()) .collect::<Vec<_>>(); results.sort(); assert_eq!(results.len(), 3); assert_eq!(results[0], ((Location::new_target(0, 0), 18), -1)); assert_eq!(results[1], ((Location::new_target(1, 0), 17), -1)); assert_eq!(results[2], ((Location::new_target(2, 0), 17), -1));
Structs
Builder | A topology builder, which can summarize reachability along paths. |
PerOperator | |
PortInformation | Per-port progress-tracking information. |
Tracker | An interactive tracker of propagated reachability information. |