abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
KBestFlows< GR , V , C > Class Template Reference

The K best integer flows of a minimum cost flow problem. More...

#include <lemon/k_best_flows.h>

Public Types

typedef GR Digraph
 The type of the digraph.
typedef V Value
 The type of the flow amounts, of the bounds and of the supplies.
typedef C Cost
 The type of the costs.

Public Member Functions

 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.

Detailed Description

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
GRThe digraph type the algorithm runs on.
VThe number type of the flow amounts, of the bounds and of the supplies; by default, int.
CThe 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.

Constructor & Destructor Documentation

◆ KBestFlows()

template< typename GR , typename V = int , typename C = V >
KBestFlows ( const GR & graph)
inlineexplicit

The bounds are 0 and infinite, the costs 1 and the supplies 0 until they are given.

Member Function Documentation

◆ upperMap()

template< typename GR , typename V = int , typename C = V >
template< typename UpperMap >
KBestFlows & upperMap ( const UpperMap & map)
inline

An upper bound that is infinite or the largest value of Value means no bound.

◆ initFlow()

template< typename GR , typename V = int , typename C = V >
template< typename FlowMap >
KBestFlows & initFlow ( const FlowMap & map)
inline

The flow must be optimal for the data given; then no algorithm of minimum cost flow is run.

◆ tolerances()

template< typename GR , typename V = int , typename C = V >
KBestFlows & tolerances ( Value flow,
Cost cost )
inline

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 )

◆ flowTolerance()

template< typename GR , typename V = int , typename C = V >
Tolerance< Value > flowTolerance ( ) const
inline

The one set by tolerances(), if any, and otherwise the one of the data, whose epsilon is zero for an exact type.

◆ costTolerance()

template< typename GR , typename V = int , typename C = V >
Tolerance< Cost > costTolerance ( ) const
inline

As flowTolerance(), for the reduced costs.

◆ run()

template< typename GR , typename V = int , typename C = V >
int run ( int k)
inline
Returns
The number of the flows found, which is less than k if the problem has fewer integer flows, and zero if it has no optimal flow (it is infeasible or unbounded).