Struct StronglyConnectedComponents 

pub struct StronglyConnectedComponents<Node>
where
    Node: EntityRef,
{ /* private fields */ }

The set of strongly-connected components for a graph of Nodes.

Implementations

impl<Node> StronglyConnectedComponents<Node>

where Node: EntityRef + Debug,

pub fn new<G>(graph: G) -> Self

where G: Graph<Node>,

Find the strongly-connected for the given graph.

pub fn len(&self) -> usize

Get the number of components.

pub fn iter(&self) -> impl ExactSizeIterator<Item = (Scc, &[Node])> + '_

Iterate over each strongly-connnected component and the Nodes that are members of it.

Iteration happens in reverse-topological order (successors are visited before predecessors in the resulting SCC DAG).

pub fn keys(&self) -> impl ExactSizeIterator<Item = Scc>

Iterate over each strongly-connected component.

Iteration happens in reverse-topological order (successors are visited before predecessors in the resulting SCC DAG).

pub fn nodes(&self, component: Scc) -> &[Node]

Get the Nodes that make up the given strongly-connected component.

pub fn evaporation<G>(&self, graph: G) -> Evaporation

where G: Graph<Node>,

Get this set of strongly-connected components’ “evaporation”.

Given an input graph G, we can construct a new graph where the new graph’s nodes are the strongly-connected components of G and there is an edge scc(a) --> scc(b) for every edge a --> b in the input graph G where scc(a) != scc(b) and scc is the function from a node to its strongly-connected component. This new graph is known as the “condensation” of G.

In the following diagram, the solid lines are the input graph and the dotted lines show its condensation:

...............
:             :
:    ,-----.  :
:    |     |  :
:    V     |  :
:  +---+   |  :
:  | a |---'  :
:  +---+      :
:    |        :
:....|........:
     |  :
     |  :
     |  :
     |  V
.....|..............       ....................
:    |             :       :                  :
:    V             :......>:                  :
:  +---+    +---+  :       :  +---+    +---+  :
:  | b |<-->| c |------------>| d |<-->| e |  :
:  +---+    +---+  :       :  +---+    +---+  :
:    |             :       :             |    :
:....|.............:       :.............|....:
     |  :                          :     |
     |  :                          :     |
     |  :                          :     |
     |  V                          :     |
.....|........................     :     |
:    |                       :     :     |
:    | ,----------------.    :     :     |
:    | |                |    :<....:     |
:    V |                V    :           |
:   +---+    +---+    +---+  :           |
:   | f |<---| g |<---| h |<-------------'
:   +---+    +---+    +---+  :
:                            :
:............................:

Note that a graph’s condensation is always acyclic, because the strongly-conneted components encapsulate and hide any cycles from the input graph.

I am not aware of an existing name for the reverse (or transpose) condensation, where each of the condensation’s edges a --> b are flipped into b --> a, so, at cfallin’s brilliant suggestion, I have decided to call it an “evaporation”.

In the context of a call graph, the condensation allows us to derive a partial dependency ordering for bottom-up inlining:

• An edge scc({a,b,...}) --> scc({c,d,...}) means that the functions {c,d,...} should be processed for inlining before functions {a,b,...}, since some functions in {a,b,...} call some functions in {c,d,...} and we might want to inline these calls but only after {c,d,...} have already had their calls inlined.

• Functions within an SCC are unordered (and we probably don’t want to inline between them at all, or only want to do so in a very limited manner, since their members are mutually recursive).

A call graph’s evaporation, by flipping edges from pointing to an SCC’s dependencies to pointing to its dependers, allows us to answer the question “given that I’ve finished processing calls in scc({e,f,...}) for inlining, which other SCCs are now potentially ready for processing?”.

Trait Implementations

impl<Node> Debug for StronglyConnectedComponents<Node>

where Node: EntityRef + Debug,

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

Formats the value using the given formatter.