Struct Graph 

pub struct Graph { /* private fields */ }

A directed acyclic graph of named nodes.

The invariant — unique ids, edges between nodes that exist, no cycles — is upheld by the constructors, so topological_sort cannot fail. Adjacency is computed on the fly: O(n) where it could be O(1), deliberately.

Implementations

impl Graph

pub fn new() -> Self

An empty graph.

pub fn add_node(&mut self, id: impl Into<NodeId>) -> Result<&NodeId, GraphError>

Adds a node, unless the id is taken.

pub fn add_edge( &mut self, source: impl Into<NodeId>, target: impl Into<NodeId>, ) -> Result<&Edge, GraphError>

Connects two nodes that exist, unless the edge is already there or would close a cycle.

pub fn free_id(&self, wanted: &str) -> NodeId

A free id starting from the one you want, suffixing _2, _3, … if needed.

pub fn nodes(&self) -> &[NodeId]

The nodes, in insertion order.

pub fn edges(&self) -> &[Edge]

The edges, in insertion order.

pub fn len(&self) -> usize

How many nodes there are.

pub fn is_empty(&self) -> bool

true while the graph has no nodes.

pub fn contains(&self, id: &NodeId) -> bool

Whether the id names a node of this graph.

pub fn predecessors(&self, id: &NodeId) -> Vec<&NodeId>

The nodes feeding into id, in their edges’ insertion order.

pub fn successors(&self, id: &NodeId) -> Vec<&NodeId>

The nodes id feeds into, in their edges’ insertion order.

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

The nodes without predecessors: where execution enters.

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

The nodes without successors: where it leaves.

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

The nodes in an order where each comes after its predecessors. Ties break by insertion order, so it is deterministic.

Trait Implementations

impl Clone for Graph

fn clone(&self) -> Graph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Graph

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

Formats the value using the given formatter.

impl Default for Graph

fn default() -> Graph

Returns the “default value” for a type.

impl PartialEq for Graph

fn eq(&self, other: &Graph) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for Graph

impl StructuralPartialEq for Graph