|
| | KBestFlows (const GR &graph) |
| | Constructor.
|
|
template< typename LowerMap > |
| KBestFlows & | lowerMap (const LowerMap &map) |
| | Sets the lower bounds of the arcs.
|
| template< typename UpperMap > |
| KBestFlows & | upperMap (const UpperMap &map) |
| | Sets the upper bounds of the arcs.
|
|
template< typename CostMap > |
| KBestFlows & | costMap (const CostMap &map) |
| | Sets the costs of the arcs.
|
|
template< typename SupplyMap > |
| KBestFlows & | supplyMap (const SupplyMap &map) |
| | Sets the supplies of the nodes (negative for the demands).
|
| template< typename FlowMap > |
| KBestFlows & | initFlow (const FlowMap &map) |
| | Gives the optimal flow to start from.
|
| KBestFlows & | tolerances (Value flow, Cost cost) |
| | Sets the tolerances on the flows and on the reduced costs.
|
| Tolerance< Value > | flowTolerance () const |
| | The tolerance on the flows in use, as a Tolerance.
|
| Tolerance< Cost > | costTolerance () const |
| | The tolerance on the reduced costs in use, as a Tolerance.
|
| int | run (int k) |
| | Finds the k best flows.
|
|
int | flowNum () const |
| | The number of the flows found by the last run().
|
|
Cost | totalCost (int i) const |
| | The total cost of the i-th flow, the first being 0.
|
|
Value | flow (int i, const Arc &a) const |
| | The flow on an arc in the i-th flow, the first being 0.
|
|
template< typename FlowMap > |
| void | flowMap (int i, FlowMap &map) const |
| | Copies the i-th flow, the first being 0, into a map.
|
template< typename GR , typename V = int , typename C = V >
class lemon::KBestFlows< GR , V , C >
This class finds the K integer flows of least cost of a minimum cost flow problem with the GEQ supply constraints, in the order of their costs: first an optimal flow, then the other optimal flows, if any, then the suboptimal ones.
The algorithm is the one of Hamacher [21]. The second best flow of a set of flows whose best one is known differs from it by one unit along a cycle of the residual network, which is the one of least cost: the difference between the two is a circulation in that network, whose cycles all have a nonnegative cost, and one unit along any of them gives a flow of the set no costlier than the second one. The set is then split on an arc where the two flows differ, as Lawler [29] does for the K best solutions of any problem: on one side the flow of the arc keeps the value it has in the best flow, which remains the best of that side, and on the other it takes the value of the second one, which becomes the best of that side; the next flow is the cheapest of the second best flows of the sides. The cycle of least cost through each residual arc is found by the algorithm of Dijkstra with the reduced costs of potentials that the algorithm of Bellman and Ford computes: one search from each node, and one more for each residual arc whose shortest path back is its own reverse, which is not a cycle. The k-th flow then takes \(O( nm\log n )\) time after the (k-1)-th, and \(O( m^2\log n )\) at worst.
The first flow is an optimal one that NetworkSimplex finds, or any optimal flow given by initFlow(): the sequence does not depend on the algorithm that found it, but for the order of the flows of equal cost.
- Template Parameters
-
| GR | The digraph type the algorithm runs on. |
| V | The number type of the flow amounts, of the bounds and of the supplies; by default, int. |
| C | The number type of the costs; by default, the same as V. |
- Warning
- The bounds and the supplies must be integer (with a floating-point
V too, whose values are then integer ones), since the flows differ from each other by whole units; the upper bounds may be infinite, but then no cycle of negative cost may be made of arcs of infinite upper bound, or the problem has no optimal flow.