Open
Graph Drawing
Framework

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

Additional Inherited Members

- 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
TCostThe type in which the weight of the edges is given.

Definition at line 52 of file MinSTCutDijkstra.h.

Constructor & Destructor Documentation

◆ MinSTCutDijkstra()

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

Definition at line 54 of file MinSTCutDijkstra.h.

Member Function Documentation

◆ 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
graphThe graph on which the min-st-cut is to be calculated.
weightProvides a weight for every edge.
sThe source node.
tThe target node.
edgeListThis 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_stAn 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
graphThe graph on which the min-st-cut is to be calculated.
sThe source node.
tThe target node.
edgeListThis 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_stAn 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: