Computes a min-cost flow using a network simplex method. More...

#include <ogdf/graphalg/MinCostFlowReinelt.h>

Inheritance diagram for ogdf::MinCostFlowReinelt< TCost >:

Classes
struct	arctype

struct	nodetype

Public Member Functions
	MinCostFlowReinelt ()

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) override
	Computes a min-cost flow in the directed graph `G` using a network simplex method.

int	infinity () const

Public Member Functions inherited from ogdf::MinCostFlowModule< TCost >
	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`.

Private Member Functions
void	beacircle (arctype eplus, arctype pre, bool *from_ub)

void	beadouble (arctype eplus, arctype pre, bool *from_ub)

int	mcf (int mcfNrNodes, int mcfNrArcs, Array< int > &mcfSupply, Array< int > &mcfTail, Array< int > &mcfHead, Array< int > &mcfLb, Array< int > &mcfUb, Array< TCost > &mcfCost, Array< int > &mcfFlow, Array< TCost > &mcfDual, TCost *mcfObj)

void	start (Array< int > &supply)

Private Attributes
Array< arctype >	arcs

arctype *	last_n1 = nullptr

arctype *	last_n2 = nullptr

EpsilonTest	m_eps

TCost	m_maxCost = std::numeric_limits<TCost>::lowest()

int	mm = 0

int	nn = 0

Array< nodetype >	nodes

nodetype *	root = nullptr

nodetype	rootStruct

arctype *	searchend = nullptr

arctype *	searchend_n1 = nullptr

arctype *	searchend_n2 = nullptr

arctype *	start_arc = nullptr

arctype *	start_b = nullptr

arctype *	start_n1 = nullptr

arctype *	start_n2 = nullptr

arctype *	startsearch = nullptr

Additional Inherited Members
Static Public Member Functions inherited from ogdf::MinCostFlowModule< TCost >
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::MinCostFlowReinelt< TCost >

Computes a min-cost flow using a network simplex method.

Definition at line 44 of file MinCostFlowReinelt.h.

Constructor & Destructor Documentation

◆ MinCostFlowReinelt()

template<typename TCost >

ogdf::MinCostFlowReinelt< TCost >::MinCostFlowReinelt ( )

inline

Definition at line 46 of file MinCostFlowReinelt.h.

Member Function Documentation

◆ beacircle()

template<typename TCost >

void ogdf::MinCostFlowReinelt< TCost >::beacircle	(	arctype **	eplus,
		arctype **	pre,
		bool *	from_ub
	)

private

Definition at line 296 of file MinCostFlowReinelt.h.

◆ beadouble()

template<typename TCost >

void ogdf::MinCostFlowReinelt< TCost >::beadouble	(	arctype **	eplus,
		arctype **	pre,
		bool *	from_ub
	)

private

Definition at line 409 of file MinCostFlowReinelt.h.

◆ call()

template<typename TCost >

bool ogdf::MinCostFlowReinelt< 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
	)

overridevirtual

Computes a min-cost flow in the directed graph G using a network simplex method.

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.

Implements ogdf::MinCostFlowModule< TCost >.

Definition at line 146 of file MinCostFlowReinelt.h.

◆ infinity()

template<typename TCost >

int ogdf::MinCostFlowReinelt< TCost >::infinity ( ) const

inline

Definition at line 73 of file MinCostFlowReinelt.h.

◆ mcf()

template<typename TCost >

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

private

->basis leaving arc

Definition at line 575 of file MinCostFlowReinelt.h.

◆ start()

template<typename TCost >

void ogdf::MinCostFlowReinelt< TCost >::start ( Array< int > & supply )

private

Definition at line 243 of file MinCostFlowReinelt.h.

Member Data Documentation

◆ arcs

template<typename TCost >

Array<arctype> ogdf::MinCostFlowReinelt< TCost >::arcs

private

Definition at line 113 of file MinCostFlowReinelt.h.

◆ last_n1

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::last_n1 = nullptr

private

Definition at line 119 of file MinCostFlowReinelt.h.

◆ last_n2

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::last_n2 = nullptr

private

Definition at line 120 of file MinCostFlowReinelt.h.

◆ m_eps

template<typename TCost >

EpsilonTest ogdf::MinCostFlowReinelt< TCost >::m_eps

private

Definition at line 110 of file MinCostFlowReinelt.h.

◆ m_maxCost

template<typename TCost >

TCost ogdf::MinCostFlowReinelt< TCost >::m_maxCost = std::numeric_limits<TCost>::lowest()

private

Definition at line 131 of file MinCostFlowReinelt.h.

◆ mm

template<typename TCost >

int ogdf::MinCostFlowReinelt< TCost >::mm = 0

private

Definition at line 134 of file MinCostFlowReinelt.h.

◆ nn

template<typename TCost >

int ogdf::MinCostFlowReinelt< TCost >::nn = 0

private

Definition at line 133 of file MinCostFlowReinelt.h.

◆ nodes

template<typename TCost >

Array<nodetype> ogdf::MinCostFlowReinelt< TCost >::nodes

private

Definition at line 112 of file MinCostFlowReinelt.h.

◆ root

template<typename TCost >

nodetype* ogdf::MinCostFlowReinelt< TCost >::root = nullptr

private

Definition at line 116 of file MinCostFlowReinelt.h.

◆ rootStruct

template<typename TCost >

nodetype ogdf::MinCostFlowReinelt< TCost >::rootStruct

private

Definition at line 117 of file MinCostFlowReinelt.h.

◆ searchend

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::searchend = nullptr

private

Definition at line 126 of file MinCostFlowReinelt.h.

◆ searchend_n1

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::searchend_n1 = nullptr

private

Definition at line 127 of file MinCostFlowReinelt.h.

◆ searchend_n2

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::searchend_n2 = nullptr

private

Definition at line 128 of file MinCostFlowReinelt.h.

◆ start_arc

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::start_arc = nullptr

private

Definition at line 121 of file MinCostFlowReinelt.h.

◆ start_b

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::start_b = nullptr

private

Definition at line 122 of file MinCostFlowReinelt.h.

◆ start_n1

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::start_n1 = nullptr

private

Definition at line 123 of file MinCostFlowReinelt.h.

◆ start_n2

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::start_n2 = nullptr

private

Definition at line 124 of file MinCostFlowReinelt.h.

◆ startsearch

template<typename TCost >

arctype* ogdf::MinCostFlowReinelt< TCost >::startsearch = nullptr

private

Definition at line 125 of file MinCostFlowReinelt.h.

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

include/ogdf/graphalg/MinCostFlowReinelt.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MinCostFlowReinelt()

Member Function Documentation

◆ beacircle()

◆ beadouble()

◆ call()

◆ infinity()

◆ mcf()

◆ start()

Member Data Documentation

◆ arcs

◆ last_n1

◆ last_n2

◆ m_eps

◆ m_maxCost

◆ mm

◆ nn

◆ nodes

◆ root

◆ rootStruct

◆ searchend

◆ searchend_n1

◆ searchend_n2

◆ start_arc

◆ start_b

◆ start_n1

◆ start_n2

◆ startsearch

Open
Graph Drawing
Framework