cairo_lang_utils/graph_algos/
graph_node.rs

1#[cfg(not(feature = "std"))]
2use alloc::vec::Vec;
3use core::hash::Hash;
4
5/// A trait for a node in a graph. Note that a GraphNode has to be able to provide its neighbors
6/// by itself, without additional information.
7pub trait GraphNode: Sized + Clone {
8    /// The type used to identify the nodes in the graph.
9    type NodeId: PartialEq + Eq + Hash + Clone;
10
11    /// Returns a list of the node's neighbors.
12    /// Must be stable for the SCC result to be stable. i.e. if the output for a node here doesn't
13    /// change between different runs, the computed SCC of the node is guaranteed to also not
14    /// change.
15    fn get_neighbors(&self) -> Vec<Self>;
16
17    /// Gets the node's ID.
18    fn get_id(&self) -> Self::NodeId;
19
20    /// Helper function to get the neighbors of the node, given its SCC. Default-implemented and
21    /// thus can be used in simple implementations of get_neighbors_in_scc.
22    fn get_neighbors_in_given_scc(&self, scc: Vec<Self::NodeId>) -> Vec<Self> {
23        let mut neighbors_in_scc = Vec::new();
24        for neighbor in self.get_neighbors() {
25            if scc.contains(&neighbor.get_id()) {
26                neighbors_in_scc.push(neighbor);
27            }
28        }
29        neighbors_in_scc
30    }
31}
cairo_lang_utils/graph_algos/graph_node.rs

cairo_lang_utils/graph_algos/
graph_node.rs
