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/// Calculates the feedback set of an SCC.
24pub fn calc_feedback_set<Node: ComputeScc>(
25    node: SccGraphNode<Node>,
26) -> OrderedHashSet<Node::NodeId> {
27    let mut ctx = FeedbackSetAlgoContext {
28        feedback_set: OrderedHashSet::default(),
29        in_flight: UnorderedHashSet::default(),
30        pending: VecDeque::new(),
31        visited: UnorderedHashSet::default(),
32    };
33    ctx.pending.push_back(node);
34    while let Some(node) = ctx.pending.pop_front() {
35        ctx.calc_feedback_set_recursive(node);
36    }
37    ctx.feedback_set
38}
39/// Context for the feedback-set algorithm.
40struct FeedbackSetAlgoContext<Node: ComputeScc> {
41    /// Nodes that were discovered as reachable from the current run, but possibly were not yet
42    /// visited.
43    /// Note that nodes added here may be visited otherwise, as they could be a part of a cycle, as
44    /// well as appear more than once in this queue, so we keep a separate account of visited
45    /// nodes.
46    pending: VecDeque<SccGraphNode<Node>>,
47    /// The accumulated feedback set so far in the process of the algorithm. In the end of the
48    /// algorithm, this is also the result.
49    feedback_set: OrderedHashSet<Node::NodeId>,
50    /// Nodes that are currently during the recursion call on them. That is - if one of these is
51    /// reached, it indicates it's in some cycle that was not "resolved" yet.
52    in_flight: UnorderedHashSet<Node::NodeId>,
53    /// Already visited nodes in the current run.
54    visited: UnorderedHashSet<Node::NodeId>,
55}
56impl<Node: ComputeScc> FeedbackSetAlgoContext<Node> {
57    fn calc_feedback_set_recursive(&mut self, node: SccGraphNode<Node>) {
58        let cur_node_id = node.get_id();
59        if !self.visited.insert(cur_node_id.clone()) {
60            return;
61        };
62        let neighbors = node.get_neighbors();
63        let has_self_loop = neighbors.iter().any(|neighbor| neighbor.get_id() == cur_node_id);
64        let mut remaining_neighbors = neighbors.into_iter();
65        if has_self_loop {
66            // If there is a self-loop, we prefer to add the current node to the feedback set as it
67            // must be there eventually. This may result in smaller feedback sets in
68            // many cases.
69            self.feedback_set.insert(cur_node_id.clone());
70        } else {
71            self.in_flight.insert(cur_node_id.clone());
72            for neighbor in remaining_neighbors.by_ref() {
73                let neighbor_id = neighbor.get_id();
74                if self.feedback_set.contains(&neighbor_id) {
75                    continue;
76                } else if self.in_flight.contains(&neighbor_id) {
77                    self.feedback_set.insert(neighbor_id);
78                } else {
79                    self.calc_feedback_set_recursive(neighbor);
80                }
81
82                // `node` might have been added to the fset during this iteration of the loop. If
83                // so, no need to continue this loop.
84                if self.feedback_set.contains(&cur_node_id) {
85                    break;
86                }
87            }
88            self.in_flight.remove(&cur_node_id);
89        };
90        self.pending
91            .extend(remaining_neighbors.filter(|node| !self.visited.contains(&node.get_id())));
92    }
93}
cairo_lang_utils/graph_algos/feedback_set.rs

cairo_lang_utils/graph_algos/
feedback_set.rs
