# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

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. More...

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

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. 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...

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 createBackArcs (Graph &gr, EdgeArray< TCap > &new_costs)
Create back arcs for all edges and set the backedges' new_costs to zero. More...

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

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

Definition at line 49 of file MaxFlowSTPlanarDigraph.h.

## ◆ 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 125 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 69 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 53 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 128 of file MaxFlowSTPlanarDigraph.h.

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