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 implementation is heavily opinionated – it does not support edge weights or undirected edges, as it’s built solely for our own purposes. It does by no means attempt to be a general-purpose graph library. For this, please refer to libraries such as petgraph.

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

Implementations

impl<T> Graph<T>

pub fn builder() -> Builder<T>

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

impl<T> Graph<T>

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

Creates an iterator over the ancestors of the given node.

Panics

Panics if the node does not exist, as this indicates that there’s a bug in the code that creates or uses the iterator. 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 iterator over ancestors
for node in graph.ancestors(c) {
    println!("{node:?}");
}

impl<T> Graph<T>

pub fn common_ancestors<N>(&self, nodes: N) -> CommonAncestors<'_>

where N: AsRef<[usize]>,

Creates an iterator over the common ancestors of the set of nodes.

This method creates an iterator over the common ancestores of a given set of nodes, and emits them in layers, starting with the lowest common ancestors (LCA). In directed acyclic graphs, nodes might have multiple common ancestors, since there can be multiple paths leading to the nodes in the provided set. The iterator peels these common ancestors layer by layer, emitting all sinks among the remaining nodes at each step.

Panics

Panics if a node does not exist, as this indicates that there’s a bug in the code that creates or uses the iterator. 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(a, c)?;

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

// Create iterator over common ancestors
for nodes in graph.common_ancestors([b, c]) {
    println!("{nodes:?}");
}

impl<T> Graph<T>

pub fn common_descendants<N>(&self, nodes: N) -> CommonDescendants<'_>

where N: AsRef<[usize]>,

Creates an iterator over the common descendants of the set of nodes.

Panics

Panics if a node does not exist, as this indicates that there’s a bug in the code that creates or uses the iterator. 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(a, c)?;

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

// Create iterator over common descendants
for nodes in graph.common_descendants([a]) {
    println!("{nodes:?}");
}

impl<T> Graph<T>

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

Creates an iterator over the descendants of the given node.

Panics

Panics if the node does not exist, as this indicates that there’s a bug in the code that creates or uses the iterator. 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 iterator over descendants
for node in graph.descendants(a) {
    println!("{node:?}");
}

impl<T> Graph<T>

pub fn filter_sinks<N>(&self, nodes: N) -> FilterSinks<'_>

where N: Into<Vec<usize>>,

Creates an iterator over the sinks in the given set of nodes.

This method creates a view over the provided set of nodes, representing an embedded subgraph, and emits only those nodes that are sinks within this subgraph. Sinks are nodes that do not have outgoing edges to other nodes in the given set.

Panics

Panics if a node does not exist, as this indicates that there’s a bug in the code that creates or uses the iterator. 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 iterator over sinks
for node in graph.filter_sinks([a, b]) {
    println!("{node:?}");
}

impl<T> Graph<T>

pub fn filter_sources<N>(&self, nodes: N) -> FilterSources<'_>

where N: Into<Vec<usize>>,

Creates an iterator over the sources in the given set of nodes.

This method creates a view over the provided set of nodes, representing an embedded subgraph, and emits only those nodes that are sources within this subgraph. Sources are nodes that do not have incoming edges from other nodes in the given set.

Panics

Panics if a node does not exist, as this indicates that there’s a bug in the code that creates or uses the iterator. 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 iterator over sources
for node in graph.filter_sources([b, c]) {
    println!("{node:?}");
}

impl<T> Graph<T>

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

Creates an iterator over the paths between the given nodes.

Panics

Panics if the node does not exist, as this indicates that there’s a bug in the code that creates or uses the iterator. 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 iterator over paths
for path in graph.paths(a, c) {
    println!("{path:?}");
}

impl<T> Graph<T>

pub fn sinks(&self) -> Sinks<'_>

Creates an iterator over the sinks.

This method returns an iterator over the sink node indices of the graph, which are the nodes with no outgoing 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)?;
builder.add_edge(b, c)?;

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

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

impl<T> Graph<T>

pub fn sources(&self) -> Sources<'_>

Creates an iterator over the sources.

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

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

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

impl<T> Graph<T>

pub fn adjacent(&self, node: usize) -> (&T, Adjacent<'_>)

Retrieve a reference to a node and its adjacent 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)?;
builder.add_edge(b, c)?;

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

// Obtain reference to node and adjacent nodes
let (data, adj) = graph.adjacent(a);

pub fn adjacent_mut(&mut self, node: usize) -> (&mut T, Adjacent<'_>)

Retrieve a mutable reference to a node and its adjacent 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)?;
builder.add_edge(b, c)?;

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

// Obtain mutable reference to node and adjacent nodes
let (data, adj) = graph.adjacent_mut(a);

impl<T> Graph<T>

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

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

impl<T> Graph<T>

pub fn is_source(&self, node: usize) -> bool

Returns whether the given node is a source.

Panics

Panics if the node does not exist.

Examples

use zrx_graph::{Graph, Topology};

// 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();

// Ensure nodes are sources (or not)
assert_eq!(graph.is_source(a), true);
assert_eq!(graph.is_source(b), false);
assert_eq!(graph.is_source(c), false);

pub fn is_sink(&self, node: usize) -> bool

Returns whether the given node is a sink.

Panics

Panics if the node does not exist.

Examples

use zrx_graph::{Graph, Topology};

// 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();

// Ensure nodes are sinks (or not)
assert_eq!(graph.is_sink(a), false);
assert_eq!(graph.is_sink(b), false);
assert_eq!(graph.is_sink(c), true);

pub fn is_ancestor(&self, source: usize, target: usize) -> bool

Returns whether the source node is an ancestor of the target node.

Panics

Panics if the node does not exist.

Examples

use zrx_graph::{Graph, Topology};

// 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();

// Ensure nodes are ancestors (or not)
assert_eq!(graph.is_ancestor(a, b), true);
assert_eq!(graph.is_ancestor(a, c), true);
assert_eq!(graph.is_ancestor(b, a), false);

pub fn is_descendant(&self, source: usize, target: usize) -> bool

Returns whether the source node is a descendant of the target node.

Panics

Panics if the node does not exist.

Examples

use zrx_graph::{Graph, Topology};

// 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();

// Ensure nodes are descendants (or not)
assert_eq!(graph.is_descendant(b, a), true);
assert_eq!(graph.is_descendant(c, a), true);
assert_eq!(graph.is_descendant(a, b), false);

pub fn is_predecessor(&self, source: usize, target: usize) -> bool

Returns whether the source node is a predecessor of the target node.

Panics

Panics if the node does not exist.

Examples

use zrx_graph::{Graph, Topology};

// 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();

// Ensure nodes are predecessors (or not)
assert_eq!(graph.is_predecessor(a, b), true);
assert_eq!(graph.is_predecessor(a, c), false);
assert_eq!(graph.is_predecessor(b, a), false);

pub fn is_successor(&self, source: usize, target: usize) -> bool

Returns whether the source node is a successor of the target node.

Panics

Panics if the node does not exist.

Examples

use zrx_graph::{Graph, Topology};

// 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();

// Ensure nodes are successors (or not)
assert_eq!(graph.is_successor(b, a), true);
assert_eq!(graph.is_successor(c, a), false);
assert_eq!(graph.is_successor(a, b), false);

impl<T> Graph<T>

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

where I: AsRef<[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 of 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)?;
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 iter(&self) -> Range<usize>

Creates an iterator over the graph.

This iterator emits the node indices, which is exactly the same as iterating over the adjacency list using 0..self.len().

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

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

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

impl<T> Graph<T>

pub fn topology(&self) -> &Topology

Returns a reference to 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> AsRef<[T]> for Graph<T>

fn as_ref(&self) -> &[T]

Returns the graph data as a slice.

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> Default for Graph<T>

fn default() -> Self

Creates an empty graph.

While an empty graph is not very useful, it’s sometimes practical as a placeholder in documentation, and in types implementing Default.

Examples

use zrx_graph::Graph;

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

impl<T> From<Builder<T>> for Graph<T>

fn from(builder: Builder<T>) -> Self

Creates a graph from a builder.

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 = Graph::from(builder);

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

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

// 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<T> IntoIterator for &Graph<T>

fn into_iter(self) -> Self::IntoIter

Creates an iterator over the graph.

This iterator emits the node indices, which is exactly the same as iterating over the adjacency list using 0..self.len().

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

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

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

type Item = usize

The type of the elements being iterated over.

type IntoIter = Range<usize>

Which kind of iterator are we turning this into?