Struct DAG 

pub struct DAG<N, E, H = RandomState> { /* private fields */ }

Data structure for maintaining a directed-acyclic graph (DAG) with topological ordering, maintained in an incremental fashion.

When iterating over edges or their associated data, the order is the insertion order.

See the module-level documentation for more information.

Implementations

impl<N, E> DAG<N, E>

pub fn new() -> Self

Create a new DAG.

Examples

use pie_graph::DAG;
let dag = DAG::<(), ()>::new();

assert!(dag.is_empty());

impl<N, E, H: BuildHasher + Default> DAG<N, E, H>

pub fn add_node(&mut self, data: N) -> Node

Add a new node with data to the graph and return a unique Node which identifies it.

Initially this node will not have any order relative to the nodes that are already in the graph. Only when relations are added with add_dependency will the order begin to matter.

Examples

use pie_graph::DAG;
let mut dag = DAG::<(), ()>::new();

let cat = dag.add_node(());
let dog = dag.add_node(());
let mouse = dag.add_node(());
let human = dag.add_node(());

assert_ne!(cat, dog);
assert_ne!(cat, mouse);
assert_ne!(cat, human);
assert_ne!(dog, mouse);
assert_ne!(dog, human);
assert_ne!(mouse, human);

assert!(dag.contains_node(&cat));
assert!(dag.contains_node(&dog));
assert!(dag.contains_node(&mouse));
assert!(dag.contains_node(&human));

pub fn contains_node(&self, node: impl Borrow<Node>) -> bool

Returns true if the graph contains the specified node.

Examples

use pie_graph::DAG;
let mut dag = DAG::<(), ()>::new();

let cat = dag.add_node(());
let dog = dag.add_node(());

assert!(dag.contains_node(cat));
assert!(dag.contains_node(dog));

pub fn get_node_data(&self, node: impl Borrow<Node>) -> Option<&N>

Gets data for given node.

pub fn get_node_data_mut(&mut self, node: impl Borrow<Node>) -> Option<&mut N>

Gets mutable data for given node.

pub fn remove_node(&mut self, node: Node) -> bool

Attempt to remove node from graph, returning true if the node was contained and removed.

Examples

use pie_graph::DAG;
let mut dag = DAG::<(), ()>::new();

let cat = dag.add_node(());
let dog = dag.add_node(());

assert!(dag.remove_node(cat));
assert!(dag.remove_node(dog));

assert!(!dag.remove_node(cat));
assert!(!dag.remove_node(dog));

pub fn add_edge( &mut self, src: impl Borrow<Node>, dst: impl Borrow<Node>, data: E, ) -> Result<bool, Error>

Add a directed edge from src to dst with edge data.

This edge indicates an ordering constraint on the two nodes, now src must always come before dst in the ordering.

Returns Ok(true) if the graph did not previously contain this edge. Returns Ok(false) if the graph did have a previous edge between these two nodes.

Errors

Returns an Err if the edge introduces a cycle or if either of the given nodes is not found in the graph.

Examples

use pie_graph::DAG;
let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert!(dag.add_edge(&human, dog, ()).unwrap());
assert!(dag.add_edge(&human, cat, ()).unwrap());
assert!(dag.add_edge(&cat, mouse, ()).unwrap());

Here is an example which returns Error::CycleDetected when introducing a cycle:

let mut dag = DAG::new();

let n0 = dag.add_node(());
assert_eq!(dag.add_edge(&n0, &n0, ()), Err(Error::CycleDetected));

let n1 = dag.add_node(());

assert!(dag.add_edge(&n0, &n1, ()).unwrap());
assert_eq!(dag.add_edge(&n1, &n0, ()), Err(Error::CycleDetected));

let n2 = dag.add_node(());

assert!(dag.add_edge(&n1, &n2, ()).unwrap());
assert_eq!(dag.add_edge(&n2, &n0, ()), Err(Error::CycleDetected));

pub fn contains_edge( &self, src: impl Borrow<Node>, dst: impl Borrow<Node>, ) -> bool

Returns true if the graph contains an edge from src to dst.

Returns false if either node is not found, or if there is no dependency.

Examples

use pie_graph::DAG;
let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let human = dag.add_node(());
let horse = dag.add_node(());

assert!(dag.add_edge(&human, &cat, ()).unwrap());
assert!(dag.add_edge(&cat, &mouse, ()).unwrap());

assert!(dag.contains_edge(&cat, &mouse));
assert!(!dag.contains_edge(&human, &mouse));
assert!(!dag.contains_edge(&cat, &horse));

pub fn contains_transitive_edge( &self, src: impl Borrow<Node>, dst: impl Borrow<Node>, ) -> bool

Returns true if the graph contains a transitive edge from src to dst.

In this context a transitive dependency means that succ exists as a descendant of pred, with some chain of other nodes in between.

Returns false if either node is not found in the graph, or there is no transitive dependency.

Examples

use pie_graph::DAG;
let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert!(dag.add_edge(&human, &cat, ()).unwrap());
assert!(dag.add_edge(&human, &dog, ()).unwrap());
assert!(dag.add_edge(&cat, &mouse, ()).unwrap());

assert!(dag.contains_transitive_edge(&human, &mouse));
assert!(!dag.contains_transitive_edge(&dog, &mouse));

pub fn get_edge_data( &self, src: impl Borrow<Node>, dst: impl Borrow<Node>, ) -> Option<&E>

Gets data for the edge from src to dst.

pub fn get_edge_data_mut( &mut self, src: impl Borrow<Node>, dst: impl Borrow<Node>, ) -> Option<&mut E>

Gets mutable data for the edge from src to dst.

pub fn get_outgoing_edges( &self, src: impl Borrow<Node>, ) -> impl Iterator<Item = (&Node, &E)> + '_

Gets the destination nodes and edge data for all outgoing edges of src.

pub fn get_outgoing_edge_nodes( &self, src: impl Borrow<Node>, ) -> impl Iterator<Item = &Node>

Gets the destination nodes of all outgoing edges of src.

pub fn get_outgoing_edge_data( &self, src: impl Borrow<Node>, ) -> impl Iterator<Item = &E> + '_

Gets the edge data for all outgoing edges of src.

pub fn get_outgoing_edge_node_data( &self, src: impl Borrow<Node>, ) -> impl Iterator<Item = &N> + '_

Gets the destination node data for all outgoing edges of src.

pub fn get_incoming_edges( &self, dst: impl Borrow<Node>, ) -> impl Iterator<Item = (&Node, &E)> + '_

Gets the source node and edge data for all incoming edges of dst.

pub fn get_incoming_edge_nodes( &self, dst: impl Borrow<Node>, ) -> impl Iterator<Item = &Node> + '_

Gets the source nodes for all incoming edges of dst.

pub fn get_incoming_edge_data( &self, dst: impl Borrow<Node>, ) -> impl Iterator<Item = &E> + '_

Gets the edge data for all incoming edges of dst.

pub fn get_incoming_edge_node_data( &self, dst: impl Borrow<Node>, ) -> impl Iterator<Item = &N> + '_

Gets the source node data for all incoming edges of dst.

pub fn remove_edge( &mut self, src: impl Borrow<Node>, dst: impl Borrow<Node>, ) -> Option<E>

Attempt to remove the edge from src to dst from the graph, returning Some(edge_data) if the edge was removed, or None otherwise.

Returns false is either node is not found in the graph.

Removing an edge from the graph is an extremely simple operation, which requires no recalculation of the topological order. The ordering before and after a removal is exactly the same.

Examples

use pie_graph::DAG;
let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert!(dag.add_edge(&human, &cat, ()).unwrap());
assert!(dag.add_edge(&human, &dog, ()).unwrap());
assert!(dag.add_edge(&cat, &mouse, ()).unwrap());

assert!(dag.remove_edge(&cat, mouse).is_some());
assert!(dag.remove_edge(&human, dog).is_some());
assert!(dag.remove_edge(&human, mouse).is_none());

pub fn remove_outgoing_edges_of_node( &mut self, src: impl Borrow<Node>, ) -> Option<Vec<(Node, E)>>

Attempt to remove all outgoing edges of src from the graph, returning Some(edge_data) if any edges were removed, or None if the node does not exist or does not have any edges.

pub fn len(&self) -> usize

Return the number of nodes within the graph.

Examples

use pie_graph::DAG;
let mut dag = DAG::<(), ()>::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert_eq!(dag.len(), 4);

pub fn is_empty(&self) -> bool

Return true if there are no nodes in the graph.

Examples

use pie_graph::DAG;
let mut dag = DAG::<(), ()>::new();

assert!(dag.is_empty());

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert!(!dag.is_empty());

pub fn iter_unsorted(&self) -> impl Iterator<Item = (u32, Node)> + '_

Return an iterator over all the nodes of the graph in an unsorted order.

Examples

use pie_graph::DAG;
use std::collections::HashSet;
let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert!(dag.add_edge(&human, &cat, ()).unwrap());
assert!(dag.add_edge(&human, &dog, ()).unwrap());
assert!(dag.add_edge(&cat, &mouse, ()).unwrap());

let pairs = dag.iter_unsorted().collect::<HashSet<_>>();

let mut expected_pairs = HashSet::new();
expected_pairs.extend(vec![(1, human), (2, cat), (4, mouse), (3, dog)]);

assert_eq!(pairs, expected_pairs);

pub fn descendants_unsorted( &self, node: impl Borrow<Node>, ) -> Result<DescendantsUnsorted<'_, N, E, H>, Error>

Return an iterator over the descendants of a node in the graph, in an unsorted order.

Accessing the nodes in an unsorted order allows for faster access using a iterative DFS search. This is opposed to the order descendants iterator which requires the use of a binary heap to order the values.

Errors

This function will return an error if the given node is not present in the graph.

Examples

use pie_graph::DAG;
use std::collections::HashSet;
let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert!(dag.add_edge(&human, &cat, ()).unwrap());
assert!(dag.add_edge(&human, &dog, ()).unwrap());
assert!(dag.add_edge(&dog, &cat, ()).unwrap());
assert!(dag.add_edge(&cat, &mouse, ()).unwrap());

let pairs = dag
    .descendants_unsorted(human)
    .unwrap()
    .collect::<HashSet<_>>();

let mut expected_pairs = HashSet::new();
expected_pairs.extend(vec![(2, dog), (3, cat), (4, mouse)]);

assert_eq!(pairs, expected_pairs);

pub fn descendants( &self, node: impl Borrow<Node>, ) -> Result<Descendants<'_, N, E, H>, Error>

Return an iterator over descendants of a node in the graph, in a topologically sorted order.

Accessing the nodes in a sorted order requires the use of a BinaryHeap, so some performance penalty is paid there. If all is required is access to the descendants of a node, use DAG::descendants_unsorted.

Errors

This function will return an error if the given node is not present in the graph.

Examples

use pie_graph::DAG;
let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());

assert!(dag.add_edge(&human, &cat, ()).unwrap());
assert!(dag.add_edge(&human, &dog, ()).unwrap());
assert!(dag.add_edge(&dog, &cat, ()).unwrap());
assert!(dag.add_edge(&cat, &mouse, ()).unwrap());

let ordered_nodes = dag.descendants(human).unwrap().collect::<Vec<_>>();

assert_eq!(ordered_nodes, vec![dog, cat, mouse]);

pub fn topo_cmp( &self, node_a: impl Borrow<Node>, node_b: impl Borrow<Node>, ) -> Ordering

Compare two nodes present in the graph, topographically.

Examples

use pie_graph::DAG;
use std::cmp::Ordering::*;

let mut dag = DAG::new();

let cat = dag.add_node(());
let mouse = dag.add_node(());
let dog = dag.add_node(());
let human = dag.add_node(());
let horse = dag.add_node(());

assert!(dag.add_edge(&human, &cat, ()).unwrap());
assert!(dag.add_edge(&human, &dog, ()).unwrap());
assert!(dag.add_edge(&dog, &cat, ()).unwrap());
assert!(dag.add_edge(&cat, &mouse, ()).unwrap());

assert_eq!(dag.topo_cmp(&human, &mouse), Less);
assert_eq!(dag.topo_cmp(&cat, &dog), Greater);
assert_eq!(dag.topo_cmp(&cat, &horse), Less);

Trait Implementations

impl<N, E, H: BuildHasher + Default> Default for DAG<N, E, H>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, N, E, H> Deserialize<'de> for DAG<N, E, H>

where N: Deserialize<'de>, E: Deserialize<'de>, H: BuildHasher + Default,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<N, E, H> Serialize for DAG<N, E, H>

where N: Serialize, E: Serialize, H: BuildHasher + Default,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.