cairo_lang_utils::graph_algos::graph_node

Trait GraphNode

pub trait GraphNode: Sized + Clone {
    type NodeId: PartialEq + Eq + Hash + Clone;

    // Required methods
    fn get_neighbors(&self) -> Vec<Self>;
    fn get_id(&self) -> Self::NodeId;

    // Provided method
    fn get_neighbors_in_given_scc(&self, scc: Vec<Self::NodeId>) -> Vec<Self> { ... }
}

Expand description

A trait for a node in a graph. Note that a GraphNode has to be able to provide its neighbors by itself, without additional information.

Required Associated Types§

source

type NodeId: PartialEq + Eq + Hash + Clone

The type used to identify the nodes in the graph.

Required Methods§

source

fn get_neighbors(&self) -> Vec<Self>

Returns a list of the node’s neighbors. Must be stable for the SCC result to be stable. i.e. if the output for a node here doesn’t change between different runs, the computed SCC of the node is guaranteed to also not change.

source

fn get_id(&self) -> Self::NodeId

Gets the node’s ID.

Provided Methods§

source

fn get_neighbors_in_given_scc(&self, scc: Vec<Self::NodeId>) -> Vec<Self>

Helper function to get the neighbors of the node, given its SCC. Default-implemented and thus can be used in simple implementations of get_neighbors_in_scc.