Loading...
Searching...
No Matches
GomoryHu< GR, CAP > Class Template Reference
Algorithms » Minimum Cut Algorithms

## Detailed Description

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>.

`#include <lemon/gomory_hu.h>`

## Classes

class | MinCutNodeIt
| Iterate on the nodes of a minimum cut. More...
class | MinCutEdgeIt
| Iterate on the edges 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 ()
| Destructor.
Execution Control
void | run ()
| Run the Gomory-Hu 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 Gomory-Hu tree.
Value | predValue (const Node &node) const
| Return the weight of the predecessor edge in the Gomory-Hu tree.
int | rootDist (const Node &node) const
| Return the distance from the root node in the Gomory-Hu 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 & Destructor Documentation

## GomoryHu()

template<typename GR, typename CAP>

GomoryHu | ( | const Graph & | graph,
|  | const Capacity & | capacity )

inline

Constructor.

Parameters

  graph | The undirected graph the algorithm runs on.
  capacity | The edge capacity map.

## ~GomoryHu()

template<typename GR, typename CAP>

~GomoryHu | ( |  | ) |

inline

Destructor.

## Member Function Documentation

## run()

template<typename GR, typename CAP>

void run | ( |  | ) |

inline

This function runs the Gomory-Hu algorithm.

## predNode()

template<typename GR, typename CAP>

Node predNode | ( | const Node & | node | ) | const

inline

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`.

Precondition
  run() must be called before using this function.

## predValue()

template<typename GR, typename CAP>

Value predValue | ( | const Node & | node | ) | const

inline

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.

Precondition
  run() must be called before using this function.

## rootDist()

template<typename GR, typename CAP>

int rootDist | ( | const Node & | node | ) | const

inline

This function returns the distance of the given node from the root node in the Gomory-Hu tree.

Precondition
  run() must be called before using this function.

## minCutValue()

template<typename GR, typename CAP>

Value minCutValue | ( | const Node & | s,
|  | const Node & | t ) const

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

Precondition
  run() must be called before using this function.

## minCutMap()

template<typename GR, typename CAP>
template<typename CutMap>

Value minCutMap | ( | const Node & | s,
|  | const Node & | t,
|  | CutMap & | cutMap ) const

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.

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`.

Precondition
  run() must be called before using this function.