Struct TraversalEngine

Source

pub struct TraversalEngine { /* private fields */ }

Expand description

A budgeted star-graph traversal with accepted-subset tracking.

Implementations§

Source §

impl TraversalEngine

Source

pub fn new( num_nodes: usize, root: usize, budget: u64, ) -> Result<Self, TraversalBuildError>

Construct a traversal rooted in the configured node universe.

Examples found in repository ?

examples/catalog.rs (line 103)

20fn main() -> Result<(), Box<dyn Error>> {
21    // Primitives.
22    let mut budget = Budget::new(8);
23    assert!(budget.try_reserve(3));
24    budget.commit_reservation(3)?;
25
26    let mut hierarchy = QualityHierarchy::new(2, 2);
27    hierarchy.set_node_properties(0, 2, 1)?;
28    hierarchy.set_node_properties(1, 1, 2)?;
29    hierarchy.add_child(0, 1)?;
30
31    let mut registry = ResourceRegistry::new();
32    registry.insert(1, 10);
33    assert_eq!(registry.get(1), Some(10));
34
35    let mut hard = CompetitiveSelectionHard::new(2)?;
36    hard.update_score(0, 2)?;
37    hard.update_score(1, 1)?;
38    assert_eq!(hard.evaluate(), 0);
39
40    let mut exclusive = CompetitiveSelectionHardExclusive::new(1, 2, 2)?;
41    exclusive.update_score(0, 0, 2)?;
42    exclusive.update_score(0, 1, 1)?;
43    assert_eq!(exclusive.evaluate(0)?, 0);
44
45    let mut soft = CompetitiveSelectionSoft::begin(vec![3, 1], 4, 3)?;
46    assert_eq!(soft.assign_next()?, 0);
47
48    let mut ranked = CompetitiveSelectionRanked::new(vec![2, 1], 1, 2)?;
49    ranked.select();
50    assert_eq!(ranked.is_selected(0), Some(true));
51
52    let mut actuation = ActuationPass::new(vec![Some(7)]);
53    actuation.actuate(0)?;
54    actuation.finish()?;
55
56    let mut propagation = PropagationPass::new(1, 2, vec![], vec![0])?;
57    propagation.start_round()?;
58    propagation.update_node(0)?;
59    propagation.end_round()?;
60
61    let mut convergence = ConvergenceGovernor::new(2, 6, 2, 10)?;
62    assert_eq!(convergence.update(1)?, 1);
63
64    let mut audit = AuditSink::new(1);
65    assert!(audit.try_record(7));
66    assert!(audit.validate());
67
68    let mut backtracking = BacktrackingTraversal::new(2, 1, 0)?;
69    backtracking.descend(1, 1)?;
70    backtracking.visit()?;
71
72    // Named compositions.
73    let mut snapshot = AllocationSnapshot::new(3, 1);
74    snapshot.accept(0, 3)?;
75
76    let mut federated = FederatedBudget::new(4, 1);
77    assert!(federated.try_delegate(0, 4));
78    assert!(federated.try_allocate(0, 2));
79
80    let mut bisection = Bisection::new(4, 2)?;
81    bisection.converge();
82    assert!(bisection.is_converged());
83
84    let mut classes = EquivalenceClass::new(2, 1);
85    assert!(classes.union(0, 1)?);
86
87    let mut rate_limit = RateLimit::new(1, 1, 1)?;
88    assert!(rate_limit.try_acquire());
89
90    let mut reduction = Reduction::new(vec![2, 3])?;
91    reduction.process_next()?;
92
93    let mut graph = RelationshipGraph::new(2, 1);
94    assert!(graph.add_edge(0, 1, 1)?);
95
96    let mut sampler = Sampler::new(vec![1, 1], 1);
97    sampler.sample(0)?;
98
99    let mut signal = Signal::new(0, 2, 1)?;
100    assert!(signal.set_value(1)?);
101    signal.notify(0)?;
102
103    let mut traversal = TraversalEngine::new(1, 0, 1)?;
104    traversal.visit(0)?;
105    traversal.terminate()?;
106
107    // Execution modalities.
108    let mut sequential = Sequential::new(1, 2, 0)?;
109    assert!(sequential.begin_step());
110    assert!(sequential.complete_step(1));
111
112    let mut fork_join = ForkJoin::new(1, 2, 0)?;
113    assert!(fork_join.start_worker(0));
114    assert!(fork_join.complete_worker(0, 1));
115    assert!(fork_join.barrier());
116    assert!(fork_join.produce_output());
117
118    let mut step_graph = StepGraph::new(1, vec![])?;
119    assert!(step_graph.start(0));
120    assert!(step_graph.complete(0));
121
122    let mut stream_graph = StreamGraph::new(3, 1, 1, 2)?;
123    assert!(stream_graph.ingest(1));
124    assert!(stream_graph.advance_first());
125    assert_eq!(stream_graph.consume(), Some(1));
126
127    // Connective roles.
128    let mut cursor = Cursor::new(0);
129    cursor.advance_to(1)?;
130
131    let mut accumulator = Accumulator::new(vec![1]);
132    assert_eq!(accumulator.advance(), Some(1));
133
134    let mut marker = Marker::new(false);
135    assert!(marker.set());
136
137    let mut counter = Counter::new(0);
138    assert!(counter.try_increment());
139
140    let mut buffer = Buffer::new(1);
141    assert_eq!(buffer.push(1), Ok(()));
142    assert_eq!(buffer.pop(), Some(1));
143
144    assert!(projection_consistent(true, true));
145    assert!(strictly_before(0, 1));
146
147    assert_debuggable!(
148        budget,
149        hierarchy,
150        registry,
151        hard,
152        exclusive,
153        soft,
154        ranked,
155        actuation,
156        propagation,
157        convergence,
158        audit,
159        backtracking,
160        snapshot,
161        federated,
162        bisection,
163        classes,
164        rate_limit,
165        reduction,
166        graph,
167        sampler,
168        signal,
169        traversal,
170        sequential,
171        fork_join,
172        step_graph,
173        stream_graph,
174        cursor,
175        accumulator,
176        marker,
177        counter,
178        buffer,
179    );
180
181    println!("all public automation structures constructed and exercised");
182    Ok(())
183}

Source

pub fn num_nodes(&self) -> usize

Number of nodes.

Source

pub fn root(&self) -> usize

Traversal root.

Source

pub fn budget_remaining(&self) -> u64

Remaining traversal budget.

Source

pub fn queued_len(&self) -> usize

Number of queued nodes.

Source

pub fn visited_len(&self) -> usize

Number of visited nodes.

Source

pub fn accepted_len(&self) -> usize

Number of budget-accepted nodes.

Source

pub fn is_queued(&self, node: usize) -> bool

Whether a node is queued.

Source

pub fn is_visited(&self, node: usize) -> bool

Whether a node was visited.

Source

pub fn is_accepted(&self, node: usize) -> bool

Whether a node was accepted under the budget.

Source

pub fn visit(&mut self, node: usize) -> Result<(), TraversalError>

Visit one queued, unvisited node.

Examples found in repository ?

examples/catalog.rs (line 104)

20fn main() -> Result<(), Box<dyn Error>> {
21    // Primitives.
22    let mut budget = Budget::new(8);
23    assert!(budget.try_reserve(3));
24    budget.commit_reservation(3)?;
25
26    let mut hierarchy = QualityHierarchy::new(2, 2);
27    hierarchy.set_node_properties(0, 2, 1)?;
28    hierarchy.set_node_properties(1, 1, 2)?;
29    hierarchy.add_child(0, 1)?;
30
31    let mut registry = ResourceRegistry::new();
32    registry.insert(1, 10);
33    assert_eq!(registry.get(1), Some(10));
34
35    let mut hard = CompetitiveSelectionHard::new(2)?;
36    hard.update_score(0, 2)?;
37    hard.update_score(1, 1)?;
38    assert_eq!(hard.evaluate(), 0);
39
40    let mut exclusive = CompetitiveSelectionHardExclusive::new(1, 2, 2)?;
41    exclusive.update_score(0, 0, 2)?;
42    exclusive.update_score(0, 1, 1)?;
43    assert_eq!(exclusive.evaluate(0)?, 0);
44
45    let mut soft = CompetitiveSelectionSoft::begin(vec![3, 1], 4, 3)?;
46    assert_eq!(soft.assign_next()?, 0);
47
48    let mut ranked = CompetitiveSelectionRanked::new(vec![2, 1], 1, 2)?;
49    ranked.select();
50    assert_eq!(ranked.is_selected(0), Some(true));
51
52    let mut actuation = ActuationPass::new(vec![Some(7)]);
53    actuation.actuate(0)?;
54    actuation.finish()?;
55
56    let mut propagation = PropagationPass::new(1, 2, vec![], vec![0])?;
57    propagation.start_round()?;
58    propagation.update_node(0)?;
59    propagation.end_round()?;
60
61    let mut convergence = ConvergenceGovernor::new(2, 6, 2, 10)?;
62    assert_eq!(convergence.update(1)?, 1);
63
64    let mut audit = AuditSink::new(1);
65    assert!(audit.try_record(7));
66    assert!(audit.validate());
67
68    let mut backtracking = BacktrackingTraversal::new(2, 1, 0)?;
69    backtracking.descend(1, 1)?;
70    backtracking.visit()?;
71
72    // Named compositions.
73    let mut snapshot = AllocationSnapshot::new(3, 1);
74    snapshot.accept(0, 3)?;
75
76    let mut federated = FederatedBudget::new(4, 1);
77    assert!(federated.try_delegate(0, 4));
78    assert!(federated.try_allocate(0, 2));
79
80    let mut bisection = Bisection::new(4, 2)?;
81    bisection.converge();
82    assert!(bisection.is_converged());
83
84    let mut classes = EquivalenceClass::new(2, 1);
85    assert!(classes.union(0, 1)?);
86
87    let mut rate_limit = RateLimit::new(1, 1, 1)?;
88    assert!(rate_limit.try_acquire());
89
90    let mut reduction = Reduction::new(vec![2, 3])?;
91    reduction.process_next()?;
92
93    let mut graph = RelationshipGraph::new(2, 1);
94    assert!(graph.add_edge(0, 1, 1)?);
95
96    let mut sampler = Sampler::new(vec![1, 1], 1);
97    sampler.sample(0)?;
98
99    let mut signal = Signal::new(0, 2, 1)?;
100    assert!(signal.set_value(1)?);
101    signal.notify(0)?;
102
103    let mut traversal = TraversalEngine::new(1, 0, 1)?;
104    traversal.visit(0)?;
105    traversal.terminate()?;
106
107    // Execution modalities.
108    let mut sequential = Sequential::new(1, 2, 0)?;
109    assert!(sequential.begin_step());
110    assert!(sequential.complete_step(1));
111
112    let mut fork_join = ForkJoin::new(1, 2, 0)?;
113    assert!(fork_join.start_worker(0));
114    assert!(fork_join.complete_worker(0, 1));
115    assert!(fork_join.barrier());
116    assert!(fork_join.produce_output());
117
118    let mut step_graph = StepGraph::new(1, vec![])?;
119    assert!(step_graph.start(0));
120    assert!(step_graph.complete(0));
121
122    let mut stream_graph = StreamGraph::new(3, 1, 1, 2)?;
123    assert!(stream_graph.ingest(1));
124    assert!(stream_graph.advance_first());
125    assert_eq!(stream_graph.consume(), Some(1));
126
127    // Connective roles.
128    let mut cursor = Cursor::new(0);
129    cursor.advance_to(1)?;
130
131    let mut accumulator = Accumulator::new(vec![1]);
132    assert_eq!(accumulator.advance(), Some(1));
133
134    let mut marker = Marker::new(false);
135    assert!(marker.set());
136
137    let mut counter = Counter::new(0);
138    assert!(counter.try_increment());
139
140    let mut buffer = Buffer::new(1);
141    assert_eq!(buffer.push(1), Ok(()));
142    assert_eq!(buffer.pop(), Some(1));
143
144    assert!(projection_consistent(true, true));
145    assert!(strictly_before(0, 1));
146
147    assert_debuggable!(
148        budget,
149        hierarchy,
150        registry,
151        hard,
152        exclusive,
153        soft,
154        ranked,
155        actuation,
156        propagation,
157        convergence,
158        audit,
159        backtracking,
160        snapshot,
161        federated,
162        bisection,
163        classes,
164        rate_limit,
165        reduction,
166        graph,
167        sampler,
168        signal,
169        traversal,
170        sequential,
171        fork_join,
172        step_graph,
173        stream_graph,
174        cursor,
175        accumulator,
176        marker,
177        counter,
178        buffer,
179    );
180
181    println!("all public automation structures constructed and exercised");
182    Ok(())
183}

Source

pub fn skip(&mut self, node: usize) -> Result<(), TraversalError>

Remove one queued node without visiting it.

Source

pub fn terminate(&mut self) -> Result<(), TraversalError>

Confirm the terminal stutter when no queued work remains.

Examples found in repository ?

examples/catalog.rs (line 105)

20fn main() -> Result<(), Box<dyn Error>> {
21    // Primitives.
22    let mut budget = Budget::new(8);
23    assert!(budget.try_reserve(3));
24    budget.commit_reservation(3)?;
25
26    let mut hierarchy = QualityHierarchy::new(2, 2);
27    hierarchy.set_node_properties(0, 2, 1)?;
28    hierarchy.set_node_properties(1, 1, 2)?;
29    hierarchy.add_child(0, 1)?;
30
31    let mut registry = ResourceRegistry::new();
32    registry.insert(1, 10);
33    assert_eq!(registry.get(1), Some(10));
34
35    let mut hard = CompetitiveSelectionHard::new(2)?;
36    hard.update_score(0, 2)?;
37    hard.update_score(1, 1)?;
38    assert_eq!(hard.evaluate(), 0);
39
40    let mut exclusive = CompetitiveSelectionHardExclusive::new(1, 2, 2)?;
41    exclusive.update_score(0, 0, 2)?;
42    exclusive.update_score(0, 1, 1)?;
43    assert_eq!(exclusive.evaluate(0)?, 0);
44
45    let mut soft = CompetitiveSelectionSoft::begin(vec![3, 1], 4, 3)?;
46    assert_eq!(soft.assign_next()?, 0);
47
48    let mut ranked = CompetitiveSelectionRanked::new(vec![2, 1], 1, 2)?;
49    ranked.select();
50    assert_eq!(ranked.is_selected(0), Some(true));
51
52    let mut actuation = ActuationPass::new(vec![Some(7)]);
53    actuation.actuate(0)?;
54    actuation.finish()?;
55
56    let mut propagation = PropagationPass::new(1, 2, vec![], vec![0])?;
57    propagation.start_round()?;
58    propagation.update_node(0)?;
59    propagation.end_round()?;
60
61    let mut convergence = ConvergenceGovernor::new(2, 6, 2, 10)?;
62    assert_eq!(convergence.update(1)?, 1);
63
64    let mut audit = AuditSink::new(1);
65    assert!(audit.try_record(7));
66    assert!(audit.validate());
67
68    let mut backtracking = BacktrackingTraversal::new(2, 1, 0)?;
69    backtracking.descend(1, 1)?;
70    backtracking.visit()?;
71
72    // Named compositions.
73    let mut snapshot = AllocationSnapshot::new(3, 1);
74    snapshot.accept(0, 3)?;
75
76    let mut federated = FederatedBudget::new(4, 1);
77    assert!(federated.try_delegate(0, 4));
78    assert!(federated.try_allocate(0, 2));
79
80    let mut bisection = Bisection::new(4, 2)?;
81    bisection.converge();
82    assert!(bisection.is_converged());
83
84    let mut classes = EquivalenceClass::new(2, 1);
85    assert!(classes.union(0, 1)?);
86
87    let mut rate_limit = RateLimit::new(1, 1, 1)?;
88    assert!(rate_limit.try_acquire());
89
90    let mut reduction = Reduction::new(vec![2, 3])?;
91    reduction.process_next()?;
92
93    let mut graph = RelationshipGraph::new(2, 1);
94    assert!(graph.add_edge(0, 1, 1)?);
95
96    let mut sampler = Sampler::new(vec![1, 1], 1);
97    sampler.sample(0)?;
98
99    let mut signal = Signal::new(0, 2, 1)?;
100    assert!(signal.set_value(1)?);
101    signal.notify(0)?;
102
103    let mut traversal = TraversalEngine::new(1, 0, 1)?;
104    traversal.visit(0)?;
105    traversal.terminate()?;
106
107    // Execution modalities.
108    let mut sequential = Sequential::new(1, 2, 0)?;
109    assert!(sequential.begin_step());
110    assert!(sequential.complete_step(1));
111
112    let mut fork_join = ForkJoin::new(1, 2, 0)?;
113    assert!(fork_join.start_worker(0));
114    assert!(fork_join.complete_worker(0, 1));
115    assert!(fork_join.barrier());
116    assert!(fork_join.produce_output());
117
118    let mut step_graph = StepGraph::new(1, vec![])?;
119    assert!(step_graph.start(0));
120    assert!(step_graph.complete(0));
121
122    let mut stream_graph = StreamGraph::new(3, 1, 1, 2)?;
123    assert!(stream_graph.ingest(1));
124    assert!(stream_graph.advance_first());
125    assert_eq!(stream_graph.consume(), Some(1));
126
127    // Connective roles.
128    let mut cursor = Cursor::new(0);
129    cursor.advance_to(1)?;
130
131    let mut accumulator = Accumulator::new(vec![1]);
132    assert_eq!(accumulator.advance(), Some(1));
133
134    let mut marker = Marker::new(false);
135    assert!(marker.set());
136
137    let mut counter = Counter::new(0);
138    assert!(counter.try_increment());
139
140    let mut buffer = Buffer::new(1);
141    assert_eq!(buffer.push(1), Ok(()));
142    assert_eq!(buffer.pop(), Some(1));
143
144    assert!(projection_consistent(true, true));
145    assert!(strictly_before(0, 1));
146
147    assert_debuggable!(
148        budget,
149        hierarchy,
150        registry,
151        hard,
152        exclusive,
153        soft,
154        ranked,
155        actuation,
156        propagation,
157        convergence,
158        audit,
159        backtracking,
160        snapshot,
161        federated,
162        bisection,
163        classes,
164        rate_limit,
165        reduction,
166        graph,
167        sampler,
168        signal,
169        traversal,
170        sequential,
171        fork_join,
172        step_graph,
173        stream_graph,
174        cursor,
175        accumulator,
176        marker,
177        counter,
178        buffer,
179    );
180
181    println!("all public automation structures constructed and exercised");
182    Ok(())
183}