Struct daggy::stable_dag::StableDag [−][src]
Expand description
A Directed acyclic graph (DAG) data structure.
StableDag is a thin wrapper around petgraph’s StableGraph
data structure, providing a refined
API for dealing specifically with DAGs.
Note: The following documentation is adapted from petgraph’s StableGraph documentation.
StableDag 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. **StableDag++ keeps all indices stable even when removing nodes/edges.
The Ix parameter is u32 by default. The goal is that you can ignore this parameter completely unless you need a very large StableDag – then you can use usize.
The StableDag also offers methods for accessing the underlying StableGraph, which can be useful for taking advantage of petgraph’s various graph-related algorithms.
Implementations
Create a new StableDag
with estimated capacity for its node and edge Vecs.
pub fn from_edges<I>(edges: I) -> Result<Self, WouldCycle<E>> where
I: IntoIterator,
I::Item: IntoWeightedEdge<E>,
<I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
N: Default,
pub fn from_edges<I>(edges: I) -> Result<Self, WouldCycle<E>> where
I: IntoIterator,
I::Item: IntoWeightedEdge<E>,
<I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
N: Default,
Create a StableDag
from an iterator yielding edges.
Node weights N
are set to default values.
Edge
weights E
may either be specified in the list, or they are filled with default
values.
Nodes are inserted automatically to match the edges.
Returns an Err
if adding any of the edges would cause a cycle.
pub fn extend_with_edges<I>(&mut self, edges: I) -> Result<(), WouldCycle<E>> where
I: IntoIterator,
I::Item: IntoWeightedEdge<E>,
<I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
N: Default,
pub fn extend_with_edges<I>(&mut self, edges: I) -> Result<(), WouldCycle<E>> where
I: IntoIterator,
I::Item: IntoWeightedEdge<E>,
<I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
N: Default,
Extend the StableDag
with the given edges.
Node weights N
are set to default values.
Edge weights E
may either be specified in the list, or they are filled with default
values.
Nodes are inserted automatically to match the edges.
Returns an Err
if adding an edge would cause a cycle.
pub fn from_elements<I>(elements: I) -> Result<Self, WouldCycle<E>> where
Self: Sized,
I: IntoIterator<Item = Element<N, E>>,
pub fn from_elements<I>(elements: I) -> Result<Self, WouldCycle<E>> where
Self: Sized,
I: IntoIterator<Item = Element<N, E>>,
Create a StableDag
from an iterator yielding elements.
Returns an Err
if an edge would cause a cycle within the graph.
Create a new Graph
by mapping node and edge weights to new values.
The resulting graph has the same structure and the same graph indices as self
.
Create a new StableDag
by mapping node and edge weights. A node or edge may be mapped to
None
to exclude it from the resulting StableDag
.
Nodes are mapped first with the node_map
closure, then edge_map
is called for the edges
that have not had any endpoint removed.
The resulting graph has the structure of a subgraph of the original graph. Nodes and edges that are not removed maintain their old node or edge indices.
The total number of nodes in the StableDag.
The total number of edges in the StableDag.
Borrow the StableDag
’s underlying StableDiGraph<N, Ix>
.
All existing indices may be used to index into this StableDiGraph
the same way they may be
used to index into the StableDag
.
Take ownership of the StableDag
and return the internal StableDiGraph
.
All existing indices may be used to index into this StableDiGraph
the same way they may be
used to index into the StableDag
.
Add a new node to the StableDag
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.
Add a new directed edge to the StableDag
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
function is used to check whether or not adding the edge would create a cycle.
Note: StableDag 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 StableDag.
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)>,
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 StableDag
, 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: StableDag allows adding parallel (“duplicate”) edges. If you want to avoid this,
use update_edge
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 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>>
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.
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
.
Access the parent and child nodes for the given EdgeIndex
.
Remove all edges.
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.
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.
Borrow the weight from the node at the given index.
Mutably borrow the weight from the node at the given index.
Borrow the weight from the edge at the given index.
Mutably borrow the weight from the edge at the given index.
pub fn index_twice_mut<A, B>(
&mut self,
a: A,
b: B
) -> (&mut <StableDiGraph<N, E, Ix> as Index<A>>::Output, &mut <StableDiGraph<N, E, Ix> as Index<B>>::Output) where
StableDiGraph<N, E, Ix>: IndexMut<A> + IndexMut<B>,
A: GraphIndex,
B: GraphIndex,
pub fn index_twice_mut<A, B>(
&mut self,
a: A,
b: B
) -> (&mut <StableDiGraph<N, E, Ix> as Index<A>>::Output, &mut <StableDiGraph<N, E, Ix> as Index<B>>::Output) where
StableDiGraph<N, E, Ix>: IndexMut<A> + IndexMut<B>,
A: GraphIndex,
B: GraphIndex,
Index the StableDag
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.
Remove the node at the given index from the StableDag
and return it if it exists.
Whether or not the graph contains a node for the given index.
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.
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.
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.
A Walker type that recursively walks the StableDag using the given recursive_fn
.
See the Walker trait for more useful methods.
Trait Implementations
type NodeWeight = N
type EdgeWeight = E
impl<'de, N, E, Ix> Deserialize<'de> for StableDag<N, E, Ix> where
Self: Sized,
N: Deserialize<'de>,
E: Deserialize<'de>,
Ix: IndexType + Deserialize<'de>,
impl<'de, N, E, Ix> Deserialize<'de> for StableDag<N, E, Ix> where
Self: Sized,
N: Deserialize<'de>,
E: Deserialize<'de>,
Ix: IndexType + Deserialize<'de>,
Deserialize this value from the given Serde deserializer. Read more
Convert a Dag
into a StableDag
The resulting graph has the same node and edge indices as the original graph.
type AdjMatrix = <StableDiGraph<N, E, Ix> as GetAdjacencyMatrix>::AdjMatrix
type AdjMatrix = <StableDiGraph<N, E, Ix> as GetAdjacencyMatrix>::AdjMatrix
The associated adjacency matrix type
Create the adjacency matrix
Performs the conversion.
type EdgeRef = EdgeReference<'a, E, Ix>
type EdgeReferences = EdgeReferences<'a, E, Ix>
type EdgesDirected = Edges<'a, E, Ix>
type NeighborsDirected = Neighbors<'a, E, Ix>
type NodeIdentifiers = NodeIndices<'a, N, Ix>
type NodeReferences = NodeReferences<'a, N, Ix>
Return an upper bound of the node indices in the graph (suitable for the size of a bitmap). Read more
Convert i
to a node index. i
must be a valid value in the graph.
Auto Trait Implementations
impl<N, E, Ix> RefUnwindSafe for StableDag<N, E, Ix> where
E: RefUnwindSafe,
Ix: RefUnwindSafe,
N: RefUnwindSafe,
impl<N, E, Ix> UnwindSafe for StableDag<N, E, Ix> where
E: UnwindSafe,
Ix: UnwindSafe,
N: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more