Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MaxFlowGoldbergTarjan< TCap > Class Template Reference

Computes a max flow via Preflow-Push (global relabeling and gap relabeling heuristic). More...

#include <ogdf/graphalg/MaxFlowGoldbergTarjan.h>

+ Inheritance diagram for ogdf::MaxFlowGoldbergTarjan< TCap >:

Public Member Functions

void computeFlowAfterValue ()
 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...
 
TCap computeValue (const EdgeArray< TCap > &cap, const node &s, const node &t)
 Compute only the value of the flow. More...
 
- Public Member Functions inherited from ogdf::MaxFlowModule< TCap >
 MaxFlowModule ()
 Empty Constructor. More...
 
 MaxFlowModule (const Graph &graph, EdgeArray< TCap > *flow=nullptr)
 Constructor that calls init. More...
 
virtual ~MaxFlowModule ()
 Destructor that deletes m_flow if it is an internal flow array. More...
 
TCap computeFlow (EdgeArray< TCap > &cap, node &s, node &t, EdgeArray< TCap > &flow)
 Only a shortcut for computeValue and computeFlowAfterValue. More...
 
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. More...
 
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. 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...
 

Private Member Functions

void findNewMaxLabel ()
 
TCap getCap (const edge e) const
 
void globalRelabel ()
 
bool isActive (const node v) const
 
bool isAdmissible (const adjEntry adj) const
 
bool isResidualEdge (const adjEntry adj) const
 
void push (const adjEntry adj)
 
void relabel (const node v)
 
void relabelStage2 (const node v)
 
void setActive (const node v)
 
void setInactive (const node v)
 
void setLabel (const node v, int label)
 

Private Attributes

Array< List< node > > m_activeLabelList
 
NodeArray< ListIterator< node > > m_activeLabelListPosition
 
List< edgem_cutEdges
 
List< nodem_cutNodes
 
NodeArray< TCap > m_ex
 
NodeArray< int > m_label
 
int m_maxLabel = 0
 

Additional Inherited Members

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

Detailed Description

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

Computes a max flow via Preflow-Push (global relabeling and gap relabeling heuristic).

Definition at line 52 of file MaxFlowGoldbergTarjan.h.

Member Function Documentation

◆ computeFlowAfterValue()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::computeFlowAfterValue ( )
inlinevirtual

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.

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 385 of file MaxFlowGoldbergTarjan.h.

◆ computeValue()

template<typename TCap >
TCap ogdf::MaxFlowGoldbergTarjan< TCap >::computeValue ( const EdgeArray< TCap > &  cap,
const node s,
const node t 
)
inlinevirtual

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.

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 253 of file MaxFlowGoldbergTarjan.h.

◆ findNewMaxLabel()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::findNewMaxLabel ( )
inlineprivate

Definition at line 111 of file MaxFlowGoldbergTarjan.h.

◆ getCap()

template<typename TCap >
TCap ogdf::MaxFlowGoldbergTarjan< TCap >::getCap ( const edge  e) const
inlineprivate

Definition at line 69 of file MaxFlowGoldbergTarjan.h.

◆ globalRelabel()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::globalRelabel ( )
inlineprivate

Definition at line 195 of file MaxFlowGoldbergTarjan.h.

◆ isActive()

template<typename TCap >
bool ogdf::MaxFlowGoldbergTarjan< TCap >::isActive ( const node  v) const
inlineprivate

Definition at line 89 of file MaxFlowGoldbergTarjan.h.

◆ isAdmissible()

template<typename TCap >
bool ogdf::MaxFlowGoldbergTarjan< TCap >::isAdmissible ( const adjEntry  adj) const
inlineprivate

Definition at line 82 of file MaxFlowGoldbergTarjan.h.

◆ isResidualEdge()

template<typename TCap >
bool ogdf::MaxFlowGoldbergTarjan< TCap >::isResidualEdge ( const adjEntry  adj) const
inlineprivate

Definition at line 73 of file MaxFlowGoldbergTarjan.h.

◆ push()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::push ( const adjEntry  adj)
inlineprivate

Definition at line 176 of file MaxFlowGoldbergTarjan.h.

◆ relabel()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::relabel ( const node  v)
inlineprivate

Definition at line 220 of file MaxFlowGoldbergTarjan.h.

◆ relabelStage2()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::relabelStage2 ( const node  v)
inlineprivate

Definition at line 236 of file MaxFlowGoldbergTarjan.h.

◆ setActive()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::setActive ( const node  v)
inlineprivate

Definition at line 99 of file MaxFlowGoldbergTarjan.h.

◆ setInactive()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::setInactive ( const node  v)
inlineprivate

Definition at line 119 of file MaxFlowGoldbergTarjan.h.

◆ setLabel()

template<typename TCap >
void ogdf::MaxFlowGoldbergTarjan< TCap >::setLabel ( const node  v,
int  label 
)
inlineprivate

Definition at line 129 of file MaxFlowGoldbergTarjan.h.

Member Data Documentation

◆ m_activeLabelList

template<typename TCap >
Array< List<node> > ogdf::MaxFlowGoldbergTarjan< TCap >::m_activeLabelList
private

Definition at line 58 of file MaxFlowGoldbergTarjan.h.

◆ m_activeLabelListPosition

template<typename TCap >
NodeArray< ListIterator<node> > ogdf::MaxFlowGoldbergTarjan< TCap >::m_activeLabelListPosition
private

Definition at line 57 of file MaxFlowGoldbergTarjan.h.

◆ m_cutEdges

template<typename TCap >
List<edge> ogdf::MaxFlowGoldbergTarjan< TCap >::m_cutEdges
mutableprivate

Definition at line 67 of file MaxFlowGoldbergTarjan.h.

◆ m_cutNodes

template<typename TCap >
List<node> ogdf::MaxFlowGoldbergTarjan< TCap >::m_cutNodes
mutableprivate

Definition at line 66 of file MaxFlowGoldbergTarjan.h.

◆ m_ex

template<typename TCap >
NodeArray<TCap> ogdf::MaxFlowGoldbergTarjan< TCap >::m_ex
private

Definition at line 55 of file MaxFlowGoldbergTarjan.h.

◆ m_label

template<typename TCap >
NodeArray<int> ogdf::MaxFlowGoldbergTarjan< TCap >::m_label
private

Definition at line 54 of file MaxFlowGoldbergTarjan.h.

◆ m_maxLabel

template<typename TCap >
int ogdf::MaxFlowGoldbergTarjan< TCap >::m_maxLabel = 0
private

Definition at line 59 of file MaxFlowGoldbergTarjan.h.


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