Classes | Public Types | Public Member Functions

Preflow< GR, CAP, TR > Class Template Reference


Detailed Description

template<typename GR, typename CAP, typename TR>
class lemon::Preflow< GR, CAP, TR >

This class provides an implementation of Goldberg-Tarjan's preflow push-relabel algorithm producing a flow of maximum value in a digraph. The preflow algorithms are the fastest known maximum flow algorithms. The current implementation use a mixture of the "highest label" and the "bound decrease" heuristics. The worst case time complexity of the algorithm is $O(n^2\sqrt{e})$.

The algorithm consists of two phases. After the first phase the maximum flow value and the minimum cut is obtained. The second phase constructs a feasible maximum flow on each arc.

Template Parameters:
GRThe type of the digraph the algorithm runs on.
CAPThe type of the capacity map. The default map type is GR::ArcMap<int>.

#include <lemon/preflow.h>

List of all members.

Classes

struct  SetElevator
 Named parameter for setting Elevator type More...
struct  SetFlowMap
 Named parameter for setting FlowMap type More...
struct  SetStandardElevator
 Named parameter for setting Elevator type with automatic allocation More...

Public Types

typedef TR Traits
 The traits class of the algorithm.
typedef Traits::Digraph Digraph
 The type of the digraph the algorithm runs on.
typedef Traits::CapacityMap CapacityMap
 The type of the capacity map.
typedef Traits::Value Value
 The type of the flow values.
typedef Traits::FlowMap FlowMap
 The type of the flow map.
typedef Traits::Elevator Elevator
 The type of the elevator.
typedef Traits::Tolerance Tolerance
 The type of the tolerance.

Public Member Functions

 Preflow (const Digraph &digraph, const CapacityMap &capacity, Node source, Node target)
 The constructor of the class.
 ~Preflow ()
PreflowcapacityMap (const CapacityMap &map)
 Sets the capacity map.
PreflowflowMap (FlowMap &map)
 Sets the flow map.
Preflowsource (const Node &node)
 Sets the source node.
Preflowtarget (const Node &node)
 Sets the target node.
Preflowelevator (Elevator &elevator)
 Sets the elevator used by algorithm.
const Elevatorelevator () const
 Returns a const reference to the elevator.
Preflowtolerance (const Tolerance &tolerance)
const Tolerancetolerance () const
Execution Control

The simplest way to execute the preflow algorithm is to use run() or runMinCut().
If you need more control on the initial solution or the execution, first you have to call one of the init() functions, then startFirstPhase() and if you need it startSecondPhase().

void init ()
 Initializes the internal data structures.
template<typename FlowMap >
bool init (const FlowMap &flowMap)
 Initializes the internal data structures using the given flow map.
void startFirstPhase ()
 Starts the first phase of the preflow algorithm.
void startSecondPhase ()
 Starts the second phase of the preflow algorithm.
void run ()
 Runs the preflow algorithm.
void runMinCut ()
 Runs the preflow algorithm to compute the minimum cut.
Query Functions

The results of the preflow algorithm can be obtained using these functions.
Either one of the run*() functions or one of the start*() functions should be called before using them.

Value flowValue () const
 Returns the value of the maximum flow.
Value flow (const Arc &arc) const
 Returns the flow value on the given arc.
const FlowMapflowMap () const
 Returns a const reference to the flow map.
bool minCut (const Node &node) const
 Returns true when the node is on the source side of the minimum cut.
template<typename CutMap >
void minCutMap (CutMap &cutMap) const
 Gives back a minimum value cut.

Constructor & Destructor Documentation

Preflow ( const Digraph digraph,
const CapacityMap capacity,
Node  source,
Node  target 
) [inline]

The constructor of the class.

Parameters:
digraphThe digraph the algorithm runs on.
capacityThe capacity of the arcs.
sourceThe source node.
targetThe target node.
~Preflow ( ) [inline]

Destructor.


Member Function Documentation

Preflow& capacityMap ( const CapacityMap map) [inline]

Sets the capacity map.

Returns:
(*this)
Preflow& flowMap ( FlowMap map) [inline]

Sets the flow map. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

Returns:
(*this)
Preflow& source ( const Node &  node) [inline]

Sets the source node.

Returns:
(*this)
Preflow& target ( const Node &  node) [inline]

Sets the target node.

Returns:
(*this)
Preflow& elevator ( Elevator elevator) [inline]

Sets the elevator used by algorithm. If you don't use this function before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated elevator, of course.

Returns:
(*this)
const Elevator& elevator ( ) const [inline]

Returns a const reference to the elevator.

Precondition:
Either run() or init() must be called before using this function.
Preflow& tolerance ( const Tolerance tolerance) [inline]

Sets the tolerance used by algorithm.

const Tolerance& tolerance ( ) const [inline]

Returns a const reference to the tolerance.

void init ( ) [inline]

Initializes the internal data structures and sets the initial flow to zero on each arc.

bool init ( const FlowMap flowMap) [inline]

Initializes the internal data structures and sets the initial flow to the given flowMap. The flowMap should contain a flow or at least a preflow, i.e. at each node excluding the source node the incoming flow should greater or equal to the outgoing flow.

Returns:
false if the given flowMap is not a preflow.
void startFirstPhase ( ) [inline]

The preflow algorithm consists of two phases, this method runs the first phase. After the first phase the maximum flow value and a minimum value cut can already be computed, although a maximum flow is not yet obtained. So after calling this method flowValue() returns the value of a maximum flow and minCut() returns a minimum cut.

Precondition:
One of the init() functions must be called before using this function.
void startSecondPhase ( ) [inline]

The preflow algorithm consists of two phases, this method runs the second phase. After calling one of the init() functions and startFirstPhase() and then startSecondPhase(), flowMap() returns a maximum flow, flowValue() returns the value of a maximum flow, minCut() returns a minimum cut

Precondition:
One of the init() functions and startFirstPhase() must be called before using this function.
void run ( ) [inline]

Runs the preflow algorithm.

Note:
pf.run() is just a shortcut of the following code.
   pf.init();
   pf.startFirstPhase();
   pf.startSecondPhase();
void runMinCut ( ) [inline]

Runs the preflow algorithm to compute the minimum cut.

Note:
pf.runMinCut() is just a shortcut of the following code.
   pf.init();
   pf.startFirstPhase();
Value flowValue ( ) const [inline]

Returns the value of the maximum flow by returning the excess of the target node. This value equals to the value of the maximum flow already after the first phase of the algorithm.

Precondition:
Either run() or init() must be called before using this function.
Value flow ( const Arc &  arc) const [inline]

Returns the flow value on the given arc. This method can be called after the second phase of the algorithm.

Precondition:
Either run() or init() must be called before using this function.
const FlowMap& flowMap ( ) const [inline]

Returns a const reference to the arc map storing the found flow. This method can be called after the second phase of the algorithm.

Precondition:
Either run() or init() must be called before using this function.
bool minCut ( const Node &  node) const [inline]

Returns true when the node is on the source side of the found minimum cut. This method can be called both after running startFirstPhase() and startSecondPhase().

Precondition:
Either run() or init() must be called before using this function.
void minCutMap ( CutMap &  cutMap) const [inline]

Sets cutMap to the characteristic vector of a minimum value cut. cutMap should be a writable node map with bool (or convertible) value type.

This method can be called both after running startFirstPhase() and startSecondPhase(). The result after the second phase could be slightly different if inexact computation is used.

Note:
This function calls minCut() for each node, so it runs in O(n) time.
Precondition:
Either run() or init() must be called before using this function.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines