|
| | HaoOrlin (const Digraph &graph, const CapacityMap &capacity, const Tolerance &tolerance=Tolerance()) |
| | Constructor.
|
| HaoOrlin & | tolerance (const Tolerance &tolerance) |
| | Set the tolerance used by the algorithm.
|
| const Tolerance & | tolerance () const |
| | Returns a const reference to the tolerance.
|
The simplest way to execute the algorithm is to use one of the member functions called run().
If you need better control on the execution, you have to call one of the init() functions first, then calculateOut() and/or calculateIn().
|
| void | init () |
| | Initialize the internal data structures.
|
| void | init (const Node &source) |
| | Initialize the internal data structures.
|
| void | calculateOut () |
| | Calculate a minimum cut with \( source \) on the source-side.
|
| void | calculateIn () |
| | Calculate a minimum cut with \( source \) on the sink-side.
|
| void | run () |
| | Run the algorithm.
|
| void | run (const Node &s) |
| | Run the algorithm.
|
The result of the HaoOrlin algorithm can be obtained using these functions.
run(), calculateOut() or calculateIn() should be called before using them.
|
| Value | minCutValue () const |
| | Return the value of the minimum cut.
|
| template< typename CutMap > |
| Value | minCutMap (CutMap &cutMap) const |
| | Return a minimum cut.
|
template< typename GR , typename CAP , typename TOL >
class lemon::HaoOrlin< GR , CAP , TOL >
This class implements the Hao-Orlin algorithm for finding a minimum value cut in a directed graph \(D=(V,A)\). It takes a fixed node \( source \in V \) and consists of two phases: in the first phase it determines a minimum cut with \( source \) on the source-side (i.e. a set \( X\subsetneq V \) with \( source \in X \) and minimal outgoing capacity) and in the second phase it determines a minimum cut with \( source \) on the sink-side (i.e. a set \( X\subsetneq V \) with \( source \notin X \) and minimal outgoing capacity). Obviously, the smaller of these two cuts will be a minimum cut of \( D \). The algorithm is a modified preflow push-relabel algorithm. Our implementation calculates the minimum cut in \( O(n^2\sqrt{m}) \) time (we use the highest-label rule), or in \(O(nm)\) for unit capacities. A notable use of this algorithm is testing network reliability.
For an undirected graph you can run just the first phase of the algorithm or you can use the algorithm of Nagamochi and Ibaraki, which solves the undirected problem in \( O( nm + n^2 \log n ) \) time. It is implemented in the NagamochiIbaraki algorithm class.
- Template Parameters
-
| GR | The type of the digraph the algorithm runs on. |
| CAP | The type of the arc map containing the capacities, which can be any numreric type. The default map type is GR::ArcMap< int >. |
| TOL | Tolerance class for handling inexact computations. The default tolerance type is Tolerance< CAP::Value >. |
template< typename GR , typename CAP , typename TOL >
template< typename CutMap >
| Value minCutMap |
( |
CutMap & | cutMap | ) |
const |
|
inline |
This function gives the best cut found by the previously called run(), calculateOut() or calculateIn().
It sets cutMap to the characteristic vector of the found minimum value cut - a non-empty set \( X\subsetneq V \) of minimum outgoing capacity (i.e. cutMap will be true exactly for the nodes of \( X \)).
- Parameters
-
| cutMap | A writable node map with bool (or convertible) value type. |
- Returns
- The value of the minimum cut.
- Precondition
- run(), calculateOut() or calculateIn() must be called before using this function.