Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

MinCostFlow Class Template Reference
[Path and Flow Algorithms]

#include <lemon/min_cost_flow.h>

Inheritance diagram for MinCostFlow:

Inheritance graph
[legend]
Collaboration diagram for MinCostFlow:

Collaboration graph
[legend]
List of all members.

Detailed Description

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

The class MinCostFlow 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 an edge-weighted directed graph. To this end, the edge-capacities and edge-weitghs have to be nonnegative. The edge-capacities should be integers, but the edge-weights can be integers, reals or of other comparable numeric type. This algorithm is intended to use 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

Definition at line 60 of file min_cost_flow.h.

Public Member Functions

 MinCostFlow (Graph &_g, LengthMap &_length, CapacityMap &_cap, Node _s, Node _t)
 The constructor of the class.
bool augment ()
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
Length totalLength ()
 Total weight of the found flow. This function gives back the total weight of the found flow.
const EdgeIntMap & getFlow () const
 Returns a const reference to the EdgeMap flow. 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

MinCostFlow Graph &  _g,
LengthMap &  _length,
CapacityMap &  _cap,
Node  _s,
Node  _t
[inline]
 

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

Definition at line 127 of file min_cost_flow.h.


Member Function Documentation

bool augment  )  [inline]
 

Tries to augment the flow between s and t by 1. The return value shows if the augmentation is successful.

Definition at line 140 of file min_cost_flow.h.

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?

Definition at line 184 of file min_cost_flow.h.

int flowValue  )  const [inline]
 

Returns the value of the actual flow.

Definition at line 201 of file min_cost_flow.h.

const PotentialMap& getPotential  )  const [inline]
 

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

Definition at line 224 of file min_cost_flow.h.

bool checkComplementarySlackness  )  [inline]
 

This function checks, whether the given flow and potential satisfiy the complementary slackness cnditions (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.

Definition at line 233 of file min_cost_flow.h.


The documentation for this class was generated from the following file:
Generated on Mon Feb 21 15:02:35 2005 for LEMON by  doxygen 1.4.1