Struct Graph 

pub struct Graph<N: Hash + Eq + Clone + Debug> {
    repr: HashMap<N, Vec<N>>,
}

A directed graph represented with an adjacency list.

repr maps each vertex u to a vector of all vertices v such that (u, v) is an edge in the graph.

In the context of this module, vertices correspond to Circuit Nodes, and edges represent precedence constraints: there is an edge (u, v) if v’s input depends on u’s output.

Type N is typically a node-identifying type, such as NodeId.

Fields

repr: HashMap<N, Vec<N>>

Implementations

impl<N: Hash + Eq + Clone + Debug> Graph<N>

fn new_from_map(map: HashMap<N, Vec<N>>) -> Self

Constructor given the map of dependencies.

fn new_from_circuit_nodes<F: Field>( intermediate_circuit_nodes: &[Box<dyn CompilableNode<F>>], input_shred_ids: &HashSet<NodeId>, ) -> Graph<NodeId>

Constructor specifically for a Graph<NodeId>, which will convert an array of CompilableNode, each of which reference their sources, and convert that into the graph representation.

Note: we only topologically sort intermediate nodes, therefore we provide input_shred_ids to exclude them from the graph.

fn visit_node_dfs( &self, node: &N, exploring_nodes: &mut HashSet<N>, terminated_nodes: &mut HashSet<N>, topological_order: &mut Vec<N>, ) -> Result<()>

Given the graph, a starting node (node), the set of visited/“marked” nodes (exploring_nodes) and nodes that have been fully explored (terminated_nodes), traverse the graph recursively using the DFS algorithm from the starting node.

Returns nothing, but mutates the exploring_nodes and terminated_nodes accordingly.

fn topo_sort(&self) -> Result<Vec<N>>

Topologically orders the graph by visiting each node via DFS. Returns the terminated nodes in order of termination.

Note: normally, the topological sort is the “reverse” order of termination via DFS. However, since we wish to order from sources -> sinks, and our dependency graph is structured as children -> parent, we do not reverse the termination order of the DFS search.

fn get_index_of_latest_dependency( &self, topological_order: &[N], idx_to_check: usize, ) -> Option<usize>

Given a list of nodes that are already topologically ordered, we check all nodes that come before it to return the index in the topological sort of the latest node that it was dependent on.

fn gen_latest_dependecy_indices( &self, topological_order: &[N], ) -> Vec<Option<usize>>

Given a valid topological ordering topological_order == [v_0, v_1, ..., v_{n-1}], this method returns a vector latest_dependency_indices such that latest_dependency_indices[i] == Some(j) iff: (a) there is a edge/dependency (v_i, v_j) in the graph, and (b) j is the maximum index for which such an edge exists. If there are no edges coming out of v_i, then latest_dependency_indices[i] == None.

Complexity

Linear in the size of the graph: O(|V| + |E|).

pub fn naive_gen_latest_dependecy_indices( &self, topological_order: &[N], ) -> Vec<Option<usize>>

Inefficient variant of gen_latest_dependency_indices used for correctness tests.

Trait Implementations

impl<N: Clone + Hash + Eq + Clone + Debug> Clone for Graph<N>

fn clone(&self) -> Graph<N>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<N: Debug + Hash + Eq + Clone + Debug> Debug for Graph<N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.