This class implements the Hao-Orlin algorithm for finding a minimum value cut in a directed graph . It takes a fixed node
and consists of two phases: in the first phase it determines a minimum cut with
on the source-side (i.e. a set
with
and minimal outgoing capacity) and in the second phase it determines a minimum cut with
on the sink-side (i.e. a set
with
and minimal outgoing capacity). Obviously, the smaller of these two cuts will be a minimum cut of
. The algorithm is a modified preflow push-relabel algorithm. Our implementation calculates the minimum cut in
time (we use the highest-label rule), or in
for unit capacities. The purpose of such algorithm is e.g. 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 time. It is implemented in the NagamochiIbaraki algorithm class.
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>. |
#include <lemon/hao_orlin.h>
Public Types | |
typedef GR | Digraph |
The digraph type of the algorithm. | |
typedef CAP | CapacityMap |
The capacity map type of the algorithm. | |
typedef TOL | Tolerance |
The tolerance type of the algorithm. | |
Public Member Functions | |
HaoOrlin (const Digraph &graph, const CapacityMap &capacity, const Tolerance &tolerance=Tolerance()) | |
Constructor. | |
Execution Control | |
The simplest way to execute the algorithm is to use one of the member functions called run(). | |
void | init () |
Initialize the internal data structures. | |
void | init (const Node &source) |
Initialize the internal data structures. | |
void | calculateOut () |
Calculate a minimum cut with ![]() | |
void | calculateIn () |
Calculate a minimum cut with ![]() | |
void | run () |
Run the algorithm. | |
void | run (const Node &s) |
Run the algorithm. | |
Query Functions | |
The result of the HaoOrlin algorithm can be obtained using these functions. | |
Value | minCutValue () const |
Return the value of the minimum cut. | |
template<typename CutMap > | |
Value | minCutMap (CutMap &cutMap) const |
Return a minimum cut. | |
|
inline |
Constructor of the algorithm class.
|
inline |
This function initializes the internal data structures. It creates the maps and some bucket structures for the algorithm. The first node is used as the source node for the push-relabel algorithm.
|
inline |
This function initializes the internal data structures. It creates the maps and some bucket structures for the algorithm. The given node is used as the source node for the push-relabel algorithm.
|
inline |
This function calculates a minimum cut with on the source-side (i.e. a set
with
and minimal outgoing capacity).
|
inline |
This function calculates a minimum cut with on the sink-side (i.e. a set
with
and minimal outgoing capacity).
|
inline |
This function runs the algorithm. It finds nodes source
and target
arbitrarily and then calls init(), calculateOut() and calculateIn().
|
inline |
This function runs the algorithm. It uses the given source
node, finds a proper target
node and then calls the init(), calculateOut() and calculateIn().
|
inline |
This function returns the value of the minimum cut.
|
inline |
This function sets cutMap
to the characteristic vector of a minimum value cut: it will give a non-empty set with minimal outgoing capacity (i.e.
cutMap
will be true
exactly for the nodes of ).
cutMap | A writable node map with bool (or convertible) value type. |