Struct incremental_topo::IncrementalTopo

pub struct IncrementalTopo { /* private fields */ }

Data structure for maintaining a topological ordering over a collection of elements, in an incremental fashion.

See the module-level documentation for more information.

Implementations

impl IncrementalTopo

pub fn new() -> Self

Create a new IncrementalTopo graph.

Examples

use incremental_topo::IncrementalTopo;
let dag = IncrementalTopo::new();

assert!(dag.is_empty());

pub fn add_node(&mut self) -> Node

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

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

Examples

use incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::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 incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::new();

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

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

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

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

Examples

use incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::new();

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

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

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

pub fn add_dependency(
    &mut self,
    prec: impl Borrow<Node>,
    succ: impl Borrow<Node>
) -> Result<bool, Error>

Add a directed link between two nodes already present in the graph.

This link indicates an ordering constraint on the two nodes, now prec must always come before succ in the ordering.

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

Errors

This function will return an Err if the dependency introduces a cycle into the graph or if either of the nodes passed is not found in the graph.

Examples

use incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::new();

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

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

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

let mut dag = IncrementalTopo::new();

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

let n1 = dag.add_node();

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

let n2 = dag.add_node();

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

pub fn contains_dependency(
    &self,
    prec: impl Borrow<Node>,
    succ: impl Borrow<Node>
) -> bool

Returns true if the graph contains a dependency from prec to succ.

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

Examples

use incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::new();

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

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

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

pub fn contains_transitive_dependency(
    &self,
    prec: impl Borrow<Node>,
    succ: impl Borrow<Node>
) -> bool

Returns true if the graph contains a transitive dependency from prec to succ.

In this context a transitive dependency means that succ exists as a descendant of prec, 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 incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::new();

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

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

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

pub fn delete_dependency(
    &mut self,
    prec: impl Borrow<Node>,
    succ: impl Borrow<Node>
) -> bool

Attempt to remove a dependency from the graph, returning true if the dependency was removed.

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

Removing a dependency 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 incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::new();

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

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

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

pub fn len(&self) -> usize

Return the number of nodes within the graph.

Examples

use incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::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 incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::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 = (usize, Node)> + '_

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

Examples

use incremental_topo::IncrementalTopo;
use std::collections::HashSet;
let mut dag = IncrementalTopo::new();

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

assert!(dag.add_dependency(&human, &cat).unwrap());
assert!(dag.add_dependency(&human, &dog).unwrap());
assert!(dag.add_dependency(&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<'_>, 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 incremental_topo::IncrementalTopo;
use std::collections::HashSet;
let mut dag = IncrementalTopo::new();

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

assert!(dag.add_dependency(&human, &cat).unwrap());
assert!(dag.add_dependency(&human, &dog).unwrap());
assert!(dag.add_dependency(&dog, &cat).unwrap());
assert!(dag.add_dependency(&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<'_>, 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 IncrementalTopo::descendants_unsorted.

Errors

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

Examples

use incremental_topo::IncrementalTopo;
let mut dag = IncrementalTopo::new();

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

assert!(dag.add_dependency(&human, &cat).unwrap());
assert!(dag.add_dependency(&human, &dog).unwrap());
assert!(dag.add_dependency(&dog, &cat).unwrap());
assert!(dag.add_dependency(&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 incremental_topo::IncrementalTopo;
use std::cmp::Ordering::*;

let mut dag = IncrementalTopo::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_dependency(&human, &cat).unwrap());
assert!(dag.add_dependency(&human, &dog).unwrap());
assert!(dag.add_dependency(&dog, &cat).unwrap());
assert!(dag.add_dependency(&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 Clone for IncrementalTopo

fn clone(&self) -> IncrementalTopo

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for IncrementalTopo

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

Formats the value using the given formatter.

impl Default for IncrementalTopo

fn default() -> IncrementalTopo

Returns the “default value” for a type.