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

If the node has already been marked as visited, Error::Completed is returned. This is likely an error in the caller’s 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)?;
}

pub fn converge(&mut self, other: Self) -> Result

Attempts to converge with the given traversal.

This method attempts to merge both traversals into a single traversal, which is possible when they have common descendants, a condition that is always true for directed acyclic graphs with a single component. There are several cases to consider when converging two traversals:

• If traversals start from the same set of source nodes, they already converged, so we just restart the traversal at these source nodes.

• If traversals start from different source nodes, yet both have common descendants, we converge at the first layer of common descendants, as all descendants of them must be revisited in the combined traversal. Ancestors of the common descendants that have already been visited in either traversal don’t need to be revisited, and thus are carried over from both traversals in their current state.

• If traversals are disjoint, they can’t be converged, so we return the given traversal back to the caller wrapped in Error::Disjoint.

Errors

If the given traversal is from a different graph, Error::Mismatch is returned. Otherwise, if the traversals are disjoint, the traversal is returned back to the caller wrapped in Error::Disjoint, so the caller can decide how to proceed.

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, c)?;
builder.add_edge(b, c)?;

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

// Create topological traversal
let mut traversal = graph.traverse([a]);

// Converge with another topological traversal
let mut other = graph.traverse([b]);
assert!(traversal.converge(other).is_ok());

impl Traversal

pub fn topology(&self) -> &Topology

Returns a reference to the graph topology.

pub fn initial(&self) -> &[usize]

Returns a reference to the initial nodes.

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 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?