ogdf::MaxFlowSTPlanarItaiShiloach< TCap > Class Template Reference

Computes a max flow in s-t-planar network via uppermost paths. More...

#include <ogdf/graphalg/MaxFlowSTPlanarItaiShiloach.h>

Inheritance diagram for ogdf::MaxFlowSTPlanarItaiShiloach< TCap >:

Public Member Functions
	~MaxFlowSTPlanarItaiShiloach ()
	Free allocated ressources.
void	computeFlowAfterValue ()
	Computes the actual flow on each edge.
TCap	computeValue (const EdgeArray< TCap > &originalCapacities, const node &source, const node &target)
	Computes the maximal flow from source to sink.
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 Types
enum class	EdgePathType { NoPath , SourcePath , TargetPath , Unknown }
	Each edge may be part of the source or target path. More...
enum class	NodeType { New , Path , Done }
	Each node has a certain type depending on its participation in any path. More...

Private Member Functions
void	appendEdge (const edge e)
	Appends an edge to the current path.
void	dropEdge (const edge e)
	Removes a single edge from the current path.
bool	findUppermostPath (const edge saturatedEdge)
	Establishes the next uppermost path.
EdgePathType	getPathType (const edge e) const
	Performs an alternating backtracking from source and target to determine whether the new node is part of the source or target path.
TCap	shiftPriority (TCap priority)
	see unshiftedPriority
TCap	unshiftedPriority (edge e)
	To work with unsigned, we need a priority shifting of the elements in the priority queue.
TCap	unshiftedTopPriority ()
	see unshiftedPriority

Private Attributes
adjEntry	m_commonFaceAdj
NodeArray< int >	m_edgeCounter
	The number of edges visited from each node.
TCap	m_partialFlow
	The flow reached thus far (monotonically increasing).
NodeArray< edge >	m_pred
	The predecessor of each node in the currently uppermost path.
PrioritizedMapQueue< edge, TCap > *	m_prioritizedEdges = nullptr
	A priority queue for storing all edges currently in a path.
NodeArray< NodeType >	m_status
	The status of each node.
EdgeArray< bool >	m_visited
	Whether each edge has was visited.

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

Computes a max flow in s-t-planar network via uppermost paths.

Definition at line 50 of file MaxFlowSTPlanarItaiShiloach.h.

Member Enumeration Documentation

EdgePathType

template<typename TCap >

enum class ogdf::MaxFlowSTPlanarItaiShiloach::EdgePathType

strongprivate

Each edge may be part of the source or target path.

We do not store this information. It is only a temporary variable in two routines.

Enumerator
NoPath
SourcePath
TargetPath
Unknown

Definition at line 85 of file MaxFlowSTPlanarItaiShiloach.h.

NodeType

template<typename TCap >

enum class ogdf::MaxFlowSTPlanarItaiShiloach::NodeType

strongprivate

Each node has a certain type depending on its participation in any path.

Enumerator
New
Path
Done

Definition at line 78 of file MaxFlowSTPlanarItaiShiloach.h.

Constructor & Destructor Documentation

~MaxFlowSTPlanarItaiShiloach()

template<typename TCap >

ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::~MaxFlowSTPlanarItaiShiloach ( )

inline

Free allocated ressources.

Definition at line 111 of file MaxFlowSTPlanarItaiShiloach.h.

Member Function Documentation

appendEdge()

template<typename TCap >

void ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::appendEdge ( const edge  e )

inlineprivate

Appends an edge to the current path.

Parameters

e	The edge to be added, must not be part of any path so far

Definition at line 286 of file MaxFlowSTPlanarItaiShiloach.h.

computeFlowAfterValue()

template<typename TCap >

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

inlinevirtual

Computes the actual flow on each edge.

Most edges have already been assigned their respective flow values. However, there might be some edges remaining (as part of tangling paths from source and sink).

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 181 of file MaxFlowSTPlanarItaiShiloach.h.

computeValue()

template<typename TCap >

TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::computeValue ( const EdgeArray< TCap > &  originalCapacities, const node &  source, const node &  target  )

inlinevirtual

Computes the maximal flow from source to sink.

Assumes the graph to be s-t-planary embedded.

Parameters

originalCapacities	the positive capacity of each edge
source	the source node
target	the sink node

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 122 of file MaxFlowSTPlanarItaiShiloach.h.

dropEdge()

template<typename TCap >

void ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::dropEdge ( const edge  e )

inlineprivate

Removes a single edge from the current path.

Note that the edge is not actually removed from the graph.

Parameters

e	The edge to be removed, must be part of a path

Definition at line 306 of file MaxFlowSTPlanarItaiShiloach.h.

findUppermostPath()

template<typename TCap >

bool ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::findUppermostPath ( const edge  saturatedEdge )

inlineprivate

Establishes the next uppermost path.

Parameters

saturatedEdge

The edge saturated most recently

Definition at line 202 of file MaxFlowSTPlanarItaiShiloach.h.

getPathType()

template<typename TCap >

EdgePathType ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::getPathType ( const edge  e ) const

inlineprivate

Performs an alternating backtracking from source and target to determine whether the new node is part of the source or target path.

Parameters

e	The newly encountered edge from the old node to a new one.

Definition at line 335 of file MaxFlowSTPlanarItaiShiloach.h.

shiftPriority()

template<typename TCap >

TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::shiftPriority ( TCap  priority )

inlineprivate

see unshiftedPriority

Parameters

priority

original priority

Returns

shifted priority

Definition at line 70 of file MaxFlowSTPlanarItaiShiloach.h.

unshiftedPriority()

template<typename TCap >

TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::unshiftedPriority ( edge  e )

inlineprivate

To work with unsigned, we need a priority shifting of the elements in the priority queue.

Parameters

e	edge in m_prioritizedEdges

Returns

unshifted priority

Definition at line 57 of file MaxFlowSTPlanarItaiShiloach.h.

unshiftedTopPriority()

template<typename TCap >

TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::unshiftedTopPriority ( )

inlineprivate

see unshiftedPriority

Returns

unshifted priority of top element

Definition at line 63 of file MaxFlowSTPlanarItaiShiloach.h.

Member Data Documentation

m_commonFaceAdj

template<typename TCap >

adjEntry ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_commonFaceAdj

private

Definition at line 87 of file MaxFlowSTPlanarItaiShiloach.h.

m_edgeCounter

template<typename TCap >

NodeArray<int> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_edgeCounter

private

The number of edges visited from each node.

Definition at line 93 of file MaxFlowSTPlanarItaiShiloach.h.

m_partialFlow

template<typename TCap >

TCap ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_partialFlow

private

The flow reached thus far (monotonically increasing).

Definition at line 105 of file MaxFlowSTPlanarItaiShiloach.h.

m_pred

template<typename TCap >

NodeArray<edge> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_pred

private

The predecessor of each node in the currently uppermost path.

Definition at line 96 of file MaxFlowSTPlanarItaiShiloach.h.

m_prioritizedEdges

template<typename TCap >

PrioritizedMapQueue<edge, TCap>* ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_prioritizedEdges = nullptr

private

A priority queue for storing all edges currently in a path.

Definition at line 102 of file MaxFlowSTPlanarItaiShiloach.h.

m_status

template<typename TCap >

NodeArray<NodeType> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_status

private

The status of each node.

Definition at line 99 of file MaxFlowSTPlanarItaiShiloach.h.

m_visited

template<typename TCap >

EdgeArray<bool> ogdf::MaxFlowSTPlanarItaiShiloach< TCap >::m_visited

private

Whether each edge has was visited.

Definition at line 90 of file MaxFlowSTPlanarItaiShiloach.h.

---

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

• include/ogdf/graphalg/MaxFlowSTPlanarItaiShiloach.h