#include <lemon/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 | |
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 () |
This function gives back the 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. |
|
|
|
Tries to augment the flow between s and t by 1. The return value shows if the augmentation is successful. |
|
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.
|
|
Returns the value of the actual flow. |
|
Returns a const reference to the NodeMap |
|
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.
|