KBestFlows
Declared in lemon/k_best_flows.h, in the group Minimum Cost Flow Algorithms; the same class on the Doxygen site.
-
template< typename GR , typename V = int , typename C = V >
class KBestFlows The K best integer flows of a minimum cost flow problem.
This class finds the K integer flows of least cost of a minimum cost flow problem with the
GEQsupply 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.
Warning
The bounds and the supplies must be integer (with a floating-point
Vtoo, 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.- 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.
Public Types
Public Functions
-
inline explicit KBestFlows( const GR & graph )
Constructor.
The bounds are 0 and infinite, the costs 1 and the supplies 0 until they are given.
-
template< typename LowerMap >
inline KBestFlows & lowerMap( const LowerMap & map ) Sets the lower bounds of the arcs.
-
template< typename UpperMap >
inline KBestFlows & upperMap( const UpperMap & map ) Sets the upper bounds of the arcs.
An upper bound that is infinite or the largest value of
Valuemeans no bound.
-
template< typename CostMap >
inline KBestFlows & costMap( const CostMap & map ) Sets the costs of the arcs.
-
template< typename SupplyMap >
inline KBestFlows & supplyMap( const SupplyMap & map ) Sets the supplies of the nodes (negative for the demands).
-
template< typename FlowMap >
inline KBestFlows & initFlow( const FlowMap & map ) Gives the optimal flow to start from.
The flow must be optimal for the data given; then no algorithm of minimum cost flow is run.
-
inline KBestFlows & tolerances( Value flow , Cost cost )
Sets the tolerances on the flows and on the reduced costs.
Those of the minimum cost flow algorithms [see NetworkSimplex::tolerances()], given to the NetworkSimplex that finds the optimal flow; the search of the next flows compares exactly, on integer data. A negative value, the default, leaves the tolerance to the data.
- Returns:
(*this)
-
inline Tolerance< Value > flowTolerance() const
The tolerance on the flows in use, as a Tolerance.
The one set by tolerances(), if any, and otherwise the one of the data, whose epsilon is zero for an exact type.
-
inline Tolerance< Cost > costTolerance() const
The tolerance on the reduced costs in use, as a Tolerance.
As flowTolerance(), for the reduced costs.
-
inline int run( int k )
Finds the k best flows.
- Returns:
The number of the flows found, which is less than
kif the problem has fewer integer flows, and zero if it has no optimal flow (it is infeasible or unbounded).