DinitzSleatorTarjan< _Graph, _CapacityMap, _Traits > Class Template Reference
[Maximum Flow algorithms]

Detailed Description

template<typename _Graph, typename _CapacityMap, typename _Traits>
class lemon::DinitzSleatorTarjan< _Graph, _CapacityMap, _Traits >

This class provides an implementation of the Dinitz-Sleator-Tarjan algorithm producing a flow of maximum value in a directed graph. The DinitzSleatorTarjan algorithm is the fastest known max flow algorithms wich using blocking flow. It is an improvement of the Dinitz algorithm by using the dynamic tree data structure of Sleator and Tarjan.

This blocking flow algorithms builds a layered graph according to breadth-first search distance from the target node in the reversed residual graph. The layered graph contains each residual edge which steps one level down. After that the algorithm constructs a blocking flow on the layered graph and augments the overall flow with it. The number of the levels in the layered graph is strictly increasing in each augmenting phase therefore the number of the augmentings is at most $n-1$. The length of each phase is at most $O(m\log(n))$, that the overall time complexity is $O(nm\log(n))$.

Parameters:
_Graph The directed graph type the algorithm runs on.
_CapacityMap The capacity map type.
_Traits Traits class to set various data types used by the algorithm. The default traits class is DinitzSleatorTarjanDefaultTraits. See DinitzSleatorTarjanDefaultTraits for the documentation of a Dinitz-Sleator-Tarjan traits class.
Author:
Tamas Hamori and Balazs Dezso
#include <lemon/dinitz_sleator_tarjan.h>

List of all members.

Classes

struct  DefFlowMap
class  InvalidArgument

Public Member Functions

 DinitzSleatorTarjan (const Graph &graph, const CapacityMap &capacity, Node source, Node target)
 The constructor of the class.
 ~DinitzSleatorTarjan ()
 Destrcutor.
DinitzSleatorTarjan & capacityMap (const CapacityMap &map)
 Sets the capacity map.
DinitzSleatorTarjan & flowMap (FlowMap &map)
 Sets the flow map.
const FlowMap & flowMap ()
 Returns the flow map.
DinitzSleatorTarjan & source (const Node &node)
 Sets the source node.
DinitzSleatorTarjan & target (const Node &node)
 Sets the target node.
DinitzSleatorTarjan & tolerance (const Tolerance &tolerance) const
const Tolerance & tolerance () const
Execution control The simplest way to execute the
algorithm is to use the run() member functions.
If you need more control on initial solution or execution then you have to call one init() function and then the start() or multiple times the augment() member function.

void init ()
 Initializes the algorithm.
template<typename FlowMap >
void flowInit (const FlowMap &flowMap)
 Initializes the algorithm.
template<typename FlowMap >
bool checkedFlowInit (const FlowMap &flowMap)
 Initializes the algorithm.
void start ()
 Executes the algorithm.
bool augment ()
 Augments the flow with a blocking flow on a layered graph.
void run ()
 runs the algorithm.
Query Functions
The result of the Dinitz-Sleator-Tarjan algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.

Value flowValue () const
 Returns the value of the maximum flow.
Value flow (const Edge &edge) const
 Returns the flow on the edge.
bool minCut (const Node &node) const
 Returns true when the node is on the source side of minimum cut.
template<typename CutMap >
void minCutMap (CutMap &cutMap) const
 Returns a minimum value cut.

Constructor & Destructor Documentation

DinitzSleatorTarjan ( const Graph &  graph,
const CapacityMap &  capacity,
Node  source,
Node  target 
) [inline]

The constructor of the class.

Parameters:
graph The directed graph the algorithm runs on.
capacity The capacity of the edges.
source The source node.
target The target node.

~DinitzSleatorTarjan (  )  [inline]

Destructor.

Member Function Documentation

DinitzSleatorTarjan& capacityMap ( const CapacityMap &  map  )  [inline]

Sets the capacity map.

Returns:
(*this)

DinitzSleatorTarjan& flowMap ( FlowMap &  map  )  [inline]

Sets the flow map.

Returns:
(*this)

const FlowMap& flowMap (  )  [inline]

Returns:
The flow map.

DinitzSleatorTarjan& source ( const Node &  node  )  [inline]

Sets the source node.

Returns:
(*this)

DinitzSleatorTarjan& target ( const Node &  node  )  [inline]

Sets the target node.

Returns:
(*this)

DinitzSleatorTarjan& tolerance ( const Tolerance &  tolerance  )  const [inline]

Sets the tolerance used by algorithm.

const Tolerance& tolerance (  )  const [inline]

Returns the tolerance used by algorithm.

void init (  )  [inline]

It sets the flow to empty flow.

void flowInit ( const FlowMap &  flowMap  )  [inline]

Initializes the flow to the flowMap. The flowMap should contain a feasible flow, ie. in each node excluding the source and the target the incoming flow should be equal to the outgoing flow.

bool checkedFlowInit ( const FlowMap &  flowMap  )  [inline]

Initializes the flow to the flowMap. The flowMap should contain a feasible flow, ie. in each node excluding the source and the target the incoming flow should be equal to the outgoing flow.

Returns:
False when the given flowMap does not contain feasible flow.

void start (  )  [inline]

It runs augmenting phases by adding blocking flow until the optimal solution is reached.

bool augment (  )  [inline]

This function builds a layered graph and then find a blocking flow on this graph. The number of the levels in the layered graph is strictly increasing in each augmenting phase therefore the number of the augmentings is at most $ n-1 /// $. The length of each phase is at most $ O(m \log(n)) /// $, that the overall time complexity is $ O(nm \log(n)) $.

Returns:
False when there is not residual path between the source and the target so the current flow is a feasible and optimal solution.

void run (  )  [inline]

It is just a shorthand for:

        ek.init();
        ek.start();

Value flowValue (  )  const [inline]

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

Value flow ( const Edge &  edge  )  const [inline]

Sets the flowMap to the flow on the edges. This method can be called after the second phase of algorithm.

bool minCut ( const Node &  node  )  const [inline]

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

void minCutMap ( CutMap &  cutMap  )  const [inline]

Sets cut to the characteristic vector of a minimum value cut It simply calls the minMinCut member.

Return values:
cut Write node bool map.

Generated on Thu Jun 4 04:04:03 2009 for LEMON by  doxygen 1.5.9