Inheritance diagram for ogdf::MinCostFlowReinelt:

Classes
struct	arctype
struct	nodetype
Public Member Functions
	MinCostFlowReinelt ()
bool	call (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< int > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow)
bool	call (const Graph &G, const EdgeArray< int > &lowerBound, const EdgeArray< int > &upperBound, const EdgeArray< int > &cost, const NodeArray< int > &supply, EdgeArray< int > &flow, NodeArray< int > &dual)
	Computes a min-cost flow in the directed graph G.
int	infinity () const
Private Member Functions
int	mcf (int mcfNrNodes, int mcfNrArcs, Array< int > &mcfSupply, Array< int > &mcfTail, Array< int > &mcfHead, Array< int > &mcfLb, Array< int > &mcfUb, Array< int > &mcfCost, Array< int > &mcfFlow, Array< int > &mcfDual, int *mcfObj)
void	start (Array< int > &supply)
void	beacircle (arctype eplus, arctype pre, bool *from_ub)
void	beadouble (arctype eplus, arctype pre, bool *from_ub)
Private Attributes
Array< nodetype >	nodes
Array< arctype >	arcs
nodetype *	root
nodetype	rootStruct
arctype *	last_n1
arctype *	last_n2
arctype *	start_arc
arctype *	start_b
arctype *	start_n1
arctype *	start_n2
arctype *	startsearch
arctype *	searchend
arctype *	searchend_n1
arctype *	searchend_n2
int	m_maxCost
int	nn
int	mm

Detailed Description

Definition at line 66 of file MinCostFlowReinelt.h.

Constructor & Destructor Documentation

ogdf::MinCostFlowReinelt::MinCostFlowReinelt ( ) [inline]

Definition at line 65 of file MinCostFlowReinelt.h.

void ogdf::MinCostFlowReinelt::beacircle	(	arctype **	eplus,
		arctype **	pre,
		bool *	from_ub
	)			`[private]`

void ogdf::MinCostFlowReinelt::beadouble	(	arctype **	eplus,
		arctype **	pre,
		bool *	from_ub
	)			`[private]`

bool ogdf::MinCostFlowReinelt::call	(	const Graph &	G,
		const EdgeArray< int > &	lowerBound,
		const EdgeArray< int > &	upperBound,
		const EdgeArray< int > &	cost,
		const NodeArray< int > &	supply,
		EdgeArray< int > &	flow,
		NodeArray< int > &	dual
	)			`[virtual]`

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

Precondition:: G must be connected, lowerBound[e] $\leq$ 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.

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

int ogdf::MinCostFlowReinelt::infinity ( ) const [inline]

Definition at line 88 of file MinCostFlowReinelt.h.

int ogdf::MinCostFlowReinelt::mcf	(	int	mcfNrNodes,
		int	mcfNrArcs,
		Array< int > &	mcfSupply,
		Array< int > &	mcfTail,
		Array< int > &	mcfHead,
		Array< int > &	mcfLb,
		Array< int > &	mcfUb,
		Array< int > &	mcfCost,
		Array< int > &	mcfFlow,
		Array< int > &	mcfDual,
		int *	mcfObj
	)			`[private]`