[FEATURE REQUEST] Add Gomory–Hu Tree (all-pairs min-cuts via n−1 max-flows)

[SamXop123]

What would you like to Propose?

Description

• Add an implementation of the Gomory–Hu tree for undirected graphs that computes all-pairs minimum cuts using n−1 max-flow computations.
• API returns {parent, weight} arrays where parent[v] is the parent in the tree and weight[v] is the min-cut capacity between v and parent[v].

Files

• src/main/java/com/thealgorithms/graph/GomoryHuTree.java
• src/test/java/com/thealgorithms/graph/GomoryHuTreeTest.java
• DIRECTORY.md entry added under graph.

Issue details

Algorithm

• For each vertex s = 1..n-1, compute max-flow between s and parent[s] (initially 0 for all).
• Determine the min-cut partition from the final residual graph (reachability from source).
• Reparent nodes on the same side of the cut and apply the classic “parent re-linking” step.
• We use an Edmonds–Karp helper that also returns the reachable set for the min-cut.

API

• GomoryHuTree.buildTree(int[][] cap) -> int[][]
  • Returns a 2-row array: [parent[], weight[]].
  • parent[0] = -1, weight[0] = 0.
  • Expects non-negative, square matrix; symmetric for undirected graphs.

Tests

• GomoryHuTreeTest:
  • Single-node trivial case.
  • Triangle graph with symmetric capacities.
  • Random small undirected graphs (n ≤ 6):
    • Validates that for all pairs (s, t) the minimum edge weight along the unique path in the tree equals EdmondsKarp.maxFlow(cap, s, t).

Checklist

• Implementation added in com.thealgorithms.graph.
• Tests pass locally (mvn test).
• DIRECTORY.md updated.
• clang-format applied to new files.
• No extraneous comments; concise class-level Javadoc with reference link.

Additional Information

Reference

• Wikipedia: Gomory–Hu tree
  • https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree