Module gomory_hu 

Gomory-Hu cut tree (Gusfield’s 1990 simplified construction).

Overview

Given an undirected weighted graph G on n vertices, the Gomory-Hu tree is a weighted tree T on the same vertex set with exactly n − 1 edges such that for every pair of vertices (s, t), the minimum-weight edge on the unique s–t path in T equals the value of a minimum s–t cut in G.

The classical Gomory-Hu construction (1961) requires graph contractions. Gusfield (1990, Very Simple Methods for All Pairs Network Flow Analysis) showed the same tree can be built with n − 1 max-flow computations performed directly on the original graph — no contractions, no Steiner trees. That is what we implement here.

Gusfield’s algorithm

parent[i] ← 0          for all i in 1..n        (tree rooted at vertex 0)
weight[i] ← 0          for all i
for s in 1..n:
    t ← parent[s]
    (f, S) ← min-cut(s, t)          # S = side of the cut containing s
    weight[s] ← f
    for v in 0..n:                  # re-parent vertices that fell on s's side
        if v ≠ s and v in S and parent[v] == t:
            parent[v] ← s
    if parent[t] in S:              # Gusfield's extra re-parent step
        parent[s] ← parent[t]
        parent[t] ← s
        weight[s] ← weight[t]
        weight[t] ← f

The resulting tree is encoded by the (parent, weight) arrays: for i ≥ 1 there is a tree edge {i, parent[i]} of weight weight[i]. Vertex 0 is the root.

Min-cuts are obtained by reusing the crate’s min_cut_from_max_flow, which runs Edmonds-Karp on a symmetric FlowNetwork and returns both the cut value and the source-side vertex set.

Structs

GomoryHuTree

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

Functions

gomory_hu_tree

Construct the Gomory-Hu cut tree of an undirected weighted graph using Gusfield’s n − 1 max-flow computations.