Struct GomoryHuTree 

pub struct GomoryHuTree {
    pub n: usize,
    pub parent: Vec<usize>,
    pub weight: Vec<f64>,
}

A Gomory-Hu cut tree for an undirected weighted graph.

The tree is rooted at vertex 0. For every non-root vertex i, parent[i] is its parent in the tree and weight[i] is the weight of the tree edge {i, parent[i]}, which equals the minimum i–parent[i] cut value in the original graph.

Fields

n: usize

Number of vertices (same as the input graph).

parent: Vec<usize>

parent[i] = parent of vertex i in the tree; parent[0] == 0 (the root).

weight: Vec<f64>

weight[i] = weight of the tree edge {i, parent[i]}; weight[0] == 0.0.

Implementations

impl GomoryHuTree

pub fn tree_edges(&self) -> Vec<(usize, usize, f64)>

The n − 1 undirected tree edges as (u, v, weight) triples (u < v).

pub fn min_cut(&self, s: usize, t: usize) -> GraphalgResult<f64>

Minimum s–t cut value, read off as the lightest edge on the tree path from s to t.

Equal vertices yield 0.0. Two vertices in different tree components (which can only happen if the original graph is disconnected, producing one or more zero-weight tree edges) also yield a 0.0 minimum on the path.

Errors

• GraphalgError::IndexOutOfBounds if s or t is not a valid vertex.

Trait Implementations

impl Clone for GomoryHuTree

fn clone(&self) -> GomoryHuTree

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for GomoryHuTree

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

Formats the value using the given formatter.