pub(crate) struct BalancedFlowGraph<G: DirectedGraph> {
graph: G,
sink_edge_nodes: DenseBitSet<G::Node>,
pub(crate) sink: G::Node,
}
Expand description
A view of an underlying graph that has been augmented to have “balanced flow”. This means that the flow (execution count) of each node is equal to the sum of its in-edge flows, and also equal to the sum of its out-edge flows.
To achieve this, a synthetic “sink” node is non-destructively added to the graph, with synthetic in-edges from these nodes:
- Any node that has no out-edges.
- Any node that explicitly requires a sink edge, as indicated by a
caller-supplied
force_sink_edge
function. - Any node that would otherwise be unable to reach the sink, because it is part of an inescapable loop.
To make the graph fully balanced, there is also a synthetic edge from the sink node back to the start node.
The benefit of having a balanced-flow graph is that it can be subsequently transformed in ways that are guaranteed to preserve balanced flow (e.g. merging nodes together), which is useful for discovering relationships between the node flows of different nodes in the graph.
Fields§
§graph: G
§sink_edge_nodes: DenseBitSet<G::Node>
§sink: G::Node
Implementations§
Source§impl<G: DirectedGraph> BalancedFlowGraph<G>
impl<G: DirectedGraph> BalancedFlowGraph<G>
Sourcepub(crate) fn for_graph(
graph: G,
force_sink_edge: impl Fn(G::Node) -> bool,
) -> Selfwhere
G: ControlFlowGraph,
pub(crate) fn for_graph(
graph: G,
force_sink_edge: impl Fn(G::Node) -> bool,
) -> Selfwhere
G: ControlFlowGraph,
Creates a balanced view of an underlying graph, by adding a synthetic sink node that has in-edges from nodes that need or request such an edge, and a single out-edge to the start node.
Assumes that all nodes in the underlying graph are reachable from the start node.
Trait Implementations§
Source§impl<G> DirectedGraph for BalancedFlowGraph<G>where
G: DirectedGraph,
impl<G> DirectedGraph for BalancedFlowGraph<G>where
G: DirectedGraph,
Source§fn num_nodes(&self) -> usize
fn num_nodes(&self) -> usize
Returns the number of nodes in this balanced-flow graph, which is 1 more than the number of nodes in the underlying graph, to account for the synthetic sink node.
type Node = <G as DirectedGraph>::Node
Source§fn iter_nodes(
&self,
) -> impl Iterator<Item = Self::Node> + DoubleEndedIterator + ExactSizeIterator
fn iter_nodes( &self, ) -> impl Iterator<Item = Self::Node> + DoubleEndedIterator + ExactSizeIterator
Source§impl<G> StartNode for BalancedFlowGraph<G>where
G: StartNode,
impl<G> StartNode for BalancedFlowGraph<G>where
G: StartNode,
fn start_node(&self) -> Self::Node
Source§impl<G> Successors for BalancedFlowGraph<G>where
G: StartNode + Successors,
impl<G> Successors for BalancedFlowGraph<G>where
G: StartNode + Successors,
Auto Trait Implementations§
impl<G> DynSend for BalancedFlowGraph<G>
impl<G> DynSync for BalancedFlowGraph<G>
impl<G> Freeze for BalancedFlowGraph<G>
impl<G> RefUnwindSafe for BalancedFlowGraph<G>
impl<G> Send for BalancedFlowGraph<G>
impl<G> Sync for BalancedFlowGraph<G>
impl<G> Unpin for BalancedFlowGraph<G>
impl<G> UnwindSafe for BalancedFlowGraph<G>
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Source§impl<T, R> CollectAndApply<T, R> for T
impl<T, R> CollectAndApply<T, R> for T
Source§impl<T> Filterable for T
impl<T> Filterable for T
Source§fn filterable(
self,
filter_name: &'static str,
) -> RequestFilterDataProvider<T, fn(_: DataRequest<'_>) -> bool>
fn filterable( self, filter_name: &'static str, ) -> RequestFilterDataProvider<T, fn(_: DataRequest<'_>) -> bool>
Source§impl<T> Instrument for T
impl<T> Instrument for T
Source§fn instrument(self, span: Span) -> Instrumented<Self>
fn instrument(self, span: Span) -> Instrumented<Self>
Source§fn in_current_span(self) -> Instrumented<Self>
fn in_current_span(self) -> Instrumented<Self>
Source§impl<T> IntoEither for T
impl<T> IntoEither for T
Source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moreSource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moreSource§impl<P> IntoQueryParam<P> for P
impl<P> IntoQueryParam<P> for P
fn into_query_param(self) -> P
Source§impl<T> MaybeResult<T> for T
impl<T> MaybeResult<T> for T
Source§impl<T> Pointable for T
impl<T> Pointable for T
Source§impl<I, T, U> Upcast<I, U> for Twhere
U: UpcastFrom<I, T>,
impl<I, T, U> Upcast<I, U> for Twhere
U: UpcastFrom<I, T>,
Source§impl<I, T> UpcastFrom<I, T> for T
impl<I, T> UpcastFrom<I, T> for T
fn upcast_from(from: T, _tcx: I) -> T
Source§impl<Tcx, T> Value<Tcx> for Twhere
Tcx: DepContext,
impl<Tcx, T> Value<Tcx> for Twhere
Tcx: DepContext,
default fn from_cycle_error( tcx: Tcx, cycle_error: &CycleError, _guar: ErrorGuaranteed, ) -> T
Source§impl<T> WithSubscriber for T
impl<T> WithSubscriber for T
Source§fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self>
Source§fn with_current_subscriber(self) -> WithDispatch<Self>
fn with_current_subscriber(self) -> WithDispatch<Self>
impl<'a, T> Captures<'a> for Twhere
T: ?Sized,
impl<'a, T> Captures<'a> for Twhere
T: ?Sized,
impl<T> ErasedDestructor for Twhere
T: 'static,
impl<T> MaybeSendSync for T
Layout§
Note: Unable to compute type layout, possibly due to this type having generic parameters. Layout can only be computed for concrete, fully-instantiated types.