GomoryHu
Declared in lemon/gomory_hu.h, in the group Minimum Cut Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename CAP >
class GomoryHu Gomory-Hu cut tree algorithm.
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 \(O( n^3 m \Delta )\) overall time complexity, \(\Delta\) being the largest number of edges incident to a node. It calculates a rooted Gomory-Hu tree. The structure of the tree and the edge weights can be obtained using
predNode(),predValue()androotDist(), which gives an order of the nodes from the root. The functionsminCutMap()andminCutValue()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 usingMinCutNodeItandMinCutEdgeIt.- 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 >.
Execution Control
-
inline void run()
Run the Gomory-Hu algorithm.
This function runs the Gomory-Hu algorithm.
Query Functions
The results of the algorithm can be obtained using these functions.
-
inline Node predNode( const Node & node ) const
Return the predecessor node in the Gomory-Hu tree.
should be called before using them.
See also
MinCutNodeIt and MinCutEdgeIt.This function returns the predecessor node of the given node in the Gomory-Hu tree. If
nodeis the root of the tree, then it returnsINVALID.- Pre:
run() must be called before using this function.
-
inline Value predValue( const Node & node ) const
Return the weight of the predecessor edge in the Gomory-Hu tree.
This function returns the weight of the predecessor edge of the given node in the Gomory-Hu tree. If
nodeis the root of the tree, the result is undefined.- Pre:
run() must be called before using this function.
-
inline int rootDist( const Node & node ) const
Return the position of the node in an order of the tree.
This function returns the position of the given node in an order of the nodes of the Gomory-Hu tree in which the root is 0 and each node comes after its parent; hence, of two nodes on a path to the root, the one with the smaller value is the nearer to the root. It is not the distance from the root, i.e., the number of edges between them.
- Pre:
run() must be called before using this function.
-
inline Value minCutValue( const Node & s , const Node & t ) const
Return the minimum cut value between two nodes.
This function returns the minimum cut value between the nodes
sandt. 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; ifsandtare the same node, it returns the largestValue.- Pre:
run() must be called before using this function.
-
template< typename CutMap >
inline Value minCutMap( - const Node & s,
- const Node & t,
- CutMap & cutMap
Return the minimum cut between two nodes.
This function returns the minimum cut between the nodes
sandtin thecutMapparameter by setting the nodes in the component ofstotrueand the other nodes tofalse.For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
If
sandtare the same node, then no cut separates them: all the nodes are set totrueand the largestValueis returned, as minCutValue() does.- Parameters:
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.
- Returns:
The value of the minimum cut between
sandt.- Pre:
run() must be called before using this function.
Public Types
Public Functions
-
inline GomoryHu( const Graph & graph , const Capacity & capacity )
Constructor.
- Parameters:
graph – The undirected graph the algorithm runs on.
capacity – The edge capacity map.
-
inline GomoryHu & tolerance( const Tolerance< Value > & tolerance )
Sets the tolerance used by the algorithm.
Sets the tolerance object used by the algorithm, i.e., by its maximum flows.
- Returns:
(*this)
-
inline ~GomoryHu()
Destructor.
Friends
- friend class MinCutNodeIt
- friend class MinCutEdgeIt
-
class MinCutNodeIt
Iterate on the nodes of a minimum cut.
This iterator class lists the nodes of a minimum cut found by GomoryHu. Before using it, you must allocate a GomoryHu class and call its run() method.
This example counts the nodes in the minimum cut separating
sfromt.GomoryHu< Graph > gom( g , capacities ); gom.run(); int cnt = 0; for( GomoryHu< Graph >::MinCutNodeIt n( gom , s , t ) ; n != INVALID ; ++n ) ++cnt;
Public Functions
- inline MinCutNodeIt(
- GomoryHu const & gomory,
- const Node & s,
- const Node & t,
- bool side = true
Constructor.
Constructor.
- Parameters:
gomory – The GomoryHu class. You must call its run() method before initializing this iterator.
s – The base node.
t – The node you want to separate from node
s.side – If it is
true(default) then the iterator lists the nodes of the component containings, otherwise it lists the other component.Note
As the minimum cut is not always unique,
andMinCutNodeIt( gomory , s , t , true );
does not necessarily give the same set of nodes. However, it is ensured thatMinCutNodeIt( gomory , t , s , false );
andMinCutNodeIt( gomory , s , t , true );
together list each node exactly once.MinCutNodeIt( gomory , s , t , false );
-
inline MinCutNodeIt & operator++()
Next node.
-
inline Graph::Node operator++(int)
Postfix incrementation.
Warning
This incrementation returns a
Node, not aMinCutNodeIt, as one may expect.
-
class MinCutEdgeIt
Iterate on the edges of a minimum cut.
This iterator class lists the edges of a minimum cut found by GomoryHu. Before using it, you must allocate a GomoryHu class and call its run() method.
This example computes the value of the minimum cut separating
sfromt.The result will be the same as the value returned by gom.minCutValue(s,t).GomoryHu< Graph > gom( g , capacities ); gom.run(); int value = 0; for( GomoryHu< Graph >::MinCutEdgeIt e( gom , s , t ) ; e != INVALID ; ++e ) value += capacities[ e ];
Public Functions
- inline MinCutEdgeIt(
- GomoryHu const & gomory,
- const Node & s,
- const Node & t,
- bool side = true
Constructor.
Constructor.
- Parameters:
gomory – The GomoryHu class. You must call its run() method before initializing this iterator.
s – The base node.
t – The node you want to separate from node
s.side – If it is
true(default) then the listed arcs will be oriented from the nodes of the component containings, otherwise they will be oriented in the opposite direction.
-
inline MinCutEdgeIt & operator++()
Next edge.
-
inline Graph::Arc operator++(int)
Postfix incrementation.
Warning
This incrementation returns an
Arc, not aMinCutEdgeIt, as one may expect.