Preflow

Declared in lemon/preflow.h, in the group Maximum Flow Algorithms; the same class on the Doxygen site.

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

Preflow algorithm class.

This class provides an implementation of Goldberg-Tarjan’s preflow push-relabel algorithm producing a flow of maximum value in a digraph [7], [1], [16]. The preflow algorithms are the fastest known maximum flow algorithms. The current implementation uses a mixture of the “highest label” and the “bound decrease” heuristics. Each phase runs in \(O( n^2 m \Delta )\) time, where \(\Delta\) is the largest number of arcs incident to a node, since a node scans its arcs from the first one at each selection; the bound \(O(n^2\sqrt{m})\) of the highest label rule needs a current arc for each node, which this implementation does not keep.

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.

Warning

This implementation cannot handle infinite or very large capacities (e.g. the maximum value of CAP::Value).

Template Parameters:
  • GR – The type of the digraph the algorithm runs on.

  • CAP – The type of the capacity map. The default map type is GR::ArcMap< int >.

  • TR – The traits class that defines various types used by the algorithm. By default, it is PreflowDefaultTraits< GR , CAP >. In most cases, this parameter should not be set directly, consider to use the named template parameters instead.

Execution Control

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

inline void init()

Initializes the internal data structures.

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

template< typename FlowMap >
inline bool init( const FlowMap & flowMap )

Initializes the internal data structures using the given flow map.

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 be greater or equal to the outgoing flow.

Returns:

false if the given flowMap is not a preflow.

inline void startFirstPhase()

Starts the first phase of the preflow algorithm.

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.

Pre:

One of the init() functions must be called before using this function.

inline void startSecondPhase()

Starts the second phase of the preflow algorithm.

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

Pre:

One of the init() functions and startFirstPhase() must be called before using this function.

inline void run()

Runs the preflow algorithm.

Note

pf.run() is just a shortcut of the following code.

pf.init();
pf.startFirstPhase();
pf.startSecondPhase();

inline void runMinCut()

Runs the preflow algorithm to compute the minimum cut.

Note

pf.runMinCut() is just a shortcut of the following code.

pf.init();
pf.startFirstPhase();

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.

inline Value flowValue() const

Returns the value of the maximum flow.

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.

Pre:

Either run() or init() must be called before using this function.

inline Value flow( const Arc & arc ) const

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

Pre:

Either run() or init() must be called before using this function.

inline const FlowMap & flowMap() const

Returns a const reference to the flow map.

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

Pre:

Either run() or init() must be called before using this function.

inline bool minCut( const Node & node ) const

Returns true when the node is on the source side of the minimum cut.

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().

Pre:

Either run() or init() must be called before using this function.

template< typename CutMap >
inline void minCutMap( CutMap & cutMap ) const

Gives back a minimum value cut.

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.

Pre:

Either run() or init() must be called before using this function.

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.

typedef Preflow Create

Public Functions

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

The constructor of the class.

Parameters:
  • digraph – The digraph the algorithm runs on.

  • capacity – The capacity of the arcs.

  • source – The source node.

  • target – The target node.

inline ~Preflow()

Destructor.

inline Preflow & capacityMap( const CapacityMap & map )

Sets the capacity map.

Returns:

(*this)

inline Preflow & flowMap( FlowMap & map )

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)

inline Preflow & source( const Node & node )

Sets the source node.

Returns:

(*this)

inline Preflow & target( const Node & node )

Sets the target node.

Returns:

(*this)

inline Preflow & elevator( Elevator & elevator )

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)

inline const Elevator & elevator() const

Returns a const reference to the elevator.

Pre:

Either run() or init() must be called before using this function.

inline Preflow & tolerance( const Tolerance & tolerance )

Sets the tolerance used by the algorithm.

Sets the tolerance object used by the algorithm.

Returns:

(*this)

inline const Tolerance & tolerance() const

Returns a const reference to the tolerance.

Returns a const reference to the tolerance object used by the algorithm.

Protected Functions

inline Preflow()
template< typename T >
struct SetFlowMapTraits : public Traits

Public Types

typedef T FlowMap

Public Static Functions

static inline FlowMap * createFlowMap( const Digraph & )
template< typename T >
struct SetFlowMap : public Preflow< Digraph , CapacityMap , SetFlowMapTraits< T > >

Named parameter for setting FlowMap type.

Public Types

typedef Preflow< Digraph , CapacityMap , SetFlowMapTraits< T > > Create
template< typename T >
struct SetElevatorTraits : public Traits

Public Types

typedef T Elevator

Public Static Functions

static inline Elevator * createElevator( const Digraph & , int )
template< typename T >
struct SetElevator : public Preflow< Digraph , CapacityMap , SetElevatorTraits< T > >

Named parameter for setting Elevator type. If this named parameter is used, then an external elevator object must be passed to the algorithm using the elevator() function before calling run() or init().

Public Types

typedef Preflow< Digraph , CapacityMap , SetElevatorTraits< T > > Create
template< typename T >
struct SetStandardElevatorTraits : public Traits

Public Types

typedef T Elevator

Public Static Functions

static inline Elevator * createElevator( const Digraph & digraph , int max_level )
template< typename T >
struct SetStandardElevator : public Preflow< Digraph , CapacityMap , SetStandardElevatorTraits< T > >

Named parameter for setting Elevator type with automatic allocation. The Elevator should have standard constructor interface to be able to automatically created by the algorithm (i.e. the digraph and the maximum level should be passed to it). However, an external elevator object could also be passed to the algorithm with the elevator() function before calling run() or init().

See also

SetElevator

Public Types

typedef Preflow< Digraph , CapacityMap , SetStandardElevatorTraits< T > > Create