Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MinCostFlowModule< TCost > Class Template Referenceabstract

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. 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...
 
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. More...
 

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. 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::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
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.
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
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.

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
Gis the 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 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
Gis the 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 the flow on each edge.
valueis 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
Gis the input graph.
lowerBoundgives the lower bound for the flow on each edge.
upperBoundgives the upper bound for the flow on each edge.
supplygives 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: