CycleCanceling< 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::CycleCanceling< Graph, LowerMap, CapacityMap, CostMap, SupplyMap >

CycleCanceling implements a cycle-canceling algorithm for finding a minimum cost flow.

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.

Note:

By default the Bellman-Ford algorithm is used for negative cycle detection with limited iteration number. However CycleCanceling also provides the "Minimum Mean Cycle-Canceling" algorithm, which is strongly polynomial, but rather slower in practice. To use this version of the algorithm, call run() with true parameter.

Author:

Peter Kovacs

#include <lemon/cycle_canceling.h>

List of all members.

Classes
class	ResidualCostMap
Public Types
typedef Graph::template EdgeMap< Capacity >	FlowMap
	The type of the flow map.
typedef Graph::template NodeMap< Cost >	PotentialMap
	The type of the potential map.
Public Member Functions
	CycleCanceling (const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, const CostMap &cost, const SupplyMap &supply)
	General constructor (with lower bounds).
	CycleCanceling (const Graph &graph, const CapacityMap &capacity, const CostMap &cost, const SupplyMap &supply)
	General constructor (without lower bounds).
	CycleCanceling (const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, const CostMap &cost, Node s, Node t, Supply flow_value)
	Simple constructor (with lower bounds).
	CycleCanceling (const Graph &graph, const CapacityMap &capacity, const CostMap &cost, Node s, Node t, Supply flow_value)
	Simple constructor (without lower bounds).
	~CycleCanceling ()
	Destructor.
CycleCanceling &	flowMap (FlowMap &map)
	Set the flow map.
CycleCanceling &	potentialMap (PotentialMap &map)
	Set the potential map.
Execution control
bool	run (bool min_mean_cc=false)
	Run the algorithm.
Query Functions
The result of the algorithm can be obtained using these functions. run() must be called before using them.
const FlowMap &	flowMap () const
	Return a const reference to the edge map storing the found flow.
const PotentialMap &	potentialMap () const
	Return a const reference to the node map storing the found potentials (the dual solution).
Capacity	flow (const Edge &edge) const
	Return the flow on the given edge.
Cost	potential (const Node &node) const
	Return the potential of the given node.
Cost	totalCost () const
	Return the total cost of the found flow.
Private Member Functions
bool	init ()
	Initialize the algorithm.
void	start ()
	Execute the algorithm using BellmanFord.
void	startMinMean ()
	Execute the algorithm using MinMeanCycle.

---

Constructor & Destructor Documentation

CycleCanceling	(	const Graph &	graph,
		const LowerMap &	lower,
		const CapacityMap &	capacity,
		const CostMap &	cost,
		const SupplyMap &	supply
	)			[inline]

General constructor (with lower bounds).

Parameters:

	graph	The directed graph the algorithm runs on.
	lower	The lower bounds of the edges.
	capacity	The capacities (upper bounds) of the edges.
	cost	The cost (length) values of the edges.
	supply	The supply values of the nodes (signed).

CycleCanceling	(	const Graph &	graph,
		const CapacityMap &	capacity,
		const CostMap &	cost,
		const SupplyMap &	supply
	)			[inline]

General constructor (without lower bounds).

Parameters:

	graph	The directed graph the algorithm runs on.
	capacity	The capacities (upper bounds) of the edges.
	cost	The cost (length) values of the edges.
	supply	The supply values of the nodes (signed).

CycleCanceling	(	const Graph &	graph,
		const LowerMap &	lower,
		const CapacityMap &	capacity,
		const CostMap &	cost,
		Node	s,
		Node	t,
		Supply	flow_value
	)			[inline]

Simple constructor (with lower bounds).

Parameters:

	graph	The directed graph the algorithm runs on.
	lower	The lower bounds of the edges.
	capacity	The capacities (upper bounds) of the edges.
	cost	The cost (length) values of the edges.
	s	The source node.
	t	The target node.
	flow_value	The required amount of flow from node s to node t (i.e. the supply of s and the demand of t).

CycleCanceling	(	const Graph &	graph,
		const CapacityMap &	capacity,
		const CostMap &	cost,
		Node	s,
		Node	t,
		Supply	flow_value
	)			[inline]

Simple constructor (without lower bounds).

Parameters:

	graph	The directed graph the algorithm runs on.
	capacity	The capacities (upper bounds) of the edges.
	cost	The cost (length) values of the edges.
	s	The source node.
	t	The target node.
	flow_value	The required amount of flow from node s to node t (i.e. the supply of s and the demand of t).

---

Member Function Documentation

CycleCanceling& flowMap

(

FlowMap &

map

)

[inline]

Set the flow map.

Returns:

(*this)

CycleCanceling& potentialMap

(

PotentialMap &

map

)

[inline]

Set the potential map.

Returns:

(*this)

bool run

(

bool

min_mean_cc = false

)

[inline]

Run the algorithm.

Parameters:

min_mean_cc

Set this parameter to true to run the "Minimum Mean Cycle-Canceling" algorithm, which is strongly polynomial, but rather slower in practice.

Returns:

true if a feasible flow can be found.

const FlowMap& flowMap

(

)

const [inline]

Return a const reference to the edge map storing the found flow.

Precondition:

run() must be called before using this function.

const PotentialMap& potentialMap

(

)

const [inline]

Return a const reference to the node map storing the found potentials (the dual solution).

Precondition:

run() must be called before using this function.

Capacity flow

(

const Edge &

edge

)

const [inline]

Return the flow on the given edge.

Precondition:

run() must be called before using this function.

Cost potential

(

const Node &

node

)

const [inline]

Return the potential of the given node.

Precondition:

run() must be called before using this function.

Cost totalCost

(

)

const [inline]

Return the total cost of the found flow. The complexity of the function is .

Precondition:

run() must be called before using this function.

void start

(

)

[inline, private]

Execute the algorithm using the Bellman-Ford algorithm for negative cycle detection with successively larger limit for the number of iterations.

void startMinMean

(

)

[inline, private]

Execute the algorithm using MinMeanCycle for negative cycle detection.