SspMinCostFlow Class Template Reference
[Path and Flow Algorithms]

#include <lemon/ssp_min_cost_flow.h>

List of all members.


Detailed Description

template<typename Graph, typename LengthMap, typename CapacityMap>
class lemon::SspMinCostFlow< Graph, LengthMap, CapacityMap >

The Successive Shortest Path Minimum Cost Flow" implements an algorithm for finding a flow of value k having minimal total cost from a given source node to a given target node in a directed graph with a cost function on the edges. To this end, the edge-capacities and edge-costs have to be nonnegative. The edge-capacities should be integers, but the edge-costs can be integers, reals or of other comparable numeric type. This algorithm is intended to be used only for small values of k, since it is only polynomial in k, not in the length of k (which is log k): in order to find the minimum cost flow of value k it finds the minimum cost flow of value i for every i between 0 and k.

Parameters:
Graph The directed graph type the algorithm runs on.
LengthMap The type of the length map.
CapacityMap The capacity map type.
Author:
Attila Bernath


Public Member Functions

 SspMinCostFlow (Graph &_g, LengthMap &_length, CapacityMap &_cap, Node _s, Node _t)
 The constructor of the class.
bool augment ()
 Tries to augment the flow between s and t by 1. The return value shows if the augmentation is successful.
int run (int k)
 Runs the algorithm.
void reset ()
 The class is reset to zero flow and potential. The class is reset to zero flow and potential.
int flowValue () const
 Returns the value of the actual flow.
Length totalLength ()
 Total cost of the found flow.
const EdgeIntMap & getFlow () const
 Returns a const reference to the EdgeMap flow.
const PotentialMap & getPotential () const
 Returns a const reference to the NodeMap potential (the dual solution).
bool checkComplementarySlackness ()
 Checking the complementary slackness optimality criteria.


Constructor & Destructor Documentation

SspMinCostFlow ( Graph _g,
LengthMap &  _length,
CapacityMap &  _cap,
Node  _s,
Node  _t 
) [inline]

Parameters:
_g The directed graph the algorithm runs on.
_length The length (cost) of the edges.
_cap The capacity of the edges.
_s Source node.
_t Target node.


Member Function Documentation

int run ( int  k  )  [inline]

Runs the algorithm. Returns k if there is a flow of value at least k from s to t. Otherwise it returns the maximum value of a flow from s to t.

Parameters:
k The value of the flow we are looking for.
Todo:
May be it does make sense to be able to start with a nonzero feasible primal-dual solution pair as well.
Todo:
If the actual flow value is bigger than k, then everything is cleared and the algorithm starts from zero flow. Is it a good approach?

Length totalLength (  )  [inline]

This function gives back the total cost of the found flow.

const EdgeIntMap& getFlow (  )  const [inline]

Returns a const reference to the EdgeMap flow.

const PotentialMap& getPotential (  )  const [inline]

Returns a const reference to the NodeMap potential (the dual solution).

bool checkComplementarySlackness (  )  [inline]

This function checks, whether the given flow and potential satisfy the complementary slackness conditions (i.e. these are optimal). This function only checks optimality, doesn't bother with feasibility. For testing purpose.

Todo:
better comparison is needed for real types, moreover, this comparison here is superfluous.


The documentation for this class was generated from the following file:
Generated on Tue Oct 31 09:51:21 2006 for LEMON by  doxygen 1.5.1