Struct Graph 

pub struct Graph { /* private fields */ }

Represents a dependency directed acyclic graph (DAG) with size information, where each node represents a crate, and each directed edge represents a binary relation of dependency of the source node on the target node.

It also keeps the size information of each crate as parsed from cargo-bloat output in a map, which can be accessed using the size method for a given node index.

The node indices can be iterated using the node_indices method, though there is no guarantee of the order of iteration. Use dfs, bfs, or topo if the order of iteration is important, e.g. when a crate must be traversed before its dependencies.

While Graph can be mutated, it is deliberately limited to only change_root, remove_deep_deps and remove_indices, as the graph structure should only be reduced and not expanded. In addition, any remaining non-reachable node from the root after these operations will also be removed.

Examples

The following example demonstrates a common pattern that will fail to compile without collect as otherwise it borrows from graph immutably:

fn remove_z(graph: &mut Graph) {
    let iter = graph.node_indices().filter(|i| {
       graph.node_weight(*i).short().starts_with('z')
    }).collect::<Vec<_>>().into_iter();

    graph.remove_indices(iter);
}

Use ordered tranversals when required:

fn dep_counts(graph: &Graph) -> Vec<usize> {
    let mut values = vec![0; graph.node_capacity()];

    let nodes: Vec<usize> = graph.topo().collect();

    for node in nodes.iter().rev() {
        for target in graph.neighbors(*node, true) {
            values[*node] += values[target] + 1;
        }
    }

    values
}

Implementations

impl Graph

pub fn new( cargo_tree_output: &str, cargo_bloat_output: &str, std: bool, bin: Option<&str>, ) -> Self

Create a new graph from the given cargo-tree and cargo-bloat outputs, with optional std standalone node.

The bin parameter is needed for accurate size accounting if the binary name is different from its crate name.

• cargo_tree_output should be the output of cargo tree --edges=no-build,no-proc-macro,no-dev,features --prefix=depth --color=never ...
• cargo_bloat_output should be the output of cargo bloat -n0 --message-format=json --crates ...

Panics

May panic if the cargo outputs are malformed.

pub fn std(&self) -> Option<usize>

Get the index of the std standalone node, if it exists.

pub fn root(&self) -> usize

Get the index of the root node.

pub fn node_count(&self) -> usize

Get the number of nodes currently in the graph.

Node indices may be greater than this value if nodes have been removed. Use node_capacity instead for allocation.

pub fn node_capacity(&self) -> usize

Get the capacity of nodes in the graph.

This is the upper bound of node indices.

pub fn node_indices(&self) -> impl Iterator<Item = usize>

Get an iterator over the node indices of the graph.

pub fn node_weight(&self, index: usize) -> &NodeWeight

Get the weight of the node at the given index.

Panics

Panics if the node does not exist in the graph.

pub fn edge_weight(&self, source: usize, target: usize) -> &EdgeWeight

Get the weight of the edge at the given index.

Panics

Panics if the source or target node, or the directed edge between them, does not exist in the graph.

fn edge_iter(graph: &Graph) -> impl Iterator<Item = &EdgeWeight> {
    graph.node_indices().flat_map(move |i| {
        graph.neighbors(i, true).map(move |j| graph.edge_weight(i, j))
    })
}

pub fn size(&self, index: usize) -> Option<usize>

Get the size of the node at the given index.

Returns None if its name is not in the size map.

Panics

Panics if the node does not exist in the graph.

pub fn dfs(&self) -> impl Iterator<Item = usize>

Get an iterator over the node indices of the graph in depth-first search order from the root.

pub fn bfs(&self) -> impl Iterator<Item = usize>

Get an iterator over the node indices of the graph in breadth-first search order from the root.

pub fn topo(&self) -> impl Iterator<Item = usize>

Get an iterator over the node indices of the graph in topological order.

pub fn neighbors( &self, index: usize, outgoing: bool, ) -> impl Iterator<Item = usize>

Get an iterator over the neighboring node indices of the given node index.

If outgoing is true, get the outgoing neighbors (i.e., dependencies), otherwise get the incoming neighbors (i.e., dependents).

pub fn remove_deep_deps(&mut self, max_depth: usize)

Remove all nodes that are deeper than max_depth from the root, and any nodes that are subsequently not reachable from the root.

pub fn remove_indices(&mut self, indices: impl Iterator<Item = usize>)

Remove the nodes at the given indices, and any nodes that are subsequently not reachable from the root.

pub fn change_root(&mut self, new_root_index: usize)

Change the root node to the given index, and remove any nodes that are not reachable from the new root.

pub fn output_dot<C, V, T, R, S, G>( &self, dot_options: &DotOptions, templating: &R, values: &S, gradient: &G, ) -> String

where R: Templating<Context = C, Value = V>, S: Values<Context = C, Value = V, Output = T>, G: Gradient<Input = T>,

Output the graph in DOT format with the given options, templating, coloring values, and gradient.

The values parameter should have been created from this graph, possibly before any node removals.

use pugio_lib::template::{Template, Templating};
use pugio_lib::coloring::{Gradient, Values, NodeColoringScheme, NodeColoringGradient, NodeColoringValues};

fn output(graph: &Graph) -> String {
    let template_options = Default::default();
    let template = Template::new(&template_options).unwrap();
    let values = Some(NodeColoringValues::new(graph, NodeColoringScheme::CumSum));
    let gradient = NodeColoringGradient::Viridis;

    graph.output_dot(&Default::default(), &template, &values, &gradient)
}

Trait Implementations

impl Debug for Graph

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

Formats the value using the given formatter.