template<typename GR, typename CAP>
class lemon::GomoryHu< GR, CAP >
The Gomory-Hu tree is a tree on the node set of a given graph, but it may contain edges which are not in the original graph. It has the property that the minimum capacity edge of the path between two nodes in this tree has the same weight as the minimum cut in the graph between these nodes. Moreover the components obtained by removing this edge from the tree determine the corresponding minimum cut. Therefore once this tree is computed, the minimum cut between any pair of nodes can easily be obtained.
The algorithm calculates n-1 distinct minimum cuts (currently with the Preflow algorithm), thus it has overall time complexity. It calculates a rooted Gomory-Hu tree. The structure of the tree and the edge weights can be obtained using predNode(), predValue() and rootDist(). The functions minCutMap() and minCutValue() calculate the minimum cut and the minimum cut value between any two nodes in the graph. You can also list (iterate on) the nodes and the edges of the cuts using MinCutNodeIt and MinCutEdgeIt.
Template Parameters
GR
The type of the undirected graph the algorithm runs on.
CAP
The type of the edge map containing the capacities. The default map type is GR::EdgeMap<int>.
This function returns the weight of the predecessor edge of the given node in the Gomory-Hu tree. If node is the root of the tree, the result is undefined.
This function returns the minimum cut value between the nodes s and t. It finds the nearest common ancestor of the given nodes in the Gomory-Hu tree and calculates the minimum weight edge on the paths to the ancestor.
This function returns the minimum cut between the nodes s and t in the cutMap parameter by setting the nodes in the component of s to true and the other nodes to false.