Interface for min-cost flow algorithms. More...

#include <ogdf/graphalg/MinCostFlowModule.h>

Inheritance diagram for ogdf::MinCostFlowModule< TCost >:

Public Member Functions
	MinCostFlowModule ()
	Initializes a min-cost flow module.

virtual	~MinCostFlowModule ()

virtual bool	call (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow)
	Computes a min-cost flow in the directed graph `G`.

virtual bool	call (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow, NodeArray< TCost > &dual)=0
	Computes a min-cost flow in the directed graph `G`.

Static Public Member Functions
static bool	checkComputedFlow (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, const EdgeArray< int > &flow)
	checks if a computed flow is a feasible solution to the given problem instance.

static bool	checkComputedFlow (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< TCost > &cost, const NodeArray< int > &supply, const EdgeArray< int > &flow, TCost &value)
	checks if a computed flow is a feasible solution to the given problem instance.

static bool	checkProblem (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const NodeArray< int > &supply)
	Checks if a given min-cost flow problem instance satisfies the preconditions.

static void	generateProblem (Graph &G, int n, int m, EdgeArray< int > &lowerBound, EdgeArray< int > &upperBound, EdgeArray< TCost > &cost, NodeArray< int > &supply)
	Generates an instance of a min-cost flow problem with `n` nodes and `m` + `n` edges.

Detailed Description

template<typename TCost>
class ogdf::MinCostFlowModule< TCost >

Interface for min-cost flow algorithms.

Definition at line 48 of file MinCostFlowModule.h.

Constructor & Destructor Documentation

◆ MinCostFlowModule()

template<typename TCost >

ogdf::MinCostFlowModule< TCost >::MinCostFlowModule ( )

inline

Initializes a min-cost flow module.

Definition at line 51 of file MinCostFlowModule.h.

◆ ~MinCostFlowModule()

template<typename TCost >

virtual ogdf::MinCostFlowModule< TCost >::~MinCostFlowModule ( )

inlinevirtual

Definition at line 54 of file MinCostFlowModule.h.

Member Function Documentation

◆ call() [1/2]

template<typename TCost >

virtual bool ogdf::MinCostFlowModule< TCost >::call	(	const Graph &	G,
		const EdgeArray< int > &	lowerBound,
		const EdgeArray< int > &	upperBound,
		const EdgeArray< TCost > &	cost,
		const NodeArray< int > &	supply,
		EdgeArray< int > &	flow
	)

inlinevirtual

Computes a min-cost flow in the directed graph G.

Precondition: G must be connected, lowerBound[e] <= upperBound[e] for all edges e, and the sum over all supplies must be zero.

Parameters

G	is the directed input graph.
lowerBound	gives the lower bound for the flow on each edge.
upperBound	gives the upper bound for the flow on each edge.
cost	gives the costs for each edge.
supply	gives the supply (or demand if negative) of each node.
flow	is assigned the computed flow on each edge.

Returns: true iff a feasible min-cost flow exists.

Definition at line 70 of file MinCostFlowModule.h.

◆ call() [2/2]

template<typename TCost >

virtual bool ogdf::MinCostFlowModule< TCost >::call	(	const Graph &	G,
		const EdgeArray< int > &	lowerBound,
		const EdgeArray< int > &	upperBound,
		const EdgeArray< TCost > &	cost,
		const NodeArray< int > &	supply,
		EdgeArray< int > &	flow,
		NodeArray< TCost > &	dual
	)

pure virtual

Computes a min-cost flow in the directed graph G.

Precondition: G must be connected, lowerBound[e] <= upperBound[e] for all edges e, and the sum over all supplies must be zero.

Parameters

G	is the directed input graph.
lowerBound	gives the lower bound for the flow on each edge.
upperBound	gives the upper bound for the flow on each edge.
cost	gives the costs for each edge.
supply	gives the supply (or demand if negative) of each node.
flow	is assigned the computed flow on each edge.
dual	is assigned the computed dual variables.

Returns: true iff a feasible min-cost flow exists.

Implemented in ogdf::MinCostFlowReinelt< TCost >.

◆ checkComputedFlow() [1/2]

template<typename TCost >

static bool ogdf::MinCostFlowModule< TCost >::checkComputedFlow	(	const Graph &	G,
		const EdgeArray< int > &	lowerBound,
		const EdgeArray< int > &	upperBound,
		const EdgeArray< TCost > &	cost,
		const NodeArray< int > &	supply,
		const EdgeArray< int > &	flow
	)

inlinestatic

checks if a computed flow is a feasible solution to the given problem instance.

Checks in particular if:

lowerBound[e] <= flow[e] <= upperBound[e]
sum flow[e], e is outgoing edge of v minus sum flow[e], e is incoming edge of v equals supply[v] for each node v

Parameters

G	is the input graph.
lowerBound	gives the lower bound for the flow on each edge.
upperBound	gives the upper bound for the flow on each edge.
cost	gives the costs for each edge.
supply	gives the supply (or demand if negative) of each node.
flow	is the flow on each edge.

Returns: true iff the solution is feasible.

Definition at line 176 of file MinCostFlowModule.h.

◆ checkComputedFlow() [2/2]

template<typename TCost >

bool ogdf::MinCostFlowModule< TCost >::checkComputedFlow	(	const Graph &	G,
		const EdgeArray< int > &	lowerBound,
		const EdgeArray< int > &	upperBound,
		const EdgeArray< TCost > &	cost,
		const NodeArray< int > &	supply,
		const EdgeArray< int > &	flow,
		TCost &	value
	)

static

checks if a computed flow is a feasible solution to the given problem instance.

Checks in particular if:

lowerBound[e] <= flow[e] <= upperBound[e]
sum flow[e], e is outgoing edge of v minus sum flow[e], e is incoming edge of v equals supply[v] for each node v

Parameters

G	is the input graph.
lowerBound	gives the lower bound for the flow on each edge.
upperBound	gives the upper bound for the flow on each edge.
cost	gives the costs for each edge.
supply	gives the supply (or demand if negative) of each node.
flow	is the flow on each edge.
value	is assigned the value of the flow.

Returns: true iff the solution is feasible.

Definition at line 242 of file MinCostFlowModule.h.

◆ checkProblem()

template<typename TCost >

bool ogdf::MinCostFlowModule< TCost >::checkProblem	(	const Graph &	G,
		const EdgeArray< int > &	lowerBound,
		const EdgeArray< int > &	upperBound,
		const NodeArray< int > &	supply
	)

static

Checks if a given min-cost flow problem instance satisfies the preconditions.

The following preconditions are checked:

lowerBound[e] <= upperBound[e] for all edges e
sum over all supply[v] = 0

Parameters

G	is the input graph.
lowerBound	gives the lower bound for the flow on each edge.
upperBound	gives the upper bound for the flow on each edge.
supply	gives the supply (or demand if negative) of each node.

Returns: true iff the problem satisfies the preconditions.

Definition at line 221 of file MinCostFlowModule.h.

◆ generateProblem()

template<typename TCost >

void ogdf::MinCostFlowModule< TCost >::generateProblem	(	Graph &	G,
		int	n,
		int	m,
		EdgeArray< int > &	lowerBound,
		EdgeArray< int > &	upperBound,
		EdgeArray< TCost > &	cost,
		NodeArray< int > &	supply
	)

static

Generates an instance of a min-cost flow problem with n nodes and m + n edges.

Definition at line 187 of file MinCostFlowModule.h.

The documentation for this class was generated from the following file:

include/ogdf/graphalg/MinCostFlowModule.h

OpenGraph DrawingFramework

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ MinCostFlowModule()

◆ ~MinCostFlowModule()

Member Function Documentation

◆ call() [1/2]

◆ call() [2/2]

◆ checkComputedFlow() [1/2]

◆ checkComputedFlow() [2/2]

◆ checkProblem()

◆ generateProblem()

Open
Graph Drawing
Framework