cairo_lang_utils/graph_algos/
strongly_connected_components.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//! Logic for computing the strongly connected component of a node in a graph.

use core::hash::Hash;

use super::graph_node::GraphNode;
use crate::unordered_hash_map::UnorderedHashMap;

#[cfg(test)]
#[path = "strongly_connected_components_test.rs"]
mod strongly_connected_components_test;

/// A trait for a type that can compute its strongly-connected-component.
pub trait ComputeScc: GraphNode {
    fn compute_scc(&self) -> Vec<Self::NodeId>;
}

/// A wrapper node to a GraphNode, to be used in the SCC algorithm. Contains the GraphNode
/// additional state for the algorithm.
#[derive(Default, PartialEq, Eq, Hash, Clone)]
struct SccAlgoNode<Node: GraphNode> {
    /// The wrapped GraphNode
    node: Node,
    /// The index of the node in the algorithm. The smaller the index, the earlier the node was
    /// reached.
    index: u32,
    /// The smallest index of a node that's reachable from this node (so far).
    lowlink: u32,
    /// Whether the node is currently on the DFS stack.
    on_stack: bool,
}

/// The context of the SCC algorithm.
struct SccAlgoContext<Node: GraphNode> {
    /// The next index to allocate to a first-seen node.
    next_index: u32,
    /// The stack of the nodes in the DFS.
    stack: Vec<Node::NodeId>,
    /// All visited nodes. If a graph node is not in the map, it wasn't yet visited.
    known_nodes: UnorderedHashMap<Node::NodeId, SccAlgoNode<Node>>,
    /// The ID of the node we want to find the SCC of.
    target_node_id: Node::NodeId,
    /// The SCC of the `target_node_id`. Populated only at the end of the algorithm.
    result: Vec<Node::NodeId>,
}
impl<Node: GraphNode> SccAlgoContext<Node> {
    fn new(target_node_id: Node::NodeId) -> Self {
        SccAlgoContext::<Node> {
            next_index: 0,
            stack: Vec::new(),
            known_nodes: UnorderedHashMap::default(),
            target_node_id,
            result: Vec::new(),
        }
    }
}

/// Computes the SCC (Strongly Connected Component) of the given node in its graph.
pub fn compute_scc<Node: GraphNode>(root: &Node) -> Vec<Node::NodeId> {
    let mut ctx = SccAlgoContext::new(root.get_id());
    compute_scc_recursive(&mut ctx, root);
    ctx.result
}

/// The recursive call to compute the SCC of a given node.
fn compute_scc_recursive<Node: GraphNode>(ctx: &mut SccAlgoContext<Node>, current_node: &Node) {
    let mut current_wrapper_node = SccAlgoNode {
        node: current_node.clone(),
        index: ctx.next_index,
        lowlink: ctx.next_index,
        on_stack: true,
    };
    let current_node_id = current_node.get_id();
    ctx.known_nodes.insert(current_node_id.clone(), current_wrapper_node.clone());
    ctx.next_index += 1;
    ctx.stack.push(current_node_id.clone());

    for neighbor in current_node.get_neighbors() {
        let neighbor_id = neighbor.get_id();
        match ctx.known_nodes.get(&neighbor_id) {
            None => {
                // neighbor was not visited yet. Visit it and maybe apply its lowlink to root.
                compute_scc_recursive(ctx, &neighbor);
                // Now neighbor should be in known_nodes.
                current_wrapper_node.lowlink = core::cmp::min(
                    current_wrapper_node.lowlink,
                    ctx.known_nodes[&neighbor_id].lowlink,
                );
            }
            Some(neighbor_node) => {
                if ctx.known_nodes[&neighbor_id].on_stack {
                    // This is a back edge, meaning neighbor is in current_node's SCC.
                    current_wrapper_node.lowlink =
                        core::cmp::min(current_wrapper_node.lowlink, neighbor_node.index);
                } else {
                    // If neighbor is known but not on stack, it's in a concluded dropped SCC.
                    // Ignore it.
                    continue;
                }
            }
        };

        // Update current_node in ctx.known_nodes.
        ctx.known_nodes.insert(current_node_id.clone(), current_wrapper_node.clone());
    }

    if current_wrapper_node.lowlink != current_wrapper_node.index {
        // `current_node` is not a root of an SCC. We only conclude SCCs when we reach their roots.
        return;
    }

    // `current_node` is a root of an SCC. Conclude this SCC.
    // Push the nodes from the latest to earliest in the call hierarchy, so that the reverse of the
    // SCC vector would form a valid path on the graph.
    let mut scc = Vec::new();
    while let Some(other_node_id) = ctx.stack.pop() {
        let other_node = ctx.known_nodes.get_mut(&other_node_id).unwrap();
        other_node.on_stack = false;
        scc.push(other_node_id.clone());

        // Stop once the popped node is the current node which is the root on the SCC.
        if other_node_id == current_node_id {
            break;
        }
    }

    // If this SCC is the one we are looking for, update it in ctx. Otherwise, throw this
    // SCC away.
    if current_node_id == ctx.target_node_id {
        ctx.result = scc;
    }
}