# Struct daggy::Dag
[−]
[src]

pub struct Dag<N, E, Ix: IndexType = DefIndex> { // some 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.

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

## Methods

`impl<N, E, Ix = DefIndex> Dag<N, E, Ix> where Ix: IndexType`

[src]

`fn new() -> Self`

Create a new, empty `Dag`

.

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

Create a new `Dag`

with estimated capacity for its node and edge Vecs.

`fn node_count(&self) -> usize`

The total number of nodes in the Dag.

`fn edge_count(&self) -> usize`

The total number of edgees in the Dag.

`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`

.

`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`

.

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

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

Computes in **O(t)** time where "t" is the time taken to check if adding the edge would
cause a cycle in the graph. See petgraph's `is_cyclic_directed`

function for more details.

**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 the Graph is at the maximum number of nodes for its index type.

`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 better performance.

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

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

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

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

Borrow the weight from the node at the given index.

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

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

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

Borrow the weight from the edge at the given index.

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

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

`fn index_twice_mut<A, B>(&mut self, a: A, b: B) -> (&mut PetGraph<N, E, Ix>::Output, &mut PetGraph<N, E, Ix>::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 `NodeIndex`

s, `EdgeIndex`

s or a combination of the two.

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

`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!

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

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

An iterator over all nodes that are parents to the node at the given index.

The returned iterator yields `EdgeIndex<Ix>`

s.

`fn walk_parents(&self, child: NodeIndex<Ix>) -> WalkParents<Ix>`

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

Unlike the `Parents`

type, `WalkParents`

does not borrow the `Dag`

's `PetGraph`

.

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

An iterator over all nodes that are children to the node at the given index.

The returned iterator yields `EdgeIndex<Ix>`

s.

`fn walk_children(&self, parent: NodeIndex<Ix>) -> WalkChildren<Ix>`

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

Unlike the `Children`

type, `WalkChildren`

does not borrow the `Dag`

's `PetGraph`

.

## Trait Implementations

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

[src]

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

[src]

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

Returns a copy of the value. Read more

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

1.0.0

Performs copy-assignment from `source`

. Read more

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

[src]

`type Output = N`

The returned type after indexing

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

The method for the indexing (`Foo[Bar]`

) operation

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

[src]

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

The method for the indexing (`Foo[Bar]`

) operation

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

[src]

`type Output = E`

The returned type after indexing

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

The method for the indexing (`Foo[Bar]`

) operation