Struct Dag 

pub struct Dag<N> {
    nodes: Vec<NodeSlot<N>>,
    edges: Vec<EdgeSlot>,
    free_nodes: Vec<u32>,
    free_edges: Vec<u32>,
    live: usize,
    visited: Vec<u32>,
    stamp: u32,
    stack: Vec<u32>,
    plan_stack: Vec<(u32, bool)>,
    order: Vec<u32>,
}

A directed acyclic graph whose edges may not close a cycle.

Slots are recycled: removing a node frees its slot, and a later insertion reuses it. Neither the node array nor the walk stamps shrink, so a graph that once held many nodes keeps scanning that many: memory is bounded by the peak number of nodes held at once, not by the number held now.

Fields

nodes: Vec<NodeSlot<N>>

edges: Vec<EdgeSlot>

free_nodes: Vec<u32>

Slots holding no node, to be handed out by Dag::insert.

free_edges: Vec<u32>

Edge slots holding no edge, to be handed out by Dag::add_edge.

live: usize

How many slots hold a node.

visited: Vec<u32>

Per-slot stamp of the most recent walk that visited it. A walk takes a fresh stamp rather than clearing this, so a traversal after the array has grown allocates nothing.

stamp: u32

The stamp visited presently records.

stack: Vec<u32>

Reused stack of slot indices for the plain depth-first walks.

plan_stack: Vec<(u32, bool)>

Reused stack for the post-order walk, where a slot is pushed once to be visited and once more — flagged true — to be emitted.

order: Vec<u32>

Reused list of the slots a plan selected, in the order it selected them.

Implementations

impl<N> Dag<N>

pub fn new() -> Self

Create an empty graph.

pub fn len(&self) -> usize

Number of nodes in the graph.

pub fn is_empty(&self) -> bool

Whether the graph holds no nodes.

pub fn insert(&mut self, weight: N) -> NodeId

Add weight as a node and return a handle to it.

Reusing a freed slot bumps its generation, so handles to the node that occupied the slot before stop resolving.

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

Every live node, as its handle and its weight, in slot order.

Slots are recycled, so the order is by slot rather than by insertion: a node that reused a freed slot appears where that slot is. The walk covers the whole node array, so it costs the peak number of nodes the graph ever held rather than the number it holds now.

pub fn get(&self, id: NodeId) -> Option<&N>

Borrow the weight of the node id names.

pub fn get_mut(&mut self, id: NodeId) -> Option<&mut N>

Mutably borrow the weight of the node id names.

pub fn add_edge(&mut self, from: NodeId, to: NodeId) -> Result<bool, EdgeError>

Record that to depends on from, and report whether this call recorded it.

Refused when either handle does not resolve, when both name the same node, or when the edge would close a cycle. Declaring an existing dependency again is a no-op rather than a second edge, so Dag::dependencies never yields the same node twice; such a repeat returns Ok(false), and only the call that recorded the edge returns Ok(true).

pub fn dependencies(&self, id: NodeId) -> impl Iterator<Item = NodeId> + '_

The nodes id depends on, in unspecified order.

Empty when the handle does not resolve.

pub fn for_each_dependent_mut(&mut self, id: NodeId, f: impl FnMut(&mut N))

Apply f to id and to every node reachable from it by following dependents.

Only the reachable nodes are visited. A handle that does not resolve visits nothing.

pub fn remove_where_drop(&mut self, is_dead: impl Fn(&N) -> bool) -> usize

Remove every node is_dead reports, and return how many were removed.

A node is dropped with the weights of the nodes that depend on it still in place, so a weight whose drop releases something another node was waiting for only shows up on the next call: a caller that has to reach a fixpoint sweeps until this reports 0.

pub fn topological_order(&self) -> Vec<NodeId>

Every node, ordered so that a node always follows the nodes it depends on.

Nodes that do not depend on one another come in an unspecified order. The graph refuses every edge that would close a cycle, so every node is listed.

fn remove(&mut self, id: NodeId) -> Option<N>

Remove the node id names together with every edge touching it, and return its weight.

Internal: callers go through Dag::remove_where_drop, which selects what to remove without needing a handle the caller may no longer hold.

fn resolve(&self, id: NodeId) -> Option<usize>

Resolve a handle to a slot index, or None when it names no node.

A handle names both a slot and the generation it was in, so a handle whose node was removed — and whose slot was perhaps reused — resolves to nothing rather than to the slot’s current occupant.

fn node_id(&self, index: u32) -> NodeId

Build the handle for a live slot, in the generation the slot is in.

fn has_edge(&self, from: usize, to: usize) -> bool

Whether to depends on from, both already resolved to slot indices.

fn incident<'a>( &'a self, id: NodeId, select: impl Fn(&'a NodeSlot<N>) -> &'a Vec<u32>, ) -> impl Iterator<Item = u32> + 'a

The edge list slot selects, or an empty one when id does not resolve.

fn reaches(&mut self, start: usize, target: usize) -> bool

Whether following dependents from start reaches target.

fn plan_dependents(&mut self, root: NodeId)

Fill Dag::order with root and every node reachable from it by following dependents, in dependency order.

The list is built before the caller acts on it, so a weight mutated as the walk proceeds cannot disturb it.

fn next_stamp(&mut self) -> u32

Take a stamp that no mark in visited carries yet, growing the array to cover the nodes if needed.

Trait Implementations

impl<N: Debug> Debug for Dag<N>

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

Formats the value using the given formatter.

impl<N> Default for Dag<N>

fn default() -> Self

Returns the “default value” for a type.