#include <lemon/ssp_min_cost_flow.h>
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
.
Graph | The directed graph type the algorithm runs on. | |
LengthMap | The type of the length map. | |
CapacityMap | The capacity map type. |
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. |
SspMinCostFlow | ( | Graph & | _g, | |
LengthMap & | _length, | |||
CapacityMap & | _cap, | |||
Node | _s, | |||
Node | _t | |||
) | [inline] |
_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. |
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.
k | The value of the flow we are looking for. |
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.