# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::MinSTCutDijkstra< TCost > Class Template Reference

Min-st-cut algorithm, that calculates the cut by calculating the shortest path between the faces adjacent to an edge between s and t, via the algorithm by Dijkstra on the dual graph. More...

#include <ogdf/graphalg/MinSTCutDijkstra.h>

Inheritance diagram for ogdf::MinSTCutDijkstra< TCost >:

## Public Member Functions

MinSTCutDijkstra ()

virtual bool call (const Graph &graph, const EdgeArray< TCost > &weight, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
The actual algorithm call. More...

virtual bool call (const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
The actual algorithm call. More...

Public Member Functions inherited from ogdf::MinSTCutModule< TCost >
MinSTCutModule ()
default constructor (empty) More...

virtual ~MinSTCutModule ()

virtual bool direction (edge e)
Returns the direction of e in the cut. More...

Protected Member Functions inherited from ogdf::MinSTCutModule< TCost >
bool preprocessingDual (const Graph &graph, GraphCopy &gc, CombinatorialEmbedding &CE, node source, node target, edge e_st)
This method preprocesses gc for minstcut calculations, by adding an st-edge if needed and embedding gc. More...

Protected Attributes inherited from ogdf::MinSTCutModule< TCost >
EdgeArray< int > m_direction

GraphCopym_gc = nullptr

## Detailed Description

### template<typename TCost> class ogdf::MinSTCutDijkstra< TCost >

Min-st-cut algorithm, that calculates the cut by calculating the shortest path between the faces adjacent to an edge between s and t, via the algorithm by Dijkstra on the dual graph.

Precondition
The input graph is st-planar.
Template Parameters
 TCost The type in which the weight of the edges is given.

Definition at line 52 of file MinSTCutDijkstra.h.

## ◆ MinSTCutDijkstra()

template<typename TCost >
 ogdf::MinSTCutDijkstra< TCost >::MinSTCutDijkstra ( )
inline

Definition at line 54 of file MinSTCutDijkstra.h.

## ◆ call() [1/2]

template<typename TCost >
 bool ogdf::MinSTCutDijkstra< TCost >::call ( const Graph & graph, const EdgeArray< TCost > & weight, node s, node t, List< edge > & edgeList, edge e_st = nullptr )
overridevirtual

The actual algorithm call.

Parameters
 graph The graph on which the min-st-cut is to be calculated. weight Provides a weight for every edge. s The source node. t The target node. edgeList This list is filled with the edges which are part of the mincut. If the graph is st-planarly embedded, this list is correctly ordered along the cut. e_st An edge between s and t which is used to determine where the cut should start, nullptr elsewise.
Returns
Indicates success.

Implements ogdf::MinSTCutModule< TCost >.

Definition at line 74 of file MinSTCutDijkstra.h.

## ◆ call() [2/2]

template<typename TCost >
 virtual bool ogdf::MinSTCutDijkstra< TCost >::call ( const Graph & graph, node s, node t, List< edge > & edgeList, edge e_st = nullptr )
inlineoverridevirtual

The actual algorithm call.

Parameters
 graph The graph on which the min-st-cut is to be calculated. s The source node. t The target node. edgeList This list is filled with the edges which are part of the mincut. If the graph is st-planarly embedded, this list is correctly ordered along the cut. e_st An edge between s and t which is used to determine where the cut should start, nullptr elsewise.
Returns
Indicates success.

Implements ogdf::MinSTCutModule< TCost >.

Definition at line 65 of file MinSTCutDijkstra.h.

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