Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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

Private Member Functions

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.

Constructor & Destructor Documentation

◆ MaxFlowModule() [1/2]

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

Empty Constructor.

Definition at line 62 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
graphis the graph for the flow problem.
flowis an optional argument that can be used to force the algorithm to work on an user given "external" EdgeArray flow

Definition at line 71 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 77 of file MaxFlowModule.h.

Member Function Documentation

◆ 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
capis the EdgeArray of non-negative capacities.
sis the source.
tis the sink.
flowA copy of the "internal" flow array is given in flow.

Definition at line 164 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.

Implemented in ogdf::MaxFlowSTPlanarDigraph< TCap >, ogdf::MaxFlowGoldbergTarjan< TCap >, ogdf::MaxFlowSTPlanarItaiShiloach< TCap >, and ogdf::MaxFlowEdmondsKarp< TCap >.

◆ 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
flowThe "internal" flow array is given in flow.

Definition at line 140 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
capis the EdgeArray of non-negative capacities.
sis the source.
tis the sink.

Implemented in ogdf::MaxFlowSTPlanarItaiShiloach< TCap >, ogdf::MaxFlowSTPlanarDigraph< TCap >, ogdf::MaxFlowGoldbergTarjan< TCap >, and ogdf::MaxFlowEdmondsKarp< TCap >.

◆ destroy()

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

Definition at line 53 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
graphis the graph for the flow problem.
flowis 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 87 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 147 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
epsuse an EpsilonTest with epsilon

Definition at line 109 of file MaxFlowModule.h.

Member Data Documentation

◆ doingAReInit

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

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

Definition at line 51 of file MaxFlowModule.h.

◆ m_cap

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

Pointer to the given capacity array.

Definition at line 45 of file MaxFlowModule.h.

◆ m_et

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

Pointer to the used EpsilonTest.

Definition at line 42 of file MaxFlowModule.h.

◆ m_flow

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

Pointer to (extern) flow array.

Definition at line 43 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 44 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 46 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 47 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 50 of file MaxFlowModule.h.


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