cairo_lang_utils/graph_algos/
scc_graph_node.rs

1#[cfg(not(feature = "std"))]
2use alloc::vec::Vec;
3
4use super::graph_node::GraphNode;
5use super::strongly_connected_components::ComputeScc;
6
7/// A node whose neighbors are only the subset of its neighbors in the full graph, which are also in
8/// the same SCC (strongly-connected-component) with it.
9#[derive(Clone)]
10pub struct SccGraphNode<Node: ComputeScc>(Node);
11impl<Node: ComputeScc> GraphNode for SccGraphNode<Node> {
12    type NodeId = Node::NodeId;
13
14    fn get_neighbors(&self) -> Vec<Self> {
15        let scc = self.0.compute_scc();
16        self.0.get_neighbors_in_given_scc(scc).into_iter().map(SccGraphNode::<Node>).collect()
17    }
18
19    fn get_id(&self) -> Self::NodeId {
20        self.0.get_id()
21    }
22}
23impl<Node: ComputeScc> From<Node> for SccGraphNode<Node> {
24    fn from(value: Node) -> Self {
25        SccGraphNode::<Node>(value)
26    }
27}