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

cairo_lang_utils/graph_algos/
strongly_connected_components.rs
