Struct Dag

pub struct Dag<N> { /* private fields */ }

An incremental directed acyclic graph, however the word ‘acyclic’ is used, this structure allows the existence of cycles in the hope that they will eventually be resolved and provides APIs to report the cycles to the user of the structure.

Implementations

impl<N> Dag<N>

where N: Hash + Eq,

pub fn new() -> Self

Create a new empty DAG instance.

pub fn insert(&mut self, node: N) -> bool

Insert a new node to the graph. Returns false if the node already existed in the graph.

pub fn remove<Q>(&mut self, node: &Q) -> Option<N>

where N: Borrow<Q>, Q: Hash + Eq + ?Sized,

Remove a node from the graph. Returns the node which got removed in an Option, if the node did not exist in the first place None is returned.

pub fn connect<Q>(&mut self, v: &Q, u: &Q) -> Result<bool, Error>

where N: Borrow<Q>, Q: Hash + Eq + ?Sized,

in the graph, Ok(false) is returned if the connection already existed in the graph.

If the same node is passed for both the values of v and u then Err(Error::SelfLoop) is returned.

use interactive_dag::{Dag, Error};
let mut g = Dag::<u32>::new();
assert_eq!(g.connect(&0, &0), Err(Error::NotFound));
g.insert(0);
assert_eq!(g.connect(&0, &0), Err(Error::SelfLoop));
g.insert(1);
assert_eq!(g.connect(&0, &1), Ok(true));
assert_eq!(g.connect(&0, &1), Ok(false));

pub fn disconnect<Q>(&mut self, v: &Q, u: &Q) -> Result<bool, Error>

where N: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes an edge from the graph.

pub fn contains<Q>(&self, v: &Q) -> bool

where N: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if the graph contains the given node.

pub fn is_connected<Q>(&self, v: &Q, u: &Q) -> bool

where N: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if there is a direct edge connection v to u.

pub fn is_reachable<Q>(&self, v: &Q, u: &Q) -> bool

where N: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if there is a path from v to u.

Trait Implementations

impl<N> Default for Dag<N>

where N: Hash + Eq,

fn default() -> Self

Returns the “default value” for a type.