Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinCostFlowReinelt< TCost > Class Template Reference

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. More...
 
int infinity () const
 
- Public Member Functions inherited from ogdf::MinCostFlowModule< TCost >
 MinCostFlowModule ()
 Initializes a min-cost flow module. More...
 
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. More...
 

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< arctypearcs
 
arctypelast_n1 = nullptr
 
arctypelast_n2 = nullptr
 
EpsilonTest m_eps
 
TCost m_maxCost = std::numeric_limits<TCost>::lowest()
 
int mm = 0
 
int nn = 0
 
Array< nodetypenodes
 
nodetyperoot = nullptr
 
nodetype rootStruct
 
arctypesearchend = nullptr
 
arctypesearchend_n1 = nullptr
 
arctypesearchend_n2 = nullptr
 
arctypestart_arc = nullptr
 
arctypestart_b = nullptr
 
arctypestart_n1 = nullptr
 
arctypestart_n2 = nullptr
 
arctypestartsearch = 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. More...
 
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. More...
 
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. More...
 
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. More...
 

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 47 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 320 of file MinCostFlowReinelt.h.

◆ beadouble()

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

Definition at line 440 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
Gis the directed input graph.
lowerBoundgives the lower bound for the flow on each edge.
upperBoundgives the upper bound for the flow on each edge.
costgives the costs for each edge.
supplygives the supply (or demand if negative) of each node.
flowis assigned the computed flow on each edge.
dualis assigned the computed dual variables.
Returns
true iff a feasible min-cost flow exists.

Implements ogdf::MinCostFlowModule< TCost >.

Definition at line 163 of file MinCostFlowReinelt.h.

◆ infinity()

template<typename TCost >
int ogdf::MinCostFlowReinelt< TCost >::infinity ( ) const
inline

Definition at line 78 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 607 of file MinCostFlowReinelt.h.

◆ start()

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

Definition at line 266 of file MinCostFlowReinelt.h.

Member Data Documentation

◆ arcs

template<typename TCost >
Array<arctype> ogdf::MinCostFlowReinelt< TCost >::arcs
private

Definition at line 130 of file MinCostFlowReinelt.h.

◆ last_n1

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::last_n1 = nullptr
private

Definition at line 136 of file MinCostFlowReinelt.h.

◆ last_n2

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::last_n2 = nullptr
private

Definition at line 137 of file MinCostFlowReinelt.h.

◆ m_eps

template<typename TCost >
EpsilonTest ogdf::MinCostFlowReinelt< TCost >::m_eps
private

Definition at line 127 of file MinCostFlowReinelt.h.

◆ m_maxCost

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

Definition at line 148 of file MinCostFlowReinelt.h.

◆ mm

template<typename TCost >
int ogdf::MinCostFlowReinelt< TCost >::mm = 0
private

Definition at line 151 of file MinCostFlowReinelt.h.

◆ nn

template<typename TCost >
int ogdf::MinCostFlowReinelt< TCost >::nn = 0
private

Definition at line 150 of file MinCostFlowReinelt.h.

◆ nodes

template<typename TCost >
Array<nodetype> ogdf::MinCostFlowReinelt< TCost >::nodes
private

Definition at line 129 of file MinCostFlowReinelt.h.

◆ root

template<typename TCost >
nodetype* ogdf::MinCostFlowReinelt< TCost >::root = nullptr
private

Definition at line 133 of file MinCostFlowReinelt.h.

◆ rootStruct

template<typename TCost >
nodetype ogdf::MinCostFlowReinelt< TCost >::rootStruct
private

Definition at line 134 of file MinCostFlowReinelt.h.

◆ searchend

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::searchend = nullptr
private

Definition at line 143 of file MinCostFlowReinelt.h.

◆ searchend_n1

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::searchend_n1 = nullptr
private

Definition at line 144 of file MinCostFlowReinelt.h.

◆ searchend_n2

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::searchend_n2 = nullptr
private

Definition at line 145 of file MinCostFlowReinelt.h.

◆ start_arc

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::start_arc = nullptr
private

Definition at line 138 of file MinCostFlowReinelt.h.

◆ start_b

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::start_b = nullptr
private

Definition at line 139 of file MinCostFlowReinelt.h.

◆ start_n1

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::start_n1 = nullptr
private

Definition at line 140 of file MinCostFlowReinelt.h.

◆ start_n2

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::start_n2 = nullptr
private

Definition at line 141 of file MinCostFlowReinelt.h.

◆ startsearch

template<typename TCost >
arctype* ogdf::MinCostFlowReinelt< TCost >::startsearch = nullptr
private

Definition at line 142 of file MinCostFlowReinelt.h.


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