Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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.
 
EpsilonTestm_et
 Pointer to the used EpsilonTest.
 
EdgeArray< TCap > * m_flow
 Pointer to (extern) flow array.
 
const Graphm_G
 Pointer to the given graph.
 
const nodem_s
 Pointer to the source node.
 
const nodem_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 44 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 48 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 149 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
capis the EdgeArray of capacities.
sis the source.
tis the sink.

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 119 of file MaxFlowEdmondsKarp.h.


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