Struct Traversal 

pub struct Traversal { /* private fields */ }

Topological traversal.

This data type manages a topological traversal of a directed acyclic graph (DAG). It allows visiting nodes in a way that respects their dependencies, meaning that a node can only be visited after all of its dependencies have been visited. Visitable nodes can be obtained with Traversal::take.

Note that the traversal itself doesn’t know whether it’s complete or not, as it only tracks visitable nodes depending on what has been reported back to Traversal::complete. This is because we also need to support partial traversals that can be resumed, which must be managed by the caller. In case a traversal starts at an intermediate node, only the nodes and dependencies reachable from this node are considered, which is necessary for implementing subgraph traversals that are self-contained, allowing for the creation of frontiers at any point in the graph.

Implementations

impl Traversal

pub fn new<I>(topology: &Topology, initial: I) -> Self

where I: AsRef<[usize]>,

Creates a topological traversal.

The given initial nodes are immediately marked as visitable, and thus returned by Traversal::take, so the caller must make sure they can be processed. Note that the canonical way to create a Traversal is to invoke the Graph::traverse method.

Examples

use zrx_graph::{Graph, Traversal};

// Create graph builder and add nodes
let mut builder = Graph::builder();
let a = builder.add_node("a");
let b = builder.add_node("b");
let c = builder.add_node("c");

// Create edges between nodes
builder.add_edge(a, b)?;
builder.add_edge(b, c)?;

// Create graph from builder
let graph = builder.build();

// Create topological traversal
let traversal = Traversal::new(graph.topology(), [a]);

pub fn take(&mut self) -> Option<usize>

Returns the next visitable node.

Examples

use zrx_graph::Graph;

// Create graph builder and add nodes
let mut builder = Graph::builder();
let a = builder.add_node("a");
let b = builder.add_node("b");
let c = builder.add_node("c");

// Create edges between nodes
builder.add_edge(a, b)?;
builder.add_edge(b, c)?;

// Create graph from builder
let graph = builder.build();

// Create topological traversal
let mut traversal = graph.traverse([a]);
while let Some(node) = traversal.take() {
    println!("{node:?}");
    traversal.complete(node)?;
}

pub fn complete(&mut self, node: usize) -> Result

Marks the given node as visited.

This method marks a node as visited as part of a traversal, which might allow visiting dependent nodes when all of their dependencies have been satisfied. After marking a node as visited, the next nodes that can be visited can be obtained using the Traversal::take method.

Errors

In case the node has already been marked as visited, Error::Found is returned. This is likely an error in the traversal business logic.

Panics

Panics if a node does not exist, as this indicates that there’s a bug in the code that creates or uses the traversal. While the Builder is designed to be fallible to ensure the structure is valid, methods that operate on Graph panic on violated invariants.

Examples

use zrx_graph::Graph;

// Create graph builder and add nodes
let mut builder = Graph::builder();
let a = builder.add_node("a");
let b = builder.add_node("b");
let c = builder.add_node("c");

// Create edges between nodes
builder.add_edge(a, b)?;
builder.add_edge(b, c)?;

// Create graph from builder
let graph = builder.build();

// Create topological traversal
let mut traversal = graph.traverse([a]);
while let Some(node) = traversal.take() {
    println!("{node:?}");
    traversal.complete(node)?;
}

impl Traversal

pub fn topology(&self) -> &Topology

Returns the graph topology.

pub fn len(&self) -> usize

Returns the number of visitable nodes.

pub fn is_empty(&self) -> bool

Returns whether there are any visitable nodes.

Trait Implementations

impl Clone for Traversal

fn clone(&self) -> Traversal

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Traversal

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

Formats the value using the given formatter.

impl IntoIterator for Traversal

fn into_iter(self) -> Self::IntoIter

Creates a consuming iterator over the topological traversal.

This consumes the traversal and produces an iterator that automatically completes each node after emitting it, allowing for convenient use in for loops and iterator chains.

Examples

use zrx_graph::Graph;

// Create graph builder and add nodes
let mut builder = Graph::builder();
let a = builder.add_node("a");
let b = builder.add_node("b");
let c = builder.add_node("c");

// Create edges between nodes
builder.add_edge(a, b)?;
builder.add_edge(b, c)?;

// Create graph from builder
let graph = builder.build();

// Create iterator over topological traversal
for node in graph.traverse([a]) {
    println!("{node:?}");
}

type Item = usize

The type of the elements being iterated over.

type IntoIter = IntoIter

Which kind of iterator are we turning this into?