Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinSTCutModule< TCost > Class Template Referenceabstract

#include <ogdf/graphalg/MinSTCutModule.h>

+ Inheritance diagram for ogdf::MinSTCutModule< TCost >:

Public Member Functions

 MinSTCutModule ()
 default constructor (empty) More...
 
virtual ~MinSTCutModule ()
 
virtual bool call (const Graph &graph, const EdgeArray< TCost > &weight, node s, node t, List< edge > &edgeList, edge e_st=nullptr)=0
 The actual algorithm call. More...
 
virtual bool call (const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr)=0
 The actual algorithm call. More...
 
virtual bool direction (edge e)
 Returns the direction of e in the cut. More...
 

Protected Member Functions

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

EdgeArray< int > m_direction
 
GraphCopym_gc = nullptr
 

Detailed Description

template<typename TCost>
class ogdf::MinSTCutModule< TCost >

Definition at line 40 of file MinSTCutModule.h.

Constructor & Destructor Documentation

◆ MinSTCutModule()

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

default constructor (empty)

Definition at line 45 of file MinSTCutModule.h.

◆ ~MinSTCutModule()

template<typename TCost >
virtual ogdf::MinSTCutModule< TCost >::~MinSTCutModule ( )
inlinevirtual

Definition at line 77 of file MinSTCutModule.h.

Member Function Documentation

◆ call() [1/2]

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

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.

Implemented in ogdf::MinSTCutMaxFlow< TCost >, ogdf::MinSTCutBFS< TCost >, and ogdf::MinSTCutDijkstra< TCost >.

◆ call() [2/2]

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

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.

Implemented in ogdf::MinSTCutMaxFlow< TCost >, ogdf::MinSTCutDijkstra< TCost >, and ogdf::MinSTCutBFS< TCost >.

◆ direction()

template<typename TCost >
virtual bool ogdf::MinSTCutModule< TCost >::direction ( edge  e)
inlinevirtual

Returns the direction of e in the cut.

Precondition
e is part of the cut calculated last.
Parameters
eAn edge in the graph for which the min-st-cut was calculated last.
Returns
true, iff the source of e is in one component with s, if all edges of the cut are deleted.

Definition at line 88 of file MinSTCutModule.h.

◆ preprocessingDual()

template<typename TCost >
bool ogdf::MinSTCutModule< TCost >::preprocessingDual ( const Graph graph,
GraphCopy gc,
CombinatorialEmbedding CE,
node  source,
node  target,
edge  e_st 
)
inlineprotected

This method preprocesses gc for minstcut calculations, by adding an st-edge if needed and embedding gc.

Parameters
graphThe original graph of gc.
gcThe input graph.
CEHolds the embedding of gc.
sources
targett
e_stIf not nullptr, this edge is meant to split the external face of the embedded gc.
Returns

Definition at line 109 of file MinSTCutModule.h.

Member Data Documentation

◆ m_direction

template<typename TCost >
EdgeArray<int> ogdf::MinSTCutModule< TCost >::m_direction
protected

Definition at line 95 of file MinSTCutModule.h.

◆ m_gc

template<typename TCost >
GraphCopy* ogdf::MinSTCutModule< TCost >::m_gc = nullptr
protected

Definition at line 96 of file MinSTCutModule.h.


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