ogdf::MaxFlowEdmondsKarp< TCap > Class Template Reference

Computes a max flow via Edmonds-Karp. More...

#include <ogdf/graphalg/MaxFlowEdmondsKarp.h>

Inheritance diagram for ogdf::MaxFlowEdmondsKarp< TCap >:

Public Member Functions
void	computeFlowAfterValue ()
	Implementation of computeFlowAfterValue from the super class. This does nothing, because the algorithm is finished after computeValue.
TCap	computeValue (const EdgeArray< TCap > &cap, const node &s, const node &t)
	Implementation of computeValue from the super class. The flow array is cleared, cap, s and t are stored and Edmonds&Karp starts. After this first phase, the flow itself is already computed! Returns 0 if source and sink are identical.
Public Member Functions inherited from ogdf::MaxFlowModule< TCap >
	MaxFlowModule ()
	Empty Constructor.
	MaxFlowModule (const Graph &graph, EdgeArray< TCap > *flow=nullptr)
	Constructor that calls init.
virtual	~MaxFlowModule ()
	Destructor that deletes m_flow if it is an internal flow array.
TCap	computeFlow (EdgeArray< TCap > &cap, node &s, node &t, EdgeArray< TCap > &flow)
	Only a shortcut for computeValue and computeFlowAfterValue.
void	computeFlowAfterValue (EdgeArray< TCap > &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 void	init (const Graph &graph, EdgeArray< TCap > *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.

Private Member Functions
bool	augmentShortestSourceSinkPath ()
	If there is an augumenting path: do an interation step. Otherwise return false so that the algorithm can stop.

Additional Inherited Members
Protected Attributes inherited from ogdf::MaxFlowModule< TCap >
const EdgeArray< TCap > *	m_cap
	Pointer to the given capacity array.
EpsilonTest *	m_et
	Pointer to the used EpsilonTest.
EdgeArray< TCap > *	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.

Detailed Description

template<typename TCap>
class ogdf::MaxFlowEdmondsKarp< TCap >

Computes a max flow via Edmonds-Karp.

Definition at line 50 of file MaxFlowEdmondsKarp.h.

Member Function Documentation

augmentShortestSourceSinkPath()

template<typename TCap >

bool ogdf::MaxFlowEdmondsKarp< TCap >::augmentShortestSourceSinkPath ( )

inlineprivate

If there is an augumenting path: do an interation step. Otherwise return false so that the algorithm can stop.

Definition at line 54 of file MaxFlowEdmondsKarp.h.

computeFlowAfterValue()

template<typename TCap >

void ogdf::MaxFlowEdmondsKarp< TCap >::computeFlowAfterValue ( )

inlinevirtual

Implementation of computeFlowAfterValue from the super class. This does nothing, because the algorithm is finished after computeValue.

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 155 of file MaxFlowEdmondsKarp.h.

computeValue()

template<typename TCap >

TCap ogdf::MaxFlowEdmondsKarp< TCap >::computeValue ( const EdgeArray< TCap > &  cap, const node &  s, const node &  t  )

inlinevirtual

Implementation of computeValue from the super class. The flow array is cleared, cap, s and t are stored and Edmonds&Karp starts. After this first phase, the flow itself is already computed! Returns 0 if source and sink are identical.

Returns

The value of the flow.

Parameters

cap	is the EdgeArray of capacities.
s	is the source.
t	is the sink.

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 125 of file MaxFlowEdmondsKarp.h.

---

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

• include/ogdf/graphalg/MaxFlowEdmondsKarp.h