Function gomory_hu_tree 

pub fn gomory_hu_tree(
    graph: &Graph,
    capacity: Option<&[f64]>,
) -> IgraphResult<GomoryHuTree>

Gomory-Hu cut tree of an undirected graph (Gusfield 1990).

Returns a GomoryHuTree whose tree field is an undirected weighted tree on the same vertex set as graph with V - 1 edges, and whose flows field gives one weight per tree edge. The minimum s-t cut value between any two vertices u, v in the original graph is exactly the minimum edge weight along the unique tree path from u to v.

Arguments

• graph — input graph. Must be undirected; directed graphs are rejected with IgraphError::InvalidArgument.
• capacity — optional per-edge capacity in the graph’s edge-id order. When None, each edge contributes unit capacity. When Some(c), c.len() must equal graph.ecount(), and every entry must be finite and ≥ 0 (same contract as crate::st_mincut).

Returns

A GomoryHuTree with tree.vcount() == graph.vcount() and flows.len() == tree.ecount() == max(graph.vcount() - 1, 0).

For graph.vcount() == 0 the returned tree is empty and flows is empty. For graph.vcount() == 1 the tree has one isolated vertex and flows is empty.

Errors

• IgraphError::InvalidArgument if graph is directed, the capacity slice length differs from ecount(), or any capacity entry is negative / non-finite.

Examples

K_4 with unit capacities — every pair has min-cut 3 (each vertex’s degree), so every tree edge weight is 3.

use rust_igraph::{Graph, gomory_hu_tree};

let mut k4 = Graph::new(4, false).unwrap();
for u in 0u32..4 {
    for v in (u + 1)..4 {
        k4.add_edge(u, v).unwrap();
    }
}

let gh = gomory_hu_tree(&k4, None).unwrap();
assert_eq!(gh.tree.vcount(), 4);
assert_eq!(gh.tree.ecount(), 3);
assert_eq!(gh.flows.len(), 3);
for &w in &gh.flows {
    assert_eq!(w, 3.0);
}

References

Gusfield D., Very simple methods for all pairs network flow analysis. SIAM J Comput 19(1):143-155, 1990.