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.

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

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
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< edge >	m_cutEdges

List< node >	m_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.

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::MaxFlowGoldbergTarjan< TCap >

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

Definition at line 53 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 363 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

cap	is the EdgeArray of non-negative capacities.
s	is the source.
t	is the sink.

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 237 of file MaxFlowGoldbergTarjan.h.

◆ findNewMaxLabel()

template<typename TCap >

void ogdf::MaxFlowGoldbergTarjan< TCap >::findNewMaxLabel ( )

inlineprivate

Definition at line 105 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 183 of file MaxFlowGoldbergTarjan.h.

◆ isActive()

template<typename TCap >

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

inlineprivate

Definition at line 86 of file MaxFlowGoldbergTarjan.h.

◆ isAdmissible()

template<typename TCap >

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

inlineprivate

Definition at line 81 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 165 of file MaxFlowGoldbergTarjan.h.

◆ relabel()

template<typename TCap >

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

inlineprivate

Definition at line 206 of file MaxFlowGoldbergTarjan.h.

◆ relabelStage2()

template<typename TCap >

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

inlineprivate

Definition at line 221 of file MaxFlowGoldbergTarjan.h.

◆ setActive()

template<typename TCap >

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

inlineprivate

Definition at line 94 of file MaxFlowGoldbergTarjan.h.

◆ setInactive()

template<typename TCap >

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

inlineprivate

Definition at line 111 of file MaxFlowGoldbergTarjan.h.

◆ setLabel()

template<typename TCap >

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

inlineprivate

Definition at line 120 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:

include/ogdf/graphalg/MaxFlowGoldbergTarjan.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ computeFlowAfterValue()

◆ computeValue()

◆ findNewMaxLabel()

◆ getCap()

◆ globalRelabel()

◆ isActive()

◆ isAdmissible()

◆ isResidualEdge()

◆ push()

◆ relabel()

◆ relabelStage2()

◆ setActive()

◆ setInactive()

◆ setLabel()

Member Data Documentation

◆ m_activeLabelList

◆ m_activeLabelListPosition

◆ m_cutEdges

◆ m_cutNodes

◆ m_ex

◆ m_label

◆ m_maxLabel

Open
Graph Drawing
Framework