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() and rootDist(), which gives an order of the nodes from the root. 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 >.

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.

run()

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 node is the root of the tree, then it returns INVALID.

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 node is 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 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; if s and t are the same node, it returns the largest Value.

Pre:

run() must be called before using this function.

template< typename CutMap >
inline Value minCutMap(
const Node & s,
const Node & t,
CutMap & cutMap
) const

Return the minimum cut between two nodes.

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.

If s and t are the same node, then no cut separates them: all the nodes are set to true and the largest Value is 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 s and t.

Pre:

run() must be called before using this function.

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 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 const Tolerance< Value > & tolerance() const

Returns a const reference to the tolerance.

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 s from t.

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 containing s, otherwise it lists the other component.

    Note

    As the minimum cut is not always unique,

    MinCutNodeIt( gomory , s , t , true );
    
    and
    MinCutNodeIt( gomory , t , s , false );
    
    does not necessarily give the same set of nodes. However, it is ensured that
    MinCutNodeIt( gomory , s , t , true );
    
    and
    MinCutNodeIt( gomory , s , t , false );
    
    together list each node exactly once.

inline operator typename Graph::Node() const

Conversion to Node.

inline bool operator==(Invalid)
inline bool operator!=(Invalid)
inline MinCutNodeIt & operator++()

Next node.

inline Graph::Node operator++(int)

Postfix incrementation.

Warning

This incrementation returns a Node, not a MinCutNodeIt, 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 s from 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 ];
The result will be the same as the value returned by gom.minCutValue(s,t).

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 containing s, otherwise they will be oriented in the opposite direction.

inline operator typename Graph::Arc() const

Conversion to Arc.

inline operator typename Graph::Edge() const

Conversion to Edge.

inline bool operator==(Invalid)
inline bool operator!=(Invalid)
inline MinCutEdgeIt & operator++()

Next edge.

inline Graph::Arc operator++(int)

Postfix incrementation.

Warning

This incrementation returns an Arc, not a MinCutEdgeIt, as one may expect.