Struct FnGraph

Source
pub struct FnGraph<F> {
    pub graph: Dag<F, Edge, FnIdInner>,
    /* private fields */
}
Expand description

Directed acyclic graph of functions.

Besides the iter_insertion* function, all iteration functions run using topological ordering – where each function is ordered before its successors.

§Type Parameters

  • F: Type of the function stored in the graph.

Fields§

§graph: Dag<F, Edge, FnIdInner>

Graph of functions.

Implementations§

Source§

impl<F> FnGraph<F>

Source

pub fn new() -> Self

Returns an empty graph of functions.

Source

pub fn ranks(&self) -> &[Rank]

Returns the ranks of each function.

Source

pub fn toposort(&self) -> Topo<FnId, FixedBitSet>

Returns the topological sorting of each function.

Topological order is where each function is ordered before its successors.

Source

pub fn iter(&self) -> impl Iterator<Item = &F>

Returns an iterator of function references in topological order.

Topological order is where each function is ordered before its successors.

If you want to iterate over the functions in insertion order, see FnGraph::iter_insertion.

Source

pub fn iter_rev(&self) -> impl Iterator<Item = &F>

Returns an iterator of function references in reverse topological order.

Topological order is where each function is ordered before its successors, so this returns the function references from the leaf nodes to the root.

If you want to iterate over the functions in reverse insertion order, use FnGraph::iter_insertion, then call .rev().

Source

pub fn stream(&self) -> impl Stream<Item = FnRef<'_, F>> + '_

Returns a stream of function references in topological order.

Functions are produced by the stream only when all of their predecessors have returned.

Source

pub fn stream_with<'rx>( &'rx self, opts: StreamOpts<'rx, 'rx>, ) -> impl Stream<Item = FnRef<'rx, F>> + 'rx

Returns a stream of function references in reverse topological order.

Functions are produced by the stream only when all of their predecessors have returned.

For this function, interruptibility fields are ignored – use the stream_with_interruptible method insteaad.

Source

pub async fn fold_async<'f, Seed, FnFold>( &'f self, seed: Seed, fn_fold: FnFold, ) -> StreamOutcome<Seed>
where for<'iter> FnFold: Fn(Seed, FnWrapper<'iter, 'f, F>) -> LocalBoxFuture<'iter, Seed>, F: 'f,

Returns a stream of function references in topological order.

Functions are produced by the stream only when all of their predecessors have returned.

Source

pub async fn fold_async_with<'f, Seed, FnFold>( &'f self, seed: Seed, opts: StreamOpts<'_, '_>, fn_fold: FnFold, ) -> StreamOutcome<Seed>
where for<'iter> FnFold: Fn(Seed, FnWrapper<'iter, 'f, F>) -> LocalBoxFuture<'iter, Seed>, F: 'f,

Returns a stream of function references in topological order.

Functions are produced by the stream only when all of their predecessors have returned.

Source

pub async fn fold_async_mut<'f, Seed, FnFold>( &'f mut self, seed: Seed, fn_fold: FnFold, ) -> StreamOutcome<Seed>
where for<'iter> FnFold: FnMut(Seed, FnWrapperMut<'iter, 'f, F>) -> LocalBoxFuture<'iter, Seed>, F: 'f,

Returns a stream of function references in topological order.

Functions are produced by the stream only when all of their predecessors have returned.

Source

pub async fn fold_async_mut_with<'f, Seed, FnFold>( &'f mut self, seed: Seed, opts: StreamOpts<'_, '_>, fn_fold: FnFold, ) -> StreamOutcome<Seed>
where for<'iter> FnFold: FnMut(Seed, FnWrapperMut<'iter, 'f, F>) -> LocalBoxFuture<'iter, Seed>, F: 'f,

Returns a stream of function references in topological order.

Functions are produced by the stream only when all of their predecessors have returned.

Source

pub async fn for_each_concurrent<'f, FnForEach, Fut>( &'f self, limit: impl Into<Option<usize>>, fn_for_each: FnForEach, ) -> StreamOutcome<()>
where FnForEach: Fn(&'f F) -> Fut, Fut: Future<Output = ()> + 'f, F: 'f,

Runs the provided logic over the functions concurrently in topological order.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn for_each_concurrent_with<'f, FnForEach, Fut>( &'f self, limit: impl Into<Option<usize>>, opts: StreamOpts<'f, 'f>, fn_for_each: FnForEach, ) -> StreamOutcome<()>
where FnForEach: Fn(&'f F) -> Fut, Fut: Future<Output = ()> + 'f, F: 'f,

Runs the provided logic over the functions concurrently with the given stream options.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn for_each_concurrent_mut<FnForEach, Fut>( &mut self, limit: impl Into<Option<usize>>, fn_for_each: FnForEach, ) -> StreamOutcome<()>
where FnForEach: Fn(&mut F) -> Fut, Fut: Future<Output = ()>,

Runs the provided logic over the functions concurrently in topological order.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn for_each_concurrent_mut_with<'f, FnForEach, Fut>( &mut self, limit: impl Into<Option<usize>>, opts: StreamOpts<'f, 'f>, fn_for_each: FnForEach, ) -> StreamOutcome<()>
where FnForEach: Fn(&mut F) -> Fut, Fut: Future<Output = ()>,

Runs the provided logic over the functions concurrently in reverse topological order.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_fold_async<'f, E, Seed, FnTryFold>( &'f self, seed: Seed, fn_try_fold: FnTryFold, ) -> Result<StreamOutcome<Seed>, E>
where for<'iter> FnTryFold: Fn(Seed, FnWrapper<'iter, 'f, F>) -> LocalBoxFuture<'iter, Result<Seed, E>>, F: 'f,

Returns a stream of function references in topological order.

Functions are produced by the stream only when all of their predecessors have returned.

Source

pub async fn try_fold_async_with<'f, E, Seed, FnTryFold>( &'f self, seed: Seed, opts: StreamOpts<'_, '_>, fn_try_fold: FnTryFold, ) -> Result<StreamOutcome<Seed>, E>
where for<'iter> FnTryFold: Fn(Seed, FnWrapper<'iter, 'f, F>) -> LocalBoxFuture<'iter, Result<Seed, E>>, F: 'f,

Attempt to execute an accumulating asynchronous computation over a stream, collecting all the values into one final result.

This combinator will accumulate all values returned by this stream according to the closure provided. The initial state is also provided to this method and then is returned again by each execution of the closure. Once the entire stream has been exhausted the returned future will resolve to this value.

This method is similar to fold, but will exit early when any of the following are true:

  • if an error is encountered in the stream.
  • if an error is encountered in the provided closure.
  • if an interrupt signal is received.
Source

pub async fn try_fold_async_mut<'f, E, Seed, FnTryFold>( &'f mut self, seed: Seed, fn_try_fold: FnTryFold, ) -> Result<StreamOutcome<Seed>, E>
where for<'iter> FnTryFold: FnMut(Seed, FnWrapperMut<'iter, 'f, F>) -> LocalBoxFuture<'iter, Result<Seed, E>>, F: 'f,

Returns a stream of function references in topological order.

Functions are produced by the stream only when all of their predecessors have returned.

Source

pub async fn try_fold_async_mut_with<'f, E, Seed, FnTryFold>( &'f mut self, seed: Seed, opts: StreamOpts<'_, '_>, fn_try_fold: FnTryFold, ) -> Result<StreamOutcome<Seed>, E>
where for<'iter> FnTryFold: FnMut(Seed, FnWrapperMut<'iter, 'f, F>) -> LocalBoxFuture<'iter, Result<Seed, E>>, F: 'f,

Attempt to execute an accumulating asynchronous computation over a stream, collecting all the values into one final result.

This combinator will accumulate all values returned by this stream according to the closure provided. The initial state is also provided to this method and then is returned again by each execution of the closure. Once the entire stream has been exhausted the returned future will resolve to this value.

This method is similar to fold, but will exit early when any of the following are true:

  • if an error is encountered in the stream.
  • if an error is encountered in the provided closure.
  • if an interrupt signal is received.
Source

pub async fn try_for_each_concurrent<'f, E, FnTryForEach, Fut>( &'f self, limit: impl Into<Option<usize>>, fn_try_for_each: FnTryForEach, ) -> Result<StreamOutcome<()>, (StreamOutcome<()>, Vec<E>)>
where E: Debug, FnTryForEach: Fn(&'f F) -> Fut, Fut: Future<Output = Result<(), E>> + 'f,

Runs the provided logic over the functions concurrently in topological order, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned. The return error type is a Vec<E> as it is possible for multiple tasks to return errors.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_for_each_concurrent_with<'f, E, FnTryForEach, Fut>( &'f self, limit: impl Into<Option<usize>>, opts: StreamOpts<'f, 'f>, fn_try_for_each: FnTryForEach, ) -> Result<StreamOutcome<()>, (StreamOutcome<()>, Vec<E>)>
where E: Debug, FnTryForEach: Fn(&'f F) -> Fut, Fut: Future<Output = Result<(), E>> + 'f,

Runs the provided logic over the functions concurrently with the given options, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned. The return error type is a Vec<E> as it is possible for multiple tasks to return errors.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_for_each_concurrent_control<'f, E, FnTryForEach, Fut>( &'f self, limit: impl Into<Option<usize>>, fn_try_for_each: FnTryForEach, ) -> ControlFlow<(StreamOutcome<()>, Vec<E>), StreamOutcome<()>>
where E: Debug, FnTryForEach: Fn(&'f F) -> Fut, Fut: Future<Output = ControlFlow<E, ()>> + 'f,

Runs the provided logic over the functions concurrently in topological order, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_for_each_concurrent_control_with<'f, E, FnTryForEach, Fut>( &'f self, limit: impl Into<Option<usize>>, opts: StreamOpts<'f, 'f>, fn_try_for_each: FnTryForEach, ) -> ControlFlow<(StreamOutcome<()>, Vec<E>), StreamOutcome<()>>
where E: Debug, FnTryForEach: Fn(&'f F) -> Fut, Fut: Future<Output = ControlFlow<E, ()>> + 'f,

Runs the provided logic over the functions concurrently with the given options, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_for_each_concurrent_mut<E, FnTryForEach, Fut>( &mut self, limit: impl Into<Option<usize>>, fn_try_for_each: FnTryForEach, ) -> Result<StreamOutcome<()>, (StreamOutcome<()>, Vec<E>)>
where E: Debug, FnTryForEach: Fn(&mut F) -> Fut, Fut: Future<Output = Result<(), E>>,

Runs the provided logic over the functions concurrently in topological order, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned. The return error type is a Vec<E> as it is possible for multiple tasks to return errors.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_for_each_concurrent_mut_with<'f, E, FnTryForEach, Fut>( &mut self, limit: impl Into<Option<usize>>, opts: StreamOpts<'f, 'f>, fn_try_for_each: FnTryForEach, ) -> Result<StreamOutcome<()>, (StreamOutcome<()>, Vec<E>)>
where E: Debug, FnTryForEach: Fn(&mut F) -> Fut, Fut: Future<Output = Result<(), E>>,

Runs the provided logic over the functions concurrently in reverse topological order, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned. The return error type is a Vec<E> as it is possible for multiple tasks to return errors.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_for_each_concurrent_control_mut<E, FnTryForEach, Fut>( &mut self, limit: impl Into<Option<usize>>, fn_try_for_each: FnTryForEach, ) -> ControlFlow<(StreamOutcome<()>, Vec<E>), StreamOutcome<()>>
where E: Debug, FnTryForEach: Fn(&mut F) -> Fut, Fut: Future<Output = ControlFlow<E, ()>>,

Runs the provided logic over the functions concurrently in topological order, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub async fn try_for_each_concurrent_control_mut_with<'f, E, FnTryForEach, Fut>( &mut self, limit: impl Into<Option<usize>>, opts: StreamOpts<'f, 'f>, fn_try_for_each: FnTryForEach, ) -> ControlFlow<(StreamOutcome<()>, Vec<E>), StreamOutcome<()>>
where E: Debug, FnTryForEach: Fn(&mut F) -> Fut, Fut: Future<Output = ControlFlow<E, ()>>,

Runs the provided logic over the functions concurrently in topological order, stopping when an error is encountered.

This gracefully waits until all produced tasks have returned.

The first argument is an optional limit on the number of concurrent futures. If this limit is not None, no more than limit futures will be run concurrently. The limit argument is of type Into<Option<usize>>, and so can be provided as either None, Some(10), or just 10.

Note: a limit of zero is interpreted as no limit at all, and will have the same result as passing in None.

Source

pub fn map<'f, FnMap, FnMapRet>( &'f mut self, fn_map: FnMap, ) -> impl Iterator<Item = FnMapRet> + 'f
where FnMap: FnMut(&mut F) -> FnMapRet + 'f,

Returns an iterator that runs the provided logic over the functions.

Source

pub fn fold<Seed, FnFold>(&mut self, seed: Seed, fn_fold: FnFold) -> Seed
where FnFold: FnMut(Seed, &mut F) -> Seed,

Runs the provided logic with every function and accumulates the result.

Source

pub fn try_fold<Seed, FnFold, E>( &mut self, seed: Seed, fn_fold: FnFold, ) -> Result<Seed, E>
where FnFold: FnMut(Seed, &mut F) -> Result<Seed, E>,

Runs the provided logic with every function and accumulates the result, stopping on the first error.

Source

pub fn for_each<FnForEach>(&mut self, fn_for_each: FnForEach)
where FnForEach: FnMut(&mut F),

Runs the provided logic over the functions.

Source

pub fn try_for_each<FnForEach, E>( &mut self, fn_for_each: FnForEach, ) -> Result<(), E>
where FnForEach: FnMut(&mut F) -> Result<(), E>,

Runs the provided logic over the functions, stopping on the first error.

Source

pub fn iter_insertion( &self, ) -> impl ExactSizeIterator<Item = &F> + DoubleEndedIterator

Returns an iterator of function references in insertion order.

To iterate in logical dependency order, see FnGraph::iter.

Source

pub fn iter_insertion_mut(&mut self) -> NodeWeightsMut<'_, F, FnIdInner>

Returns an iterator of mutable function references in insertion order.

Return type should behave like: impl Iterator<Item = &mut F>.

Source

pub fn iter_insertion_with_indices(&self) -> NodeReferences<'_, F, FnIdInner>

Returns an iterator of function references in insertion order.

Each iteration returns a (FnId, &'a F).

Methods from Deref<Target = Dag<F, Edge, FnIdInner>>§

Source

pub fn extend_with_edges<I>(&mut self, edges: I) -> Result<(), WouldCycle<E>>

Extend the Dag 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.

Source

pub fn map<'a, F, G, N2, E2>( &'a self, node_map: F, edge_map: G, ) -> Dag<N2, E2, Ix>
where F: FnMut(NodeIndex<Ix>, &'a N) -> N2, G: FnMut(EdgeIndex<Ix>, &'a E) -> E2,

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.

Source

pub fn filter_map<'a, F, G, N2, E2>( &'a self, node_map: F, edge_map: G, ) -> Dag<N2, E2, Ix>
where F: FnMut(NodeIndex<Ix>, &'a N) -> Option<N2>, G: FnMut(EdgeIndex<Ix>, &'a E) -> Option<E2>,

Create a new Dag by mapping node and edge weights. A node or edge may be mapped to None to exclude it from the resulting Dag.

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. If no nodes are removed, the resulting graph has compatible node indices.

If neither nodes nor edges are removed, the resulting graph has compatible node indices. If neither nodes nor edges are removed the result has the same graph indices as self.

The resulting graph has the same structure and the same graph indices as self.

Source

pub fn clear(&mut self)

Removes all nodes and edges from the Dag.

Source

pub fn node_count(&self) -> usize

The total number of nodes in the Dag.

Source

pub fn edge_count(&self) -> usize

The total number of edges in the Dag.

Source

pub fn reserve_nodes(&mut self, additional: usize)

Reserves capacity for at least additional more nodes to be inserted in the graph. Graph may reserve more space to avoid frequent reallocations.

Panics if the new capacity overflows usize.

Source

pub fn reserve_exact_nodes(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more nodes to be inserted in the graph. Does nothing if the capacity is already sufficient.

Prefer reserve_nodes if future insertions are expected.

Panics if the new capacity overflows usize.

Source

pub fn reserve_edges(&mut self, additional: usize)

Reserves capacity for at least additional more edges to be inserted in the graph. Graph may reserve more space to avoid frequent reallocations.

Panics if the new capacity overflows usize.

Source

pub fn reserve_exact_edges(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more edges to be inserted in the graph. Does nothing if the capacity is already sufficient.

Prefer reserve_edges if future insertions are expected.

Panics if the new capacity overflows usize.

Source

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the graph as much as possible.

Source

pub fn shrink_to_fit_nodes(&mut self)

Shrinks the capacity of the underlying nodes collection as much as possible.

Source

pub fn shrink_to_fit_edges(&mut self)

Shrinks the capacity of the underlying edges collection as much as possible.

Source

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

Borrow the Dag’s underlying DiGraph<N, Ix>.

All existing indices may be used to index into this DiGraph the same way they may be used to index into the Dag.

Source

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.

Source

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

Source

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

Source

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 method documentation 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.

Source

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.

Source

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

Access the parent and child nodes for the given EdgeIndex.

Source

pub fn clear_edges(&mut self)

Remove all edges.

Source

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.

Source

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.

Source

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

Borrow the weight from the node at the given index.

Source

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

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

Source

pub fn raw_nodes(&self) -> &[Node<N, Ix>]

Read from the internal node array.

Source

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.

Source

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

Borrow the weight from the edge at the given index.

Source

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

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

Source

pub fn raw_edges(&self) -> &[Edge<E, Ix>]

Read from the internal edge array.

Source

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.

Source

pub fn index_twice_mut<A, B>( &mut self, a: A, b: B, ) -> (&mut <Graph<N, E, Directed, Ix> as Index<A>>::Output, &mut <Graph<N, E, Directed, Ix> as Index<B>>::Output)
where Graph<N, E, Directed, 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.

Source

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!

Source

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.

Source

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.

Source

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.

Source

pub fn recursive_walk<F>( &self, start: NodeIndex<Ix>, recursive_fn: F, ) -> Recursive<Dag<N, E, Ix>, F>
where F: FnMut(&Dag<N, E, Ix>, 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.

Source

pub fn transitive_reduce(&mut self, roots: Vec<NodeIndex<Ix>>)

Mutates the DAG into its transitive reduction

Trait Implementations§

Source§

impl<F: Clone> Clone for FnGraph<F>

Source§

fn clone(&self) -> FnGraph<F>

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<F: Debug> Debug for FnGraph<F>

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<F> Default for FnGraph<F>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<F> Deref for FnGraph<F>

Source§

type Target = Dag<F, Edge, FnIdInner>

The resulting type after dereferencing.
Source§

fn deref(&self) -> &Self::Target

Dereferences the value.
Source§

impl<F> DerefMut for FnGraph<F>

Source§

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.
Source§

impl<F> PartialEq for FnGraph<F>
where F: PartialEq,

Source§

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl<F> Eq for FnGraph<F>
where F: Eq,

Auto Trait Implementations§

§

impl<F> Freeze for FnGraph<F>

§

impl<F> RefUnwindSafe for FnGraph<F>
where F: RefUnwindSafe,

§

impl<F> Send for FnGraph<F>
where F: Send,

§

impl<F> Sync for FnGraph<F>
where F: Sync,

§

impl<F> Unpin for FnGraph<F>
where F: Unpin,

§

impl<F> UnwindSafe for FnGraph<F>
where F: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

Source§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<P, T> Receiver for P
where P: Deref<Target = T> + ?Sized, T: ?Sized,

Source§

type Target = T

🔬This is a nightly-only experimental API. (arbitrary_self_types)
The target type on which the method may be called.
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.