cairo_lang_utils/graph_algos/
feedback_set.rs

1//! A feedback-vertex-set is a set of vertices whose removal leaves a graph without cycles
2//! (<https://en.wikipedia.org/wiki/Feedback_vertex_set>).
3//!
4//! We use this algorithm to spot the relevant places for adding `withdraw_gas` statements in the
5//! resulting Sierra code - there should be a `withdraw_gas` call in every recursive call, or in
6//! other words, in any cycle in the function call graph.
7//! An efficient algorithm to find the minimum feedback-vertex-set in a directed graph is not known,
8//! so here we implement some straight-forward algorithm that guarantees to cover all the cycles in
9//! the graph, but doesn't necessarily produce the minimum size of such a set.
10
11use std::collections::VecDeque;
12
13use super::graph_node::GraphNode;
14use super::scc_graph_node::SccGraphNode;
15use super::strongly_connected_components::ComputeScc;
16use crate::ordered_hash_set::OrderedHashSet;
17use crate::unordered_hash_set::UnorderedHashSet;
18
19#[cfg(test)]
20#[path = "feedback_set_test.rs"]
21mod feedback_set_test;
22
23/// Context for the feedback-set algorithm.
24struct FeedbackSetAlgoContext<Node: ComputeScc> {
25    /// Nodes that were discovered as reachable from the current run, but possibly were not yet
26    /// visited.
27    /// Note that nodes added here may be visited otherwise, as they could be a part of a cycle, as
28    /// well as appear more than once in this queue, so we keep a separate account of visited
29    /// nodes.
30    pending: VecDeque<SccGraphNode<Node>>,
31    /// The accumulated feedback set so far in the process of the algorithm. In the end of the
32    /// algorithm, this is also the result.
33    feedback_set: OrderedHashSet<Node::NodeId>,
34    /// Nodes that are currently during the recursion call on them. That is - if one of these is
35    /// reached, it indicates it's in some cycle that was not "resolved" yet.
36    in_flight: UnorderedHashSet<Node::NodeId>,
37    /// Already visited nodes in the current run.
38    visited: UnorderedHashSet<Node::NodeId>,
39}
40
41/// Calculates the feedback set of an SCC.
42pub fn calc_feedback_set<Node: ComputeScc>(
43    node: SccGraphNode<Node>,
44) -> OrderedHashSet<Node::NodeId> {
45    let mut ctx = FeedbackSetAlgoContext {
46        feedback_set: OrderedHashSet::default(),
47        in_flight: UnorderedHashSet::default(),
48        pending: VecDeque::new(),
49        visited: UnorderedHashSet::default(),
50    };
51    ctx.pending.push_back(node);
52    while let Some(node) = ctx.pending.pop_front() {
53        calc_feedback_set_recursive(node, &mut ctx);
54    }
55    ctx.feedback_set
56}
57
58fn calc_feedback_set_recursive<Node: ComputeScc>(
59    node: SccGraphNode<Node>,
60    ctx: &mut FeedbackSetAlgoContext<Node>,
61) {
62    let cur_node_id = node.get_id();
63    if !ctx.visited.insert(cur_node_id.clone()) {
64        return;
65    };
66    let neighbors = node.get_neighbors();
67    let has_self_loop = neighbors.iter().any(|neighbor| neighbor.get_id() == cur_node_id);
68    let mut remaining_neighbors = neighbors.into_iter();
69    if has_self_loop {
70        // If there is a self-loop, we prefer to add the current node to the feedback set as it must
71        // be there eventually. This may result in smaller feedback sets in many cases.
72        ctx.feedback_set.insert(cur_node_id.clone());
73    } else {
74        ctx.in_flight.insert(cur_node_id.clone());
75        for neighbor in remaining_neighbors.by_ref() {
76            let neighbor_id = neighbor.get_id();
77            if ctx.feedback_set.contains(&neighbor_id) {
78                continue;
79            } else if ctx.in_flight.contains(&neighbor_id) {
80                ctx.feedback_set.insert(neighbor_id);
81            } else {
82                calc_feedback_set_recursive(neighbor, ctx);
83            }
84
85            // `node` might have been added to the fset during this iteration of the loop. If so, no
86            // need to continue this loop.
87            if ctx.feedback_set.contains(&cur_node_id) {
88                break;
89            }
90        }
91        ctx.in_flight.remove(&cur_node_id);
92    };
93    ctx.pending.extend(remaining_neighbors.filter(|node| !ctx.visited.contains(&node.get_id())));
94}
cairo_lang_utils/graph_algos/feedback_set.rs

cairo_lang_utils/graph_algos/
feedback_set.rs
