Open
Graph Drawing
Framework

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

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::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 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
capis the EdgeArray of non-negative capacities.
sis the source.
tis 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
graphis the graph for the flow problem.
flowis 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: