Struct incremental_topo::IncrementalTopo

pub struct IncrementalTopo<T: Hash + Eq, NodeId: Hash + Eq + Copy = usize> { /* fields omitted */ }

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

See the module-level documentation for more information.

Methods

impl<T: Hash + Eq> IncrementalTopo<T>

pub fn new() -> Self

Create a new IncrementalTopo graph.

Examples

use incremental_topo::IncrementalTopo;
let dag = IncrementalTopo::<usize>::new();

assert!(dag.is_empty());

pub fn add_node(&mut self, node: T) -> bool

Add a new node to the graph.

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.

Returns false if the graph already contains the node.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("dog"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));

assert!(!dag.add_node("cat"));

pub fn contains_node<Q: ?Sized>(&self, node: &Q) -> bool where
    T: Borrow<Q>,
    Q: Hash + Eq, 

Returns true if the graph contains the specified node.

The passed node may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("dog"));

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

assert!(!dag.contains_node("horse"));
assert!(!dag.contains_node("orc"));

pub fn delete_node<Q: ?Sized>(&mut self, node: &Q) -> bool where
    T: Borrow<Q>,
    Q: Hash + Eq, 

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

The passed node may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("dog"));

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

assert!(!dag.delete_node("horse"));
assert!(!dag.delete_node(&"orc"));

pub fn add_dependency<Q: ?Sized, R: ?Sized>(
    &mut self,
    prec: &Q,
    succ: &R
) -> Result<bool> where
    T: Borrow<Q> + Borrow<R>,
    Q: Hash + Eq,
    R: Hash + Eq, 

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.

The values of prec and succ may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("dog"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));

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

pub fn contains_dependency<Q: ?Sized, R: ?Sized>(
    &self,
    prec: &Q,
    succ: &R
) -> bool where
    T: Borrow<Q> + Borrow<R>,
    Q: Hash + Eq,
    R: Hash + Eq, 

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.

The values of prec and succ may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));

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<Q: ?Sized, R: ?Sized>(
    &self,
    prec: &Q,
    succ: &R
) -> bool where
    T: Borrow<Q> + Borrow<R>,
    Q: Hash + Eq,
    R: Hash + Eq, 

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.

The values of prec and succ may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));
assert!(dag.add_node("dog"));

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<Q: ?Sized, R: ?Sized>(
    &mut self,
    prec: &Q,
    succ: &R
) -> bool where
    T: Borrow<Q> + Borrow<R>,
    Q: Hash + Eq,
    R: Hash + Eq, 

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.

The values of prec and succ may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));
assert!(dag.add_node("dog"));

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 size(&self) -> usize

Return the number of nodes within the graph.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));
assert!(dag.add_node("dog"));

assert_eq!(dag.size(), 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());

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));
assert!(dag.add_node("dog"));

assert!(!dag.is_empty());

pub fn iter_unsorted(&self) -> impl Iterator<Item = (u32, &T)>

Return an iterator over the nodes of the graph

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("human"));
assert!(dag.add_node("dog"));

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"), (3, &"mouse"), (4, &"dog")]);

assert_eq!(pairs, expected_pairs);

pub fn descendants_unsorted<Q: ?Sized>(
    &self,
    node: &Q
) -> Result<DescendantsUnsorted<T>> where
    T: Borrow<Q>,
    Q: Hash + Eq, 

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

The passed node may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

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.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("dog"));
assert!(dag.add_node("human"));

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<Q: ?Sized>(&self, node: &Q) -> Result<Descendants<T>> where
    T: Borrow<Q>,
    Q: Hash + Eq, 

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

The passed node may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

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 descendants_unsorted.

Examples

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

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("dog"));
assert!(dag.add_node("human"));

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<Q: ?Sized, R: ?Sized>(
    &self,
    node_a: &Q,
    node_b: &R
) -> Result<Ordering> where
    T: Borrow<Q> + Borrow<R>,
    Q: Hash + Eq,
    R: Hash + Eq, 

Compare two nodes present in the graph, topographically. Returns Err(...) if either node is missing from the graph.

The values of prec and succ may be any borrowed form of the graph's node type, but Hash and Eq on the borrowed form must match those for the node type.

Examples

use incremental_topo::IncrementalTopo;
use std::cmp::Ordering::*;
let mut dag = IncrementalTopo::new();

assert!(dag.add_node("cat"));
assert!(dag.add_node("mouse"));
assert!(dag.add_node("dog"));
assert!(dag.add_node("human"));

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").unwrap(), Less);
assert_eq!(dag.topo_cmp("cat", "dog").unwrap(), Greater);
assert!(dag.topo_cmp("cat", "horse").is_err());

Trait Implementations

impl<T: Clone + Hash + Eq, NodeId: Clone + Hash + Eq + Copy> Clone for IncrementalTopo<T, NodeId>

fn clone(&self) -> IncrementalTopo<T, NodeId>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Default + Hash + Eq, NodeId: Default + Hash + Eq + Copy> Default for IncrementalTopo<T, NodeId>

fn default() -> IncrementalTopo<T, NodeId>

Returns the "default value" for a type.

impl<T: Debug + Hash + Eq, NodeId: Debug + Hash + Eq + Copy> Debug for IncrementalTopo<T, NodeId>

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

Formats the value using the given formatter.