|
| | GomoryHu (const Graph &graph, const Capacity &capacity) |
| | Constructor.
|
| GomoryHu & | tolerance (const Tolerance< Value > &tolerance) |
| | Sets the tolerance used by the algorithm.
|
|
const Tolerance< Value > & | tolerance () const |
| | Returns a const reference to the tolerance.
|
| | ~GomoryHu () |
| | Destructor.
|
| void | run () |
| | Run the Gomory-Hu algorithm.
|
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 position of the node in an order of the 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.
|
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 \(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 >. |
template< typename GR , typename CAP >
| int rootDist |
( |
const Node & | node | ) |
const |
|
inline |
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.
- Precondition
- run() must be called before using this function.
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.
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.
- Precondition
- run() must be called before using this function.