ogdf::MaxFlowSTPlanarDigraph< TCap > Class Template Reference

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

#include <ogdf/graphalg/MaxFlowSTPlanarDigraph.h>

Inheritance diagram for ogdf::MaxFlowSTPlanarDigraph< TCap >:

Public Member Functions
void	computeFlowAfterValue () override
	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) override
	Compute only the value of the flow.
void	init (const Graph &graph, EdgeArray< TCap > *flow=nullptr) override
	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.
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.
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	createBackArcs (Graph &gr, EdgeArray< TCap > &new_costs)
	Create back arcs for all edges and set the backedges' new_costs to zero.

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

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

Definition at line 49 of file MaxFlowSTPlanarDigraph.h.

Member Function Documentation

computeFlowAfterValue()

template<typename TCap >

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

inlineoverridevirtual

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

Implements ogdf::MaxFlowModule< TCap >.

Definition at line 123 of file MaxFlowSTPlanarDigraph.h.

computeValue()

template<typename TCap >

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

inlineoverridevirtual

Compute only the value of the flow.

After this first phase, the flow itself is already computed!

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 68 of file MaxFlowSTPlanarDigraph.h.

createBackArcs()

template<typename TCap >

void ogdf::MaxFlowSTPlanarDigraph< TCap >::createBackArcs ( Graph &  gr, EdgeArray< TCap > &  new_costs  )

inlineprivate

Create back arcs for all edges and set the backedges' new_costs to zero.

Definition at line 52 of file MaxFlowSTPlanarDigraph.h.

init()

template<typename TCap >

void ogdf::MaxFlowSTPlanarDigraph< TCap >::init ( const Graph &  graph, EdgeArray< TCap > *  flow = nullptr  )

inlineoverridevirtual

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.

Parameters

graph	is the graph for the flow problem.
flow	is an optional argument that can be used to force the algorithm to work on an user given "external" EdgeArray flow

Reimplemented from ogdf::MaxFlowModule< TCap >.

Definition at line 126 of file MaxFlowSTPlanarDigraph.h.

---

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

• include/ogdf/graphalg/MaxFlowSTPlanarDigraph.h