Struct Graph 

pub struct Graph<N> { /* private fields */ }

A directed graph over nodes of type N.

Implementations

impl<N> Graph<N>

where N: Hash + Eq + Clone + Ord,

pub const fn new() -> Self

Construct an empty graph.

pub fn add_node(&mut self, n: N)

Add a node. No-op if already present.

pub fn add_edge(&mut self, from: N, to: N)

Add an edge from -> to, meaning from depends on to. Both endpoints are added as nodes if not already present.

The edge carries no explicit provenance; dep_edges() will report it as DepSource::Structural by default. Use add_dep_edge on Graph<NodeId> to record explicit provenance for v0.2 edges.

pub fn remove_edge(&mut self, from: &N, to: &N)

Remove an edge from -> to. No-op if absent.

Does not touch edge_sources. If the edge was inserted via Graph::add_dep_edge on a Graph<NodeId>, the stale provenance entry will survive and be returned by Graph::dep_edges if the edge is re-added later. Use Graph::remove_dep_edge instead when provenance correctness matters.

pub fn node_count(&self) -> usize

Number of nodes in the graph.

pub fn nodes(&self) -> impl Iterator<Item = &N>

Iterate over all nodes in Ord order.

pub fn dependencies_of<'a>( &'a self, n: &N, ) -> impl Iterator<Item = &'a N> + 'a + use<'a, N>

Iterate the dependencies of n (the set edges[n]).

pub fn topological_sort(&self) -> Result<Vec<N>, Cycle<N>>

Topological sort using Kahn’s algorithm.

Returns nodes with no remaining dependencies first. Ties are broken by the smallest node per Ord, so the result is deterministic.

pub fn reverse_topological_sort(&self) -> Result<Vec<N>, Cycle<N>>

Reverse topological sort: dependents first, dependencies last. Used for drop ordering (drop the index before the table it indexes).

pub fn edges(&self) -> impl Iterator<Item = (&N, &N)>

Iterate all edges as (from, to) pairs in ascending (from, to) order by Ord.

impl Graph<NodeId>

pub fn add_dep_edge(&mut self, from: NodeId, to: NodeId, source: DepSource)

Add an edge from -> to and record its DepSource.

If an edge between these two nodes already exists (inserted via Graph::add_edge or a prior call to this method), the source is overwritten with the new value. Both endpoints are added as nodes if not already present.

Use this instead of Graph::add_edge when populating v0.2 edges from AST walks (AstExtracted) or -- @pgevolve dep: directives (AstDeclared).

pub fn remove_dep_edge(&mut self, from: &NodeId, to: &NodeId)

Remove an edge from -> to and its DepSource from the source map. No-op if the adjacency (or source entry) is absent.

Prefer this over Graph::remove_edge whenever the edge may have been inserted via Self::add_dep_edge; it prevents stale provenance from surviving a remove-then-re-add cycle.

pub fn dep_edges(&self) -> impl Iterator<Item = DepEdge> + '_

Iterate edges as DepEdge records with per-edge provenance.

Edges inserted via Self::add_dep_edge carry their recorded DepSource. Edges inserted via Graph::add_edge default to DepSource::Structural, preserving v0.1 behaviour.

Trait Implementations

impl<N: Clone> 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> Debug for Graph<N>

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

Formats the value using the given formatter.

impl<N> Default for Graph<N>

where N: Hash + Eq + Clone + Ord,

fn default() -> Self

Returns the “default value” for a type.