The GomoryHu 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 n1 distinct minimum cuts (currently with the Preflow algorithm), thus it has overall time complexity. It calculates a rooted GomoryHu 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
.
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>. 
#include <lemon/gomory_hu.h>
Classes  
class  MinCutEdgeIt 
Iterate on the edges of a minimum cut. More...  
class  MinCutNodeIt 
Iterate on the nodes of a minimum cut. More...  
Public Types  
typedef GR  Graph 
The graph type of the algorithm.  
typedef CAP  Capacity 
The capacity map type of the algorithm.  
typedef Capacity::Value  Value 
The value type of capacities.  
Public Member Functions  
GomoryHu (const Graph &graph, const Capacity &capacity)  
Constructor.  
~GomoryHu ()  
Execution Control  
void  run () 
Run the GomoryHu algorithm.  
Query Functions  
The results of the algorithm can be obtained using these functions.  
Node  predNode (const Node &node) const 
Return the predecessor node in the GomoryHu tree.  
Value  predValue (const Node &node) const 
Return the weight of the predecessor edge in the GomoryHu tree.  
int  rootDist (const Node &node) const 
Return the distance from the root node in the GomoryHu tree.  
Value  minCutValue (const Node &s, const Node &t) const 
Return the minimum cut value between two nodes.  
template<typename CutMap >  
Value  minCutMap (const Node &s, const Node &t, CutMap &cutMap) const 
Return the minimum cut between two nodes.  
Constructor.
graph  The undirected graph the algorithm runs on. 
capacity  The edge capacity map. 

inline 
Destructor.

inline 
This function runs the GomoryHu algorithm.

inline 
This function returns the predecessor node of the given node in the GomoryHu tree. If node
is the root of the tree, then it returns INVALID
.

inline 
This function returns the weight of the predecessor edge of the given node in the GomoryHu tree. If node
is the root of the tree, the result is undefined.

inline 
This function returns the distance of the given node from the root node in the GomoryHu tree.

inline 
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 GomoryHu tree and calculates the minimum weight edge on the paths to the ancestor.

inline 
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
.
For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
s  The base node. 
t  The node you want to separate from node s . 
cutMap  The cut will be returned in this map. It must be a bool (or convertible) ReadWriteMap on the graph nodes. 
s
and t
.