# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::MaxFlowModule< T > Class Template Referenceabstract

#include <ogdf/graphalg/MaxFlowModule.h>

## Public Member Functions

MaxFlowModule ()
Empty Constructor. More...

MaxFlowModule (const Graph &graph, EdgeArray< T > *flow=nullptr)
Constructor that calls init. More...

virtual ~MaxFlowModule ()
Destructor that deletes m_flow if it is an internal flow array. More...

computeFlow (EdgeArray< T > &cap, node &s, node &t, EdgeArray< T > &flow)
Only a shortcut for computeValue and computeFlowAfterValue. More...

virtual void computeFlowAfterValue ()=0
Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phases. The flow is stored in the array that the user gave in the constructor. More...

void computeFlowAfterValue (EdgeArray< T > &flow)
Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phases. The flow is stored in the parameter flow. More...

virtual T computeValue (const EdgeArray< T > &cap, const node &s, const node &t)=0
Compute only the value of the flow. More...

virtual void init (const Graph &graph, EdgeArray< T > *flow=nullptr)
Initialize the problem with a graph and optional flow array. If no flow array is given, a new ("internal") array will be created. If a flow array is given, the algorithm uses this "external" array. More...

bool isFeasibleInstance () const
Return whether the instance is feasible, i.e. the capacities are non-negative. More...

void useEpsilonTest (const double &eps)
Change the used EpsilonTest from StandardEpsilonTest to a user given EpsilonTest. More...

## Protected Attributes

const EdgeArray< T > * m_cap
Pointer to the given capacity array. More...

EpsilonTestm_et
Pointer to the used EpsilonTest. More...

EdgeArray< T > * m_flow
Pointer to (extern) flow array. More...

const Graphm_G
Pointer to the given graph. More...

const nodem_s
Pointer to the source node. More...

const nodem_t
Pointer to the sink node. More...

void destroy ()

## Private Attributes

bool doingAReInit = false
Is the next "init" call a re-init? More...

bool usingExternFlow = false
Is an extern flow array given in the constructor? More...

## Detailed Description

### template<typename T> class ogdf::MaxFlowModule< T >

Definition at line 40 of file MaxFlowModule.h.

## ◆ MaxFlowModule() [1/2]

template<typename T >
 ogdf::MaxFlowModule< T >::MaxFlowModule ( )
inline

Empty Constructor.

Definition at line 64 of file MaxFlowModule.h.

## ◆ MaxFlowModule() [2/2]

template<typename T >
 ogdf::MaxFlowModule< T >::MaxFlowModule ( const Graph & graph, EdgeArray< T > * flow = nullptr )
inlineexplicit

Constructor that calls init.

Parameters
 graph is the graph for the flow problem. flow is an optional argument that can be used to force the algorithm to work on an user given "external" EdgeArray flow

Definition at line 73 of file MaxFlowModule.h.

## ◆ ~MaxFlowModule()

template<typename T >
 virtual ogdf::MaxFlowModule< T >::~MaxFlowModule ( )
inlinevirtual

Destructor that deletes m_flow if it is an internal flow array.

Definition at line 80 of file MaxFlowModule.h.

## ◆ computeFlow()

template<typename T >
 T ogdf::MaxFlowModule< T >::computeFlow ( EdgeArray< T > & cap, node & s, node & t, EdgeArray< T > & flow )
inline

Only a shortcut for computeValue and computeFlowAfterValue.

Returns
The value of the flow.
Parameters
 cap is the EdgeArray of non-negative capacities. s is the source. t is the sink. flow A copy of the "internal" flow array is given in flow.

Definition at line 174 of file MaxFlowModule.h.

## ◆ computeFlowAfterValue() [1/2]

template<typename T >
 virtual void ogdf::MaxFlowModule< T >::computeFlowAfterValue ( )
pure virtual

Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phases. The flow is stored in the array that the user gave in the constructor.

## ◆ computeFlowAfterValue() [2/2]

template<typename T >
 void ogdf::MaxFlowModule< T >::computeFlowAfterValue ( EdgeArray< T > & flow )
inline

Compute the flow itself after the flow value is already computed. Only used in algorithms with 2 phases. The flow is stored in the parameter flow.

Parameters
 flow The "internal" flow array is given in flow.

Definition at line 149 of file MaxFlowModule.h.

## ◆ computeValue()

template<typename T >
 virtual T ogdf::MaxFlowModule< T >::computeValue ( const EdgeArray< T > & cap, const node & s, const node & t )
pure virtual

Compute only the value of the flow.

There are algorithms with two phases where the value of the flow is known after the first phase, but the flow itself is not feasible or not known at this time. If source and target are the same node, the algorithm must return zero.

Returns
The value of the flow.
Parameters
 cap is the EdgeArray of non-negative capacities. s is the source. t is the sink.

## ◆ destroy()

template<typename T >
 void ogdf::MaxFlowModule< T >::destroy ( )
inlineprivate

Definition at line 54 of file MaxFlowModule.h.

## ◆ init()

template<typename T >
 virtual void ogdf::MaxFlowModule< T >::init ( const Graph & graph, EdgeArray< T > * flow = nullptr )
inlinevirtual

Initialize the problem with a graph and optional flow array. If no flow array is given, a new ("internal") array will be created. If a flow array is given, the algorithm uses this "external" array.

Parameters
 graph is the graph for the flow problem. flow is an optional argument that can be used to force the algorithm to work on an user given "external" EdgeArray flow

Reimplemented in ogdf::MaxFlowSTPlanarDigraph< TCap >.

Definition at line 93 of file MaxFlowModule.h.

## ◆ isFeasibleInstance()

template<typename T >
 bool ogdf::MaxFlowModule< T >::isFeasibleInstance ( ) const
inline

Return whether the instance is feasible, i.e. the capacities are non-negative.

Definition at line 157 of file MaxFlowModule.h.

## ◆ useEpsilonTest()

template<typename T >
 void ogdf::MaxFlowModule< T >::useEpsilonTest ( const double & eps )
inline

Change the used EpsilonTest from StandardEpsilonTest to a user given EpsilonTest.

Parameters
 eps use an EpsilonTest with epsilon

Definition at line 117 of file MaxFlowModule.h.

## ◆ doingAReInit

template<typename T >
 bool ogdf::MaxFlowModule< T >::doingAReInit = false
private

Is the next "init" call a re-init?

Definition at line 52 of file MaxFlowModule.h.

## ◆ m_cap

template<typename T >
 const EdgeArray* ogdf::MaxFlowModule< T >::m_cap
protected

Pointer to the given capacity array.

Definition at line 46 of file MaxFlowModule.h.

## ◆ m_et

template<typename T >
 EpsilonTest* ogdf::MaxFlowModule< T >::m_et
protected

Pointer to the used EpsilonTest.

Definition at line 43 of file MaxFlowModule.h.

## ◆ m_flow

template<typename T >
 EdgeArray* ogdf::MaxFlowModule< T >::m_flow
protected

Pointer to (extern) flow array.

Definition at line 44 of file MaxFlowModule.h.

## ◆ m_G

template<typename T >
 const Graph* ogdf::MaxFlowModule< T >::m_G
protected

Pointer to the given graph.

Definition at line 45 of file MaxFlowModule.h.

## ◆ m_s

template<typename T >
 const node* ogdf::MaxFlowModule< T >::m_s
protected

Pointer to the source node.

Definition at line 47 of file MaxFlowModule.h.

## ◆ m_t

template<typename T >
 const node* ogdf::MaxFlowModule< T >::m_t
protected

Pointer to the sink node.

Definition at line 48 of file MaxFlowModule.h.

## ◆ usingExternFlow

template<typename T >
 bool ogdf::MaxFlowModule< T >::usingExternFlow = false
private

Is an extern flow array given in the constructor?

Definition at line 51 of file MaxFlowModule.h.

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