#include <ogdf/graphalg/MaxFlowModule.h>

Public Member Functions
	MaxFlowModule ()
	Empty Constructor.

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

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

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

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.

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

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

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.

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

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

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

EpsilonTest *	m_et
	Pointer to the used EpsilonTest.

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

const Graph *	m_G
	Pointer to the given graph.

const node *	m_s
	Pointer to the source node.

const node *	m_t
	Pointer to the sink node.

Private Member Functions
void	destroy ()

Private Attributes
bool	doingAReInit = false
	Is the next "init" call a re-init?

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

Detailed Description

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

Definition at line 41 of file MaxFlowModule.h.

Constructor & Destructor Documentation

◆ MaxFlowModule() [1/2]

template<typename T >

ogdf::MaxFlowModule< T >::MaxFlowModule ( )

inline

Empty Constructor.

Definition at line 63 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 72 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 78 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

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 165 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::MaxFlowEdmondsKarp< TCap >, ogdf::MaxFlowGoldbergTarjan< TCap >, ogdf::MaxFlowSTPlanarItaiShiloach< TCap >, and ogdf::MaxFlowSTPlanarDigraph< 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

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

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

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

◆ 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 88 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 148 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 110 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 52 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 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<T>* 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:

include/ogdf/graphalg/MaxFlowModule.h

OpenGraph DrawingFramework

Public Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ MaxFlowModule() [1/2]

◆ MaxFlowModule() [2/2]

◆ ~MaxFlowModule()

Member Function Documentation

◆ computeFlow()

◆ computeFlowAfterValue() [1/2]

◆ computeFlowAfterValue() [2/2]

◆ computeValue()

◆ destroy()

◆ init()

◆ isFeasibleInstance()

◆ useEpsilonTest()

Member Data Documentation

◆ doingAReInit

◆ m_cap

◆ m_et

◆ m_flow

◆ m_G

◆ m_s

◆ m_t

◆ usingExternFlow

Open
Graph Drawing
Framework