Struct daggy::Dag

pub struct Dag<N, E, Ix: IndexType = DefaultIx> { /* fields omitted */ }

A Directed acyclic graph (DAG) data structure.

Dag is a thin wrapper around petgraph's Graph data structure, providing a refined API for dealing specifically with DAGs.

Note: The following documentation is adapted from petgraph's [Graph documentation] (http://bluss.github.io/petulant-avenger-graphlibrary/doc/petgraph/graph/struct.Graph.html).

Dag is parameterized over the node weight N, edge weight E and index type Ix.

NodeIndex is a type that acts as a reference to nodes, but these are only stable across certain operations. Removing nodes may shift other indices. Adding kids to the Dag keeps all indices stable, but removing a node will force the last node to shift its index to take its place.

The fact that the node indices in the Dag are numbered in a compact interval from 0 to n-1 simplifies some graph algorithms.

The Ix parameter is u32 by default. The goal is that you can ignore this parameter completely unless you need a very large Dag -- then you can use usize.

The Dag also offers methods for accessing the underlying Graph, which can be useful for taking advantage of petgraph's various graph-related algorithms.

Implementations

impl<N, E, Ix> Dag<N, E, Ix> where
    Ix: IndexType, 

pub fn new() -> Self

Create a new, empty Dag.

pub fn with_capacity(nodes: usize, edges: usize) -> Self

Create a new Dag with estimated capacity for its node and edge Vecs.

pub fn clear(&mut self)

Removes all nodes and edges from the Dag.

pub fn node_count(&self) -> usize

The total number of nodes in the Dag.

pub fn edge_count(&self) -> usize

The total number of edgees in the Dag.

pub fn graph(&self) -> &PetGraph<N, E, Ix>

Borrow the Dag's underlying PetGraph<N, Ix>. All existing indices may be used to index into this PetGraph the same way they may be used to index into the Dag.

pub fn into_graph(self) -> PetGraph<N, E, Ix>

Take ownership of the Dag and return the internal PetGraph. All existing indices may be used to index into this PetGraph the same way they may be used to index into the Dag.

pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix>

Add a new node to the Dag with the given weight.

Computes in O(1) time.

Returns the index of the new node.

Note: If you're adding a new node and immediately adding a single edge to that node from some other node, consider using the add_child or add_parent methods instead for better performance.

Panics if the Graph is at the maximum number of nodes for its index type.

pub fn add_edge(
    &mut self,
    a: NodeIndex<Ix>,
    b: NodeIndex<Ix>,
    weight: E
) -> Result<EdgeIndex<Ix>, WouldCycle<E>>

Add a new directed edge to the Dag with the given weight.

The added edge will be in the direction a -> b

Checks if the edge would create a cycle in the Graph.

If adding the edge would not cause the graph to cycle, the edge will be added and its EdgeIndex returned.

If adding the edge would cause the graph to cycle, the edge will not be added and instead a WouldCycle<E> error with the given weight will be returned.

In the worst case, petgraph's [is_cyclic_directed] (http://bluss.github.io/petulant-avenger-graphlibrary/doc/petgraph/algo/fn.is_cyclic_directed.html) function is used to check whether or not adding the edge would create a cycle.

Note: Dag allows adding parallel ("duplicate") edges. If you want to avoid this, use update_edge instead.

Note: If you're adding a new node and immediately adding a single edge to that node from some other node, consider using the add_child or add_parent methods instead for better performance.

Panics if either a or b do not exist within the Dag.

Panics if the Graph is at the maximum number of edges for its index type.

pub fn add_edges<I>(
    &mut self,
    edges: I
) -> Result<EdgeIndices<Ix>, WouldCycle<Vec<E>>> where
    I: IntoIterator<Item = (NodeIndex<Ix>, NodeIndex<Ix>, E)>, 

Adds the given directed edges to the Dag, each with their own given weight.

The given iterator should yield a NodeIndex pair along with a weight for each Edge to be added in a tuple.

If we were to describe the tuple as (a, b, weight), the connection would be directed as follows:

a -> b

This method behaves similarly to the add_edge method, however rather than checking whether or not a cycle has been created after adding each edge, it only checks after all edges have been added. This makes it a slightly more performant and ergonomic option that repeatedly calling add_edge.

If adding the edges would not cause the graph to cycle, the edges will be added and their indices returned in an EdgeIndices iterator, yielding indices for each edge in the same order that they were given.

If adding the edges would cause the graph to cycle, the edges will not be added and instead a WouldCycle<Vec<E>> error with the unused weights will be returned. The order of the returned Vec will be the reverse of the given order.

Note: Dag allows adding parallel ("duplicate") edges. If you want to avoid this, use update_edges instead.

Note: If you're adding a series of new nodes and edges to a single node, consider using the add_child or [add_parent] (./struct.Dag.html#method.add_parent) methods instead for greater convenience.

Panics if the Graph is at the maximum number of nodes for its index type.

pub fn update_edge(
    &mut self,
    a: NodeIndex<Ix>,
    b: NodeIndex<Ix>,
    weight: E
) -> Result<EdgeIndex<Ix>, WouldCycle<E>>

Update the edge from nodes a -> b with the given weight.

If the edge doesn't already exist, it will be added using the add_edge method.

Please read the add_edge for more important details.

Checks if the edge would create a cycle in the Graph.

Computes in O(t + e) time where "t" is the complexity of add_edge and e is the number of edges connected to the nodes a and b.

Returns the index of the edge, or a WouldCycle error if adding the edge would create a cycle.

Note: If you're adding a new node and immediately adding a single edge to that node from some parent node, consider using the add_child method instead for greater convenience.

Panics if the Graph is at the maximum number of nodes for its index type.

pub fn find_edge(
    &self,
    a: NodeIndex<Ix>,
    b: NodeIndex<Ix>
) -> Option<EdgeIndex<Ix>>

Find and return the index to the edge that describes a -> b if there is one.

Computes in O(e') time, where e' is the number of edges connected to the nodes a and b.

pub fn edge_endpoints(
    &self,
    e: EdgeIndex<Ix>
) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)>

Access the parent and child nodes for the given EdgeIndex.

pub fn clear_edges(&mut self)

Remove all edges.

pub fn add_parent(
    &mut self,
    child: NodeIndex<Ix>,
    edge: E,
    node: N
) -> (EdgeIndex<Ix>, NodeIndex<Ix>)

Add a new edge and parent node to the node at the given NodeIndex. Returns both the edge's EdgeIndex and the node's NodeIndex.

node -> edge -> child

Computes in O(1) time.

This is faster than using add_node and add_edge. This is because we don't have to check if the graph would cycle when adding an edge to the new node, as we know it it will be the only edge connected to that node.

Panics if the given child node doesn't exist.

Panics if the Graph is at the maximum number of edges for its index.

pub fn add_child(
    &mut self,
    parent: NodeIndex<Ix>,
    edge: E,
    node: N
) -> (EdgeIndex<Ix>, NodeIndex<Ix>)

Add a new edge and child node to the node at the given NodeIndex. Returns both the edge's EdgeIndex and the node's NodeIndex.

child -> edge -> node

Computes in O(1) time.

This is faster than using add_node and add_edge. This is because we don't have to check if the graph would cycle when adding an edge to the new node, as we know it it will be the only edge connected to that node.

Panics if the given parent node doesn't exist.

Panics if the Graph is at the maximum number of edges for its index.

pub fn node_weight(&self, node: NodeIndex<Ix>) -> Option<&N>

Borrow the weight from the node at the given index.

pub fn node_weight_mut(&mut self, node: NodeIndex<Ix>) -> Option<&mut N>

Mutably borrow the weight from the node at the given index.

pub fn raw_nodes(&self) -> RawNodes<'_, N, Ix>

Read from the internal node array.

pub fn node_weights_mut(&mut self) -> NodeWeightsMut<'_, N, Ix>

An iterator yielding mutable access to all node weights.

The order in which weights are yielded matches the order of their node indices.

pub fn edge_weight(&self, edge: EdgeIndex<Ix>) -> Option<&E>

Borrow the weight from the edge at the given index.

pub fn edge_weight_mut(&mut self, edge: EdgeIndex<Ix>) -> Option<&mut E>

Mutably borrow the weight from the edge at the given index.

pub fn raw_edges(&self) -> RawEdges<'_, E, Ix>

Read from the internal edge array.

pub fn edge_weights_mut(&mut self) -> EdgeWeightsMut<'_, E, Ix>

An iterator yielding mutable access to all edge weights.

The order in which weights are yielded matches the order of their edge indices.

pub fn index_twice_mut<A, B>(
    &mut self,
    a: A,
    b: B
) -> (&mut <PetGraph<N, E, Ix> as Index<A>>::Output, &mut <PetGraph<N, E, Ix> as Index<B>>::Output) where
    PetGraph<N, E, Ix>: IndexMut<A> + IndexMut<B>,
    A: GraphIndex,
    B: GraphIndex, 

Index the Dag by two indices.

Both indices can be either NodeIndexs, EdgeIndexs or a combination of the two.

Panics if the indices are equal or if they are out of bounds.

pub fn remove_node(&mut self, node: NodeIndex<Ix>) -> Option<N>

Remove the node at the given index from the Dag and return it if it exists.

Note: Calling this may shift (and in turn invalidate) previously returned node indices!

pub fn remove_edge(&mut self, e: EdgeIndex<Ix>) -> Option<E>

Remove an edge and return its weight, or None if it didn't exist.

Computes in O(e') time, where e' is the size of four particular edge lists, for the nodes of e and the nodes of another affected edge.

pub fn parents(&self, child: NodeIndex<Ix>) -> Parents<N, E, Ix>

A Walker type that may be used to step through the parents of the given child node.

Unlike iterator types, Walkers do not require borrowing the internal Graph. This makes them useful for traversing the Graph while still being able to mutably borrow it.

If you require an iterator, use one of the Walker methods for converting this Walker into a similarly behaving Iterator type.

See the Walker trait for more useful methods.

pub fn children(&self, parent: NodeIndex<Ix>) -> Children<N, E, Ix>

A "walker" object that may be used to step through the children of the given parent node.

Unlike iterator types, Walkers do not require borrowing the internal Graph. This makes them useful for traversing the Graph while still being able to mutably borrow it.

If you require an iterator, use one of the Walker methods for converting this Walker into a similarly behaving Iterator type.

See the Walker trait for more useful methods.

pub fn recursive_walk<F>(
    &self,
    start: NodeIndex<Ix>,
    recursive_fn: F
) -> RecursiveWalk<N, E, Ix, F> where
    F: FnMut(&Self, NodeIndex<Ix>) -> Option<(EdgeIndex<Ix>, NodeIndex<Ix>)>, 

A Walker type that recursively walks the Dag using the given recursive_fn.

See the Walker trait for more useful methods.

Trait Implementations

impl<N: Clone, E: Clone, Ix: Clone + IndexType> Clone for Dag<N, E, Ix>

fn clone(&self) -> Dag<N, E, Ix>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N: Debug, E: Debug, Ix: Debug + IndexType> Debug for Dag<N, E, Ix>

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

Formats the value using the given formatter.

impl<N, E, Ix> Index<EdgeIndex<Ix>> for Dag<N, E, Ix> where
    Ix: IndexType, 

type Output = E

The returned type after indexing.

fn index(&self, index: EdgeIndex<Ix>) -> &E

Performs the indexing (container[index]) operation.

impl<N, E, Ix> Index<NodeIndex<Ix>> for Dag<N, E, Ix> where
    Ix: IndexType, 

type Output = N

The returned type after indexing.

fn index(&self, index: NodeIndex<Ix>) -> &N

Performs the indexing (container[index]) operation.

impl<N, E, Ix> IndexMut<EdgeIndex<Ix>> for Dag<N, E, Ix> where
    Ix: IndexType, 

fn index_mut(&mut self, index: EdgeIndex<Ix>) -> &mut E

Performs the mutable indexing (container[index]) operation.

impl<N, E, Ix> IndexMut<NodeIndex<Ix>> for Dag<N, E, Ix> where
    Ix: IndexType, 

fn index_mut(&mut self, index: NodeIndex<Ix>) -> &mut N

Performs the mutable indexing (container[index]) operation.

impl<N, E, Ix> Walker<Dag<N, E, Ix>> for Children<N, E, Ix> where
    Ix: IndexType, 

type Index = Ix

The unsigned integer type used for node and edge indices.

fn next(
    &mut self,
    dag: &Dag<N, E, Ix>
) -> Option<(EdgeIndex<Ix>, NodeIndex<Ix>)>

Fetch the EdgeIndex and NodeIndex to the next neighbour in our walk through the given Graph.

fn next_edge(&mut self, graph: &G) -> Option<EdgeIndex<Self::Index>>

The next edge in our walk for the given Graph.

fn next_node(&mut self, graph: &G) -> Option<NodeIndex<Self::Index>>

The next node in our walk for the given Graph.

fn count(self, graph: &G) -> usize where
    Self: Sized, 

Counts all the steps in the entire walk of the given graph.

fn last(self, graph: &G) -> Option<IndexPair<Self::Index>> where
    Self: Sized, 

Walks the whole walk until reaching and returning the last edge node pair.

fn last_edge(self, graph: &G) -> Option<EdgeIndex<Self::Index>> where
    Self: Sized, 

Walks the whole walk until reaching and returning the last edge.

fn last_node(self, graph: &G) -> Option<NodeIndex<Self::Index>> where
    Self: Sized, 

Walks the whole walk until reaching and returning the last node.

fn nth(self, graph: &G, n: usize) -> Option<IndexPair<Self::Index>> where
    Self: Sized, 

Walks "n" number of steps and produces the resulting edge node pair.

fn nth_edge(self, graph: &G, n: usize) -> Option<EdgeIndex<Self::Index>> where
    Self: Sized, 

Walks "n" number of steps and produces the resulting edge.

fn nth_node(self, graph: &G, n: usize) -> Option<NodeIndex<Self::Index>> where
    Self: Sized, 

Walks "n" number of steps and produces the resulting node.

fn chain<O>(self, other: O) -> Chain<G, Self::Index, Self, O> where
    Self: Sized,
    O: Walker<G, Index = Self::Index>, 

Produces a walker that will walk the entirey of self before walking the entirey of other.

fn filter<P>(self, predicate: P) -> Filter<Self, P> where
    Self: Sized,
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Creates a walker that applies the predicate to each element returned by this walker. The only elements that will be yielded are those that make the predicate evaluate to true.

fn peekable(self) -> Peekable<G, Self::Index, Self> where
    Self: Sized, 

Creates a walker that has a .peek(&graph) method that returns an optional next neighbor.

fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
    Self: Sized,
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Creates a walker that invokes the predicate on elements until it returns false. Once the predicate returns false, that element and all further elements are yielded.

fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
    Self: Sized,
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Creates a walker that yields elements so long as the predicate returns true. After the predicate returns false for the first time, no further elements will be yielded.

fn skip(self, n: usize) -> Skip<G, Self::Index, Self> where
    Self: Sized, 

Creates a walker that skips the first n steps of this walk, and then yields all further steps.

fn take(self, n: usize) -> Take<G, Self::Index, Self> where
    Self: Sized, 

Creates a walker that yields the first n steps of this walk.

fn all<P>(&mut self, graph: &G, predicate: P) -> bool where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Tests whether the predicate holds true for all steps in the walk.

fn any<P>(&mut self, graph: &G, predicate: P) -> bool where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Tests whether any step in the walk satisfies the given predicate.

fn find<P>(&mut self, graph: &G, predicate: P) -> Option<IndexPair<Self::Index>> where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Returns the first edge node index pair satisfying the specified predicate.

fn find_edge<P>(
    &mut self,
    graph: &G,
    predicate: P
) -> Option<EdgeIndex<Self::Index>> where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Returns the edge index satisfying the specified predicate.

fn find_node<P>(
    &mut self,
    graph: &G,
    predicate: P
) -> Option<NodeIndex<Self::Index>> where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Returns the node index satisfying the specified predicate.

fn cycle(self) -> Cycle<G, Self::Index, Self> where
    Self: Clone + Sized, 

Repeats the walker endlessly.

fn fold<B, F>(self, init: B, graph: &G, f: F) -> B where
    Self: Sized,
    F: FnMut(B, &G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> B, 

Performs a fold operation over the entire walker, returning the eventual state at the end of the walk.

fn inspect<F>(self, f: F) -> Inspect<Self, F> where
    Self: Sized,
    F: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>), 

Creates a walker that calls a function with a reference to each index pair before yielding them. This is often useful for debugging a walker pipeline.

fn iter(self, graph: &G) -> Iter<'_, G, Self::Index, Self> where
    Self: Sized, 

Converts the walker into an iterator yielding index pairs.

fn iter_weights(self, graph: &G) -> IterWeights<'_, G, Self::Index, Self> where
    Self: Sized, 

Converts the walker into an iterator yielding (&e, &n), where e is the edge weight for the next EdgeIndex and n is the node weight for the next NodeIndex.

impl<N, E, Ix> Walker<Dag<N, E, Ix>> for Parents<N, E, Ix> where
    Ix: IndexType, 

type Index = Ix

The unsigned integer type used for node and edge indices.

fn next(
    &mut self,
    dag: &Dag<N, E, Ix>
) -> Option<(EdgeIndex<Ix>, NodeIndex<Ix>)>

Fetch the EdgeIndex and NodeIndex to the next neighbour in our walk through the given Graph.

fn next_edge(&mut self, graph: &G) -> Option<EdgeIndex<Self::Index>>

The next edge in our walk for the given Graph.

fn next_node(&mut self, graph: &G) -> Option<NodeIndex<Self::Index>>

The next node in our walk for the given Graph.

fn count(self, graph: &G) -> usize where
    Self: Sized, 

Counts all the steps in the entire walk of the given graph.

fn last(self, graph: &G) -> Option<IndexPair<Self::Index>> where
    Self: Sized, 

Walks the whole walk until reaching and returning the last edge node pair.

fn last_edge(self, graph: &G) -> Option<EdgeIndex<Self::Index>> where
    Self: Sized, 

Walks the whole walk until reaching and returning the last edge.

fn last_node(self, graph: &G) -> Option<NodeIndex<Self::Index>> where
    Self: Sized, 

Walks the whole walk until reaching and returning the last node.

fn nth(self, graph: &G, n: usize) -> Option<IndexPair<Self::Index>> where
    Self: Sized, 

Walks "n" number of steps and produces the resulting edge node pair.

fn nth_edge(self, graph: &G, n: usize) -> Option<EdgeIndex<Self::Index>> where
    Self: Sized, 

Walks "n" number of steps and produces the resulting edge.

fn nth_node(self, graph: &G, n: usize) -> Option<NodeIndex<Self::Index>> where
    Self: Sized, 

Walks "n" number of steps and produces the resulting node.

fn chain<O>(self, other: O) -> Chain<G, Self::Index, Self, O> where
    Self: Sized,
    O: Walker<G, Index = Self::Index>, 

Produces a walker that will walk the entirey of self before walking the entirey of other.

fn filter<P>(self, predicate: P) -> Filter<Self, P> where
    Self: Sized,
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Creates a walker that applies the predicate to each element returned by this walker. The only elements that will be yielded are those that make the predicate evaluate to true.

fn peekable(self) -> Peekable<G, Self::Index, Self> where
    Self: Sized, 

Creates a walker that has a .peek(&graph) method that returns an optional next neighbor.

fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P> where
    Self: Sized,
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Creates a walker that invokes the predicate on elements until it returns false. Once the predicate returns false, that element and all further elements are yielded.

fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where
    Self: Sized,
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Creates a walker that yields elements so long as the predicate returns true. After the predicate returns false for the first time, no further elements will be yielded.

fn skip(self, n: usize) -> Skip<G, Self::Index, Self> where
    Self: Sized, 

Creates a walker that skips the first n steps of this walk, and then yields all further steps.

fn take(self, n: usize) -> Take<G, Self::Index, Self> where
    Self: Sized, 

Creates a walker that yields the first n steps of this walk.

fn all<P>(&mut self, graph: &G, predicate: P) -> bool where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Tests whether the predicate holds true for all steps in the walk.

fn any<P>(&mut self, graph: &G, predicate: P) -> bool where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Tests whether any step in the walk satisfies the given predicate.

fn find<P>(&mut self, graph: &G, predicate: P) -> Option<IndexPair<Self::Index>> where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Returns the first edge node index pair satisfying the specified predicate.

fn find_edge<P>(
    &mut self,
    graph: &G,
    predicate: P
) -> Option<EdgeIndex<Self::Index>> where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Returns the edge index satisfying the specified predicate.

fn find_node<P>(
    &mut self,
    graph: &G,
    predicate: P
) -> Option<NodeIndex<Self::Index>> where
    P: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> bool, 

Returns the node index satisfying the specified predicate.

fn cycle(self) -> Cycle<G, Self::Index, Self> where
    Self: Clone + Sized, 

Repeats the walker endlessly.

fn fold<B, F>(self, init: B, graph: &G, f: F) -> B where
    Self: Sized,
    F: FnMut(B, &G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>) -> B, 

Performs a fold operation over the entire walker, returning the eventual state at the end of the walk.

fn inspect<F>(self, f: F) -> Inspect<Self, F> where
    Self: Sized,
    F: FnMut(&G, EdgeIndex<Self::Index>, NodeIndex<Self::Index>), 

Creates a walker that calls a function with a reference to each index pair before yielding them. This is often useful for debugging a walker pipeline.

fn iter(self, graph: &G) -> Iter<'_, G, Self::Index, Self> where
    Self: Sized, 

Converts the walker into an iterator yielding index pairs.

fn iter_weights(self, graph: &G) -> IterWeights<'_, G, Self::Index, Self> where
    Self: Sized, 

Converts the walker into an iterator yielding (&e, &n), where e is the edge weight for the next EdgeIndex and n is the node weight for the next NodeIndex.