cairo_lang_utils/graph_algos/
strongly_connected_components.rs

1//! Logic for computing the strongly connected component of a node in a graph.
2
3use core::hash::Hash;
4
5use super::graph_node::GraphNode;
6use crate::unordered_hash_map::UnorderedHashMap;
7
8#[cfg(test)]
9#[path = "strongly_connected_components_test.rs"]
10mod strongly_connected_components_test;
11
12/// A trait for a type that can compute its strongly-connected-component.
13pub trait ComputeScc: GraphNode {
14    fn compute_scc(&self) -> Vec<Self::NodeId>;
15}
16
17/// A wrapper node to a GraphNode, to be used in the SCC algorithm. Contains the GraphNode
18/// additional state for the algorithm.
19#[derive(Default, PartialEq, Eq, Hash, Clone)]
20struct SccAlgoNode<Node: GraphNode> {
21    /// The wrapped GraphNode
22    node: Node,
23    /// The index of the node in the algorithm. The smaller the index, the earlier the node was
24    /// reached.
25    index: u32,
26    /// The smallest index of a node that's reachable from this node (so far).
27    lowlink: u32,
28    /// Whether the node is currently on the DFS stack.
29    on_stack: bool,
30}
31
32/// The context of the SCC algorithm.
33struct SccAlgoContext<Node: GraphNode> {
34    /// The next index to allocate to a first-seen node.
35    next_index: u32,
36    /// The stack of the nodes in the DFS.
37    stack: Vec<Node::NodeId>,
38    /// All visited nodes. If a graph node is not in the map, it wasn't yet visited.
39    known_nodes: UnorderedHashMap<Node::NodeId, SccAlgoNode<Node>>,
40    /// The ID of the node we want to find the SCC of.
41    target_node_id: Node::NodeId,
42    /// The SCC of the `target_node_id`. Populated only at the end of the algorithm.
43    result: Vec<Node::NodeId>,
44}
45impl<Node: GraphNode> SccAlgoContext<Node> {
46    fn new(target_node_id: Node::NodeId) -> Self {
47        SccAlgoContext::<Node> {
48            next_index: 0,
49            stack: Vec::new(),
50            known_nodes: UnorderedHashMap::default(),
51            target_node_id,
52            result: Vec::new(),
53        }
54    }
55}
56
57/// Computes the SCC (Strongly Connected Component) of the given node in its graph.
58pub fn compute_scc<Node: GraphNode>(root: &Node) -> Vec<Node::NodeId> {
59    let mut ctx = SccAlgoContext::new(root.get_id());
60    compute_scc_recursive(&mut ctx, root);
61    ctx.result
62}
63
64/// The recursive call to compute the SCC of a given node.
65fn compute_scc_recursive<Node: GraphNode>(ctx: &mut SccAlgoContext<Node>, current_node: &Node) {
66    let mut current_wrapper_node = SccAlgoNode {
67        node: current_node.clone(),
68        index: ctx.next_index,
69        lowlink: ctx.next_index,
70        on_stack: true,
71    };
72    let current_node_id = current_node.get_id();
73    ctx.known_nodes.insert(current_node_id.clone(), current_wrapper_node.clone());
74    ctx.next_index += 1;
75    ctx.stack.push(current_node_id.clone());
76
77    for neighbor in current_node.get_neighbors() {
78        let neighbor_id = neighbor.get_id();
79        match ctx.known_nodes.get(&neighbor_id) {
80            None => {
81                // neighbor was not visited yet. Visit it and maybe apply its lowlink to root.
82                compute_scc_recursive(ctx, &neighbor);
83                // Now neighbor should be in known_nodes.
84                current_wrapper_node.lowlink = core::cmp::min(
85                    current_wrapper_node.lowlink,
86                    ctx.known_nodes[&neighbor_id].lowlink,
87                );
88            }
89            Some(neighbor_node) => {
90                if ctx.known_nodes[&neighbor_id].on_stack {
91                    // This is a back edge, meaning neighbor is in current_node's SCC.
92                    current_wrapper_node.lowlink =
93                        core::cmp::min(current_wrapper_node.lowlink, neighbor_node.index);
94                } else {
95                    // If neighbor is known but not on stack, it's in a concluded dropped SCC.
96                    // Ignore it.
97                    continue;
98                }
99            }
100        };
101
102        // Update current_node in ctx.known_nodes.
103        ctx.known_nodes.insert(current_node_id.clone(), current_wrapper_node.clone());
104    }
105
106    if current_wrapper_node.lowlink != current_wrapper_node.index {
107        // `current_node` is not a root of an SCC. We only conclude SCCs when we reach their roots.
108        return;
109    }
110
111    // `current_node` is a root of an SCC. Conclude this SCC.
112    // Push the nodes from the latest to earliest in the call hierarchy, so that the reverse of the
113    // SCC vector would form a valid path on the graph.
114    let mut scc = Vec::new();
115    while let Some(other_node_id) = ctx.stack.pop() {
116        let other_node = ctx.known_nodes.get_mut(&other_node_id).unwrap();
117        other_node.on_stack = false;
118        scc.push(other_node_id.clone());
119
120        // Stop once the popped node is the current node which is the root on the SCC.
121        if other_node_id == current_node_id {
122            break;
123        }
124    }
125
126    // If this SCC is the one we are looking for, update it in ctx. Otherwise, throw this
127    // SCC away.
128    if current_node_id == ctx.target_node_id {
129        ctx.result = scc;
130    }
131}
cairo_lang_utils/graph_algos/strongly_connected_components.rs

cairo_lang_utils/graph_algos/
strongly_connected_components.rs
