GomoryHuTree< _UGraph, _Capacity > Class Template Reference
[Minimum Cut algorithms]
Detailed Description
template<typename _UGraph, typename _Capacity = typename _UGraph::template UEdgeMap<int>>
class lemon::GomoryHuTree< _UGraph, _Capacity >
The Gomory-Hu tree is a tree on the nodeset of the graph, but it may contain edges which are not in the original graph. It helps to calculate the minimum cut between all pairs of nodes, because the minimum capacity edge on the tree path between two nodes has the same weight as the minimum cut in the graph between these nodes. Moreover this edge separates the nodes to two parts which determine this minimum cut.
The algorithm calculates n-1 distinict minimum cuts with preflow algorithm, therefore the algorithm has 
overall time complexity. It calculates a rooted Gomory-Hu tree, the structure of the tree and the weights can be obtained with predNode() and predValue() functions. The minCutValue() and minCutMap() calculates the minimum cut and the minimum cut value between any two node in the graph. #include <lemon/gomory_hu_tree.h>
Public Types | |
| typedef _UGraph | UGraph |
| The undirected graph type. | |
| typedef _Capacity | Capacity |
| The capacity on undirected edges. | |
| typedef Capacity::Value | Value |
| The value type of capacities. | |
Public Member Functions | |
| GomoryHuTree (const UGraph &ugraph, const Capacity &capacity) | |
| Constructor. | |
| ~GomoryHuTree () | |
| Destructor. | |
| void | init () |
| void | start () |
| void | run () |
| Runs the Gomory-Hu algorithm. | |
| Node | predNode (const Node &node) |
| Returns the predecessor node in the Gomory-Hu tree. | |
| Value | predValue (const Node &node) |
| Returns the weight of the predecessor edge in the Gomory-Hu tree. | |
| Value | minCutValue (const Node &s, const Node &t) const |
| Returns the minimum cut value between two nodes. | |
| template<typename CutMap > | |
| Value | minCutMap (const Node &s, const Node &t, CutMap &cutMap) const |
| Returns the minimum cut between two nodes. | |
Constructor & Destructor Documentation
| GomoryHuTree | ( | const UGraph & | ugraph, | |
| const Capacity & | capacity | |||
| ) | [inline] |
Constructor
- Parameters:
-
ugraph The undirected graph type. capacity The capacity map.
| ~GomoryHuTree | ( | ) | [inline] |
Destructor
Member Function Documentation
| void init | ( | ) | [inline] |
Initializes the internal data structures.
| void start | ( | ) | [inline] |
Starts the algorithm.
| void run | ( | ) | [inline] |
Runs the Gomory-Hu algorithm.
- Note:
- gh.run() is just a shortcut of the following code.
ght.init(); ght.start();
| Node predNode | ( | const Node & | node | ) | [inline] |
Returns the predecessor node in the Gomory-Hu tree. If the node is the root of the Gomory-Hu tree, then it returns INVALID.
| Value predValue | ( | const Node & | node | ) | [inline] |
Returns the weight of the predecessor edge in the Gomory-Hu tree. If the node is the root of the Gomory-Hu tree, the result is undefined.
| Value minCutValue | ( | const Node & | s, | |
| const Node & | t | |||
| ) | const [inline] |
Returns the minimum cut value between two nodes. The algorithm finds the nearest common ancestor in the Gomory-Hu tree and calculates the minimum weight edge on the paths to the ancestor.
| Value minCutMap | ( | const Node & | s, | |
| const Node & | t, | |||
| CutMap & | cutMap | |||
| ) | const [inline] |
Returns the minimum cut value between two nodes. The algorithm finds the nearest common ancestor in the Gomory-Hu tree and calculates the minimum weight edge on the paths to the ancestor. Then it sets all nodes to the cut determined by this edge. The cutMap should be ReadWriteMap.
