Struct Graph 

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

Graph.

This data type represents a directed graph with nodes of type T, which is optimized for very efficient traversal, since it offers lookups of nodes and edges in O(1), i.e., constant time. It’s built with the Graph::builder method, which allows to add nodes and edges, before building the graph.

Note that this graph implementation is unweighted, which means edges do not carry associated weights, something that we don’t need for our case.

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

// 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)?;
}

Implementations

impl<T> Graph<T>

pub fn builder<W>() -> Builder<T, W>

where W: Clone,

Creates a graph builder.

Examples

use zrx_graph::Graph;

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

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

pub fn empty() -> Self

Creates an empty graph.

While an empty graph is not very useful, it’s sometimes practical as a placeholder in documentation or examples, where a graph is expected.

Examples

use zrx_graph::Graph;

// Create empty graph
let graph = Graph::empty();
assert!(graph.is_empty());

pub fn map<F, U>(self, f: F) -> Graph<U>

where F: FnMut(T) -> U,

Maps the nodes to a different type.

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

// Create graph from builder and map data
let graph = builder.build();
graph.map(str::to_uppercase);

pub fn traverse<I>(&self, initial: I) -> Traversal

where I: IntoIterator<Item = usize>,

Creates a topogical traversal starting from the given initial nodes.

This method creates a topological traversal of the graph, which allows to visit nodes in a topological order, i.e., visiting a node only after all its dependencies have been visited. The traversal is initialized with the given initial nodes, which are the starting points.

Note that an arbitrary number of parallel traversals can be created from the same graph, as the underlying topology is shared between them.

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

// 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 sources(&self) -> impl Iterator<Item = usize>

Creates an iterator over the sources of the graph.

This method returns an iterator over the source node indices of the graph, which are the nodes with no incoming edges.

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

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

// Create iterator over sources
for node in graph.sources() {
    println!("{node:?}");
}

pub fn sinks(&self) -> impl Iterator<Item = usize>

Creates an iterator over the sinks of the graph.

This method returns an iterator over the sink node indices of the graph, which are the nodes with no incoming edges.

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

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

// Create iterator over sinks
for node in graph.sinks() {
    println!("{node:?}");
}

pub fn ancestors(&self, node: usize) -> Ancestors<'_>

Creates an iterator over the ancestors of the given 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, 0)?;
builder.add_edge(b, c, 0)?;

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

// Create iterator over ancestors
for node in graph.ancestors(c) {
    println!("{node:?}");
}

pub fn descendants(&self, node: usize) -> Descendants<'_>

Creates an iterator over the descendants of the given 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, 0)?;
builder.add_edge(b, c, 0)?;

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

// Create iterator over descendants
for node in graph.descendants(a) {
    println!("{node:?}");
}

pub fn paths(&self, source: usize, target: usize) -> Paths<'_>

Creates an iterator over all paths between the given nodes.

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

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

// Create iterator over paths
for path in graph.paths(a, c) {
    println!("{path:?}");
}

pub fn iter(&self) -> Iter<'_, T>

Creates an iterator over the graph.

This iterator yields the data T associated with each node. If you need to iterate over the node indices of a graph, use Graph::topology to obtain the Topology::incoming or Topology::outgoing adjacency list, and iterate over those.

Examples

use zrx_graph::topology::Adjacency;
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, 0)?;
builder.add_edge(b, c, 0)?;

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

// Create iterator over data
for data in graph.iter() {
    println!("{data:?}");
}

impl<T> Graph<T>

pub fn topology(&self) -> &Topology

Returns the graph topology.

pub fn len(&self) -> usize

Returns the number of nodes.

pub fn is_empty(&self) -> bool

Returns whether there are any nodes.

Trait Implementations

impl<T: Clone> Clone for Graph<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for Graph<T>

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

Formats the value using the given formatter.

impl<T> Index<usize> for Graph<T>

fn index(&self, index: usize) -> &Self::Output

Returns a reference to the node at the index.

Panics

Panics if the index is out of bounds.

Examples

use zrx_graph::topology::Adjacency;
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, 0)?;
builder.add_edge(b, c, 0)?;

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

// Obtain references to nodes
assert_eq!(&graph[a], &"a");
assert_eq!(&graph[b], &"b");
assert_eq!(&graph[c], &"c");

type Output = T

The returned type after indexing.

impl<T> IndexMut<usize> for Graph<T>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Returns a mutable reference to the node at the index.

Panics

Panics if the index is out of bounds.

Examples

use zrx_graph::topology::Adjacency;
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, 0)?;
builder.add_edge(b, c, 0)?;

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

// Obtain mutable references to nodes
assert_eq!(&mut graph[a], &mut "a");
assert_eq!(&mut graph[b], &mut "b");
assert_eq!(&mut graph[c], &mut "c");

impl<'a, T> IntoIterator for &'a Graph<T>

fn into_iter(self) -> Self::IntoIter

Creates an iterator over the graph.

This iterator yields the data T associated with each node. If you need to iterate over the node indices of a graph, use Graph::topology to obtain the Topology::incoming or Topology::outgoing adjacency list, and iterate over those.

Examples

use zrx_graph::topology::Adjacency;
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, 0)?;
builder.add_edge(b, c, 0)?;

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

// Create iterator over data
for data in &graph {
    println!("{data:?}");
}

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?