ogdf::MinSTCutModule< TCost > Class Template Reference

#include <ogdf/graphalg/MinSTCutModule.h>

Inheritance diagram for ogdf::MinSTCutModule< TCost >:

Public Member Functions
	MinSTCutModule ()
	default constructor (empty)
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.
virtual bool	call (const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr)=0
	The actual algorithm call.
virtual bool	direction (edge e)
	Returns the direction of e in the cut.

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.

Protected Attributes
EdgeArray< int >	m_direction
GraphCopy *	m_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 78 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

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.

Implemented in ogdf::MinSTCutBFS< TCost >, ogdf::MinSTCutDijkstra< TCost >, and ogdf::MinSTCutMaxFlow< 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

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.

Implemented in ogdf::MinSTCutBFS< TCost >, ogdf::MinSTCutDijkstra< TCost >, and ogdf::MinSTCutMaxFlow< 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

e	An 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 87 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

graph	The original graph of gc.
gc	The input graph.
CE	Holds the embedding of gc.
source	s
target	t
e_st	If not nullptr, this edge is meant to split the external face of the embedded gc.

Returns

Definition at line 108 of file MinSTCutModule.h.

Member Data Documentation

m_direction

template<typename TCost >

EdgeArray<int> ogdf::MinSTCutModule< TCost >::m_direction

protected

Definition at line 94 of file MinSTCutModule.h.

m_gc

template<typename TCost >

GraphCopy* ogdf::MinSTCutModule< TCost >::m_gc = nullptr

protected

Definition at line 95 of file MinSTCutModule.h.

---

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

• include/ogdf/graphalg/MinSTCutModule.h