MinCostFlow< Graph, LowerMap, CapacityMap, CostMap, SupplyMap > Class Template Reference
[Minimum Cost Flow algorithms]

---

Detailed Description

template<typename Graph, typename LowerMap = typename Graph::template EdgeMap<int>, typename CapacityMap = typename Graph::template EdgeMap<int>, typename CostMap = typename Graph::template EdgeMap<int>, typename SupplyMap = typename Graph::template NodeMap<int>>
class lemon::MinCostFlow< Graph, LowerMap, CapacityMap, CostMap, SupplyMap >

MinCostFlow provides an efficient algorithm for finding a minimum cost flow.

This class is just an alias for NetworkSimplex, which is the most efficient algorithm for the minimum cost flow problem in LEMON according to our benchmark tests. For the detailed documentation of this class see NetworkSimplex.

There are four implementations for the minimum cost flow problem, which can be used exactly the same way.

• CapacityScaling
• CostScaling
• CycleCanceling
• NetworkSimplex

Template Parameters:

	Graph	The directed graph type the algorithm runs on.
	LowerMap	The type of the lower bound map.
	CapacityMap	The type of the capacity (upper bound) map.
	CostMap	The type of the cost (length) map.
	SupplyMap	The type of the supply map.

Warning:

• Edge capacities and costs should be non-negative integers.
• Supply values should be signed integers.
• The value types of the maps should be convertible to each other.
• CostMap::Value must be signed type.

Author:

Peter Kovacs

#include <lemon/min_cost_flow.h>

Inheritance diagram for MinCostFlow< Graph, LowerMap, CapacityMap, CostMap, SupplyMap >:

[legend]

List of all members.

Public Member Functions
	MinCostFlow (const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, const CostMap &cost, const SupplyMap &supply)
	General constructor (with lower bounds).
	MinCostFlow (const Graph &graph, const CapacityMap &capacity, const CostMap &cost, const SupplyMap &supply)
	General constructor of the class (without lower bounds).
	MinCostFlow (const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, const CostMap &cost, Node s, Node t, Supply flow_value)
	Simple constructor (with lower bounds).
	MinCostFlow (const Graph &graph, const CapacityMap &capacity, const CostMap &cost, Node s, Node t, Supply flow_value)
	Simple constructor (without lower bounds).