#include <lemon/min_cost_flow.h>
Inheritance diagram for MinCostFlow:
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
.
Graph | The directed graph type the algorithm runs on. | |
LengthMap | The type of the length map. | |
CapacityMap | The capacity map type. |
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. |
|
Definition at line 127 of file min_cost_flow.h. |
|
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. |
|
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.
Definition at line 184 of file min_cost_flow.h. |
|
Returns the value of the actual flow. Definition at line 201 of file min_cost_flow.h. |
|
Returns a const reference to the NodeMap Definition at line 224 of file min_cost_flow.h. |
|
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.
Definition at line 233 of file min_cost_flow.h. |